Proof. We first prove the removal assertion without summation. Coordinates with \(z_i=0\) give zero rows and columns and may be discarded. Temporarily evaluate all remaining entries using the product of factors, even when a repeated removal would give a negative coordinate. This evaluation is well-defined because the factors are defined on all integers. Write \[l_G=\sum_{i\in G}z_i, \qquad \gamma_G= \frac{\psi_G(l_G)\psi_G(l_G-2)} {\psi_G(l_G-1)^2}.\] Log-concavity gives \(0<\gamma_G\le1\). Factor out the value of the product at the display and, from each matrix index \(i\), the positive single-removal ratio \[\prod_{G\ni i}\frac{\psi_G(l_G-1)}{\psi_G(l_G)}.\] Thus, up to a positive scalar and a positive diagonal congruence, the entry at \(i,h\) is \(\prod_{G\supseteq\{i,h\}}\gamma_G\). Restrict the factor sets to the retained coordinates and combine duplicates if necessary. Laminarity then gives the matrix identity \[ \left(\prod_{G\supseteq\{i,h\}}\gamma_G\right)_{i,h} = \mathbf 1\mathbf 1^{\mathsf T} - \sum_{G\in\mathcal L} (1-\gamma_G) \left(\prod_{\substack{G'\in\mathcal L\\G'\supsetneq G}} \gamma_{G'}\right) \mathbf 1_G\mathbf 1_G^{\mathsf T}. \tag{13}\] For each entry the identity telescopes along the chain of sets containing both indices. The right-hand side is a rank-one positive semidefinite matrix minus a positive semidefinite matrix, so it has at most one positive eigenvalue. The only invalid removals still present are repeated removals from a coordinate with displayed value one. Their positive diagonal entries must be replaced by zero, which subtracts a nonnegative diagonal matrix. This cannot increase the number of positive eigenvalues.

We now induct on the number of summed pairs. Suppose some pairs have already been summed, and let \(\Psi\) denote the resulting weight before the next pair of capacity \(M\ge1\) is summed. Fix a box-valid display \(z\) on the other coordinates, two above their new required total. For \(0\le k\le M\), apply the induction hypothesis to the display \((z,k,M-k)\). The resulting matrix, with the two pair coordinates listed last, is \[ N_k= \begin{pmatrix} V_k&S(k-1)&S(k)\\ S(k-1)^{\mathsf T}&u_{k-1}&u_k\\ S(k)^{\mathsf T}&u_k&u_{k+1} \end{pmatrix}, \tag{14}\] where \[\begin{align*} (V_k)_{ih}&=\Psi(z-e_i-e_h,k,M-k), \\ S(l)_i&=\Psi(z-e_i,l,M-1-l), \\ u_k&=\Psi(z,k-1,M-1-k). \tag{15}\end{align*}\] Every \(N_k\) has at most one positive eigenvalue. As usual, all out-of-box terms are zero. In particular, \(S(-1)=S(M)=0\), and \(u_k=0\) outside \(1\le k\le M-1\). The matrix after summation is \(\sum_{k=0}^M V_k\). We must find one common subspace of codimension at most one on which this sum is nonpositive; simply adding the matrices \(N_k\) would not establish that property.

If \(M=1\), put \(S=S(0)\). After deleting their zero pair axis, \(N_0\) and \(N_1\) have the respective forms \[\begin{pmatrix}V_0&S\\S^{\mathsf T}&0\end{pmatrix}, \qquad \begin{pmatrix}V_1&S\\S^{\mathsf T}&0\end{pmatrix}.\] When \(S\ne0\), the null-axis projection just proved shows that both \(V_0\) and \(V_1\) are nonpositive on \(\{a:a^{\mathsf T}S=0\}\). Their sum therefore has at most one positive eigenvalue. If any displayed coordinate \(z_i\) is positive, then \(S_i=\Psi(z-e_i,0,0)>0\): the profile has the required total and every previously summed pair supplies a positive balanced term. Thus \(S=0\) can occur only when \(z=0\), in which case all removals are invalid and \(V_0=V_1=0\). This proves the width-one case.

Assume henceforth that \(M\ge2\). For each interior index \(k\), \(u_k>0\): the displayed coordinates are box-valid and have the correct total, and any balanced profile on each previously summed pair supplies a positive term in the original positive-factor model.

For larger widths the common subspace is determined by the sum of the one-removal vectors \(S(l)\). Cumulative sums provide auxiliary coordinates whose contributions will telescope. Consider an old-index vector \(a\) satisfying the single linear condition \[a^{\mathsf T}\sum_{l=0}^{M-1}S(l)=0.\] Define \[g_k= \frac{a^{\mathsf T}\sum_{l=0}^{k-1}S(l)}{u_k} \quad(1\le k\le M-1), \qquad g_k=0\quad\text{otherwise}.\] The endpoint condition on \(a\), as well as the cumulative-sum definition at interior indices, gives \[ a^{\mathsf T}S(l)=u_{l+1}g_{l+1}-u_lg_l \qquad(0\le l\le M-1). \tag{16}\] For \(v_k=(a,g_k,-g_k)\), its products under the form \(N_k\) with the first and second new coordinate axes are, respectively, \[u_{k-1}(g_k-g_{k-1}), \qquad u_{k+1}(g_{k+1}-g_k).\] If either of those axes has positive square, applying (10) to that axis and adding the other nonnegative term gives \[ v_k^{\mathsf T}N_kv_k \le u_{k-1}(g_k-g_{k-1})^2+ u_{k+1}(g_k-g_{k+1})^2. \tag{17}\] If both axis squares vanish, their diagonal entries \(u_{k-1},u_{k+1}\) are zero. The endpoint cases \(k=0,M\) have a positive other diagonal because \(M\ge2\); hence in the remaining case \(u_k>0\). The sum of the two axes then has square \(2u_k>0\) and product zero with \(v_k\). Applying (10) to this sum again gives (17), whose right-hand side is now zero. This includes the case \(M=2,k=1\).

Substitute (16) into (17) and expand. The terms involving \(g_kg_{k-1}\) and \(g_kg_{k+1}\) cancel, leaving \[ a^{\mathsf T}V_ka +2u_kg_k^2 -u_{k-1}g_{k-1}^2 -u_{k+1}g_{k+1}^2 \le0. \tag{18}\] Sum this inequality over \(0\le k\le M\). Every interior \(u_kg_k^2\) cancels, and all exterior terms are zero. Consequently \(\sum_kV_k\), which is the desired matrix after summing the next pair, is nonpositive on the kernel of one linear functional. Its number of positive eigenvalues is therefore at most one. This completes the induction.

Finally reflect every coordinate in its box: \(z_i\mapsto m_i-z_i\). A factor on a set \(G\) remains a positive log-concave sequence in the sum on \(G\), with its argument reversed and translated. A balanced pair of capacity \(M\) remains balanced under this reflection, so reflection commutes with balanced summation. The reflected remaining weight is \(\Phi^\vee(z)=\Phi(m-z)\). A display two below the original total becomes a display two above the reflected total, and \[\Phi^\vee(m-z-e_i-e_h)=\Phi(z+e_i+e_h).\] The removal assertion for the reflected model is precisely the addition assertion for the original model. ◻

Proof. Introduce a finite physical interval \([\ell_s,\ell_s+M_s]\) for every retained cell. For small and free cells take \([0,b_s]\), and for a tree cell take \[[\ell_s,\ell_s+M_s]=[-10db_s,10db_s].\] Lemma 2 shows that these tree intervals contain every completion required by the definition of \(h_j\). Represent a physical row-view value as \(\ell_s+x_s\) and a physical column-view value as \(\ell_s+M_s-y_s\), where \(0\le x_s,y_s\le M_s\). The two views agree when \(x_s+y_s=M_s\). Use the full total slice \[\sum_s(x_s+y_s)=\sum_sM_s.\]

For a row or column vertex \(v\), let \(\kappa_v\) be its prescribed margin and write its physical line sum as \[L_v(x,y)= \begin{cases} \sum_{s\ni v}(\ell_s+x_s),&v\text{ is a row},\\ \sum_{s\ni v}(\ell_s+M_s-y_s),&v\text{ is a column}. \end{cases}\] For \(0<\alpha<1\), give each box-valid profile on the full total slice the positive weight \[ \alpha^{\sum_{v\text{ nonroot}}|L_v-\kappa_v|} 2^{-\frac{jA}{H}\left( \sum_{v\text{ root}}|L_v-\kappa_v| +\sum_{t\in\mathcal T} \frac{\mathop{\mathrm{dist}}(\ell_t+x_t,[0,b_t])}{b_t}\right)}. \tag{19}\] Each factor is log-concave in its indicated coordinate sum. Row factors use disjoint groups of \(x\) coordinates, and column factors use disjoint groups of \(y\) coordinates. These two collections are also disjoint from one another. The only additional factors are unary tree factors, each nested in its row group. Thus the entire family is laminar. Letting \(\alpha\downarrow0\) imposes every nonroot equation exactly while retaining the root and tree penalties.

Sum every large-cell pair at balance. The widths of all summed pairs are positive. The remaining total is \(p\). For every small count profile on that slice and every free-cell assignment, the exact nonroot equations have a unique tree completion, and it lies in the chosen intervals by Lemma 2. Therefore, in the equality limit, each free assignment contributes exactly one term, with precisely the root and tree penalty defining \(h_j\); there is no multiplicity from tree coordinates. The removal assertion follows from Lemma 4 and passage to a finite limit. Reflecting all coordinates, including those that are summed, gives the addition assertion by the same lemma. ◻

Proof. Use the finite interval representation and positive weight (19) at \(j=H\), with \(0<\alpha<1\). Sum every cell pair except \(t\) at balance. All retained cells have positive width, including small cells of bound one, so Lemma 4 applies. The remaining required total is \(M_t\). Let \(a_{t;\alpha}(k)\) be the resulting weight of the retained balanced pair with physical value \(k\), for \(\ell_t\le k\le\ell_t+M_t\). It is positive throughout this integer interval: after fixing the retained pair, any balanced choices for all other pairs satisfy the boxes and total slice, and every factor is positive. Exact nonroot equations are not required before taking the limit.

At an interior value \(k\), the retained profile is \[(k-\ell_t,\ \ell_t+M_t-k).\] Adding one to both coordinates gives a box-valid display two above its required total. Lemma 4 applied to the two remaining coordinates gives the matrix \[\begin{pmatrix} a_{t;\alpha}(k-1)&a_{t;\alpha}(k)\\ a_{t;\alpha}(k)&a_{t;\alpha}(k+1) \end{pmatrix}\] with at most one positive eigenvalue. Its positive trace implies a nonpositive determinant, so \[a_{t;\alpha}(k)^2 \ge a_{t;\alpha}(k-1)a_{t;\alpha}(k+1).\] All these marginal masses are positive. Their logarithms therefore have nonincreasing successive differences, which proves global interpolation between any two values in the interval.

Now let \(\alpha\downarrow0\). The sums are finite, and the surviving profiles satisfy every nonroot equation. For each balanced small profile and free assignment those equations have exactly one tree completion, contained in the chosen intervals by Lemma 2. The surviving weight is exactly \(2^{-D}\). Consequently, term by term, \[a_{t;\alpha}(k)\longrightarrow a_t(k).\] Pass the global interpolation inequality to this limit. For positive limiting endpoint masses its right-hand side is positive, giving (21) and ruling out any internal support gap. No inference from adjacent inequalities alone after the limit is needed. ◻

Proof of Proposition 3. Expand \(C(H)\) over balanced small profiles and free integer vectors, giving each assignment mass \(2^{-D}\). The forest equations determine one tree vector for each such assignment. It represents a feasible table exactly when every root deviation is zero and every tree value belongs to its allowed interval. These assignments each have mass one, so \(C(H)\ge Z\ge1\). The total number of assignments is \(\prod_{s\in\mathcal S}(b_s+1)\prod_{e\in\mathcal F}(b_e+1)\le2^K\), and every mass is at most one.

Call an assignment far if a root deviation is nonzero or a tree value has distance at least \(\gamma b_t\) from \([0,b_t]\). A nonzero root deviation is an integer of absolute value at least one. Since \(\gamma<1\) and \(A\gamma\ge4K\), every far assignment has \(D\ge4K\). The total mass of all far assignments is therefore at most \(2^K2^{-4K}=2^{-3K}\le\varepsilon/128\). Because \(C(H)\ge1\), this also bounds its fraction of the total mass.

For each tree cell \(t\), its marginal satisfies \[\sum_{k\in\mathbb Z}a_t(k)=C(H),\qquad 0\le a_t(k)\le2^K,\qquad a_t(0),a_t(b_t)\ge1.\] The endpoint inequalities follow from endpoint attainability after tightening and the unit mass of each feasible table. If \(k<0\) and \(a_t(k)>0\), use (21) from \(k\) toward \(b_t\). For every integer \(0\le r\le\lfloor(b_t-k)/K\rfloor\), writing \(\alpha=r/(b_t-k)\le1/K\), the endpoint cases and interpolation give \[a_t(k+r)\ge a_t(k)^{1-\alpha}a_t(b_t)^\alpha \ge a_t(k)\,2^{-K\alpha}\ge\frac{a_t(k)}2.\] All these integers lie between \(k\) and \(b_t\). Their number is \(\lfloor(b_t-k)/K\rfloor+1\ge b_t/K\), and hence \(a_t(k)/C(H)\le2K/b_t\).

For the other exterior side, let \(k>b_t\) with \(a_t(k)>0\) and interpolate toward zero. Every integer \(0\le r\le\lfloor k/K\rfloor\) satisfies \[a_t(k-r)\ge a_t(k)^{1-r/k}a_t(0)^{r/k} \ge a_t(k)\,2^{-Kr/k}\ge\frac{a_t(k)}2.\] There are \(\lfloor k/K\rfloor+1\ge b_t/K\) such integers, giving the same bound \(a_t(k)/C(H)\le2K/b_t\). The bound also holds when \(a_t(k)=0\).

On either exterior side of \([0,b_t]\), the number of integers at positive distance strictly less than \(\gamma b_t\) is \(\max\{\lceil\gamma b_t\rceil-1,0\}<\gamma b_t\). Consequently the fraction of mass with \(0<\mathop{\mathrm{dist}}(z_t,[0,b_t])<\gamma b_t\) is at most \(4\gamma K\). A union bound over at most \(d\) tree cells bounds all these near violations by \(4d\gamma K=\varepsilon/128\). Every infeasible assignment is far or has such a near tree violation. We conclude that \[\frac{C(H)-Z}{C(H)}\le\frac{\varepsilon}{64}.\] Finally, \(C(H)\le Z/(1-\varepsilon/64)\le(1+\varepsilon/32)Z\) for \(0<\varepsilon<1\), as claimed. ◻

Proof. Fixing inclusions enlarges the set of fixed elements in the quadratic test, and fixing exclusions restricts that test to a principal submatrix. Positivity is retained whenever the residual degree is valid.

We prove the contraction assertion through a symmetric cubic tensor. Suppose \(T_{iuh}\) is positive on triples of distinct indices and zero on repetitions, and every slice \(T_i=(T_{iuh})_{u,h}\) has at most one positive eigenvalue. There are at least three indices. For a vector \(a\) with all entries positive, set \[M=\sum_i a_iT_i.\] Tensor symmetry gives \[a^{\mathsf T}T_i a=(Ma)_i>0, \qquad h^{\mathsf T}T_i a=(Mh)_i.\] The strict inequality holds even with exactly three indices: the two indices other than \(i\) give a strictly positive term. Applying (10) to every slice and then summing with coefficients \(a_i\) yields \[ h^{\mathsf T}Mh \le \sum_i\frac{a_i(Mh)_i^2}{(Ma)_i} =h^{\mathsf T}MD_*^{-1}Mh, \qquad D_*=\operatorname{diag}\left(\frac{(Ma)_i}{a_i}\right). \tag{25}\] Thus the symmetric matrix \(M'=D_*^{-1/2}MD_*^{-1/2}\) satisfies \(M'\preceq(M')^2\). It has the positive eigenvector \(u=D_*^{1/2}a\) with eigenvalue one. Every off-diagonal entry of \(M\), and hence of \(M'\), is strictly positive, because a third distinct index contributes a positive term. The matrix with entries \(M'_{ih}u_h/u_i\) is therefore irreducible and row-stochastic. The maximum principle bounds the absolute values of its real eigenvalues by one and shows that its eigenvalue-one eigenspace consists of the constant vectors. Since \(M'\) is symmetric, eigenvalue one is simple. On the other hand, (25) requires every eigenvalue \(\lambda\) of \(M'\) to satisfy \(\lambda\le\lambda^2\), so a positive eigenvalue must be at least one. There can consequently be only one positive eigenvalue. Positive diagonal congruence gives the same conclusion for \(M\). For nonnegative \(a\), replace it by \(a+\varepsilon\mathbf 1\) and pass to the matrix limit as \(\varepsilon\downarrow0\). This establishes the full-matrix contraction assertion.

Now sum a pair \(\{\alpha,\beta\}\) at occupancy one in a positive weight \(F\) on \(k\)-subsets: \[F^\downarrow(U)=F(U\cup\{\alpha\})+F(U\cup\{\beta\}), \qquad |U|=k-1,\quad U\cap\{\alpha,\beta\}=\varnothing.\] If \(k-1<2\), the desired addition property is vacuous. Otherwise fix \(k-3\) included elements outside the pair. The remaining three-element weights form a tensor \(T\) of the kind just considered. Each slice is an addition matrix of \(F\), with a zero row and column at its fixed index. Contract with the indicator of \(\{\alpha,\beta\}\). Restricting the resulting full matrix to the other indices gives exactly the addition matrix of \(F^\downarrow\). The result is therefore valid. Every valid residual weight is a sum of positive terms, so positivity also persists.

Finally, complementation interchanges fixed inclusions with fixed exclusions and preserves occupancy one in a two-element pair. Applying the addition argument to complement weights proves all the omission assertions. ◻

Proof. The case \(p=1\) is immediate for the original two properties, so consider a quadratic test when it is nonvacuous. For the omission property of \(f\), fix \(p-2\) omitted elements. This leaves a display of \(p+2\) elements from which two must be removed. Group its elements by small-cell row or column coordinate, and write \(n_u\) for the number in group \(u\).

Within a group, all distinct-copy matrix entries are equal, and the diagonal entries are zero. Vectors whose entries sum to zero in each group have nonpositive square: in each group the form is a nonnegative multiple of \(\mathbf 1\mathbf 1^{\mathsf T}-I\). These vectors have no coupling to vectors that are constant within each group. It remains to examine the latter subspace.

Let its value on group \(u\) be \(t_u\). For distinct groups \(u,v\), the \(n_un_v\) ordered-copy multiplicity cancels the two factorial reductions when passing from displayed counts \(n\) to \(n-e_u-e_v\). For a single group \(u\), the multiplicity \(n_u(n_u-1)\) similarly cancels the factorial reduction for two removals. If \(n_u<2\) this term is zero. The resulting quadratic form is exactly \[\frac{\prod_u n_u!}{\prod_s b_s!} \sum_{u,v} h_j(n-e_u-e_v)t_ut_v,\] with zero entries for invalid removals. By Corollary 5, it has at most one positive eigenvalue. Together with the nonpositive group-sum-zero subspace, this proves the omission property of \(f\).

For the addition property of \(\widetilde f\), fix \(p-2\) included elements, with coordinate counts \(r_u\). There are \(n_u=b_u-r_u\) available elements in coordinate group \(u\), where \(b_u=b_s\) for either coordinate of cell \(s\). After adding two elements, the factorial numerator of \(\widetilde f\) is the product of the remaining-capacity factorials. The same group decomposition and the same multiplicity cancellation therefore give, up to a common positive scalar, the form \[\sum_{u,v}h_j(r+e_u+e_v)t_ut_v.\] Invalid additions give zero entries. The addition assertion of Corollary 5 proves that this form has at most one positive eigenvalue. The group-sum-zero subspace again contributes only nonpositive squares. This proves the addition property of \(\widetilde f\).

All \(p\)-subset weights in (22) are strictly positive. The closure assertions now follow from Lemma 7, applied respectively in omission and addition variables. ◻

Proof. Fix the inclusions and exclusions specified by \(\sigma\). For (26), sum every other unassigned pair at occupancy one, leaving only \(i,l\). By Lemma 8, the remaining positive two-element weight has an addition matrix with at most one positive eigenvalue. Restrict its quadratic form to vectors constant on each of the two pairs. The resulting matrix is \[\begin{pmatrix} 2\widetilde c_{li}^{\sigma}&z_\sigma\\ z_\sigma&2\widetilde c_{il}^{\sigma} \end{pmatrix}.\] The diagonal factor two counts the two orders of the elements in a full pair; the off-diagonal sums exactly the transversals. The matrix has positive trace and at most one positive eigenvalue, so its determinant is nonpositive. This proves (26).

For (27), sum every other unassigned pair at occupancy one, leaving the six elements in \(i,l,k\) and a positive weight on their three-element subsets. Form its symmetric cubic tensor, zero on repeated indices. Contract it along the indicator of the two elements of pair \(k\). By the full-matrix assertion of Lemma 7, the resulting matrix has at most one positive eigenvalue even while the two contracted indices are retained. Restrict its form to vectors constant on each pair, and call the resulting three-by-three matrix \(N\), indexed by \(i,l,k\). Its relevant entries are \[ N_{ll}=2\widetilde c_{il}^{\sigma}, \qquad N_{ik}=2\widetilde c_{lk}^{\sigma}, \qquad N_{il}=z_\sigma, \qquad N_{lk}=2\widetilde c_{ik}^{\sigma}. \tag{28}\] For example, in \(N_{ik}\) the full pair \(k\) can contribute either of its elements to the contraction and the other to the matrix index, explaining the factor two. All entries of \(N\) are nonnegative, and \(N_{ll}>0\).

By (10), the Schur complement against the \(l,l\) entry is negative semidefinite. Its two remaining coordinates \(i,k\) therefore satisfy \[\begin{align*} N_{ik} &\le \frac{N_{il}N_{lk}}{N_{ll}} +\sqrt{ \left(\frac{N_{il}^2}{N_{ll}}-N_{ii}\right) \left(\frac{N_{lk}^2}{N_{ll}}-N_{kk}\right)}\\ &\le \frac{2N_{il}N_{lk}}{N_{ll}}. \end{align*}\] The square-root factors are nonnegative by the same Schur complement condition. The second inequality uses \(N_{ii},N_{kk}\ge0\) and the nonnegativity of the off-diagonal entries. Substituting (28) gives (27). ◻

Proof. We seek a signed edge current whose divergence is \(f(S)/s_0\) at states with hole \(P_0\), \(-f(S)/s_1\) at states with hole \(P_1\), and zero at all ordinary-hole states. Orient each edge once, write \(I_{SS'}\) for its signed current, and write \(c_{SS'}\) for its conductance. Such a current satisfies, by summation by parts and Cauchy–Schwarz, \[ \begin{split} (\bar g_0-\bar g_1)^2 &=\left(\sum_{\{S,S'\}} I_{SS'}\bigl(g(S)-g(S')\bigr)\right)^2\\ &\leq \left(\sum_{\{S,S'\}}\frac{I_{SS'}^2}{c_{SS'}}\right) D_{\mathrm{sl}}(g). \end{split} \tag{33}\] It therefore suffices to bound its flow energy by the coefficient in (32).

The local routing step explains the energy quantity we will use. A complete display \(R\) contains the two singleton elements and one chosen element from every ordinary slot. Its one-hole sets \(S_i=F\cup(R\setminus\{i\})\), \(i\in R\), form a clique of exchange edges. For an element \(i\), write \(W_i\) for its slot’s multiplier. Put \(m_i=f(S_i)\). For any coefficients \(h_i\) with \(\sum_i m_i h_i=0\), regard \(m_i h_i\) as the prescribed signed divergence at \(S_i\). Choose a hub \(h_*\) maximizing \(W_i m_i\), and send current \(m_i h_i\) from each nonhub \(S_i\) to the hub. Balance gives the prescribed divergence at the hub as well. Each used edge has conductance \(W_i m_i\) at its nonhub endpoint, so this routing has energy at most \[\sum_{i\ne h_*}\frac{(m_i h_i)^2}{W_i m_i} \leq\sum_{i\in R}\frac{m_i h_i^2}{W_i}.\] We now assign these balanced demands recursively. Their sum over complete displays will have the required source and sink divergences; the recursion will also bound the sum of their routing energies.

Fix an order of the ordinary slots. Initially display the two singleton elements. Expose ordinary slots in that order, branching into two children according to which element of the next slot is added to the display. At a node write \(R\) for its displayed elements, excluding \(F\). For \(i\in R\), let \(m_i\) be the sum of \(f\) over sets that contain \(F\cup(R\setminus\{i\})\), omit the nondisplayed mates in already processed slots, and have single occupancy in every unprocessed ordinary slot. These sets all have size \(p\), and \(m_i>0\). At a complete display this definition reduces to \(m_i=f(S_i)\). Maintain coefficients \(h_i\), interpreted as demand per unit unmultiplied weight, satisfying \[ \sum_{i\in R}m_i h_i=0. \tag{34}\] At the root their values are \(1/s_0\) and \(-1/s_1\) at the elements of \(P_0\) and \(P_1\), respectively. Assign the node the potential \[\Psi(R,h)=\sum_{i\in R}\frac{m_i h_i^2}{W_i}.\] At a leaf this potential bounds the routing energy just computed. Each \(W_i\) is fixed by its slot throughout the recursion. These multipliers enter the energy bound and the eventual hub choice, but not the recursive coefficients or prescribed divergences.

Suppose the next slot \(t\) has elements \(a,b\). For an old hole \(i\in R\), let \(m_i^a,m_i^b\) be its masses in the two children. Then \(m_i^a+m_i^b=m_i\). The mass of the newly introduced hole, at \(a\) in the first child and at \(b\) in the second, is the same positive number \(u\): in either case the entire slot \(t\) is empty. Put \(X=\sum_{i\in R}h_i m_i^a\). Retain every old coefficient unchanged, and give the new hole coefficient \(-X/u\) in the \(a\) child and \(X/u\) in the \(b\) child. Equation (34) holds in both children because \(\sum_i h_i m_i^b=-X\). The sum of their potentials exceeds the parent potential by exactly \[ \frac{2X^2}{uW_t}. \tag{35}\]

We bound these increments using the omission signature. At any node, and for any unprocessed ordinary slot \(t\), define a symmetric matrix \(V_t(R)\) on the displayed elements, with zero diagonal. For distinct \(i,k\in R\), its entry is the sum of \(f\) over configurations with holes at \(i,k\) in the display, double occupancy in slot \(t\), and single occupancy in every other unprocessed slot. Fixed inclusions, exclusions, and previously excluded mates remain in force. All these configurations have size \(p\).

When \(t=\{a,b\}\) is the next slot, \(V_t(R)\) is the old block of \[N=\begin{pmatrix} V_t(R)&(m_i^b)_{i\in R}&(m_i^a)_{i\in R}\\ (m_i^b)_{i\in R}^{\mathsf T}&0&u\\ (m_i^a)_{i\in R}^{\mathsf T}&u&0 \end{pmatrix}.\] This form has at most one positive eigenvalue. To see the precise application, fix the context and exclude the nondisplayed mates of processed slots. Sum all unprocessed ordinary slots other than \(t\) at occupancy one. On the remaining ground set \(R\cup\{a,b\}\) the resulting degree is \(|R|\), so \(N\) is its two-omission matrix. Lemmas 8 and 7 give the asserted signature. In particular, this argument uses the full-domain weight \(f\) even when an entry of \(V_t(R)\) describes multiple empty and full original pairs. No comparison with \(\widetilde f\) is made here.

Extend \(h\) by zero at \(a,b\) and put \(d_{ab}=e_a-e_b\). The vector \(e_a+e_b\) has square \(2u>0\) under \(N\). Both \(h\) and \(d_{ab}\) are orthogonal to it in this form, since (34) holds and the two new diagonal entries are zero. A symmetric form with at most one positive eigenvalue is nonpositive on the form-orthogonal complement of a positive-square vector: another positive-square vector in that complement would span a positive definite plane with the first vector. On the complement, Cauchy–Schwarz for the negative of the form applies. Here \[h^{\mathsf T}N d_{ab}=-2X, \qquad d_{ab}^{\mathsf T}N d_{ab}=-2u, \qquad h^{\mathsf T}Nh=h^{\mathsf T}V_t(R)h.\] Consequently \[ \frac{2X^2}{u}\leq -h^{\mathsf T}V_t(R)h. \tag{36}\]

Fix now a slot \(t\) to be processed at a later level. When a preceding slot is split, the sum of the two child quantities \(h^{\mathsf T}V_t(R)h\) equals the parent quantity. The old entries split additively. A cross entry involving the new hole represents a configuration in which the split slot is empty, so it is identical in the two children. Its contributions cancel because the new coefficients are opposite and all old coefficients are retained. There is no new diagonal contribution. Iterating this identity shows that, immediately before processing \(t\), the sum of these quadratic quantities over the whole level is their value at the root. The root matrix has off-diagonal entry \(v_t\) and zero diagonal, so that value is \(-2v_t/(s_0s_1)\). By (35) and (36), the total potential increase at the level of slot \(t\) is at most \(2v_t/(s_0s_1W_t)\). The root potential is \(1/(s_0W_{P_0})+1/(s_1W_{P_1})\). Thus the sum of all leaf potentials is bounded by the parenthetical coefficient in (32).

Route the prescribed demands at every leaf by the clique construction above. Its energy is at most \(\Psi(R,h)\). Different leaves cannot use the same edge: the union of two distinct endpoints of a leaf edge is exactly \(F\cup R\), and so determines the entire display and its unique sequence of choices. Hence the assembled flow has energy at most the sum of the leaf potentials.

It remains to identify the divergence after summing the leaf flows. A state with a singleton hole has one leaf representation; its divergence is \(f(S)/s_0\) or \(-f(S)/s_1\). A state \(S\) with an ordinary hole at slot \(t\) has exactly two representations, obtained by adjoining either element of \(t\) to \(S\setminus F\). Every other displayed ordinary choice is fixed by \(S\). The two histories agree before processing \(t\), so the same \(X,u\) create opposite coefficients there. Those coefficients remain unchanged at every later branch, regardless of the later masses and new coefficients. At the leaves both masses are exactly \(f(S)\), and their divergences cancel. This reasoning also applies if the state is a hub in either leaf, since its net divergence is still \(m_i h_i\). The assembled flow therefore has the required divergence, and (33) together with the leaf-potential bound proves (32). If \(s=0\), the root is already a complete display and the same clique argument applies directly. ◻

Proof. We decompose the transversal variance along a tree of partial assignments, choosing the next pair as a function of the current assignment. Let \(\sigma\) fix some pairs to specified single choices. For distinct unassigned labels define \[a_{il}= \frac{\widetilde c_{il}^{\sigma}}{z_\sigma} \frac{\widetilde c_{li}}{C}.\] Lemma 10 gives \[ a_{il}a_{li}\leq\frac1{16}, \qquad a_{il}a_{lk}\leq a_{ik} \quad\text{for distinct }i,l,k. \tag{38}\] For the second inequality, use the conditional defect inequality on the first factors and the unconditioned inequality with indices \(k,l,i\) on the second factors. Form a directed graph with arc \(i\to l\) when \(a_{il}>1\). It has no directed two-cycle. A shortest longer directed cycle could be shortened using the second inequality in (38), also a contradiction. Thus this graph has a sink \(k\), for which \(a_{kt}\leq1\) at every other unassigned label \(t\). If only one label remains, choose it as \(k\).

Branch on the two choices in pair \(k\). Apply Lemma 11 with the two elements of \(k\) as singleton slots, both of multiplier one, and with the other unassigned pairs as ordinary slots. Keep \(\sigma\) fixed. A singleton-hole state is a transversal respecting \(\sigma\); an ordinary-hole state at \(t\) has type \(tk\) and multiplier \(W_t=w_{tk}\). The auxiliary doubled-slot mass is exactly \(v_t=c_{kt}^\sigma\). Thus every one-hole state in this application belongs to \(\mathcal X\) with precisely its weight \(\lambda\). The good-multiplier bound, followed by two uses of (24), gives \[\begin{align*} \frac{v_t}{W_t} =\frac{c_{kt}^\sigma}{w_{tk}} &\leq\frac{4c_{kt}^\sigma c_{tk}}{C} \leq\frac{4q^2\widetilde c_{kt}^\sigma \widetilde c_{tk}}{C} \\ &=4q^2z_\sigma a_{kt}\leq4q^2z_\sigma. \tag{39}\end{align*}\] These comparisons involve only actual defect types.

Let \(s_0,s_1\) and \(\bar g_0,\bar g_1\) be the masses and means of the two transversal children, so \(s_0+s_1=z_\sigma\). Their unnormalized between-means variance contribution is \[\frac{s_0s_1}{z_\sigma}(\bar g_0-\bar g_1)^2.\] Let \(\mathfrak D_\sigma(g)\) be the sum in (31) restricted to edges whose two endpoints respect \(\sigma\). The slot energy in this application is a subgraph energy, so it is at most \(\mathfrak D_\sigma(g)\). Multiplying (32) by \(s_0s_1/z_\sigma\) and using (39) yields \[ \frac{s_0s_1}{z_\sigma}(\bar g_0-\bar g_1)^2 \leq (1+8pq^2)\mathfrak D_\sigma(g). \tag{40}\] The first two terms in the transport coefficient contribute exactly \((s_0+s_1)/z_\sigma=1\); the ordinary slots contribute at most \(8pq^2\).

Iterate this branching until every pair is fixed. The conditional variance identity decomposes \(C\mathop{\mathrm{Var}}_\mu(g)\) as the sum of the between-means contributions over the internal nodes. At any depth, two distinct nodes disagree on the choice of the pair fixed at their first divergence. Their restricted state sets are disjoint, even if subsequent pairs were chosen in different orders. Consequently their internal edge sets are disjoint and \[\sum_{\sigma\text{ at a fixed depth}}\mathfrak D_\sigma(g) \leq\mathfrak D(g).\] An edge crossing a fixed-pair choice is internal to neither of the two resulting restrictions; it does not create a duplicate charge. There are \(p\) possible branching depths. Summing (40) proves (37). The conditioning tree and sink choices are used only in this proof. ◻

Proof. Of the four possible joint choices in pairs \(i,l\), choose one whose transversal mass is at least \(C/4\). Denote the selected elements by \(a_i,a_l\) and their mates by \(b_i',b_l'\). In Lemma 11, fix \(a_l\) included and \(b_i'\) excluded, and take \(P_0=\{a_i\}\), \(P_1=\{b_l'\}\). All other pairs are ordinary slots. A hole at \(P_0\) gives the entire defect type \(il\), whereas a hole at \(P_1\) gives the selected conditional transversal class. Thus \[s_0=c_{il},\quad W_{P_0}=w_{il},\qquad s_1\geq C/4,\quad W_{P_1}=1.\] An ordinary hole at \(t\) has type \(tl\), restricted to the choice \(a_i\) in pair \(i\), and has multiplier \(W_t=w_{tl}\). A doubled ordinary slot with both singleton slots empty is a subset of type \(it\), so \(v_t\leq c_{it}\). All one-hole states and their exchange edges are therefore genuine states and edges of the chain, with the same endpoint weights. Their energy is at most \(\mathfrak D(g)\).

The lift comparison and Lemma 10 give, for each ordinary slot \(t\), \[ c_{it}c_{tl} \leq q^2\widetilde c_{it}\widetilde c_{tl} \leq q^2C\widetilde c_{il} \leq q^3C c_{il}. \tag{42}\] The first two terms in the coefficient of (32) are at most \(4/C+4/C\). For its last term, (29) and (42) give \[\frac{2}{s_0s_1}\sum_t\frac{v_t}{W_t} \leq\frac{8}{c_{il}s_1C}\sum_t c_{it}c_{tl} \leq\frac{8pq^3}{s_1} \leq\frac{32pq^3}{C}.\] This proves the first inequality of (41) with \(\bar g'\) the selected conditional mean. The conditioning event has \(\mu\)-probability at least \(1/4\); conditional Cauchy–Schwarz gives \[(\bar g'-\mathbb E_\mu g)^2 \leq \mathbb E_\mu\bigl[(g-\mathbb E_\mu g)^2 \mid\text{selected choices}\bigr] \leq4\mathop{\mathrm{Var}}_\mu(g),\] which proves the second inequality. ◻

Proof. Let \(m=\mathbb E_\mu g\). Lemma 13 and \((a+b)^2\leq2a^2+2b^2\) give \[(\bar g_{il}-m)^2 \leq\frac{2C_{\mathrm d}}{C}\mathfrak D(g) +8\mathop{\mathrm{Var}}_\mu(g).\] Variance is no larger than squared deviation about any fixed constant. Therefore \[\begin{align*} \mathop{\mathrm{Var}}_\pi(\mathcal Qg) &\leq\mathbb E_\pi[(\mathcal Qg-m)^2]\\ &=\pi(\mathcal A)\mathop{\mathrm{Var}}_\mu(g) +\sum_{i\ne l}\pi(\mathcal A_{il})(\bar g_{il}-m)^2\\ &\leq9\mathop{\mathrm{Var}}_\mu(g)+\frac{2C_{\mathrm d}}{C}\mathfrak D(g)\\ &\leq(9C_{\mathrm p}+2C_{\mathrm d})\frac{\mathfrak D(g)}{C}, \end{align*}\] using Proposition 12 in the last step. Finally, (31) and (30) give \(\mathfrak D(g)/C\leq10p^4\mathcal E(g)\). When \(p=1\) the defect sum is empty and \(\mathcal Q=I\); the same inequalities apply. ◻

Proof. Write \(G_c=G-\mathbb E_\pi G\) and \(v=\mathop{\mathrm{Var}}_\pi(G)\). Because \(\mathcal Q\) is an orthogonal projection fixing constants, for every \(g\), \[\begin{align*} |\langle G_c,g\rangle_\pi|^2 &=|\langle G_c,\mathcal Qg-\mathbb E_\pi g\rangle_\pi|^2\\ &\leq v\mathop{\mathrm{Var}}_\pi(\mathcal Qg) \leq K_{\mathrm{obs}}v\mathcal E(g). \end{align*}\] On the mean-zero subspace, \(I-P\) is positive definite and invertible: reversibility makes \(P\) self-adjoint, and finite irreducibility makes its eigenvalue one simple. Take \(g=(I-P)^{-1}G_c\) on this subspace and put \[a=\langle G_c,(I-P)^{-1}G_c\rangle_\pi=\mathcal E(g)\geq0.\] The previous inequality gives \(a^2\leq K_{\mathrm{obs}}va\), and hence \(a\leq K_{\mathrm{obs}}v\), also when \(a=0\).

Laziness puts the spectrum of \(P\) in \([0,1]\): the operator \(2P-I\) is itself a reversible stochastic contraction. Thus the stationary covariances \(c_t=\langle G_c,P^tG_c\rangle_\pi\) are nonnegative, and finite spectral decomposition on the mean-zero subspace gives \[\sum_{t=0}^{\infty}c_t =\langle G_c,(I-P)^{-1}G_c\rangle_\pi=a.\] For a stationary trajectory the mean squared error of the average is \[\frac{Nv+2\sum_{t=1}^{N-1}(N-t)c_t}{N^2} \leq\frac{2a}{N} \leq\frac{2K_{\mathrm{obs}}v}{N}.\] Finally, the law of an entire trajectory started from \(\nu\) is bounded by \(U\) times the corresponding stationary trajectory law: only the initial factor changes in the product of transition probabilities. Applying this domination to the nonnegative squared error proves (45). ◻

Proof. Finite irreducibility ensures finite expected hitting and return times to \(\mathcal A\). Explicitly, from each state choose a finite positive-probability path to \(\mathcal A\). Finiteness of the state space gives a common bound on path length and a positive lower bound on these path probabilities. The Markov property then gives a geometric bound in blocks on the hitting-time tail. Applying this after the first transition also bounds the strictly positive return time. These qualitative bounds justify the harmonic extensions and occupation sums below; no polynomial estimate is assumed at this point.

For a function \(h\) on \(\mathcal A\), let \(\widehat h\) be its harmonic extension \[\widehat h(x)=\mathbb E_x h(S_{T_{\mathcal A}}), \qquad T_{\mathcal A}=\inf\{t\geq0:S_t\in\mathcal A\}.\] Then \(\widehat h=h\) on \(\mathcal A\), \((I-P)\widehat h=0\) off \(\mathcal A\), and \((I-P)\widehat h=(I-P_{\mathrm{tr}})h\) on \(\mathcal A\) by conditioning on the first transition. For harmonic extensions \(\widehat h,\widehat k\) of \(h,k\), it follows that \[ \langle \widehat h,(I-P)\widehat k\rangle_\pi =\frac{C}{\Lambda} \langle h,(I-P_{\mathrm{tr}})k\rangle_\mu. \tag{48}\] Symmetry of the left side proves reversibility of the stochastic kernel \(P_{\mathrm{tr}}\) with respect to \(\mu\), and thus stationarity. Tracing positive-probability paths of \(P\) proves irreducibility. Also \(P_{\mathrm{tr}}(x,x)\geq P(x,x)\geq1/2\).

Let \(\mathcal E_{\mathrm{tr}}(h) =\langle h,(I-P_{\mathrm{tr}})h\rangle_\mu\). Taking \(k=h\) in (48) gives the exact normalization \[\mathfrak D(\widehat h) =2p^2\Lambda\mathcal E(\widehat h) =2p^2C\mathcal E_{\mathrm{tr}}(h).\] Proposition 12 therefore implies \[\mathop{\mathrm{Var}}_\mu(h)\leq2p^2C_{\mathrm p}\mathcal E_{\mathrm{tr}}(h).\] This is the stated inverse-gap bound. The inequality \(2p^2C_{\mathrm p}\leq K_{\mathrm{obs}}\) follows immediately from (43) and \(p\geq1\).

For the pointwise estimate put \(e_x(z)=\mathbf 1_{\{x\}}(z)/\mu(x)-1\). Reversibility and spectral contraction on mean-zero functions give \[\begin{align*} \left|\frac{P_{\mathrm{tr}}^s(x,y)}{\mu(y)}-1\right| &=|\langle e_x,P_{\mathrm{tr}}^s e_y\rangle_\mu|\\ &\leq\exp(-s/K_{\mathrm{obs}}) \sqrt{\bigl(\mu(x)^{-1}-1\bigr) \bigl(\mu(y)^{-1}-1\bigr)}\\ &\leq\mu_{\min}^{-1}\exp(-s/K_{\mathrm{obs}}), \end{align*}\] which proves (46).

To compute the mean return cost, start the underlying chain with law \(\mu\) on \(\mathcal A\) and define the finite occupation measure \[m(z)=\mathbb E_\mu \sum_{t=0}^{T_{\mathcal A}^+-1}\mathbf 1_{\{S_t=z\}}.\] Shifting the sum by one transition removes the initial law and adds the return law. Both are \(\mu\), since the trace is stationary. Thus \(mP=m\). Uniqueness of the stationary probability measure for the finite irreducible chain implies \(m=c\pi\) for some positive constant \(c\). Before the return, the only visit to \(\mathcal A\) is at time zero, so \(m\) restricted to \(\mathcal A\) is exactly \(\mu\). Consequently \(c\pi(\mathcal A)=1\) and \[\mathbb E_\mu T_{\mathcal A}^+ =\sum_zm(z)=\frac{1}{\pi(\mathcal A)}.\] Pointwise domination of the starting law proves (47). Since \(\mu\) is stationary for the trace, \(\nu P_{\mathrm{tr}}^r\leq U\mu\) for every deterministic integer \(r\geq0\). Applying (47) to each of these laws and using the Markov property at return times bounds the expected sum of \(s\) excursion lengths by \(sU/\pi(\mathcal A)\). This last bound is unconditional at the deterministic trace indices; it does not assert domination after conditioning on an arbitrary past event or on meeting a running-time cap.

When \(p=1\), every state is a transversal, \(P_{\mathrm{tr}}=P\), and every return costs exactly one underlying transition. The stated bounds include this case. ◻

Proof. In dimension one, write \(A_i=\int_{S_i}f_i\) for \(i=1,2\); zero source mass makes the conclusion immediate. Let \(x(u),y(u)\) be the increasing quantiles of the two normalized source densities, \(0<u<1\). Away from finitely many subdivision parameters they are continuously differentiable, with \[x'(u)=\frac{A_1}{f_1(x(u))}, \qquad y'(u)=\frac{A_2}{f_2(y(u))}.\] The map \(z(u)=(1-t)x(u)+ty(u)\) is increasing. Its smooth pieces have disjoint images contained in \(S_0\); jumps merely omit nonnegative contributions to the target integral. Change of variables on these pieces, followed by the weighted arithmetic–geometric mean inequality, gives \[\begin{align*} \int_{S_0}f_0 &\ge\int_0^1 f_0(z(u)) \left((1-t)\frac{A_1}{f_1(x(u))} +t\frac{A_2}{f_2(y(u))}\right)\,du\\ &\ge\int_0^1 A_1^{1-t}A_2^t\,du =A_1^{1-t}A_2^t. \end{align*}\] This argument also permits nonnegative piecewise-continuous densities with finitely many zero intervals, provided each nonzero piece is bounded above and bounded away from zero.

For the induction on dimension, fix first coordinates \(x_1,y_1\) of the two sources and put \(z_1=(1-t)x_1+ty_1\). The corresponding slices satisfy the same set inclusion and interpolation hypothesis in one lower dimension. The induction hypothesis therefore gives the one-dimensional interpolation inequality for the three marginal integrals over slices. Subdivide the first-coordinate axis at the finitely many box endpoints. On each resulting interval every slice domain is constant; positivity and continuity on the ambient compact box make each nonzero marginal continuous, bounded, and bounded away from zero there. Thus the one-dimensional argument just proved applies to the marginals. Iterated integration proves the claim. ◻

Proof. Write \(\mu\) for unnormalized integration against \(\varrho_a\) on \(D_0=(0,B)^e\). For a fixed cut, let \(S\) be the union of the open unit bins on the side of smaller continuous mass. Grid hyperplanes have zero mass, so \(\mu(S)\le\mu(D_0)/2\). Set \[t=\frac{1}{4dB},\qquad r=tB=\frac{1}{4d}, \qquad M=(1-t)S+tD_0.\] The set \(M\) is a finite union of open boxes and contains \(S\). Lemma 18, applied with all three functions equal to \(\varrho_a\), gives \[ \mu(M\setminus S)\ge(2^t-1)\mu(S)\ge\frac t2\mu(S). \tag{55}\]

We cover the added mass by neighborhoods of cut faces. Consider a point \(z\in M\setminus S\) off the grid hyperplanes, and choose \(x\in S\), \(y\in D_0\) with \(z=(1-t)x+ty\). The segment from \(x\) to \(z\) has sup-norm length less than \(r\). At some grid-crossing event its entering and exiting bins have different cut membership. If several coordinates cross simultaneously, flip those coordinates one at a time between the entering and exiting bins. All intermediate bins are incident to the crossing point and lie in the cube. At least one consecutive pair belongs to opposite sides of the cut. Its closed common face contains the crossing point, so \(z\) is within sup distance \(r\) of an actual axis-adjacent cut face.

This proves containment, up to the null set of grid hyperplanes, in the union of the radius-\(r\) neighborhoods of the cut faces. It does not charge a multiplicity for the number of incident bins. Disconnectedness of \(S\) causes no change in the argument. The segment stays in the open ambient cube, and intersecting a face neighborhood with that cube only reduces its volume.

Each face neighborhood has volume at most \[2r(1+2r)^{e-1} =\frac{1}{2d}\left(1+\frac{1}{2d}\right)^{e-1}\le1.\] Every point in it is within sup distance \(1+r\) of either adjacent lower corner. The logarithmic Lipschitz bound and \(\varrho_a(v)\le V_a(v)\) therefore bound its density by \(2^{1+r}V_a(v)\le4V_a(v)\) for each of the two adjacent corners separately. Thus, if \(F\) is the sum of \(\min\{V_a(v),V_a(w)\}\) over cut edges, the covering gives \(\mu(M\setminus S)\le4F\).

Let \(m\) be the smaller of the two unnormalized discrete side masses. By (52), \[\mu(S)\ge\frac14\sum_{v:\,v+(0,1)^e\subset S}V_a(v)\ge\frac m4.\] This remains true if the smaller continuous side is the larger discrete side. Combining with (55) yields \(F\ge tm/32\). The directional proposal probability is at least \(1/(8d)\), so the normalized conductance is at least \[\frac{t}{256d}=\frac{1}{1024d^2B}\ge\kappa.\] ◻

Proof. Each output has either \(\lfloor2^k/M\rfloor\) or \(\lceil2^k/M\rceil\) preimages. Summing its deviation from probability \(1/M\) gives a total-variation bound at most \(M2^{-k}\). Computing the displayed integer quotient needs no rejection step. ◻

Proof. Lemma 2 gives \(0\leq D\leq H\). Each summand in \(h_{j+1}\) is therefore between one half and one times the corresponding summand in \(h_j\), proving (59). The factorial factor in \(f_j\) is independent of \(j\). Summing the same inequalities over any type gives \[\frac12\leq \frac{C(j+1)}{C(j)}\leq 1, \qquad \frac12\leq \frac{c_{il}(j+1)}{c_{il}(j)}\leq 1.\] These bounds imply the multiplier comparison and \(\mu_j\leq 2\mu_{j+1}\).

On a transversal the factorial factor is \(\prod_s\binom{b_s}{x_s}^{-1}\geq 2^{-p}\). Also \(h_j(x,y)\geq M_f2^{-H}\), while \[C(j)\leq M_f\prod_{s\ {\rm small}}(b_s+1) \leq M_f2^K.\] Their quotient proves (60).

At parameter zero, \(h_0=M_f\), so \[ C(0)=M_f\prod_{s\ {\rm small}}(b_s+1). \tag{61}\] We give an explicit formula for every defect total. Fix distinct pair labels \(i,l\), with \(i\) empty and \(l\) full. For each small cell \(s\), let \[u_s=\mathbf 1_{\{i\text{ belongs to }s\}},\qquad v_s=\mathbf 1_{\{l\text{ belongs to }s\}},\qquad n_s=b_s-u_s-v_s.\] There are \(n_s\) singly occupied pairs left in that cell. If exactly \(k\) of these use their row elements, then \(x_s=k+v_s\), \(y_s=n_s-k+v_s\), with multiplicity \(\binom{n_s}{k}\). Hence \[ c_{il}(0) =M_f\prod_{s\ {\rm small}} \left[ \frac{1}{b_s!} \sum_{k=0}^{n_s} \binom{n_s}{k}(k+v_s)!(n_s-k+v_s)! \right]. \tag{62}\] This includes the case in which \(i,l\) lie in the same cell: then \(u_s=v_s=1\) and \(n_s=b_s-2\geq 0\). All factorial arguments are at most \(p\), and all sums have at most \(p+1\) terms. Using the common denominator \(b_s!\) within each bracket, the numerators and denominators in (62) have \(O(L+p\log(p+1))\) bits. There are at most \(p(p-1)\) such totals. The multipliers \[w_{il}^{(0)}=\frac{C(0)}{c_{il}(0)}\] are therefore positive rationals of polynomial bit length and are computable by bounded integer arithmetic. In fact the local bracket in (62) equals \(b_s+1\), \(1\), \((b_s+1)(b_s+2)/6\), or \((b_s+1)/6\), according as the cell contains neither designated pair, only the hole, only the full pair, or both. If \(s(i)\) denotes the cell containing pair \(i\), the equivalent initializer is \[w_{il}^{(0)} = \begin{cases} 6,&s(i)=s(l),\\[2mm] \displaystyle\frac{6(b_{s(i)}+1)}{b_{s(l)}+2}, &s(i)\ne s(l). \end{cases}\]

Finally, the asserted sampler assigns any particular transversal probability \[\prod_{s\ {\rm small}} \frac{1}{(b_s+1)\binom{b_s}{x_s}} =\frac{f_0(S)}{C(0)}.\] This proves its distribution. The finite-choice description will be implemented with bounded fair-bit draws below. ◻

Proof. We make the conditioning in the argument explicit. Let \(\mathcal F_j\) be the sigma-field generated by the completed trajectories, transition decisions, and counts of phases before \(j\) in the capped reference experiment. The stored multipliers and the event that all these earlier phases were successful are \(\mathcal F_j\)-measurable. Fix a past history on that event. The multipliers \(w^{(0)},\ldots,w^{(j)}\) are now fixed and good; this will follow inductively from the update calculation below. The current phase uses independent fresh randomness.

For analysis of this one phase, define a virtual experiment that continues its restart without a transition cap, and then takes its \(N_{\rm av}\) observations using fresh randomness. Write \(M=H+p+K\). Lemma 16 and (60) imply that, from any starting transversal, a stage of \(\tau\) trace steps has pointwise relative error at most \[2^M\exp(-\tau/K_{\rm obs}) =2^M\exp(-2(M+5))<1.\] Its endpoint law is consequently at most \(2\mu_a\). At the entrance to stage \(a=1\), the law is \(\mu_0\leq 2\mu_1\). At every later stage it is at most \(2\mu_{a-1}\leq 4\mu_a\). Invariance of the trace law preserves the bound \(4\mu_a\) throughout that stage.

For good multipliers, \(\pi(\mathcal A)\geq 1/(5p^2)\). The warm return-cost bound of Lemma 16 therefore bounds the expected number of underlying transitions in each trace step by \(20p^2\). The virtual restart uses at most \(H\tau\) trace steps, so its expected total cost is at most \(20p^2H\tau\). Markov’s inequality gives \[ \mathbb P\{\text{virtual restart cost}>B_{\rm ret} \mid\mathcal F_j\} \leq \frac{H}{100(H+1)^2} \leq \frac{1}{100(H+1)}. \tag{68}\] For \(j=0\), the cost is zero and the same upper bound holds.

The virtual restart endpoint is at most \(2\mu_j\), including \(j=0\). Since \(\mu_j\) is the conditional law of the current stationary distribution \(\pi\) on \(\mathcal A\), this endpoint law is at most \(10p^2\pi\) on the full state space. Each type indicator and \(G_j\) is fixed by the projection \(\mathcal Q\) of Section 5. They take values in \([0,1]\). Their stationary means \(p_T,u\), given by (63), are at least \(1/(20p^2)\): this is the type probability bound for defect types, while \(p_0\geq 1/(5p^2)\) and \(C(j+1)/C(j)\geq 1/2\).

By Lemma 15, each empirical mean in the virtual observation trajectory has mean squared error about its stationary mean at most \[\frac{20p^2K_{\rm obs}}{N_{\rm av}}.\] There are \(p(p-1)+2\leq 2p^2\) observables. Markov’s inequality and a union bound therefore give \[ \begin{split} &\mathbb P\{\text{some virtual empirical mean has relative error greater than }\eta \mid\mathcal F_j\}\\ &\hspace{12mm}\leq \frac{16000p^8K_{\rm obs}}{N_{\rm av}\eta^2} \leq\frac{1}{100(H+1)}. \end{split} \tag{69}\] These bounds concern the virtual, uncapped current phase. Whenever its restart cost is at most \(B_{\rm ret}\), it agrees with the actual capped phase. Thus failure of the capped phase is contained in the union of the two virtual failure events in (68) and (69). In particular, we never condition the endpoint law on surviving the cap.

It remains to check that empirical success maintains the induction and controls the output. Because \(\eta<1/4\), empirical success makes every type count positive. By (63), the exact ratio \(w_{il}^{(j)}p_0/p_{il}\) is the current ideal multiplier \(C(j)/c_{il}(j)\). The relative errors in \(\widehat p_0,\widehat p_{il}\) change this value by a factor between \((1-\eta)/(1+\eta)\) and its reciprocal, both lying in \([1/2,2]\). Lemma 21 changes the ideal multiplier by at most another factor two at the next parameter. Equation (66) therefore satisfies (29) for \(j+1\). The update estimates the current ideal multiplier directly; its error does not multiply the earlier error in \(w^{(j)}\).

The same empirical bounds, and \(u/p_0=C(j+1)/C(j)\), give \[\left|\log\frac{\widehat R_j}{C(j+1)/C(j)}\right| \leq 4\eta.\] Initialization is good by Lemma 21. For every successful fixed past, the conditional probability of a current failure is at most \(2/[100(H+1)]\). Summing the probabilities of the first failing phase gives total failure probability at most \[\frac{2H}{100(H+1)}<\frac1{50}.\] On the complementary event, the ratio product telescopes and its logarithmic errors sum to (67). ◻

Proof. We first bound the number of outer random actions. Let \(s_{\rm sm}\) be the number of positive small cells, so \(s_{\rm sm}\leq\min(p,d)\), and put \[T_{\max}=H(B_{\rm ret}+N_{\rm av}).\] This bounds all underlying transitions in the capped run. Each transition needs at most two weight evaluations, four outer draws (a hold coin, two element choices, and an acceptance threshold), and one transition count. Each of at most \(HN_{\rm av}\) observations needs at most two additional weight evaluations. Initial sampling needs at most \(2s_{\rm sm}\) outer draws per phase. Consequently \[ \begin{split} &\#\{\text{evaluation calls, outer draws, and transitions}\}\\ &\quad\leq 7T_{\max}+2HN_{\rm av}+2Hs_{\rm sm}\\ &\quad\leq 9H(B_{\rm ret}+N_{\rm av})+2H(p+d)<J_*. \end{split} \tag{71}\] A visited state has a single type, whose counter is incremented. There is no separate sampling for each defect type. Initializing the \(p(p-1)\) counters and computing their updates are additional deterministic polynomial computations.

For the coupling, expose the completed joint history of both processes immediately before each requested evaluation or draw. The event that the processes have matched so far, and the current evaluation input, are measurable in this history. A new evaluation uses a fresh bit stream independent of that history. Its conditional failure probability is therefore at most \(\xi\), uniformly over the requested profile. This conclusion remains valid after earlier matching and accuracy events, because they concern only already exposed randomness.

Before a discrepancy, both runs have the same state and stored multipliers. Couple their initial and proposal draws at total variation cost at most \(\xi\) per finite choice. Conditional on matching proposals and accurate evaluations, let \(r\) be the reference acceptance ratio before clipping and \(r'\) the computed ratio. The exact factorial and multiplier factors are the same in both runs, and hence \[\frac{1-\xi}{1+\xi}\leq\frac{r'}r \leq\frac{1+\xi}{1-\xi}.\] It follows, regardless of the magnitude or quality of the multipliers, that \[\big|\min(1,r')-\min(1,r)\big| \leq \frac{2\xi}{1-\xi}<4\xi.\] The dyadic threshold adds at most \(\xi\) to this absolute probability difference. To realize a common-uniform coupling, let \(Y\) be the actual fresh uniform \(k\)-bit integer used for the acceptance decision, and write its dyadic threshold as \(m/2^k\). In the proof alone, introduce \(V\) uniform on \([0,1)\), independent of \(Y\), the completed joint past, and the current weight evaluations. Then \(U=(Y+V)/2^k\) is uniform on \([0,1)\), and the implemented test \(Y<m\) is exactly \(U<m/2^k\). Use \(U<\min(1,r)\) for the reference decision. Their mismatch probability is the absolute difference of these thresholds, with the bound just obtained. The auxiliary variable \(V\) is never sampled by the algorithm.

The coupling preserves the reference transition marginal conditional on the completed joint past. We do not condition the reference process on the event that the entire coupling eventually succeeds. Matching paths have exactly the same integer type counts, and the update (66) depends only on those counts. Thus their stored multipliers remain exactly equal, even though their observations of \(G_j\) need not be equal. Trace return times and cap decisions are functions of the matched state paths, so they also agree. A union bound over (71), charging evaluation failures and draw or acceptance discrepancies, is at most \(10J_*\xi\). On the remaining event, each positive observed weight ratio has logarithmic relative error at most \(4\xi\). Zero observations are zero in both runs.

We next prove the unconditional resource bound. Since all input cells are listed explicitly and the parameters are included in the input length, \(d,K=O(L)\). The definitions in (2) give, for example, \[A=O(L^3\varepsilon^{-1}),\quad B=O(L^5\varepsilon^{-1}),\quad W=O(L^6\varepsilon^{-1}),\quad H=O(L^{11}\varepsilon^{-2}),\quad p\leq dW.\] All quantities in (64) and (70), including \(\xi^{-1}\), are therefore bounded by fixed polynomials in \(L,\varepsilon^{-1}\). Their rational encodings have polynomial length. The state can be stored using \(2p\) membership bits or \(p\) element labels; the small counts and state type can be recovered by bounded scans.

There is also a uniform size bound for stored multipliers on unsuccessful histories. Let \(B_0=O(L+p\log(p+1))\) bound the initial numerator and denominator lengths obtained from (62). On every nonaborting history, \[w_{il}^{(a)} =w_{il}^{(0)} \prod_{r=0}^{a-1}\frac{n_0^{(r)}}{n_{il}^{(r)}}, \qquad 1\leq n_0^{(r)},n_{il}^{(r)}\leq N_{\rm av}.\] Thus, even without fraction reduction, its numerator and denominator each have at most \[ B_0+H\left\lceil\log_2(N_{\rm av}+1)\right\rceil \tag{72}\] bits, up to a fixed additive constant. A zero count causes an abort before any such division. This bound does not assume good multipliers or accurate weight calls.

Proposition 17 supplies a deterministic polynomial bound on the work and output length of each evaluation, including its statistically unsuccessful executions. More explicitly, its ratio averages always lie in \([1/2,1]\) and its rounded correction average always lies in \([1/16,8]\), so every call at parameter \(j\) returns a number in \[[\,M_f2^{-j}/16,\ 8M_f\,].\] Its bounded dyadic precision and bounded numbers of rational operations give a polynomial representation length as well. The inputs of this subroutine are \(j\), a valid small-count profile, and the fixed tolerances; multiplier values are not subroutine inputs. Multiplication by the exact factorial factor adds only \(O(p\log(p+1))\) bits. Combining this bound with (72) proves that every Metropolis ratio and threshold comparison has polynomial-sized operands.

For the output arithmetic, let \(B_f\) be an unconditional polynomial bound on the lengths of evaluated \(f\)-weights. Each observation ratio has \(O(B_f)\)-bit numerator and denominator. Adding \(N_{\rm av}\) such rationals using their product as a common denominator requires \(O(N_{\rm av}B_f+\log(N_{\rm av}+1))\) bits. Dividing by a nonzero empirical type probability adds only \(O(\log(N_{\rm av}+1))\) bits. The product of the \(H\) phase estimates and \(C(0)\) therefore has polynomial bit length. Ordinary integer arithmetic on these bounded operands, including the output operation, has polynomial cost.

Finally, every outer loop has its displayed deterministic cap, and the evaluation subroutine itself has bounded loops and finite bit draws. Initialization and counter updates add at most polynomially many operations on the bounded integers just described. No part of this resource argument conditions on empirical accuracy, on successful coupling, or on survival of a restart. An abort outputs the rational zero; otherwise all estimates are positive rationals. This proves the claim on every execution. ◻

Proof of Theorem 1. For an infeasible input the preliminary deterministic test returns zero on every execution, as required. Suppose that the input is feasible.

First let \(p\geq 1\). Combine Proposition 22 with Lemma 23. Except on an event of probability at most \(1/50+10J_*\xi\), there is no abort, reference and implemented paths agree, and every positive observation differs from its reference counterpart by a factor between \(\exp(-4\xi)\) and \(\exp(4\xi)\). The same bounds hold for sums of these positive observations. Since type counts agree exactly, each implemented ratio estimate differs from its reference ratio by at most that same logarithmic amount. The implemented output \(\widehat Z\) consequently satisfies \[ \left|\log\frac{\widehat Z}{C(H)}\right| \leq H(4\eta+4\xi)\leq\frac{\varepsilon}{16}. \tag{73}\] The failure bound is less than \(1/4\), since \(10J_*\xi=\eta/100\).

Proposition 3 gives \[Z\leq C(H)\leq (1+\varepsilon/32)Z.\] Together with (73), this implies the desired relative inequalities. Indeed, \(e^{-\varepsilon/16}\geq 1-\varepsilon/16\), and for \(0<\varepsilon<1\), \[e^{\varepsilon/16}(1+\varepsilon/32) \leq (1+\varepsilon/8)(1+\varepsilon/32) \leq 1+\varepsilon.\] Thus a single implemented run succeeds with probability greater than \(3/4\).

The case \(p=1\) is already included in this argument. The enlarged state space then consists of the two transversals, the defect-type family and multiplier updates are empty, and \(\pi(\mathcal A)=1\). Only the type-zero indicator and \(G_j\) are observed. All denominators and time bounds used above remain defined.

If \(p=0\), there is a single small-count profile and \(C(H)=h_H(\varnothing)\). The call specified at the start of this section returns a positive rational satisfying \[(1-\varepsilon/32)C(H) \leq \widehat Z \leq (1+\varepsilon/32)C(H)\] with probability at least \(15/16\). The contamination bound again places this interval inside \([(1-\varepsilon)Z,(1+\varepsilon)Z]\). The evaluation procedure covers zero free coordinates as well, in which case its sum and bin space each have one element. This branch invokes none of the \(p\)-dependent chain parameters and has the same required polynomial bit bound.

It remains to obtain the requested failure probability. Put \[s=\left\lceil\log_2(\delta^{-1})\right\rceil,\qquad R=10s+1,\] run the appropriate constant-success algorithm independently \(R\) times, and return the median of its nonnegative rational outputs. Let \(F\) be the number of runs outside the desired relative interval. Independence and the single-run failure bound \(1/4\) give \[\mathbb E\,2^F\leq(5/4)^R.\] A bad median requires at least half the runs to fail, so \[\mathbb P\{\text{bad median}\} \leq \left(\frac{5}{4\sqrt2}\right)^{10s+1} \leq 2^{-s}\leq\delta.\] The middle inequality follows, for example, from \((5/(4\sqrt2))^{10}<1/2\).

Lemma 23, or Proposition 17 for \(p=0\), bounds the work and output length of every run by one fixed polynomial in \(L,\varepsilon^{-1}\). The number of repetitions is \(O(\log(\delta^{-1}))\); exact comparisons and median selection on their polynomial-length rational outputs also have polynomial bit cost. Ceilings of binary logarithms used for the parameters and bit counts are computable by integer shifts and comparisons. All randomness in the implemented procedure consists of independent unbiased bits. Partition functions, defect totals away from parameter zero, proof-only conditioning trees, and transport flows are never queried or enumerated. The only weight evaluation used is the bounded procedure proved in Proposition 17. This establishes a uniform FPRAS with the stated bound on every execution. ◻