Proof. For \(n=1\), Equation (2) follows directly from \(0\le F_r^{+v}-F_r\le20\). Suppose henceforth that \(n\ge2\).

Incident clauses. Split the Poisson process into the clauses avoiding \(v\), called the base, and the clauses involving \(v\). The base has rate \[\lambda_n=\left(\frac{n-1}{n}\right)^3\ge\frac18,\] and its clauses have the relaxed distribution on the other \(n-1\) variables. It is independent of the incident streams.

At a deterministic time \(t\), condition on the entire base up to \(t\). Let \(U_t\) be its finite set of surviving pairs \((D,\sigma)\), where \(D\subseteq[n]\setminus\{v\}\) has size at most \(r\) and \(\sigma\) is an assignment on \([n]\setminus(D\cup\{v\})\). When a literal is tested on such a pair, a literal on \(D\) is declared true. This convention exactly implements clause deletion. The event \(U_t\ne\varnothing\) is \(\{T_r^{+v}>t\}\). For a nonempty deterministic candidate set \(U\), let \(q(U)\) be the probability that \(\operatorname{Poi}(K)\) independent relaxed two-literal clauses on the other variables eliminate every candidate, where \(K=3B=60\).

For \(0\le t<Bn\) and \(U_t\ne\varnothing\), we claim \[ \mathbb P(T_r\le t\mid\text{base up to }t) \le \bigl(q(U_t)+60/n\bigr)^2. \tag{4}\] To check this, fix a value for \(v\). Only incident clauses in which every occurrence of \(v\) has the sign falsified by that value can obstruct an extension of a candidate in \(U_t\). Among these clauses, those containing \(v\) once project to independent relaxed two-literal clauses. Their number is Poisson with mean at most \(3t/n\le60\). The expected number containing \(v\) at least twice is at most \(3t/n^2\le60/n\), by a union bound over the three pairs of positions. The obstruction probability for this value is therefore at most \(q(U_t)+60/n\). The obstructing groups for the two values of \(v\) are disjoint Poisson thinnings, hence independent of one another and of the base. If either group leaves a candidate, restoring \(v\) with that value gives an \(r\)-deletion satisfying assignment. Both groups must therefore obstruct, which proves Equation (4).

Replacing shorter tests. In any list of independent tests, replacing one relaxed two-literal clause by \(d\ge1\) independent relaxed three-literal clauses reduces the probability of eliminating all candidates by at most \(d^{-2}\). Indeed, condition on all other tests, leaving a candidate set \(U'\). There is nothing to prove if it is empty. Otherwise let \(x\) be the proportion of signed literals false on every member of \(U'\). Each variable contributes at most one such sign, so \(0\le x\le1/2\), including under the deleted-literal convention. The two-literal clause alone eliminates \(U'\) with probability \(x^2\). The \(d\) three-literal clauses do so with probability at least \(1-(1-x^3)^d\ge1-e^{-dx^3}\). If \(dx^3>1\), this lower bound exceeds \(1/4\ge x^2\). If \(dx^3\le1\), it is at least \(dx^3/2\), and \[x^2-\frac d2x^3\le\frac{16}{27d^2}<\frac1{d^2}.\] This proves the comparison. Applying it successively is valid because, at each replacement, one can condition on all the other independent tests.

How long a residual set can survive. The replacement estimate converts a large value of \(q(U_t)\) into a chance that the future base eliminates \(U_t\). Partition the possible values \(q(U_t)\ge1/n\) into disjoint dyadic bins \(q_0\le q(U_t)\le2q_0\), with \(q_0=2^{-j}\) and \(j\ge1\), using any fixed endpoint convention. Every bin that is used has \(q_0\ge1/(2n)\). For its index \(j\), set \[ L_j=j+122,\qquad d_j=\left\lceil\sqrt{4L_j/q_0}\right\rceil,\qquad \ell_j=32L_jd_j. \tag{5}\] Since \(\mathbb E2^{\operatorname{Poi}(60)}=e^{60}<2^{120}\), \(\mathbb P(\operatorname{Poi}(60)>L_j)\le q_0/4\). If \(U\) belongs to the bin, then \(L_j\) two-literal tests eliminate it with probability at least \(q(U)-q_0/4\). Replacing each test by \(d_j\) three-literal tests loses at most \(L_j/d_j^2\le q_0/4\). Thus \(L_jd_j\) three-literal tests eliminate \(U\) with probability at least \(q_0/2\).

In a future interval of length \(\ell_j\), the base has a Poisson number of arrivals with mean at least \(4L_jd_j\). If \(M=L_jd_j\ge1\) and \(X\) is Poisson with mean \(\mu\ge4M\), Chebyshev’s inequality gives \[\mathbb P(X<M)\le\frac{\mu}{(\mu-M)^2} \le\frac4{9M}<\frac12.\] Consequently this interval eliminates the fixed \(U\) with probability at least \(q_0/4\). Write \[S_{r,v}(t)=\mathbb P(T_r^{+v}>t),\qquad E_j(t)=\{U_t\ne\varnothing,\ q(U_t)\text{ belongs to bin }j\}.\] The independent future base then gives \[ \begin{split} S_{r,v}(t)-S_{r,v}(t+\ell_j)&\ge(q_0/4)\mathbb P(E_j(t)),\\ \int_0^{Bn}\mathbb P(E_j(t))\,\,\mathrm dt&\le4\ell_j/q_0. \end{split} \tag{6}\] For the second inequality, integrate the first: the integral of \(S_{r,v}(t)-S_{r,v}(t+\ell_j)\) over \([0,Bn]\) is at most \(\ell_j\). This argument does not require \(T_r^{+v}\) to be finite. Conditional on the base at time \(t\) in \(E_j(t)\), survival to \(t+u\) is also bounded by \[ (1-q_0/4)^{\lfloor u/\ell_j\rfloor}. \tag{7}\] For each complete future interval, failure to eliminate even the original \(U_t\) is necessary for survival; these interval events are independent.

Integrating the delay. For any \(0\le F_r\le F_r^{+v}\le Bn\), direct integration gives the pathwise identity \[ (F_r^{+v}-F_r)^p =p(p-1)\int_{\substack{t,u\ge0\\t+u<Bn}} u^{p-2}\mathbf 1_{\{T_r\le t,\ T_r^{+v}>t+u\}}\,\,\mathrm dt\,\,\mathrm du. \tag{8}\] The boundaries have Lebesgue measure zero, so a hitting time equal to the cap causes no difficulty. Conditional on the base up to \(t\), incident arrivals up to \(t\) and future base arrivals are independent. The incident killing estimate (4) and the future survival estimate (7) therefore multiply.

Here is why the resulting sum over bins converges. On a bin of scale \(q_0\), incident killing has probability at most a constant times \(q_0^2\). The expected total time spent in that bin before \(Bn\) is at most \(4\ell_j/q_0\), by Equation (6). Integrating the geometric future-survival bound against \(u^{p-2}\) contributes at most a constant times \((\ell_j/q_0)^{p-1}\). Thus the bin contribution is bounded by a constant times \(\ell_j^p q_0^{2-p}\). Since \(\ell_j\) grows like a polynomial in \(j\) times \(q_0^{-1/2}\), the power of \(q_0\) is \(2-3p/2=1/5>0\).

We now retain explicit constants for the later one-sided certificate. On bin \(j\), \[(q(U_t)+60/n)^2\le(122q_0)^2<2^{14}q_0^2, \qquad \ell_j\le2^{20}(j+1)^{3/2}2^{j/2}.\] For the latter, \(d_j\le3\sqrt{L_j/q_0}\) and \(L_j\le64(j+1)\) suffice. Moreover, \[\begin{split} &\int_0^\infty u^{p-2} (1-q_0/4)^{\lfloor u/\ell_j\rfloor}\,\,\mathrm du\\ &\qquad\le e\,\Gamma(1/5)(4\ell_j/q_0)^{1/5} <2^7(\ell_j/q_0)^{p-1}. \end{split}\] Indeed, the geometric term is at most \(e\exp(-q_0u/(4\ell_j))\), and splitting the defining Gamma integral at \(1\) gives \(\Gamma(1/5)<6\). Using Equation (6) and \(p(p-1)<1\), the contribution of bin \(j\) to the expectation in Equation (8) is at most \[2^{47}(j+1)^2\,2^{-j/5}.\] Grouping \(j=5k+1,\ldots,5k+5\) gives \[\sum_{j\ge1}(j+1)^2\,2^{-j/5} \le5\sum_{k\ge0}(5k+6)^2\,2^{-k} =1710<2^{11}.\] The total bin contribution is less than \(2^{58}\). When \(q(U_t)<1/n\), Equation (4) is at most \(61^2/n^2\). Integrating over the entire truncated region in Equation (8) bounds the remaining contribution by \[61^2 B^p n^{p-2}<2^{18}.\] This proves Equation (2) with \(C=2^{60}\), without assuming that the free-deletion problem eventually fails. In particular, if \(r\ge n-1\), a candidate can delete all other variables, so \(q(U_t)=0\) and only the small-\(q\) estimate is used.

From deletion to concentration. Partition all arrivals up to \(Bn\) into \(n\) independent buckets according to the smallest variable index in a clause. Resample bucket \(i\) independently, and denote the resulting capped time by \(F'_r\). Deleting \(i\) removes that entire bucket, so \(F_r^{+i}\) is unchanged by the resampling and dominates both \(F_r\) and \(F'_r\). Hence \[\mathbb E|F_r-F'_r|^p \le\mathbb E(F_r^{+i}-F_r)^p+\mathbb E(F_r^{+i}-F'_r)^p \le2C.\] Reveal the buckets in their index order and let \(D_i\) be the successive differences of the Doob martingale for \(F_r\). Averaging over the independent replacement and all unrevealed buckets identifies \(D_i\) as the conditional expectation of \(F_r-F'_r\) given the first \(i\) buckets. Conditional Jensen therefore gives \(\mathbb E|D_i|^p\le2C\).

For real \(x,y\) and \(1<p<2\), \[|x+y|^p\le |x|^p +p\operatorname{sgn}(x)|x|^{p-1}y+2|y|^p.\] Here \(\operatorname{sgn}(0)=0\). The signed \((p-1)\)-power is Hölder continuous with constant \(2^{2-p}\), and integration of the derivative gives a remainder at most \(2^{2-p}|y|^p\le2|y|^p\). Apply this inequality successively to the centered martingale sum. Each linear term has expectation zero, giving \(\mathbb E|F_r-\mathbb EF_r|^p\le2\sum_i\mathbb E|D_i|^p\le4Cn\). This is Equation (3). ◻

Proof. Mixing the blocks. Put \(n=n_1+n_2\), \(t=t_1+t_2\). The case \(t=0\) is immediate, so set \(\lambda_i=t_i/t\). A local clause first chooses block \(i\) with probability \(\lambda_i\) and then chooses its three indices uniformly in that block. A weighted global clause chooses its block independently at each of the three positions with these same probabilities, followed by a uniform index in the chosen block. Interpolate between independent Poisson counts of local and weighted global clauses, with respective means \((1-s)t\) and \(st\), for \(0\le s\le1\).

The derivative of the expected satisfiability indicator is \(t\) times the expected difference of its add-one increments for the two clause types. This follows by differentiating the Poisson series for a bounded function; the differentiated series is absolutely convergent. For a satisfiable base formula, let \(x_i\) be the proportion of signed literals in block \(i\) that are false in every satisfying assignment. A single clause eliminates all satisfying assignments exactly when each of its literals is false in every such assignment. The local and weighted global killing probabilities are therefore \[\sum_{i=1}^2\lambda_i x_i^3, \qquad \left(\sum_{i=1}^2\lambda_i x_i\right)^3,\] respectively. Convexity of \(x^3\) on \([0,\infty)\) makes the derivative nonnegative. An unsatisfiable base contributes zero. At the local endpoint the two blocks are independent, so its satisfiability probability is the right-hand side of Equation (9).

Balancing the variable weights. The mixed endpoint still has weight \(\lambda_i/n_i\) on each variable of block \(i\). It remains to show that making these weights uniform cannot decrease the probability at the weighted global endpoint. We prove this for every fixed clause count. Choose two variables with weights \(w_1,w_2\) and replace both weights by \((w_1+w_2)/2\). If their sum is zero, there is nothing to change. Otherwise condition on the set of occurrence positions that use one of these two variables, and on all choices and signs in the other positions. These conditioned data have the same distribution before and after averaging. Let \(k\) be the number of selected positions. Treating their literal truth values as independent placeholders defines a set \(S\subseteq\{0,1\}^k\): a vector belongs to \(S\) if the variables outside the selected pair can be assigned so that the formula is satisfied. This set does not depend on the identities or signs still to be sampled in the selected positions.

Let \(y\) be the vector of literal truth values when the two selected variables are both assigned zero, and let \(\xi\) indicate positions occupied by the second variable. Fair independent signs make \(y\) uniform on the bit cube, independently of \(\xi\), whose coordinates are independent Bernoulli variables with parameter \(\theta=w_2/(w_1+w_2)\). The four assignments to the selected pair yield exactly the truth vectors \[y,\quad\bar y,\quad y\oplus\xi,\quad\overline{y\oplus\xi}.\] Here a bar denotes coordinatewise complement. Let \(A=S\cup\{\bar z:z\in S\}\) and \(g=\mathbf 1_A\). The conditional probability of satisfaction is consequently \[2\mathbb Eg(y)-\mathbb E[g(y)g(y\oplus\xi)].\] Expand \(g\) in the orthonormal parity characters \(\chi_I(y)=(-1)^{\sum_{j\in I}y_j}\) of the uniform bit cube. Independence of the selector bits gives \[\mathbb E[g(y)g(y\oplus\xi)] =\sum_{I\subseteq[k]}\widehat g(I)^2(1-2\theta)^{|I|}.\] Complement invariance of \(g\) makes every odd-degree coefficient vanish. Every remaining nonconstant term is nonnegative and is zero at \(\theta=1/2\). Thus equalizing the selected weights maximizes the conditional satisfiability probability.

Repeatedly average a largest and a smallest weight. The sum over all weights of squared deviations from \(1/n\) decreases by half the square of their difference. This nonnegative sum converges, so the largest-smallest difference tends to zero and all weights converge to \(1/n\). For a fixed clause count the satisfiability probability is a polynomial in the weights, hence continuous. It cannot decrease in this averaging procedure. Bounded convergence then permits averaging over the Poisson count. The uniform endpoint is the left-hand side of Equation (9), proving the result. ◻

Proof. We first turn the survival comparison into an almost-superadditive inequality for \(f_n\). Then a dyadic construction makes its accumulated error summable after division by the size. Set \(H=2^{60}\) and \(h_k=Hk^b\). Equation (3) and Markov’s inequality give \[\mathbb P(|F_0-f_k|\ge h_k) \le C_1/H^p=2^{-10}<1/10\] at size \(k\). In Lemma 4, choose \(t_i=(f_{n_i}-h_{n_i})_+\). If \(t_i=0\), survival is certain. Otherwise \(t_i<Bn_i\), so survival has probability at least \(9/10\) by this deviation bound. With \(n=n_1+n_2\) and \(t=t_1+t_2\), Equation (9) gives \(P_n(t)\ge81/100\). Also \(t<Bn\). If \(f_n<t-h_n\), the same deviation bound at size \(n\) would give \(P_n(t)\le1/10\), a contradiction. Hence \[ f_{n_1+n_2}\ge f_{n_1}+f_{n_2}-C_2(n_1+n_2)^b, \qquad C_2=2^{62}, \tag{11}\] because \(h_{n_1}+h_{n_2}+h_n\le H(2^{1-b}+1)n^b<4Hn^b\).

Fix \(k\ge1\). Iterating Equation (11) on equal-size blocks gives \[\frac{f_{2^jk}}{2^jk} \ge\frac{f_k}{k} -C_2k^{b-1}\sum_{i=1}^j2^{-(1-b)i}.\] Let \[D_b=\sum_{i\ge1}2^{-(1-b)i} =\frac1{2^{1/6}-1}<32.\] The last inequality follows from \((33/32)^6<2\). Thus every dyadic multiple \(s=2^jk\) satisfies \(f_s\ge s(f_k/k-C_2D_bk^{-1/6})\). For \(n\ge k\), use the binary expansion of \(\lfloor n/k\rfloor\) to partition \(k\lfloor n/k\rfloor\) into distinct dyadic multiples of \(k\). Merge them in increasing order of size. When a block of size \(2^jk\) is added, the total merged size is less than \(2^{j+1}k\); the sum of merging errors in Equation (11) is bounded by \[C_2\sum_{j=0}^{\lfloor\log_2(n/k)\rfloor}(2^{j+1}k)^b \le A_b C_2 n^b\] for a fixed finite constant \(A_b\). Add the remainder, if nonzero, in one more application of Equation (11), using \(f_s\ge0\) for its contribution. Divide by \(n\) and let \(n\) tend to infinity with \(k\) fixed. Since \(b<1\), the merging errors vanish and \[\liminf_{n\to\infty}\frac{f_n}{n} \ge\frac{f_k}{k}-C_2D_bk^{-1/6} \ge\frac{f_k}{k}-2^{67}k^{-1/6}.\] The bounded sequence \(f_n/n\in[0,B]\) has a limsup subsequence. Let \(k\) tend to infinity along that subsequence in the last inequality. Its liminf is at least its limsup, proving convergence and Equation (10). ◻

Proof. For a fixed assignment, a relaxed clause is violated with probability \(1/8\), even if some variable indices repeat, because the signs are independent. The expected number of satisfying assignments at time \(10n\) is therefore \[2^n\exp(-10n/8)\longrightarrow0.\] Consequently \(P_n(10n)\to0\), and \(f_n\le10n+(B-10)nP_n(10n)\) shows that \(\alpha\le10<B\).

For a lower bound set \(c=1/100\) and \(M=\lfloor cn\rfloor\). A union bound shows that the probability some \(\ell\) of the first \(M\) clauses touch fewer than \(\ell\) distinct variables is at most \[ \sum_{\ell=1}^{M}\binom M\ell\binom n\ell (\ell/n)^{3\ell} \le\sum_{\ell=1}^{M}(e^2c\ell/n)^\ell=o(1). \tag{12}\] To obtain the first inequality, pad any set of fewer than \(\ell\) touched variables to one of size \(\ell\); all \(3\ell\) index choices must lie in that set. The second uses \(\binom u\ell\le(eu/\ell)^\ell\). For the last limit, the terms with \(\ell\le\sqrt n\) sum to \(O(n^{-1/2})\), and the remaining terms are at most \(n(e^2c^2)^{\sqrt n}\) in total. On the complementary event, Hall’s marriage theorem (Hall 1935, Theorem 1) assigns every clause a distinct representative variable appearing in it. Set each representative to satisfy one of its occurrences in its assigned clause. These requirements are consistent because the representatives are distinct, and they satisfy all clauses. This argument permits repeated indices and signs within a clause. At time \(cn/2\) the Poisson clause count is at most \(M\) with probability tending to one. Thus \(P_n(cn/2)\to1\). Since \(f_n\ge(cn/2)P_n(cn/2)\), we obtain \(\alpha\ge c/2=1/200\).

If \(a<\alpha\), convergence of \(f_n/n\) and Equation (3) imply \(P_n(an)\to1\). Explicitly, for \(a>0\) and sufficiently large \(n\), \(f_n-an\ge(\alpha-a)n/2\), so the failure probability is at most \(C_1n/((\alpha-a)n/2)^p\), which tends to zero. The case \(a=0\) is immediate. If \(\alpha<a<B\), the analogous upper-tail estimate gives \(P_n(an)\to0\). For \(a\ge B\), use monotonicity and any intermediate density in \((\alpha,B)\).

We now take \(n\ge3\) and return to distinct-variable clauses. Write \(P_n^{\mathrm d}(t)\) for their rate-one Poisson satisfiability probability. Thinning out the relaxed clauses having repeated variable indices leaves an independent distinct-clause stream of rate \[s_n=(1-1/n)(1-2/n).\] Removing clauses can only help satisfiability. Conversely, the discarded stream is empty up to time \(an\) with probability \(\exp(-an(1-s_n))\), independently of the retained stream. Thus \[ e^{-an(1-s_n)}P_n^{\mathrm d}(s_n a n) \le P_n(an)\le P_n^{\mathrm d}(s_n a n). \tag{13}\] For fixed \(a\), the exponential factor is at least \(e^{-3a}\). If \(a<\alpha\), choose \(a'\in(a,\alpha)\). For large \(n\), \(s_na'>a\), and monotonicity with Equation (13) gives \(P_n^{\mathrm d}(an)\ge P_n(a'n)\to1\). If \(a>\alpha\), choose \(a'\in(\alpha,a)\). Then \[P_n^{\mathrm d}(an) \le P_n^{\mathrm d}(s_na'n) \le e^{3a'}P_n(a'n)\longrightarrow0.\]

Finally let \(p(n,m)\) denote the probability for exactly \(m\) independently sampled distinct-variable clauses, allowing repeated clauses. It is nonincreasing in \(m\). Below the threshold, compare \(m=\lfloor an\rfloor\) with a Poisson count of mean \(a'n\) for \(a<a'<\alpha\). This count is at least \(m\) with probability tending to one, so \(p(n,m)\ge P_n^{\mathrm d}(a'n)-o(1)\to1\). Above the threshold use \(\alpha<a'<a\); the Poisson count is at most \(m\) with probability tending to one, giving \(p(n,m)\le P_n^{\mathrm d}(a'n)+o(1)\to0\). Conditioning three ordered uniform indices to be distinct and then forgetting their order produces exactly a uniform three-element subset with independent fair signs. Clauses remain independent and may repeat. This completes the transfer to the exact model. ◻

Proof. For integers \(n\ge1\) and \(m\ge0\), let \(s_{n,m}\) be the relaxed-model satisfiability probability with exactly \(m\) clauses. This is rational and can be computed by enumerating all \((8n^3)^m\) ordered signed clause lists and all \(2^n\) assignments. The survival-integral identity and conditioning on the Poisson count give \[f_n=\int_0^{Bn}P_n(t)\,\,\mathrm dt =\sum_{m=0}^\infty s_{n,m} \int_0^{Bn}e^{-t}\frac{t^m}{m!}\,\,\mathrm dt.\] The summands are nonnegative. Uniformly for \(0\le t\le Bn\), \[\mathbb P(\operatorname{Poi}(t)>M)\le e^{Bn}2^{-(M+1)}.\] Thus truncation at \(M\) changes the integral by at most \(Bn e^{Bn}2^{-(M+1)}\), a bound that can be made smaller than any prescribed positive rational error by a finite search using the integer upper bound \(e^{Bn}<3^{Bn}\). Each remaining integral equals \[1-e^{-Bn}\sum_{j=0}^m\frac{(Bn)^j}{j!},\] and is computable with certified rational intervals. For completeness, if \(x=Bn\) and \(J\ge2x\) is an integer, the partial sum \(S_J=\sum_{j=0}^Jx^j/j!\) satisfies \[S_J\le e^x\le S_J+2\frac{x^{J+1}}{(J+1)!}.\] Indeed, each ratio after the first omitted term is at most \(1/2\). The rational upper bound for the tail tends to zero. Taking reciprocals gives certified intervals for \(e^{-x}\), and then for each displayed integral. Together with the explicit Poisson tail, this proves uniform computability of \(f_n\).

Rational bisection on \([0,1]\) computes the sixth root of \(1/n\), so \[v_n=\frac{f_n}{n}-2^{67}n^{-1/6}\] is uniformly computable. By Proposition 5, \(v_n\le\alpha\), and \(v_n\to\alpha\). For each pair of positive integers \((n,j)\), compute a rational \(\widehat v_{n,j}\) within \(2^{-j}\) of \(v_n\), and output \[\ell_{n,j}=\widehat v_{n,j}-2^{1-j}.\] Every output is strictly less than \(v_n\), hence less than \(\alpha\). Enumerating all pairs \((n,j)\) is effective, and the supremum of the outputs is \(\alpha\). To obtain a single sequence, choose effectively \(j(n)\) with \(3\,2^{-j(n)}\le1/n\) and put \(\ell_n=\ell_{n,j(n)}\). Then \[v_n-\frac1n\le\ell_n<v_n\le\alpha.\] Since \(v_n\to\alpha\), this sequence also tends to \(\alpha\). It therefore supplies the lower sequence required by Lemma 2. ◻

Proof. The case \(r=0\) is equality. For \(r\ge1\), fix a realization. The survival time with at most \(r\) deletions is the maximum of the survival times over finitely many fixed deletion sets. Capping commutes with this finite maximum. Choose a maximizing set \(D\), padding it to size exactly \(r\); padding cannot worsen survival. For every \(v\in D\), the free deletion of \(v\) followed by at most \(r-1\) other deletions has capped survival time exactly \(F_r\): the choice \(D\setminus \{v\}\) attains it, and every competing choice uses at most \(r\) deletions in total. Hence, for \(1\le r\le n\), \[r(F_r-F_{r-1})^p \le\sum_{v=1}^n(F_{r-1}^{+v}-F_{r-1})^p.\] This includes the case of survival up to the cap and the case \(r=n\). Take expectations and use Lemma 3, followed by the \(L^p\) bound on the first moment. Summing over the deletion allowance, \[\mathbb EF_r-f_n \le (Cn)^{1/p}\sum_{j=1}^r j^{-1/p} \le6C^{5/6}n^{5/6}r^{1/6} <2^{53}n^{5/6}r^{1/6},\] which proves Equation (14).

Fix \(a>\alpha\) and choose \(a_0\in(\alpha,\min(a,B))\). Let \(\Delta=a_0-\alpha>0\) and choose \(0<\epsilon<1\) so small that \(C_4\epsilon^{1/6}<\Delta/4\). For large \(n\), convergence of \(f_n/n\) and Equation (14), with \(r=\lfloor\epsilon n\rfloor\), give \(\mathbb EF_r\le(\alpha+\Delta/2)n\). Since \(a_0<B\), survival at time \(a_0n\) implies \(F_r>a_0n\). Equation (3) therefore shows \[\mathbb P(T_r>a_0n) \le\frac{C_1n}{(\Delta n/2)^p}\longrightarrow0.\] By monotonicity the same conclusion holds at time \(an\). If an assignment violated at most \(r\) clauses, selecting one variable from each violated clause and deleting those variables would discard every violation. The remaining clauses would be satisfied by the restricted assignment, using at most \(r\) deletions. This contradiction proves the violation assertion. ◻

Proof. Put \(V_n=\min_\sigma H_n(\sigma)\), and let \(M_n\sim\operatorname{Poi}(an)\) be the total clause count. Below the threshold, \(\mathbb P(V_n>0)\to0\) and \(0\le V_n\le M_n\). Cauchy–Schwarz gives \[\frac{\mathbb EV_n}{n} \le\bigl((a^2+a/n)\mathbb P(V_n>0)\bigr)^{1/2}\longrightarrow0.\] The bound \(\log Z_n\ge-\beta V_n\) proves Equation (15). Above the threshold, Proposition 8 gives \(\liminf_n\mathbb EV_n/n\ge\epsilon\) for some \(\epsilon>0\). Since \(\log Z_n\le n\log2-\beta V_n\), any integer \(\beta>(\log2)/\epsilon\) proves Equation (16). ◻

Proof. Fix the count and signs of one packet. Every reservoir occurrence uses its own site coordinates; only the root coordinate is common. Subdividing the finitely many grids expresses each conditional integral as a finite sum with rational weights. The nested transforms and the remaining root average are consequently finite expressions using rational arithmetic, exponentials, and logarithms. Every exponent is positive, and every clause factor is at least \(e^{-\beta}\). Thus all logarithms have strictly positive arguments, and these operations admit uniform rational interval approximations to any prescribed accuracy. The finite sign average and the Poisson probabilities are computable in the same way.

It remains to control the count tail uniformly over the description. The conditional transforms preserve the bounds in Equation (23). For \(D\sim\operatorname{Poi}(\lambda)\) and any integer \(M\ge0\), \[\begin{align*} \mathbb E\bigl[(\log2+\beta D)\mathbf 1_{\{D>M\}}\bigr] &\le 2^{-M}\mathbb E\bigl[(\log2+\beta D)2^D\bigr] \\ &=2^{-M}e^{\lambda}(\log2+2\beta\lambda), \tag{26}\end{align*}\] where \(\lambda=3a\) for the A-packet and \(\lambda=2a\) for the B-packet. Choose \(M\) so that the sum of these two computable bounds is smaller than the desired tail error, and then approximate the finitely many retained terms. This gives a rational interval containing \(G_1\) with arbitrarily small width. Its upper endpoint eventually becomes negative exactly when \(G_1<0\). ◻

Proof. Partition \(n=n_1+n_2\) variables into two nonempty blocks and put \(\lambda_i=n_i/n\). At \(s\in[0,1]\), take independent within-block clauses of means \((1-s)an_i\) and global clauses of mean \(san\), and write \(Z_s\) for the resulting partition function. Brackets denote the current Gibbs distribution, with independent replicas when several samples occur. Adding a clause with violation indicator \(I\) changes the log partition function by \[ \log(1-w\langle I\rangle) =-\sum_{\ell\ge1}\frac{w^\ell}{\ell}\langle I\rangle^\ell. \tag{28}\] The series is uniformly absolutely summable because \(0<w<1\).

For fixed replicas \(\sigma^1,\ldots,\sigma^\ell\), let \(x_i\) be the fraction of the \(2n_i\) signed literals in block \(i\) that are false in every replica. Then \(x_i\in[0,1]\). A fresh within-block clause has mean replica product \(x_i^3\), whereas a fresh global clause has mean replica product \((\lambda_1x_1+\lambda_2x_2)^3\). Poisson differentiation and Equation (28) therefore give \[\frac{\mathrm d}{\mathrm ds}\mathbb E\log Z_s =an\sum_{\ell\ge1}\frac{w^\ell}{\ell} \mathbb E\left\langle \lambda_1x_1^3+\lambda_2x_2^3 -(\lambda_1x_1+\lambda_2x_2)^3 \right\rangle\ge0.\] The last inequality is convexity of the cube on \([0,1]\). Differentiation is justified because one added clause changes \(\log Z_s\) by at most \(\beta\), and the series has the uniform bound just noted. At \(s=0\) the partition function factors into the two block partition functions; at \(s=1\) it has the size-\(n\) law. Thus \(L_n\ge L_{n_1}+L_{n_2}\).

If the formula has \(M\) clauses, then \(n\log2-\beta M\le\log Z_n\le n\log2\). Taking expectations gives \(n(\log2-\beta a)\le L_n\le n\log2\). The superadditive lemma now proves Equation (27). The argument specializes sparse interpolation from (Bayati et al. 2013); its nonnegative signed-literal proportions give the cubic convexity used here. ◻

Proof. At every vertex of depth \(j-1\), independently place a Poisson process of positive child points with intensity \(t_j u^{-t_j-1}\,\,\mathrm du\). The unnormalized weight \(W_\alpha\) of a leaf is the product of the points along its path. To verify that their total mass is finite, suppose a child subtree has total mass \(S'\) measured from that child. For \(x=t_j\), the mapping \(u\mapsto v=uS'\) turns its child process into one of intensity \[cxv^{-x-1}\,\,\mathrm dv,\qquad c=\mathbb E(S')^x.\] The attached subtree law is tilted by \((S')^x/c\) and is independent of the mapped point. This is the marked Poisson mapping formula. At a leaf, \(S'=1\).

If \(S\) is the sum of a process with intensity \(cxv^{-x-1}\,\,\mathrm dv\), then \[ \mathbb Ee^{-qS}=\exp\{-c\Gamma(1-x)q^x\},\qquad q>0. \tag{32}\] It follows that \(0<S<\infty\) almost surely. For \(s\ge1\), \[\mathbb P(S>s)\le \frac{1-\mathbb Ee^{-S/s}}{1-e^{-1}}\le C_{c,x}s^{-x},\] with a finite constant \(C_{c,x}\). For \(0<s\le1\), \[\mathbb P(S\le s)\le e\,\mathbb Ee^{-S/s} =e\exp\{-c\Gamma(1-x)s^{-x}\}.\] Consequently \(\mathbb ES^y<\infty\) for \(0\le y<x\), and \(\mathbb E|\log S|<\infty\). Since the exponents strictly increase down the tree, induction from the leaves gives the required moment \(\mathbb E(S')^{t_j}<\infty\) at every vertex. The total leaf mass is therefore finite and positive; normalize it to obtain \(v_\alpha=W_\alpha/\sum_\gamma W_\gamma\).

We next derive the prediction rule, including the effect of selection through a parent. Consider a node whose child exponent is \(x\) and whose parent exponent is \(y<x\), with \(y=0\) at the root. Once this node is selected from its parent, its point-sum law is tilted by \(S^y/\mathbb ES^y\). Its subtree marks remain independent of the mapped child points, with the individually tilted laws described above. Write \((V_i)\) for the mapped points, so that \(S=\sum_iV_i\). For a specified partition of \(n\) samples into \(h\) nonempty children with sizes \(n_1,\ldots,n_h\), the probability is \[\begin{align*} &\frac1{\mathbb ES^y} \mathbb E\sum_{i_1,\ldots,i_h\ \mathrm{distinct}} S^{y-n}\prod_{j=1}^hV_{i_j}^{n_j} \\ &\quad= \frac{\prod_{j=1}^h\bigl(cx\Gamma(n_j-x)\bigr)} {\mathbb ES^y\,\Gamma(n-y)} \int_0^\infty q^{hx-y-1} e^{-c\Gamma(1-x)q^x}\,\,\mathrm dq. \tag{33}\end{align*}\] Indeed, the Gamma integral represents \(S^{-(n-y)}\), and the Poisson factorial-moment formula evaluates the sum over distinct points. Increasing \(n_j\) by one changes the displayed expression by the factor \((n_j-x)/(n-y)\). The complementary probability of a new child is \((hx-y)/(n-y)\). Observations deeper in the tree concern independent subtree marks and do not change these point predictions. Along an already seen chain, multiplication of the within-parent probabilities telescopes to Equation (30). In the usual Poisson–Dirichlet notation, the child partition seen through its parent has law \(\operatorname{PD}(x,-y)\), rather than the fresh \(\operatorname{PD}(x,0)\) law. The finite prediction probabilities determine the nested partition laws, and conditional independent sampling with the strong law recovers their cluster masses as frequencies.

For Equation (31), condition on root data and put \(y_d=Y\) and \(y_{j-1}=T_{t_j}y_j\) recursively, integrating the level-\(j\) marks. At the last level, map a Poisson point \(u\) to \(ue^{y_d}\). Conditional on the ancestor marks, the mapped process is the original process scaled by \(e^{y_{d-1}}\), since its intensity is multiplied by \(\mathbb Ee^{t_dy_d}=e^{t_dy_{d-1}}\). Discard the integrated marks. After the scale is divided out, the remaining descendant total has its unmarked law and is independent of the retained ancestor marks. Repeating this mapping at the preceding levels gives, conditionally on the root data, \[\sum_\alpha W_\alpha e^{Y_\alpha} \ \stackrel{\mathrm{law}}{=}\ e^{T_{t_1}\cdots T_{t_d}Y_{\mathrm{path}}} \sum_\alpha W_\alpha.\] This is an equality of marginal distributions. Taking mean logarithms and subtracting the mean logarithm of the unmarked total proves Equation (31); log integrability was established above. For a root-conditionally bounded \(Y\), apply the identity at each admissible root value and then integrate its bound.

Children may initially be ordered by raw Poisson points or by total subtree masses. These permutations depend only on the unmarked cascade and preserve ancestry, so independent hierarchical marks have the same conditional law in either ordering. A permutation made after multiplication by \(e^Y\) need not preserve the law of retained marks. The backward calculation discards exactly the marks it integrates and makes no such independence assertion. ◻

Proof of Proposition 12. Use the cascade of Lemma 13. For each reservoir occurrence, attach a fresh tree of site marks and a fresh root site uniform. All these trees are independent conditional on the root global \(z_0\); the site-only message functions use no nonroot global marks. At \(s\in[0,1]\), take independent Poisson collections of three kinds of factors: \[\begin{array}{c|c|c} \text{kind}&\text{mean count}&\text{factor}\\ \hline \text{three real positions}&(1-s)an&1-wI\\ \text{three reservoir occurrences}&(1-s)2an&1-wf_1f_2f_3\\ \text{one real position, two reservoir occurrences}&s3an&1-wI_0f_1f_2. \end{array}\] Real indices are uniform in \([n]\), with independent positions in the first kind; all signs are independent and fair. Here \(I\) is the violation indicator of a real clause and \(I_0\) indicates that the one real literal is false. Let \(\mathcal Z_s\) be the sum over real assignments \(\sigma\) and cascade leaves \(\alpha\) of \(v_\alpha\) times the product of these factors, using the marks on path \(\alpha\) for its messages.

A Gibbs replica for this partition sum consists of a real assignment and a cascade label. Conditional on \(\ell\) replicas and the existing data, including \(z_0\), let \(x\in[0,1]\) be the fraction of real signed literals false in all their assignments. Let \(y\in[0,1]\) be the expected product of the \(\ell\) signed messages at one fresh reservoir occurrence evaluated at their labels. This expectation includes its fresh root uniform, its fresh tree of site marks, and one fresh fair sign; within the occurrence, the replicas use the marks on their respective paths. Distinct occurrences use independent copies of these data. Hence the mean replica products for the three rows of the table are respectively \(x^3\), \(y^3\), and \(xy^2\).

Poisson differentiation and Equation (28) now give \[\frac{\mathrm d}{\mathrm ds}\mathbb E\log\mathcal Z_s =an\sum_{\ell\ge1}\frac{w^\ell}{\ell} \mathbb E\langle x^3+2y^3-3xy^2\rangle\ge0,\] because \[ x^3+2y^3-3xy^2=(x-y)^2(x+2y)\ge0. \tag{34}\] Each new factor lies in \([e^{-\beta},1]\), so the same bounded-increment and absolute-convergence arguments justify the differentiation. The fresh-site factorization just used is the one supplied by the site-only class. We apply this upper-bound argument only to that class, while later intermediate trials retain their used nonroot shared variables.

At \(s=0\), the real partition sum separates from the cascade sum. Splitting the reservoir clause process into \(n\) independent B-packets gives \[\mathbb E\log\mathcal Z_0 =L_n+\mathbb E\mathcal T\sum_{i=1}^nX_{B,i}\] by Equation (31). At \(s=1\), splitting by the uniform real index gives an independent A-packet at each index. The sum over real bits then factors before the cascade sum, and the same identity gives \[\mathbb E\log\mathcal Z_1=\mathbb E\mathcal T\sum_{i=1}^nX_{A,i}.\] The nonnegative derivative therefore proves \(L_n\le G_n=nG_1\), where the last equality is Equation (25). Taking the pressure limit proves the second inequality in Equation (29). ◻

Proof. Fix positive integers \(M,k\) and split a size-\(M+k\) formula into \(M\) old and \(k\) new variables. Its all-old clauses have mean \[ \lambda_{M,k}=a(M+k)\left(\frac{M}{M+k}\right)^3 =\frac{aM^3}{(M+k)^2}. \tag{36}\] Use this old formula as the root disorder \(z_0\). A uniform generator \(z_1\) samples an assignment from its Gibbs law and is shared by all sites. A reservoir occurrence samples an independent uniform old index using its root site variable \(u_0\), and its two messages are the hard indicators that the corresponding signed literals are false in that assignment. Its level-one site variable may be ignored. Thus the depth-one transform \(T_1\) is exactly a log Gibbs average over the old assignment. Each occurrence samples its own old index; accidental repetitions agree with the independent position law of the formula.

Clauses with exactly one new position have total mean \(3akM^2/(M+k)^2\) and split uniformly among the new indices. Clauses with at least two new positions have mean \[\mu_{\ge2}=\frac{ak^2(3M+k)}{(M+k)^2}.\] If the latter clauses are omitted, summing over the new bits gives the log Gibbs average of a product of \(k\) one-bit sums. Replacing the exactly-one-new mean by \(3a\) at each new index produces the \(k\) A-packets. The excess mean in this replacement is \[\Delta_A=3ak-\frac{3akM^2}{(M+k)^2} =\frac{3ak^2(2M+k)}{(M+k)^2}.\] On the other hand, a size-\(M\) formula is obtained from the same old formula by adding old clauses of mean \(aM-\lambda_{M,k}\). Replacing this mean by \(2ak\) produces the \(k\) B-packets, with excess \[\Delta_B=2ak-(aM-\lambda_{M,k}) =\frac{ak^2(3M+2k)}{(M+k)^2}.\] All these replacements can be coupled by adding independent Poisson clauses. An added factor lies in \([e^{-\beta},1]\), so it changes the log of any of the relevant positive partition sums by at most \(\beta\). At the ideal rates, the two mean log Gibbs increments from the same old formula are exactly the A and B terms of \(G_k\) for this trial, which depends on \((M,k)\). Comparing the original and ideal rates therefore gives \[\begin{align*} \bigl|L_{M+k}-L_M-G_k\bigr| &\le\beta(\mu_{\ge2}+\Delta_A+\Delta_B) \\ &=\frac{a\beta k^2(12M+6k)}{(M+k)^2} \le\frac{12a\beta k^2}{M}. \tag{37}\end{align*}\]

For fixed \(k\), the pressure limit implies \[\liminf_{M\to\infty}(L_{M+k}-L_M)\le kP(a,\beta).\] Indeed, if all sufficiently large increments exceeded \(kP\) by one fixed positive amount, summing along any arithmetic progression of step \(k\) would contradict \(L_n/n\to P\). Choose \(M\) large along this liminf so that the increment divided by \(k\) is at most \(P+\epsilon/2\) and the last term of Equation (37), divided by \(k\), is at most \(\epsilon/2\). This proves Equation (35). Finally, apply the result separately at \(k=N\) with any error sequence tending to zero. The reservoir size may depend on \(N\) and on that error; no uniform choice is needed. ◻

Proof. Condition on the root data, and let \(\mathcal H_\ell\) be the history through level \(\ell\). By the definition of \(Y_{\ell-1}\), the density in Equation (38) integrates to one conditional on the history through level \(\ell-1\). Put \[V_\ell=T_{t_{\ell+1}}\cdots T_{t_d}(Y+X)-Y_\ell, \qquad V_d=X.\] At each level the identity \[V_{\ell-1}=\frac1{t_\ell}\log\mathbb E\left[ e^{t_\ell(Y_\ell-Y_{\ell-1})}e^{t_\ell V_\ell} \,\middle|\,\mathcal H_{\ell-1}\right]\] follows by subtracting \(Y_{\ell-1}\) from the two logarithms. Applying it successively outward proves the asserted nested transform.

Each density uses only globals and old-site variables, because \(Y\) does. It leaves the product uniform law of all fresh site generators unchanged. The old-site variables can be included in the enlarged global history, which is a standard Borel random object and can again be sampled by successive uniform generators. Its finite-path law is absolutely continuous with respect to the original global and old-site law. Hence any original null set of complete global paths remains null, while the fresh-site kernels and their conditional uniform laws stay the same. The argument holds for almost every root value, as required. ◻

Proof. Choose measurable feature maps \(v_j\) with \(C_j(\zeta,\zeta')=\langle v_j(\zeta),v_j(\zeta')\rangle\); their norms are at most one. Fix \(l\) and write \(x=x_l\). We allow \(x\) to range over \([0,3]\) during the proof. Numerical constants denoted by \(K_l\) depend only on \(l\). Consider \[\Psi(x)=\frac{1}{s^2a_l^2}\log\mu(e^h)+\frac{x^2}{2}, \qquad A_x(\zeta)=\frac{g_l(\zeta)}{sa_l}-xC_l(\zeta,\zeta).\] Differentiation gives \[ \Psi'(x)=\langle A_x\rangle+x, \qquad \Psi''(x)=s^2a_l^2\langle(A_x-\langle A_x\rangle)^2\rangle +1-\langle C_l(\zeta,\zeta)\rangle\ge0. \tag{52}\] The deterministic diagonal correction in (49) is exactly what permits both this convexity and the cancellation in (51) below.

For every fixed \(\zeta\), \(\mathbb E_g e^{h(\zeta)}=1\) and \(-Cs^2\le\mathbb E_g h(\zeta)\le0\), with an absolute constant \(C\). The two Jensen inequalities therefore give \[ -Cs^2\le\mathbb E_g\log\mu(e^h)\le0. \tag{53}\] Consequently the convex function \(\bar\Psi=\mathbb E_g\Psi\) is bounded on \([0,3]\) by a constant depending only on \(l\), and its one-sided derivatives are uniformly bounded on \([1/2,5/2]\). Integrating (52) over \([1,2]\) yields \[ \int_1^2\mathbb E_g\langle(A_x-\langle A_x\rangle)^2\rangle\,\,\mathrm dx \le K_l s^{-2}. \tag{54}\] Interchanging expectation with the first derivative is legitimate here: on any compact interior interval, convexity bounds the derivative by secants to two fixed outer points, whose absolute values are integrable by (53) and Gaussian integrability.

The Gaussian gradient of \(\log\mu(e^h)\) has norm at most \(Cs\). Indeed it is the Gibbs mean of the direct-sum feature vector \((s a_jx_j v_j(\zeta))_j\), whose squared norm is at most \(s^2\sum_j a_j^2x_j^2\). The Gaussian variance inequality gives \[ \mathbb E_g|\Psi(x)-\bar\Psi(x)|\le K_l/s. \tag{55}\] For \(0<u<1/2\), compare \(\Psi'(x)\) with its left and right secants of length \(u\), and do the same for \(\bar\Psi\). After integrating over \(x\in[1,2]\), (55) bounds the random secant errors by \(K_l/(su)\). The remaining deterministic error is at most \[\int_1^2\bigl(\bar\Psi'_+(x+u)-\bar\Psi'_-(x-u)\bigr)\,\,\mathrm dx \le K_lu;\] the integral telescopes and the interior derivatives are bounded. Thus \[ \int_1^2\mathbb E_g|\Psi'(x)-\mathbb E_g\Psi'(x)|\,\,\mathrm dx \le K_l\bigl((su)^{-1}+u\bigr). \tag{56}\] Since \(V_l=A_x/x\) and \(x\ge1\), the sum of (54), by Cauchy–Schwarz, and (56), with \(u=s^{-1/2}\), proves (50).

For completeness, all the preceding operations can first be performed with finitely many Gaussian coordinates in finitely many feature spaces. The resulting bounds do not depend on these truncations. The Gaussian series converge in \(L^2(\mathbb P_g\otimes\mu)\). For fixed \(s\) their limit is finite for \(\mu\)-almost every index, for almost every field realization, so the normalizer is positive. Also \(\mathbb E_g\mu(e^h)=1\) by Fubini, so the normalizer is finite almost surely. For fixed \(s\) the exponentials have uniformly bounded moments of every fixed positive order, while Jensen’s inequality gives \[\mu(e^h)^{-q}\le\mu(e^{-qh})\qquad(q>0).\] The right side has uniformly bounded Gaussian expectation. These bounds give uniform integrability of the logarithms and of the replica integrals, including polynomial factors in \(g_l\). They justify passage from finite-dimensional differentiation, concentration, and Gaussian integration by parts to the displayed formulas. Equivalently one can construct the fields by isonormal processes on the separable feature spaces; joint measurability is needed only outside a \(\mathbb P_g\otimes\mu\) null set.

Average the additional marks conditional on their sample indices. The resulting test is independent of the fields, so Gaussian integration by parts gives \[\mathbb E_g\left\langle f\frac{g_l(\zeta^1)}{s a_lx_l}\right\rangle =\mathbb E_g\left\langle f\left(\sum_{i=1}^n C_l(1,i)-nC_l(1,n+1)\right) \right\rangle.\] Subtracting the diagonal term in \(V_l\) removes \(C_l(1,1)\). The case \(f=1\), \(n=1\) says \(\mathbb E_g\langle V_l\rangle=-\mathbb E_g\langle C_l(1,2)\rangle\). Finally, \[\left|\mathbb E_g\langle fV_l\rangle -\mathbb E_g\langle f\rangle\mathbb E_g\langle V_l\rangle\right| \le e_l,\] which proves (51). ◻

Proof. The Dovbysh–Sudakov representation, in Proposition 1 of (Panchenko 2010b), realizes the array as a mixture of arrays \[R_{ij}=\langle v_i,v_j\rangle+a_i\mathbf 1_{\{i=j\}},\qquad a_i\ge0,\] where the pairs \((v_i,a_i)\) are conditionally independent with the same law on a separable Hilbert space times \([0,\infty)\). The unit diagonal puts every \(v_i\) in the unit ball. Let \(\mathcal G\) denote the random directing law of the vectors and put \(q_* = \max\operatorname{supp}\operatorname{Law}(R_{12})\); this support is compact because positive semidefiniteness and the unit diagonal imply \(|R_{ij}|\le1\).

Theorem 2(a) of Panchenko (Panchenko 2010a) applies to these off-diagonal Ghirlanda–Guerra identities and gives \[\mathcal G\{v:\|v\|^2=q_*\}=1\qquad\hbox{almost surely}.\] Its sphere conclusion has no finite-support hypothesis. Now form the true Gram array \(\widehat R_{ij}=\langle v_i,v_j\rangle\), including its diagonal. It has the same off-diagonal entries as \(R\) and the deterministic diagonal \(q_*\). A bounded test of its complete first-\(n\) matrix is therefore a bounded test of the off-diagonal matrix with constants substituted on the diagonal. Thus the displayed identities give the full Ghirlanda–Guerra identities for \(\widehat R\) under the joint, averaged law. No conditioning on a realization of \(\mathcal G\) is used in this implication.

The random measure \(\mathcal G\) is supported on the unit ball of a separable Hilbert space. Theorem 1 of Panchenko (Panchenko 2013b) now applies to its true Gram array and gives the asserted ultrametric inequalities for the off-diagonal entries. This theorem likewise permits a general overlap distribution. ◻

Proof. In each replica array, set \(Q_j(u,u)=1\) for every sample index \(u\). Leave all \(Q_j(u,v)\) with \(u\ne v\) unchanged, even when the sampled values of \(z_1\) coincide. Before passage to the limit this adds a nonnegative diagonal matrix to a Gram matrix, so it preserves positive semidefiniteness. The finite-matrix condition is closed and hence also holds in the limit. Every convex combination with positive rational coefficients is therefore a weakly exchangeable positive semidefinite array with unit diagonal. Its off-diagonal identities follow from (59), so Lemma 19 makes it ultrametric.

There are countably many rational combinations, so their conclusions hold simultaneously. In any off-diagonal triple the three vector overlaps must contain an equal pair. Otherwise some positive rational linear functional avoids their three equality hyperplanes and gives three distinct scalar overlaps, contrary to ultrametricity. If the repeated vector is \(v\) and the remaining vector is \(v'\), then \(v\le v'\) componentwise: otherwise a positive rational functional concentrated on a violating coordinate would make the unique value the strict minimum, again impossible.

It follows that \(\mathbf Q(1,2)\) and \(\mathbf Q(1,3)\) are almost surely comparable. If two points in \(\mathcal S\) were incomparable, they would have incomparable neighborhoods \(A,B\) of positive pair-law probability. Apply (59) with \(n=2\), \(f=\mathbf 1_{\{\mathbf Q(1,2)\in A\}}\), and \(\psi=\mathbf 1_B\). Since \(A\cap B=\varnothing\), it gives probability \(\mathbb P(\mathbf Q\in A)\mathbb P(\mathbf Q\in B)/2>0\) of seeing an incomparable pair, a contradiction. Componentwise ordering implies (60); ultrametricity of \(Q\) was already obtained from the equal-weight combination. ◻

Proof. For a cut of parameter \(x_j\), let \(C\) be a cluster seen among the first \(n\) samples, of size \(n_C\). Select an anchor in \(C\) by a finite case distinction. Equation (59), with the indicator of the anchor’s cut relation as \(\psi\), shows that, conditionally on all past pair and decoration data, the next sample belongs to \(C\) with probability \[ \frac{n_C-x_j}{n}. \tag{63}\] Indeed the independent term contributes \((1-x_j)/n\) and the past anchor-neighbor terms contribute \((n_C-1)/n\). Differences between these probabilities specify the creation of new children within each parent. These are exactly the RPC predictions in Lemma 13, Equation (30). They determine every finite nested partition law. Consequently the full partition has that law, its clusters have positive frequencies, and the frequencies at every level have total mass one. The ranked leaf frequencies have the corresponding RPC distribution. For \(h=0\) these statements mean a single cluster of mass one.

We now prove independence from the full partition using the decoration tests in Equation (59). Let \(I\) be a deterministic ordered tuple of distinct sample indices, let \(D_I\) be all their decorations, and let \(\Pi\) be the full nested partition. Expose \(I\) first, using exchangeability. Given its cut pattern and decorations, iterating (63) shows that the conditional law of the partition on all remaining indices depends only on that cut pattern. In this iteration one can condition down from all intermediate decorations, since the predictions do not depend on them. Extending from finite restrictions to the countable partition gives, for every bounded decoration test \(f\), \[ \mathbb E[f(D_I)\mid\Pi]=K_{\Pi|_I}(f), \tag{64}\] where the probability kernel \(K\) depends only on the ordered internal cut pattern \(\Pi|_I\), and not on the actual values of the indices.

The inverse image of a fixed finite tuple of distinct positions in the ranked-cluster/natural-order indexing is a tuple of original indices measurable with respect to the partition. Partitioning according to its countably many possible values and applying Equation (64) proves that the reindexed tuple’s decoration law is independent of the partition. Its internal cut pattern is fixed by its new positions. The same argument shows invariance under ancestry-preserving permutations of the hidden clusters and of the sample indices within them. It applies to arbitrary finite decoration cylinders and hence to the complete arrays. The old descendant permutations and the site permutations do not change the cut partition, so their invariances are retained as well. ◻

Proof. For a one-step transform of a random variable \(Y\in[-C,C]\), \[T_tY=\frac1t\log\mathbb Ee^{tY}, \qquad \widehat T_tY=\frac1t\log\left(\frac1B\sum_{b=1}^B e^{tY_b}\right).\] The standard deviation of \(e^{tY}\) is at most \(2tCe^C\), while \(t^{-1}\log v\) is \(e^C/t\)-Lipschitz on \([e^{-tC},e^{tC}]\). Hence \[ \mathbb E|\widehat T_tY-T_tY| \le2Ce^{2C}/\sqrt B. \tag{65}\] If exact child values \(Y\) are replaced by values \(Y'\) in \([-C,C]\), interpolation between the two sets of values gives \[|T_tY-T_tY'|\le e^{2C}\mathbb E|Y-Y'|,\] and the identical bound with an empirical mean holds for an empirical transform. Apply these bounds recursively from the leaves upward. Every intermediate value remains in \([-C,C]\), so the constants depend only on \(C,d\). A joint child variable may include the global coordinate and all the finitely many site coordinates; conditional independence between children is all that was used. ◻

Proof. First fix all packet counts and signs, so the endpoint uses finitely many distinct sites and its loss \(X\) is bounded, say by \(C\). For each fixed \(B\), the empirical tree evaluation is a continuous function of finitely many retained message values and of the old exponents. Continuity follows also at messages equal to zero or one, because every factor \(1-wf_1f_2f_3\) is at least \(1-w=e^{-\beta}>0\). The old exponents converge to positive limits since \(t_j\ge m_0\). Thus weak convergence of the natural-order arrays gives convergence of the expected empirical evaluation. Lemma 22 is uniform before the limit, so taking \(B\to\infty\) afterward recovers exactly the subsequential expected endpoint value.

We now evaluate that same limit using the representation and its independent cut partition. Below the sample level, replace empirical evaluations by the true conditional transforms \(T_{t_2},\ldots,T_{t_d}\). The error tends to zero by the same uniform estimate, even after propagation through the top empirical average. Write \(Y_{\alpha,l}\in[-C,C]\) for the resulting value at sample position \((\alpha,l)\in\mathbb N^h\times\mathbb N\). Condition on the full cut partition and on all represented variables through the hidden levels, including their root variables. The remaining sample-level variables are independent across sample positions, and their laws are identical within each hidden leaf. If \(\alpha(u)\) is the leaf containing natural sample \(u\), then the conditional mean of the first-\(B\) natural-order average is \[\frac1B\sum_{u=1}^B \mathbb E_{\rm sample}e^{mY_{\alpha(u),1}}.\] Its conditional variance is \(O_C(B^{-1})\). The empirical frequencies of the hidden leaves converge to their masses \((v_\alpha)\); convergence is in \(\ell^1\), since these are probability masses whose pointwise limits have sum one. Hence, in \(L^1\), \[ \frac1B\sum_{u=1}^B e^{mY_{\alpha(u),l(u)}} \longrightarrow \sum_\alpha v_\alpha\mathbb E_{\rm sample}e^{mY_{\alpha,1}}. \tag{67}\] Boundedness makes passage to the divided logarithm legitimate. For \(h=0\) the sum consists of one term of weight one.

Set \(V_\alpha=T_m^{\rm sample}Y_{\alpha,1}\). The represented marks and their root variables were chosen independently of the full partition, so the RPC weights retain their original law conditional on those root variables and are independent of the attached marks. If \(h=0\), the divided logarithm in (67) is simply \(V_{\varnothing}\), where \(\varnothing\) is the unique empty label. If \(h\ge1\), the hidden parameters satisfy \(0<x_1<\cdots<x_h<1\), exactly the strict cascade hypothesis of Lemma 13. Applying its logarithmic identity conditionally on the root data to marks \(mV_\alpha\) shows that the expectation of the divided logarithm on the right of (67) is the nested transform with hidden exponents \(mx_1,\ldots,mx_h\), followed by the sample exponent \(m\). The scaling is the identity \[T_x(mV)=mT_{mx}V,\] applied successively at the hidden levels and followed by division by \(m\). Below them remain the old exponents \(t_2,\ldots,t_d\). This proves precisely (66). The hidden exponents, when present, are increasing and lie strictly between zero and \(m\). Every old descendant exponent is at least \(m\), and their old order persists. Thus these are admissible intermediate trial exponents, including when some old exponents coincide or equal one.

Finally remove the conditioning on counts and signs. Both the prelimit and limit transforms are bounded in absolute value by \(k\log2+\beta\sum D_i\), with the fixed Poisson packet laws. Their tails are uniformly integrable. Truncating counts, applying the proved finite-count assertion, and then removing the truncation establishes the assertion for each expected endpoint. Subtracting the B endpoint from the A endpoint and using (57) yields \(G_k/k\le U\). ◻

Proof. A closed set of full product measure contains the product of the two supports: otherwise a pair of support points has product neighborhoods of positive measure disjoint from that set. The first assertion follows by putting the same support point in both coordinates. In the second, for support points \(v,v'\), both squared norms and their inner product belong to the same interval, so \[\|v-v'\|^2=\|v\|^2+\|v'\|^2-2\langle v,v'\rangle \le2\varepsilon.\] Jensen’s inequality gives the assertion about the barycenter. The same reasoning applies after disintegration; separability ensures that the relevant supports have full measure. ◻

Proof. Let \((b,c]\) be an old block. Since the input hierarchy is active, \(b\ge1\). In the prelimit natural array we may therefore choose two paths in the same first-level sample, agreeing through \(b\) and diverging immediately afterward. At site \(i\), form the product of their two values of \[\phi(S_c)-S_b(\phi), \qquad \phi\in\Phi_j.\] Condition on the complete globals of the two paths. The sites are independent and identically distributed, and the conditional mean of this product is the \(L^2(\,\mathrm du_{0:b})\) inner product of the two error functions \[E_z(u_{0:b})= \int\phi(S_c)\,\,\mathrm du_{b+1:c}-S_b(\phi).\] The fresh site variables after the branching point are independent on the two paths; their shared site variables are exactly those through \(b\). Equation (45), which survived the posterior and Gaussian changes of law, bounds both error norms by \(\delta\). Cauchy–Schwarz therefore bounds the absolute conditional mean by \(\delta^2\).

Let \(M_I\) be the empirical mean over the first \(I\) sites. The summands belong to \([-1,1]\), so \[ \mathbb E\operatorname{dist}(M_I,[-\delta^2,\delta^2])^2\le I^{-1}. \tag{68}\] For fixed \(I\), the integrand on its left is a bounded continuous function of finitely many retained type values: \(\phi\) is continuous, and evaluation of a probability measure against \(\phi\) is continuous in the type-space topology. The inequality thus passes to the limit. On \(I=2^j\), Markov’s inequality and Borel–Cantelli imply that the displayed distance tends to zero almost surely. This holds simultaneously for all countably many path choices and all the finitely many tests. It consequently remains true for the partition-selected paths after reindexing.

In the product-tree representation, the conditional strong law for the sites identifies the limit of \(M_I\) with the inner product of the analogous error vectors, now in \(L^2(\,\mathrm du_{0:b+h})\). Conditional on the common globals through the shifted block start, those two vectors are independent and identically distributed as their continuation globals vary. Thus their inner product has absolute value at most \(\delta^2\) almost surely. Apply the first assertion of Lemma 24 to this conditional law. Each error vector has norm at most \(\delta\) for almost every global continuation. Fubini’s theorem gives precisely Equation (45) for almost every complete global path. The weak-limit step used a closed finite-column condition; the pathwise conclusion then followed from the conditional support bound. ◻

Proof. For two distinct natural first-level samples, average over the first \(I\) sites the product of their \(\phi_j(S_1)\) values. Conditional on their globals and Gaussian fields, the site’s root variable is shared between the two samples, and its first-level variables are independent. The conditional mean is exactly \(Q_j\) from (48). Therefore \[ \mathbb E\left|\frac1I\sum_{i=1}^I \phi_j(S_1^{1,i})\phi_j(S_1^{2,i})-Q_j(1,2) \right|^2\le I^{-1}. \tag{69}\] For each fixed \(I\) this inequality passes by continuity to the natural-order limit array. Along dyadic \(I\), it gives almost-sure convergence of the empirical average to \(Q_j\), simultaneously for all pairs and tests.

After reindexing, take two sample positions agreeing through \(b\) and diverging immediately below \(b\). If the parent is present, they are in the same parent cluster; otherwise \(\mathbb P(Q<q)=0\). If the child is present, they lie in distinct child clusters; otherwise \(\mathbb P(Q<r)=1\). Consequently their natural pair overlap satisfies \(q\le Q<r\) almost surely in all cases. By (61) and Lemma 20, the corresponding \(Q_j\) belongs to a fixed closed interval \(I_j\) of length at most \(J_f\gamma\). The empirical characterization just proved shows that this interval condition is a property of the reindexed decorations alone; we do not need a separate representation of the kernels \(Q_j\).

In the product-tree representation, the site empirical limit is the inner product in \(L^2(\,\mathrm du_{0:b})\) of the two vectors \[ A_j(u_{0:b})= \int\phi_j(S_c)\,\,\mathrm du_{b+1:c}. \tag{70}\] Conditional on the ancestor globals through \(b\), these are independent copies as their continuation globals vary. Their inner product belongs to \(I_j\) almost surely. The second assertion of Lemma 24 shows that the conditional support of \(A_j\) has diameter at most \(\sqrt{2J_f\gamma}\).

Define, for each ancestor global and site history, \[ S_b(z_{0:b},u_{0:b}) =\operatorname{Law}_{z_{b+1:c},u_{b+1:c}}(S_c). \tag{71}\] All continuation variables in this formula have their current independent uniform laws. This is a measurable probability kernel on the type space of \(S_c\), hence has exactly the required next type space. By Fubini’s theorem, \(S_b(\phi_j)\) is the conditional continuation-global barycenter of the vector \(A_j\) in (70). The support diameter bound gives \[\int\left| \int\phi_j(S_c)\,\,\mathrm du_{b+1:c}-S_b(\phi_j) \right|^2\,\mathrm du_{0:b}\le 2J_f\gamma\] for almost every complete global path. Choose \(0<\gamma\le\delta^2/(2J_f)\) to obtain the new record.

It remains to check the exponent band. The only possible intermediate level between \(b\) and \(c\) is the child cut, whose exponent is \(mx_c\). By (61), \(x_c\ge1-\eta\), so \(m-mx_c\le m\eta\le\eta\). The end exponent is \(m\). If the parent is present, its exponent satisfies \(0<mx_p\le(1-\eta)m\), as claimed.

The type in (71) is defined once, at this transition. In subsequent posterior changes it is retained as the same measurable function; it is not redefined by averaging under the changed global law. The pathwise record just proved then survives by absolute continuity, exactly as do the old records. ◻

Completion of the proof of Lemma 17. The compactness and representation construction inserts at most two levels. Lemma 23 supplies the limiting expected endpoint values and \(G_k/k\le U\). Lemma 25 preserves every old record, while their exponent-band inequalities survive ordinary limits. Lemma 26 supplies the new processed block. If there is no parent cut it begins at the root and processing is complete. Otherwise the hierarchy is active, its first exponent is \(mx_p>0\), and this is at most \((1-\eta)m\). All records hold for almost every complete global path. These constructions were made for the fixed output horizon \(k\); repeating them for any other fixed horizon proves the asserted quantifiers. All nonroot shared globals remain in this output. The next section removes them by a separate approximation argument. ◻

Proof. Kantorovich–Rubinstein duality expresses \(W_1\) as the supremum of integral differences over \(1\)-Lipschitz functions. Constants cancel from such differences; since the space has diameter at most one, each test can be shifted into \([0,1]\). The class of these bounded Lipschitz functions is compact in the uniform norm. A finite \(e_0/4\)-net gives Equation (72), since replacing a test by a net point changes the difference of its two integrals by at most \(e_0/2\).

For a fixed test, the structural record and Cauchy–Schwarz give \[\int |\nu_{z,u_{0:b}}(\phi)-S_b(z_{0:b},u_{0:b})(\phi)| \,\,\mathrm du_{0:b}\le\delta.\] Bound the maximum over tests by their sum, integrate Equation (72), and use Equation (73). This proves Equation (74) with its almost-everywhere global quantifier intact. ◻

Proof. Lemma 14 supplies trials for arbitrarily large integer horizons \(N\), initially of depth one and first exponent \(1\), with \(G_N/N\le U\). There are initially no processed blocks. A trial is terminal if its blocks start at the root or if its first unprocessed exponent is less than \(m_0\).

Suppose a sequence at a given stage contains no terminal trial. All its first exponents are then at least \(m_0\). Depth has increased by at most two at each preceding transition, so there are only finitely many possible patterns of block boundaries. Pass to an unbounded horizon subsequence with a common pattern, and then to a subsequence on which the exponents converge. Lemma 17, with its fixed tests and tolerance, produces for each fixed positive integer \(k\) an output trial satisfying \(G_k/k\le U\). It preserves the old records and adds one processed block. Either the output is terminal, or its new first exponent is at most \((1-\eta)\) times the limiting old first exponent.

This use of the transition involves nested limits, not a uniform limit in \(k\). First fix \(k\); then take the input horizon to infinity as required by the transition; finally retain an output for that \(k\). Doing this separately for \(k=1,2,\ldots\) gives the next unbounded horizon sequence if no terminal output occurs. After \(j\) transitions every still-active output has first exponent at most \((1-\eta)^j\). Equation (75) therefore forces termination after at most \(J\) transitions. The resulting terminal trial has some finite horizon, at most \(J\) blocks, and depth at most \(2J+1\).

Reduce its horizon to one using the packet telescope of Lemma 15, without a Gaussian perturbation. There is no remainder when the blocks have size one. The sum of the averaged one-packet posterior differences is the original \(G_k\), so one step, and then base root data outside the conditional null sets, have posterior value at most \(U+\rho\). This selection is made before fresh packet data are sampled. The conditional laws generated by the posterior densities remain equivalent to the old laws, and the old site-law functions are kept rather than recomputed. Hence all the almost-everywhere records persist. Neither the exponents nor the terminal boundary changes. This gives the asserted one-packet trial. ◻

Proof. We first condition on either endpoint’s fresh count and sign data with \(D\le D_0\). Its loss \(X\) is bounded in absolute value by \(C\), and it uses at most \(M\) distinct reservoir occurrences. Simultaneously replace all exponents in each processed block \((b,c]\) by \(t_c\). The resulting vector is still nondecreasing and is within \(\eta\) of the original. Lemma 16 bounds the change by \(K(C)\eta\). A block with constant exponent is one conditional \(T_{t_c}\) operation over all its coordinates, by the tower property.

Define deterministic functions of vectors of single-site types, one coordinate for each reservoir occurrence, working upwards through the block boundaries. At the last boundary put \(F_d(\mathbf S_d)=X\). For a block \((b,c]\) put \[ F_b(\mathbf s)=\frac1{t_c}\log\int \exp\bigl(t_cF_c(\mathbf u)\bigr)\prod_i s_i(\,\mathrm du_i). \tag{77}\] These functions depend on the fixed count and sign data, but the probability kernels \(S_b\) do not. The functions \(F_b\) are bounded in absolute value by \(C\).

Use the sum metric on each finite product of type spaces. The terminal loss is \(e^\beta\)-Lipschitz: a clause factor is bounded below by \(1-w=e^{-\beta}\), the product of at most three \([0,1]\) messages changes by at most the sum of their changes, and the log-sum-exp for the two branches of an A packet preserves the largest branchwise log error. Thus we may take \(L_d=e^\beta\) as a Lipschitz constant for \(F_d\). Coordinatewise couplings in Equation (77) give \[ L_b\le e^{2C}L_c. \tag{78}\] Indeed \(v\mapsto e^{t_cv}\) has Lipschitz constant at most \(t_ce^C\) on \([-C,C]\), and the divided logarithm on the possible integral values has Lipschitz constant at most \(e^C/t_c\). The same two bounds show that a mean absolute error in an inside value propagates through a block by at most the factor \(e^{2C}\).

Let \(Y_b\) denote the actual effective value at boundary \(b\) after flattening the processed blocks’ exponents. Thus \(Y_d=X\), and across a block \((b,c]\) the value \(Y_b\) is the conditional \(T_{t_c}\) average of \(Y_c\) over the block’s global and site coordinates. Define \[E_b=\mathbb E_{\mathrm{base}} \bigl|Y_b-F_b(\mathbf S_b)\bigr|.\] Here the expectation uses the current trial law on the global history and all occurrences’ fresh site histories through \(b\), before any exponential reweighting by this fresh packet. This law already includes any old-packet posterior used to obtain the trial; the packet count and signs remain fixed. In particular \(E_d=0\). We claim that \[ E_b\le e^{2C}E_c+e^{2C}L_cMe_0. \tag{79}\]

First replace \(Y_c\) inside the block average by \(F_c(\mathbf S_c)\). The mean-error propagation bound above gives the first term of Equation (79). To bound the remaining error, fix the ancestor histories through \(b\) and the continuation globals through \(c\). Under this conditioning, the occurrences’ fresh site continuations are independent; write \(\nu_i\) for the resulting law of \(S_c^i\). A product of Wasserstein couplings and the Lipschitz constant of \(F_c\) give \[\left|\int e^{t_cF_c(\mathbf u)}\prod_i\nu_i(\,\mathrm du_i) -\int e^{t_cF_c(\mathbf u)}\prod_iS_b^i(\,\mathrm du_i)\right| \le t_ce^C L_c\sum_i W_1(\nu_i,S_b^i).\] The second integral depends only on the ancestor histories. Average this inequality over the continuation globals, apply the \(e^C/t_c\) Lipschitz bound for the divided logarithm, and then average over the ancestor histories. For almost every fixed global path, Equation (74) bounds the integral over each occurrence’s site ancestors by \(e_0\). The continuation-global law is independent of these fresh site generators, including when the trial was obtained by a posterior change of law. Fubini’s theorem therefore bounds the final average by \(e^{2C}L_cMe_0\) and proves Equation (79).

There are at most \(J\) processed blocks, and \(L_c\le e^{2CJ}e^\beta\) at every boundary. Iterating Equation (79) from \(E_d=0\) bounds their accumulated error. If the starting boundary is \(1\), propagating once through the remaining first-level transform adds at most one factor \(e^{2C}\). In either case the error is at most \[JM e^\beta e^{2C(2J+2)}e_0=R.\]

If the processed blocks begin at the root, the resulting recursion already describes a site-only trial. Retain the common root \(z_0\) and sample each occurrence’s initial type \(S_0(z_0,u_0^i)\) using its own fresh root-site uniform. At one level of exponent \(t_c\) for each old block, draw each site’s next type independently from its preceding type, and continue to the message pair. Probability kernels on these compact metric spaces can be sampled by measurable functions of fresh uniform variables. This construction evaluates Equation (77).

If the blocks begin at boundary \(1\), there is still the operation \(T_mF_1(\mathbf S_1)\), where \(0<m<m_0\). Conditional on the root data, factor this operation as \[T_m^{z_1}T_m^{\mathrm{sites}}F_1(\mathbf S_1).\] The inside quantity is in \([-C,C]\). By Equation (41), replacing the outside \(T_m^{z_1}\) by ordinary expectation changes its value by at most \(\tfrac12 C^2e^{2C}m_0\). Move \(z_1\), with this ordinary sampling law, into the root global data. Retain the level-\(1\) site transform and the independent block draws just constructed. This is again site-only. Its kernels were constructed from the recorded types alone, not from any fresh count or sign data.

For counts greater than \(D_0\), both the old and new endpoint transforms are bounded in absolute value by \(\log2+\beta D\), regardless of their kernels or exponents. Their contribution to the difference is thus at most twice the corresponding tail expectation. Summing the bounded-count estimates for the two endpoints proves Equation (76). ◻

Proof. The upper bound of Proposition 12 gives \(P(a,\beta)\le G_1\) for every member of \(\mathcal Q\). We prove the reverse inequality by giving the order of all approximation choices.

Fix \(\epsilon>0\) and put \(U=P(a,\beta)+\epsilon\). First choose a count cutoff \(D_0\ge1\) with \(\tau_A,\tau_B\le\epsilon\), and set \(C=\log2+\beta D_0\). Choose \(\eta,m_0\in(0,1)\) so that \[K(C)\eta\le\epsilon,\qquad \tfrac12 C^2e^{2C}m_0\le\epsilon.\] Next choose \(J\) satisfying Equation (75), and only then choose \(e_0>0\) so small that \[J(3D_0)e^\beta e^{2C(2J+2)}e_0\le\epsilon.\] Choose the finite test sets on all type spaces through \(K^{(J)}\) by Lemma 27, and finally choose \(\delta\) satisfying Equation (73). In particular, neither the test precision nor the allowed number of transitions is chosen in response to the eventual hierarchy depth. The overlap widths used inside each transition are chosen only after these test sets and \(\delta\), as in Lemma 17.

Proposition 28, with \(\rho=\epsilon\), gives a terminal one-packet trial of value at most \(P+2\epsilon\). Lemma 29 turns it into a site-only trial whose value is at most \(P+12\epsilon\): the exponent changes contribute at most \(2\epsilon\), the kernel replacements at most \(2\epsilon\), the possible small-exponent replacement at most \(2\epsilon\), and the two tails at most \(4\epsilon\).

It remains to obtain a finite rational description. Approximate the finite weakly increasing exponent vector by strictly increasing rational vectors in \((0,1)\). This is possible even if some original exponents coincide or equal \(1\). For fixed count data, Lemma 16 gives convergence of the transform values. The packet bound of Equation (23), uniform over the approximations, then gives convergence after averaging the Poisson counts and signs.

Encode the root randomness by a single uniform coordinate. After the independent conditional type samplings have likewise been encoded by uniform coordinates, the message pair is a measurable function of finitely many independent uniforms: the root global, the root site coordinate, and the finitely many site-level coordinates. Approximate this pair in \(L^1\) by rational-valued step functions on finite dyadic rectangular grids. For example, conditional expectations on the successive dyadic grids converge in \(L^1\), and subsequent rational quantization preserves the range \([0,1]^2\) and the convergence. The shared root coordinate is retained as shared; no independence across sites is introduced there.

For fixed counts and signs, the leaf Lipschitz estimate in the proof of Lemma 29 bounds the mean leaf error by \(e^\beta\) times the sum of the \(L^1\) message errors over the finitely many occurrences. The mean-error propagation bound through the fixed finite hierarchy proves convergence of both endpoint values. Once more, the root linear-in-count bound makes the Poisson tails uniform, so their fully averaged \(G_1\) values converge. Thus a member of \(\mathcal Q\) has value at most \(P+13\epsilon\).

Since \(\epsilon\) is arbitrary, Equation (80) follows. Finite depths, finite grids, rational exponents, and finite rational tables all have finite encodings and can be enumerated by a single ordinary algorithm. These are the trials used in the certificate search; none of the compactness limits or tolerance choices in the existence proof is input to that search. The larger class of strict measurable site-only trials contains \(\mathcal Q\) and obeys the same upper bound, so its infimum also equals \(P(a,\beta)\). ◻