Proof. When \(E=\varnothing\), all assertions are immediate, so assume \(n\geq1\). Submodularity implies decreasing marginal increments: if \(C\subseteq D\) and \(j\notin D\), then \(f(C\cup\{j\})-f(C)\geq f(D\cup\{j\})-f(D)\). Apply this inequality to the elements of any \(A\) in their \(\pi\)-order. The increments defining \(b(A)\) are no greater than those along the induced chain in \(A\), and hence \(b(A)\leq f(A)\). Also \(b(E)=f(E)\). Summation by parts gives, for every \(x\in B(f)\), \[w\cdot x=w_{\pi(n)}f(E) +\sum_{k=1}^{n-1}(w_{\pi(k)}-w_{\pi(k+1)})x(A_k).\] All coefficients in the sum are nonnegative, and \(b\) attains equality in each of the resulting upper bounds. This proves the first assertion and, in particular, nonemptiness of \(B(f)\).

The displayed support-function formula is additive in \(f\). Since nonempty compact convex sets are determined by their support functions, it proves the Minkowski-sum identity. Translation follows directly from the inequalities. For reflection, the equation \(x(E)=f(E)\) converts \(-x(A)\leq f(E\setminus A)-f(E)\) into the inequality on \(E\setminus A\) for \(x\). The reflected function is normalized and submodular.

For the projection identity, containment in \(B(\bar f)\) follows from the inequalities on unions of parts. Conversely, maximize a linear functional on the projected coordinates. Its lift to \(\mathbb R^E\) is constant on each part. In the greedy formula, place the parts in decreasing order of these constants and place each part’s elements consecutively. The increments telescope to the greedy formula for \(\bar f\). The two projected sets thus have the same support function.

Finally, \(q_{ab}\) is the cut function of a single edge and is submodular, as is checked from its four possible membership patterns on \(\{a,b\}\). Its base inequalities force every other coordinate to be zero, force \(x_a+x_b=0\), and give \(|x_a|\leq t\). This proves the last assertion. ◻

Proof. Hereditary closure is immediate. Let \(I,J\) be independent copy sets with occupancy vectors \(z,z'\) and \(|I|<|J|\). If no element of \(J\setminus I\) can be added to \(I\), then, for every coordinate \(j\) with \(z'_j>z_j\), some set \(A_j\) containing \(j\) is tight for \(z\). Indeed, failure of the increment \(z+e_j\) yields such a set because both its slack and its rank are integral. Tight sets are closed under union and intersection: submodularity and modularity give \[r(A)+r(B)=z(A)+z(B)=z(A\cup B)+z(A\cap B) \leq r(A\cup B)+r(A\cap B)\leq r(A)+r(B).\] Their union \(A\) is therefore tight. On \(E\setminus A\) we have \(z'_j\leq z_j\), whereas \(z'(A)\leq r(A)=z(A)\). This contradicts \(|J|>|I|\) and proves augmentation.

Every independent subprofile \(z\leq v\) has \(z(E)\leq r(A)+v(E\setminus A)\) for every \(A\). Choose a maximal independent subprofile of \(v\). Each coordinate where \(z_j<v_j\) is blocked by a tight set containing \(j\). The union \(A\) of these sets is tight, and \(z=v\) outside \(A\). Thus \(z(E)=r(A)+v(E\setminus A)\), proving equality in (4). If no coordinate is blocked, take \(A=\varnothing\). ◻

Proof. We first establish the structure of the tight constraint normals. For a fixed rank system at \(y\in B(f)\), the tight sets are closed under union and intersection by the calculation in the preceding proof. Choose a maximal strictly increasing chain of tight sets from \(\varnothing\) to \(E\). No tight set can cut a difference between successive members of this chain: otherwise intersecting that set with the upper member and adjoining the lower member inserts another tight set. Every tight-set indicator is therefore a sum of these difference indicators. In particular, the chain indicators span all tight rank normals.

A second version preserves nonnegative coefficients. Any nonnegative combination of tight-set indicators can be expressed as a nonnegative combination of indicators from a chain. To see this, keep the resulting vector and the total coefficient fixed, allowing a coefficient on the empty set, and maximize the sum of the coefficients times \(|A|^2\). The feasible coefficient set is compact. Two incomparable sets with positive coefficients can be replaced, with the smaller coefficient, by their union and intersection. The vector and total coefficient are unchanged, while the maximized quantity increases by \(2|A\setminus B|\,|B\setminus A|\) times that coefficient. Thus no such pair remains. Signed multiples of the total equation can be kept separately.

The matrix formed by the indicators of two chains is totally unimodular. More generally this holds for two laminar families, and therefore for a chain and a partition. We apply Ghouila-Houri’s row-signing criterion (Ghouila-Houri 1964, II, Section 3, fundamental theorem). For any selection of rows from the first family, alternate signs along nested selected sets, starting with \(+1\) on the maximal sets. In any column their sum is either \(0\) or \(1\). Start with \(-1\) in the second family, obtaining \(0\) or \(-1\). Their combined sum is in \(\{-1,0,1\}\). Coordinate rows may be added: choose their signs separately in each column to retain this bound. Negating rows or adding signed copies also preserves total unimodularity. Thus the same conclusion holds with either orientation of equality normals and with coordinate bounds.

At a vertex, the tight normals span \(\mathbb R^E\). Replace the tight rank rows by their chain spans, retain the partition and coordinate rows, and choose \(n\) independent rows. Their square matrix is unimodular. With integral right sides its unique solution is integral, proving the first assertion.

For the distance estimate, let \(y\in Q\) minimize \(\|x-y\|_\infty\) and write \(t=\|x-y\|_\infty\). If \(t=0\) there is nothing to prove. The optimality condition for this convex minimization supplies a normal \(g\) to \(Q\) at \(y\) satisfying \[\|g\|_1=1,\qquad g\cdot(x-y)=t.\] Express \(g\) as a nonnegative combination of the active inequality normals and the two orientations of active equality normals. Uncross the rank contributions separately as above. The remaining normals belong to a totally unimodular matrix. A conic representation can be chosen with linearly independent normals, say \(g=\sum_{k=1}^m\mu_k a_k\) with \(m\leq n\) and \(\mu_k\geq0\). Choose \(m\) columns giving a nonsingular square minor of the row matrix. That minor has determinant \(\pm1\) and every cofactor is \(0\) or \(\pm1\). Solving for the coefficients gives \(\mu_k\leq\|g\|_1=1\). Each active oriented row satisfies \(a_k\cdot(x-y)\leq b\), so \[t=\sum_{k=1}^m\mu_k a_k\cdot(x-y)\leq nb.\] This stronger estimate implies (5).

For the last assertion, the cube constraint is \(y_j\leq a_j+l\) and \(-y_j\leq-a_j+l\). Every vertex of the constrained system has a basis selected by the same chain-span argument. Its basis matrix is unimodular and its right side has the form \(b_0+l b_1\) with \(b_1\) integral. Thus that vertex depends affinely on \(l\), with integral derivative wherever the basis is feasible. There are only finitely many possible bases. Optimizing \(F\) consequently gives a piecewise affine function whose slopes are integers. Inclusion of cubes gives monotonicity; convex combinations of feasible points for radii \(l_1,l_2\) give concavity. Continuity on \((0,\infty)\) follows from finite concavity, and at zero from \(|F(y)-F(a)|\leq\|\nabla F\|_1l\). Boundedness of \(Q\) gives eventual equality with its unrestricted maximum.

If \(\phi(L)<\max_QF\), concavity and monotonicity exclude a zero-slope interval before \(L\). Every preceding affine piece then has slope at least one, so \(\phi(L)\geq\phi(0)+L\geq L\) when \(F\geq0\) on \(Q\). This proves the stated consequence. ◻

Proof. Start from a vertex \(v_0\) obtained by linear optimization. Given vertices whose affine span has direction space \(L\), optimize both signs of a rational basis of \(L^\perp\). Either every optimum equals its value at \(v_0\), proving that \(Q\) lies in the current span, or an optimal vertex extends the span. After at most \(n\) extensions this gives \(d+1\) affinely independent vertices, where \(d=\dim Q\). For \(d=0\), take \(c=v_0\) and stop.

Choose a rational coordinate projection that is one-to-one on the affine hull. For the current simplex \(v_0,\ldots,v_d\), let \(\lambda_0,\ldots,\lambda_d\) be its affine barycentric-coordinate functions on that hull. Optimize both signs of each \(\lambda_j\) over \(Q\). If some value has absolute value greater than two, replace \(v_j\) by an attaining vertex. The absolute determinant of the simplex in the fixed coordinate projection is multiplied by \(|\lambda_j|>2\).

All vertices of a well-described rational polytope have polynomial encoding length (Grötschel et al. 1988, Lemma 6.2.4). Consequently every nonzero simplex determinant encountered lies between \(2^{-B}\) and \(2^B\) for a polynomially bounded \(B\). There are at most \(2B+1\) replacements. Determinants, barycentric functions, objectives, and returned vertices throughout the procedure have polynomial encoding length, so the entire construction has polynomial cost.

At termination, \(|\lambda_j(x)|\leq2\) for every \(x\in Q\) and every \(j\). Set \(c=(d+1)^{-1}\sum_{j=0}^d v_j\). If \(F\geq0\) on \(Q\), then \(F(v_j)\geq0\), and for every \(x\in Q\), \[F(x)=\sum_{j=0}^d\lambda_j(x)F(v_j) \leq2\sum_{j=0}^dF(v_j)=2(d+1)F(c).\] This implies (6). ◻

Proof. Fixing coordinates restricts each test to a principal submatrix of the original test. For summation it suffices to remove one pair at a time. Suppose earlier pairs have been summed, giving a positive weight \(\Psi\), and the next pair has capacity \(M\). Fix a box-valid display \(z\) on the other coordinates, two above their required total after this pair is summed. For \(0\le k\le M\), the removal matrix at \((z,k,M-k)\) 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{10}\] where \[\begin{align*} (V_k)_{ij}&=\Psi(z-e_i-e_j,k,M-k),\\ S(l)_i&=\Psi(z-e_i,l,M-1-l),\\ u_k&=\Psi(z,k-1,M-1-k). \end{align*}\] Each \(N_k\) has at most one positive eigenvalue by induction. Out-of-box terms are zero, so \(S(-1)=S(M)=0\) and \(u_k=0\) unless \(1\le k\le M-1\). The matrix we must control is \(\sum_{k=0}^M V_k\). We will find one common subspace of codimension at most one on which its quadratic form is nonpositive.

When \(M=1\), put \(S=S(0)\). After discarding a zero axis, the two matrices in (10) are \[\begin{pmatrix}V_0&S\\S^{\mathsf T}&0\end{pmatrix}, \qquad \begin{pmatrix}V_1&S\\S^{\mathsf T}&0\end{pmatrix}.\] If \(S\ne0\), the null-axis form of (9) makes both \(V_0\) and \(V_1\) nonpositive on \(\{a:a^{\mathsf T}S=0\}\). If some \(z_i>0\), positivity gives \(S_i=\Psi(z-e_i,0,0)>0\). Thus \(S=0\) implies \(z=0\), and then both \(V_k\) are zero because all removals are invalid. This proves the assertion for \(M=1\).

Let \(M\ge2\). Positivity on the full slice gives \(u_k>0\) for \(1\le k\le M-1\). Take a vector \(a\) on the old coordinates with \[a^{\mathsf T}\sum_{l=0}^{M-1}S(l)=0,\] and 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 definition and the condition on \(a\) give, including the endpoints, \[ a^{\mathsf T}S(l)=u_{l+1}g_{l+1}-u_lg_l \qquad(0\le l\le M-1). \tag{11}\] For \(v_k=(a,g_k,-g_k)\), its products under the form \(N_k\) with the two new coordinate axes are \[u_{k-1}(g_k-g_{k-1}),\qquad u_{k+1}(g_{k+1}-g_k),\] respectively. If at least one axis has positive square, (9) applied to that axis bounds \(v_k^{\mathsf T}N_kv_k\) by its corresponding term in \[ 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{12}\] Adding the other, nonnegative term preserves the bound. If both axis squares vanish, \(u_{k-1}=u_{k+1}=0\). At \(k=0\) or \(M\) the other neighboring \(u\) is positive, so this case is interior and \(u_k>0\). The sum of the two axes then has square \(2u_k>0\) and product zero with \(v_k\). Applying (9) to that sum proves (12), with right-hand side zero.

Expanding (12) and substituting (11) cancels the mixed terms and gives \[a^{\mathsf T}V_ka+2u_kg_k^2 -u_{k-1}g_{k-1}^2-u_{k+1}g_{k+1}^2\le0.\] Summing over \(0\le k\le M\) cancels every \(u_kg_k^2\) term. Hence \(\sum_kV_k\) is nonpositive on the kernel of the single linear functional \(a\mapsto a^{\mathsf T}\sum_lS(l)\), as required. Every remaining box-valid profile has positive weight because any balanced choices of the summed pairs supply a positive summand. This completes the removal induction.

For addition, reflect all coordinates in their boxes, \(z_i\mapsto m_i-z_i\). This interchanges the two signatures. It preserves balance and commutes with the balanced sum, so the removal result for the reflected weight gives the addition result. ◻

Proof. First take the increasing orientation and an addition test. Realize the displayed \(v\) by a set \(S\) in the expansion matroid, and assign two distinct spare copies to each retained count coordinate, with these assignments disjoint even when several count coordinates feed the same physical coordinate. Contract \(S\); equivalently, contract a basis of \(S\) and delete its remaining loops. A new copy increases rank exactly when it is a nonloop in this contraction. Two individually rank-increasing copies increase rank by only one precisely when they are parallel, meaning that their two-element set has rank one. In every other case their rank increments add.

The affine terms in the exponent of (13) cancel in (14). Thus, when both steps are valid, \(Q_{ij}\) is \(\exp(-2H)\) if their two nonloop copies are parallel, and is \(1\) otherwise. For a repeated step we use two distinct copies from that count coordinate. Copies from one physical coordinate are interchangeable by matroid automorphisms fixing \(S\). If the representative of one count coordinate is parallel to that of another, exchange the first representative with its second copy while fixing the other representative. This shows that the second copy is parallel to the other representative and hence to the first. It follows that each nontrivial parallel class of retained count indices has normalized entry \(\exp(-2H)\) throughout its block, including every valid repeated-step diagonal. A single index whose two copies are parallel contributes a singleton block. All remaining valid diagonal entries are \(1\). Consequently \[ \mathbf 1\mathbf 1^{\mathsf T}-Q =(1-e^{-2H})\sum_{C}\mathbf 1_C\mathbf 1_C^{\mathsf T} +\mathop{\mathrm{diag}}(\eta_i),\qquad \eta_i\ge0. \tag{15}\] Here \(C\) ranges over these disjoint parallel classes. The diagonal correction replaces an invalid repeated-step entry by zero; this only increases the diagonal of the left-hand side. This proves the addition assertion, including box boundaries.

For removals, use a finite expansion on a ground set \(\Omega\) with enough copies to realize every display and with rank \(r(E)\). The complement \(\Omega\setminus S\) in its dual matroid has rank \[m^*(\Omega\setminus S)=|\Omega\setminus S|-r(E)+m_r(v).\] Writing \(r^*=|\Omega|-r(E)\), we obtain the exact identity \[|S|+r(E)-2m_r(v) =|\Omega\setminus S|+r^*-2m^*(\Omega\setminus S).\] A removal from \(S\) is an addition to its dual complement. Realize \(S\) using \(b_e\) fixed copies and disjoint sets of \(z_i\) copies for the count coordinates in physical group \(e\). Choose one representative from every nonempty such set, and a second copy when \(z_i\ge2\). A transposition of those two copies fixes every other representative, preserves \(S\), and preserves the dual contraction. The preceding parallel-class argument therefore gives the same block description (15). When only one removal is allowed in a count coordinate, its diagonal is zero and the nonnegative correction in that formula handles it. No nonexistent second copy is required.

Reflection \(z_i\mapsto m_i-z_i\) on the entire coordinate set of one factor exchanges addition and removal, proving both tests for the decreasing orientation. Fixed coordinates merely become part of \(b\). For factors on disjoint groups, normalized entries between different groups equal one; hence the matrix \(\mathbf 1\mathbf 1^{\mathsf T}-Q\) is the direct sum of their nonnegative definite matrices. Unused coordinates contribute zero blocks, apart from the permitted diagonal corrections. This proves the product assertion. Raising to a nonnegative power replaces each \(H\) by that power times \(H\).

Finally let \(f\) be an integral normalized submodular function that need not be nondecreasing. Choose an integer vector \(a\) large enough that \(f'(A)=f(A)+a(A)\) is nondecreasing and that every translated lower endpoint of the grouped arguments plus \(a\) is nonnegative. This is possible: there are finitely many marginal differences \(f(A\cup\{e\})-f(A)\) and finitely many box endpoints. The equation \(B(f')=B(f)+a\) follows from Lemma 3. Apply the proved construction to the shifted argument and \(f'\), then let \(H\to\infty\). This gives exactly the desired base indicator on the finite box. The copy matroids and these possibly large boxes are used only to prove the inequalities; the algorithm does not construct them. ◻

Proof. Every base polytope here is bounded: its \(e\)th coordinate lies between \(f_i(E)-f_i(E\setminus\{e\})\) and \(f_i(\{e\})\). Fix any finite integer interval \([A,B]\) of parameter values, with \(B-A=M\ge2\). For each \(e\in E\), choose an integer interval \([L_e,U_e]\) containing all \(e\)th coordinates of \(B(f_2)\) and having width \(D_e=U_e-L_e\ge2\). Introduce two count coordinates \(a_e,b_e\), each of capacity \(D_e\), and two further coordinates \(p,q\), each of capacity \(M\). Use the full box slice of total \(\sum_eD_e+M\). Define physical arguments by \[\begin{align*} w_{2,e}&=U_e-b_e,\\ w_{1,e}&=L_e+a_e+(d_0)_e +A\mathbf 1_{\{e=j\}}-B\mathbf 1_{\{e=k\}} +p\mathbf 1_{\{e=j\}}+q\mathbf 1_{\{e=k\}}. \tag{17}\end{align*}\] The first rank factor uses the increasing counts \((a_e)_e,p,q\); the second uses the decreasing counts \((b_e)_e\). These sets of count coordinates are disjoint. In the first factor, the coordinates \(a_j,p\) feed the same physical coordinate, as do \(a_k,q\), exactly as allowed in Lemma 9.

On this finite box, choose modular translations \(c_1,c_2\) so that \(f_i+c_i\) is nondecreasing and every lower endpoint of \(w_i+c_i\) is nonnegative. For finite \(H\), the product \[F_H=\Phi_{f_1+c_1,H}(w_1+c_1) \Phi_{f_2+c_2,H}(w_2+c_2)\] is strictly positive on the full slice and has both signatures. Sum every ordinary pair \((a_e,b_e)\) at balance, leaving the pair \((p,q)\) of total \(M\). By Lemma 8, the resulting weight has the removal signature. Let \(y_H(t)\) denote its value at \((p,q)=(t-A,B-t)\). It is positive for every integer \(A\le t\le B\).

For \(A<t<B\), add one to each coordinate of this retained pair. This is a box-valid display of total \(M+2\), whose removal matrix is \[\begin{pmatrix} y_H(t-1)&y_H(t)\\y_H(t)&y_H(t+1) \end{pmatrix}.\] It has positive trace and at most one positive eigenvalue, so \(y_H(t)^2\ge y_H(t-1)y_H(t+1)\). Because all entries are positive, the successive differences of \(\log y_H\) are nonincreasing. It follows that, for all \(A\le a<t<b\le B\), \[y_H(t)\ge y_H(a)^{(b-t)/(b-a)} y_H(b)^{(t-a)/(b-a)}.\]

At balance \(a_e+b_e=D_e\), the vector \(w_2\) equals \(L+a\). At \((p,q)=(t-A,B-t)\), formula (17) therefore gives \(w_1-w_2=d_0+t(e_j-e_k)\). Each possible integer \(x_2\) in the chosen intervals has exactly one balanced encoding. Letting \(H\to\infty\) thus gives \(y_H(t)\to y(t)\) term by term, since the finite product of rank penalties converges to the two base indicators. Pass the global interpolation inequality to this limit. Positive endpoint counts give a positive lower bound at every intermediate integer. The interval \([A,B]\) was arbitrary, proving both (16) and the assertion about support. ◻

Proof. For an atom \(D\), intersect all generators containing \(D\), obtaining \(H_D\). This is the union of atoms whose membership sets contain the membership set of \(D\). Order the atoms so that a strict superset of memberships comes first. Every prefix is then the union of \(H_D\) over its own atoms. Nonnegative submodularity gives \(s(U\cup V),s(U\cap V)\le s(U)+s(V)\), which proves the prefix bound. At any \(x\in Q\), apply that bound to the nonnegative slack function \(r(\cdot)-x(\cdot)\). For a fixed prefix its value lies in \([0,n(m+1)b]\), so the prefix total varies by at most \(n(m+1)b\). Subtract consecutive prefix totals to obtain (21). ◻

Proof. If \(s_*(A)<S\), then \(s_1(A)<W\) and \(s_2(E\setminus A)<W\), since \(S<W\). Thus neither \(A\) nor its complement cuts a fine part, proving the containment.

For each ordered pair of distinct elements \((a,b)\), minimize the relevant slack function subject to \(a\in A\), \(b\notin A\). Restricted submodular minimization, with rational modular terms for \(s_i\), applies as in Section 2. If the minimum is below the threshold, retain a minimizer. Two elements separable by any set below the threshold are separated by a retained set in one of the two orientations. The retained family therefore has exactly the required atoms, and contains at most \(n(n-1)\) sets. Its values and all comparisons have polynomial encoding length. The prefix bound is now Lemma 11, because \(n(n^2+1)S\le N^4S\). ◻

Proof. First, \(Y(d)\ge1\) for every integral \(d\) with zero superblock sums and \(\|d\|_1\le S/2\). If a set \(A\) cuts no superblock then \(d(A)=0\le s_*(A)\); otherwise \(d(A)\le\|d\|_1\le S/2<s_*(A)\). Thus \(d\in B(s_*)\), so \(B(r_1)\cap(B(r_2)+d)\) is nonempty. Its integrality, from Lemma 5, supplies an integer point. Inclusion gives the same positivity for \(Y^+\).

All coordinates of an expanded base lie in \([-nT,R+nT]\). The product-of-lengths bound (19) therefore gives \(Y(d),Y^+(d)\le e^K\) for every \(d\). In the positive region just proved, their logarithms lie between zero and \(K\). By Proposition 10, these logarithms are concave on integer lines parallel to \(e_j-e_k\).

Introduce the star shifts successively. Each partial shift has \(\ell^1\)-norm at most \(2nS/N^{25}\). On the line for the next shift, an integer interval of radius \(\lfloor S/10\rfloor\) about that partial shift remains in the positive region. A concave integer sequence taking values in \([0,K]\) on this interval has successive slopes of absolute value at most \(100K/S\) within distance \(S/N^{25}\) of its center: compare each slope with the secants to the two ends of the interval. Adding at most \(n\) changes proves \[|\log F(d(l))-\log F(0)| \le \frac{100K}{S}\sum_j|l_j| \le 100nK/N^{25}<N^{-8}.\]

For completeness, put \(b=S/N^{25}\). For an individual \(\omega\)-coordinate the normalized tail beyond \(b\) is at most \(4e^{-b/(2h)}\), by summing a geometric series. For an individual \(\psi\)-coordinate it is at most \(4e^{-b^2/(2M^2)}\): compare the decreasing Gaussian tail with its integral and use \(b\ge2M\). The full normalized tail is at most the sum of these one-coordinate tails. Since \(b/h=N^{25}\), \(b^2/M^2=N^{5950}\), and \(K=N^5\), in either case the tail probability \(\tau\) satisfies \[e^K\tau\le e^{-N^{20}}.\] On the complementary region use (29); on the tail use \(F\le e^K\) and \(F(0)\ge1\). The resulting lower bound \((1-\tau)e^{-N^{-8}}F(0)\) and upper bound \(e^{N^{-8}}F(0)+e^K\tau\) imply (30), including its truncated version. All assertions are exact when the star is empty. ◻

Proof. We first control the starting totals. If \(A\) is one of the \(s_*\)-generators, it is a union of superblocks. For any \(x_1\in Q_1(w)\), \(x_2\in Q_2(w)\), \[[r_1(A)-x_1(A)]+[r_2(E\setminus A)-x_2(E\setminus A)] =s_*(A)<S.\] Both terms are nonnegative. Thus on the whole first slice every generator has slack below \(S\), and on the whole second slice its complement has slack below \(S\). The same assertions hold at \(c\). Apply Lemma 11 to \(Q_i(w)\cup\{c\}\), using complemented generators for system 2. It gives \[ |w_G-c(G)|\le 2n(n^2+1)S\le N^6S. \tag{35}\] The distance bound in Lemma 5, applied to one rank system and these partition equalities, gives a point \(a\in Q_i(w)\) with \(\|a-c\|_\infty\le N^{10}S\). Choose such a point rationally: its allowed set is a nonempty rational polytope, since \(c\) and the cube radius are rational.

We now describe one refinement step on one system. Maintain a nonempty original slice \(Q\), its partition \(\mathcal P\), and a point \(a\in Q\). A list of generators produces \(\mathcal P\); initially it is the list just described. The list has at most \(n^2+n\) members. Each initial generator has slack at most \(S\) throughout the current slice, and every subsequently added generator will have slack at most \(N^3S\) throughout the slice on which it is added and all its descendants.

Intersect \(Q\) with the cube of radius \(L=N^{10}S\) about \(a\), and choose a center \(b\) of this boxed slice with the property of Lemma 6. If every rank inequality cutting a current part has slack at least \(S\) at \(b\), stop on this branch with \(a^*=b\). Otherwise select a set \(A\) cutting a current part with \(r_i(A)-b(A)<S\). The center property implies \[\max_{x\in Q,\ \|x-a\|_\infty\le L} (r_i(A)-x(A)) \le 4(n+1)S<N^3S.\] The slack \(x\mapsto r_i(A)-x(A)\) is nonnegative on \(Q\) and has integral linear part \(-\mathbf 1_A\). Since its displayed maximum is less than \(N^3S<L\), the last assertion of Lemma 5 identifies this maximum with the unrestricted maximum on \(Q\). Thus the new generator has slack at most \(N^3S\) throughout the current slice.

We check simultaneously that the selected set does not cut a fine part and that proximity to \(c\) survives refinement. At depth \(t\), maintain \[ \|a-c\|_\infty\le N^{10}S+tN^{17}S. \tag{36}\] As each refinement increases the number of parts, \(t\le n\). Every tested center \(b\), being within \(L\) of \(a\), is therefore within \(N^{60}S\) of \(c\). If \(A\) cut a fine part, then its slack at \(c\) would satisfy \(s_i(A)=r_i(A)-c(A)\ge W\), and so \[r_i(A)-b(A)\ge W-nN^{60}S\ge W/2>S,\] a contradiction. The refined partition obtained by adding \(A\) still consists of unions of fine parts.

On this refined partition prescribe every integer vector of part totals that occurs in the expanded current slice. Every such vector occurs in the original real slice: in a decomposition \(x+v\in Q+\Delta_i\), the vector \(v\) preserves the new totals, since it preserves each fine-part total. Thus each retained original child slice is nonempty, and its expanded partner remains its Minkowski sum with \(\Delta_i\). The new generator list has slack at most \(N^3S\) throughout \(Q\). By (21), the range of every new part total over \(Q\) is at most \[2n(n^2+n+1)N^3S\le N^{12}S.\] The current \(a\) consequently satisfies all the child’s new equalities with error at most \(N^{12}S\). The distance bound in Lemma 5 supplies a point in the child within \(N^{17}S\) of \(a\). As before, choose this point rationally within the indicated rational cube. This proves (36) at the next depth.

Each branch stops after at most \(n-1\) strict refinements. There are finitely many branches because the slices are bounded. The stopping rule gives (33); the distance induction gives (32); and the same comparison with \(c\) gives (34) for every fine-cutting inequality. Prescribing totals partitions lattice points without multiplicity. Integral prescribed totals are compatible with the unit lattice in every terminal affine space; in particular, nonempty original terminal slices contain integer points by Lemma 5. ◻

Proof. The lower bound follows from inclusion. For the upper bound, define the full-star weighted pair sums \[\mathcal W=\sum_l\omega(l)Y(d(l)),\qquad \mathcal W^+=\sum_l\omega(l)Y^+(d(l)).\] Fix common integer superblock totals \(w\), and perform the two independent subdivisions of Lemma 14. We compare one pair of terminal slices \(Q_1,Q_2\) and its expanded pair \(Q_1+\Delta_1,Q_2+\Delta_2\). Their partitions \(\mathcal P_1,\mathcal P_2\) may differ. Let their witnesses be \(a_1^*,a_2^*\), and put \(a^*=(a_1^*,a_2^*)\).

For each system use the affine coordinates obtained by retaining all but one physical coordinate in each terminal part. The omitted coordinate is the prescribed integer total minus the retained coordinates. The integral points in this affine space therefore form precisely a unit grid. Lebesgue measure below is the product measure in these free coordinates, independently for the two systems. The slack in (33) ensures that each original slice is full-dimensional in its specified affine space: every inequality not fixed by its part totals is strict at the witness. An affine space of dimension zero is given measure one.

Tile these affine spaces by half-open unit cells based at all their integral points. In physical coordinates any point of a cell differs from its base point by at most \(2n\) in sup norm; the same bound applies when rounding to the base of the containing cell. This uses the formula for the omitted coordinate and is valid for negative coordinates as well. No truncation at zero is made: the expanded bases can have negative coordinates, and feasibility will be checked using their full rank inequalities.

Let \(\mathcal C\) be the union of cells based at pairs of original feasible lattice points in these terminal slices, and let \(\mathcal C^+\) be the corresponding expanded union. Extend the weight to their whole product affine space by \[\omega(x_1,x_2)=e^{-\Phi(x_1,x_2)},\qquad \Phi(x_1,x_2)=\frac1h\sum_{G\in\mathcal G} \sum_{j\in G\setminus\{j_G\}}|x_{1j}-x_{2j}|.\] The common superblock totals ensure that this is the weight in (26). It is continuous and \(\Phi\) is convex. Its logarithm varies by at most \[ \kappa_0=4n^2/h \tag{38}\] within any one of our product cells relative to the base point. Thus integration over \(\mathcal C\) or \(\mathcal C^+\) approximates the corresponding weighted lattice sum within a factor \(e^{\kappa_0}\).

Put \(\theta=N^{-200}\) and apply the homothety \[H(x)=(1-\theta)x+\theta a^*.\] We claim that \(H(\mathcal C^+)\subseteq\mathcal C\). Fix \(x\in\mathcal C^+\), and round \(H(x)\) to the base point \(y=(y_1,y_2)\) of its containing cell. All prescribed terminal totals are preserved. In system \(i\), the rank inequality for \(A\) is satisfied by the expanded lattice point under \(x\) with additional allowance \[\sigma_i(A)=T\sum_{D\in\mathcal D_i} |A\cap D|\,|D\setminus A| \le n^2T.\] The move to \(x\) and the final rounding each change a subset sum by at most \(2n^2\). If \(A\) cuts a terminal part but no fine part, then \(\sigma_i(A)=0\), and \[y_i(A)-r_i(A)\le 4n^2-\theta S<0.\] If \(A\) cuts a fine part, it also cuts a terminal part, and \[y_i(A)-r_i(A) \le 4n^2+n^2T-\theta W/2<0.\] These strict inequalities follow from the chosen scales: \(\theta S=N^{4800}\) and \(\theta W/T=N^{100}\). Finally, if \(A\) cuts no terminal part, its total is fixed on the affine space and equals a feasible original total. Every original rank inequality holds at \(y_i\), proving the claim. This also enforces nonnegativity of \(y_i\), since it follows from the original base constraints.

Write \(d\le2n\) for the product free dimension. The map \(H\) is injective, with Jacobian \((1-\theta)^d\). Convexity and nonnegativity of \(\Phi\) give \[\Phi(H(x))\le(1-\theta)\Phi(x)+\theta\Phi(a^*) \le\Phi(x)+\theta\Phi(a^*).\] Moreover, (32) gives \[\theta\Phi(a^*) \le\theta\,2nN^{60}S/h<N^{-80}.\] Integration and the inclusion just proved imply \[\int_{\mathcal C}\omega \ge (1-\theta)^d e^{-\theta\Phi(a^*)} \int_{\mathcal C^+}\omega.\] Together with (38), this bounds the expanded weighted lattice sum in this pair of slices by the original weighted sum times \[\exp\{2\kappa_0+\theta\Phi(a^*)-d\log(1-\theta)\} \le e^{N^{-8}}.\] The same argument holds in dimension zero, with Jacobian and cell measure one. Summing over the terminal pairs and then over \(w\) yields \(\mathcal W^+\le e^{N^{-8}}\mathcal W\). Finally, Lemma 13 gives \[Z^+\le e^{3N^{-8}}\frac{\mathcal W^+}{A_\omega} \le e^{4N^{-8}}\frac{\mathcal W}{A_\omega} \le e^{7N^{-8}}Z\le e^{20N^{-8}}Z.\] ◻

Proof. Remove the prescribed nontree contributions from each vertex margin. A leaf of the remaining tree determines its unique incident edge; subtract that value from the neighboring margin and delete the leaf. The final equation holds because the two margin sums agree. This proves existence, uniqueness, and integrality. Equivalently, deleting a tree edge divides the vertices into two sets; its value is the signed sum of the residual margins on either one of those sets. Every original port has coefficient \(0\), \(1\), or \(-1\) in that sum before the representative correction, and every free edge contributes with coefficient of absolute value at most one. Substituting (40) gives the stated loose coefficient bound. Conversely, the prescribed margins of any such pair give \(\sum_{e\in C}(X_{1e}-X_{2e})=t_C\). Representative support forces its discrepancy on \(e_C\) to equal \(t_C\), so it obeys exactly the equations just solved. The inverse map reads off the part totals and nontree values. Thus there is no multiplicity or lattice determinant in this parametrization. ◻

Proof. The representative shift has sum zero on each superblock, proving the hard conditions. For an original pair, every forward superblock prefix \(A\) satisfies \(x_1(A)=x_2(A)\). Its two complementary rank slacks therefore add to \(s_*(A)\le N^4S\). The system-2 prefixes are complements of such forward prefixes. In particular the slack at either prefix \(A_{iG}\) is at most \(N^4S\). The inequality on \(A_{iG}\cup U\) gives \[x_i(U)-r_{iG}(U)\le r_i(A_{iG})-x_i(A_{iG}),\] so summing over the two systems and at most \(n\) blocks proves the first bound.

For the converse, fix \(i\) and put \(U_G=A\cap G\). Diminishing marginal returns, applied successively in the order of system \(i\), gives \[\sum_G\bigl(r_i(A_{iG}\cup U_G)-r_i(A_{iG})\bigr)\le r_i(A).\] Indeed the prefix of the already selected pieces of \(A\) is contained in \(A_{iG}\); its marginal increment from \(U_G\) is at least the increment from the full prefix. Summing the defining inequalities for \(V_G\) proves the claim. The hard rank conditions enforce the correct total and every inequality on a union of parts of \(\mathcal D_i\). Any other set cuts at least one part. Its rank bound in \(B_i^+\) increases by \(T\) for every pair of coordinates in that part separated by the set, and hence by at least \(T\). This absorbs the remaining violation. ◻

Proof. A uniform density on an interval of length \(b_0/3\) has distributional derivative of total variation \(6/b_0\). Assigning at most three derivatives to distinct uniform factors in each sixfold convolution shows that every product-kernel derivative of total order \(q\le3\) has total variation at most \(6^qb_0^{-q}\). The remaining convolutions give continuous derivatives through order three. Every positive-order derivative has integral zero. Subtracting \(I_G(u)\) inside its integral, and using (47), bounds each relative derivative of \(\widetilde I_G\) of order \(q=1,2,3\) by \[10^{11}L_0b_0^{1-q}.\] Here \(e^{L_0b_0}-1\le2L_0b_0\), and \(\widetilde I_G(u)\ge e^{-L_0b_0}I_G(u)\). The identities for derivatives of a logarithm give second derivatives bounded by a constant times \(L_0/b_0+L_0^2\), and third derivatives bounded by a constant times \(L_0/b_0^2+L_0^2/b_0+L_0^3\); the constants from the preceding display are absorbed by the powers in (55). For example \(L_0/b_0=N^{730}/W^2\) and \(L_0/b_0^2=N^{1130}/W^3\). Reflection of side-2 coordinates only changes derivative signs and conjugates the Hessian by a diagonal sign matrix. Thus the bounds and concavity hold in the count convention as claimed. ◻

Proof. Fix a display \(b\) and a direction \(\sigma\in\{-1,1\}\). Initially allow repeated changes outside the box, where the defining positive formula still makes sense. The normalized entry for a factor \(F\) is \[Q_{ij}=\frac{F(b)F(b+\sigma e_i+\sigma e_j)} {F(b+\sigma e_i)F(b+\sigma e_j)}.\] Ignore the last, absolute-value term of (51) for the moment. The finite difference of the smoothed logarithm integrates its Hessian along two unit segments. Comparing it with the Hessian at \(b\) costs at most \(4A_3\) in every entry, also when \(i=j\). The auxiliary quadratic has exact finite difference \(-\alpha\mathbf1_{i=j}\). Thus these two factors contribute \[\exp(sD_{ij}),\qquad D_{ij}=g''_{ij}(b)-\alpha\mathbf1_{i=j}+e_{ij},\quad |e_{ij}|\le4A_3.\] The imbalance Gaussian contributes \(\gamma=\exp(-2s/M^2)\) when \(i,j\) belong to the same nonroot component, and contributes one otherwise. Let \(B\) be the matrix of these latter entries. Its complement is explicitly positive semidefinite: \[\mathbf 1\mathbf 1^{\mathsf T}-B =(1-\gamma)\sum_{C\ne C_0(G)}\mathbf 1_C\mathbf 1_C^{\mathsf T}\succeq0,\] where \(\mathbf 1_C\) indicates the block coordinates incident to \(C\).

We next compare \(Q=B\circ\exp(sD)\), with entrywise operations, to its linear approximation. The inequalities \(1-e^{-2s/M^2}\le2s/M^2\) and \(|e^x-1-x|\le2x^2\) for \(|x|\le1\) give \[ \mathbf 1\mathbf 1^{\mathsf T}-Q =(\mathbf 1\mathbf 1^{\mathsf T}-B)-s g''(b)+s\alpha I+E, \qquad |E_{ij}|\le s\mathcal E, \tag{56}\] where one may take \[\mathcal E=10A_3+100(A_2+\alpha+4A_3)^2 +10(A_2+\alpha)/M^2.\] More explicitly, the error entries in this identity are \[E_{ij}=-sB_{ij}e_{ij} +s(1-B_{ij})(g''_{ij}(b)-\alpha\mathbf1_{i=j}) -B_{ij}(e^{sD_{ij}}-1-sD_{ij}).\] All entries of \(D\) have absolute value below one. The three terms are bounded respectively by \(4sA_3\), \(2s^2(A_2+\alpha)/M^2\), and \(2s^2(A_2+\alpha+4A_3)^2\). Since \(s^2\le s\), they give the displayed budget uniformly even for arbitrarily small positive \(s\). There are at most \(2n\) block coordinates, so \(\lVert E\rVert_{\rm op}\le2ns\mathcal E\). The scale choices give \[\frac{2n\mathcal E}{\alpha} \le N^4\left(\frac{N^{1350}}W+ \frac{N^{1700}}{W^2}+N^{-3100}\right)<\frac12.\] Both the first term on the right of (56) and \(-sg''(b)\) are positive semidefinite. The term \(s\alpha I\) therefore absorbs the error for every \(s>0\). At \(s=0\) the assertion is immediate.

Finally the total imbalance in a block is the sum of all its count coordinates plus a constant. Put \(v=\sum_{C\subseteq G}t_C(b)\). Its absolute-value penalty multiplies every normalized entry by the same number \[\beta=\exp\{-sH(|v+2\sigma|-2|v+\sigma|+|v|)\}\in(0,1].\] Since \(\mathbf 1\mathbf 1^{\mathsf T}-\beta Q =(1-\beta)\mathbf 1\mathbf 1^{\mathsf T} +\beta(\mathbf 1\mathbf 1^{\mathsf T}-Q)\), the test persists. Discard unavailable single changes and set the diagonal to zero for invalid repeated changes. These operations take principal matrices and add a nonnegative diagonal to their complements, so they also preserve the test. ◻

Proof. The balanced profiles are in bijection with the original integer port settings, and their weights are \(w(u)\), so (53) proves the comparison. Positivity is explicit in the definitions. Lemma 9 applies to the rank factors, including the simultaneous reflection on side 1. Lemma 19 applies to every block factor. The coordinate groups of all these factors are disjoint; hence the full normalized complement is the direct sum of their normalized complements. The signature criterion in Section 3 proves the result. ◻

Proof. The integral’s upper bound is its free-box volume, \((R+1)^{|\mathcal F_G|}\le e^K\), since smoothing uses probability kernels. For the lower bound put \(u^c_{iD}=c(D)\) and \(z^c_e=c_e\) on free edges. The tree solve gives \(X_1=X_2=c\), so the prefix-slack argument of Lemma 17 gives \(V_G(u^c,z^c)\le2N^4S\). For each free coordinate choose \(z^*_e=\max\{c_e,1/4\}\). It lies in \([0,R+1]\) with at least \(1/4\) clearance from its boundary and differs from \(c_e\) by at most \(1/4\). On the cube of sup radius \(1/8\) about \(z^*\), and for every smoothing displacement, the port and free-coordinate displacements from \((u^c,z^c)\) are at most \(N^{21}W+b_0+1\). Therefore \[ \lambda V_G(u-v,z) \le2\lambda N^4S+L_0(N^{21}W+b_0+1)<N^{5000}. \tag{59}\] Integrating over this cube and over the whole probability kernel gives \(\widetilde I_G(u)\ge4^{-|\mathcal F_G|}e^{-N^{5000}} \ge e^{-N^{50000}}\). This proof includes \(\mathcal F_G=\varnothing\).

For the rank factors, choose any common integral base \(x^*\), which exists by the feasibility and integrality results of Section 2. Its projected totals \(v^*_i\) satisfy the rank constraint and are within \(N^{10}W\) of the center totals by (39). For any nonnegative vector \(v\) on a rank index set, its rank penalty is \[v(E_r)+r(E_r)-2m_r(v) =\max_{A\subseteq E_r} \{v(A)-v(E_r\setminus A)+r(E_r)-2r(A)\}.\] Every affine function on the right has coordinate slopes \(\pm1\). Thus this penalty is 1-Lipschitz in the \(1\)-norm. It vanishes at \(v_i^*\), so throughout a port box it is at most \(N^{23}W\), independently of the numerical value of \(R\). Multiplication by \(H\) still gives a fixed power of \(N\). For each component, \(t_C\) vanishes at the center and has absolute value at most \(N^{23}W\) throughout the boxes. Consequently all Gaussian and absolute-value exponents in (51) have absolute value bounded by fixed powers below \(N^{40000}\); the auxiliary quadratic is smaller than one. Summing these bounds and (57) over at most \(n\) blocks proves (58).

The center, endpoints, scales, and tree coefficients have polynomial encoding length. Ranks of unions and contracted ranks require ordinary rank queries. For the minima defining \(m_r\) and the maxima defining \(V_G\), rational modular terms are handled by clearing their common denominator and applying Proposition 2. The binary length of that denominator is at most the sum of the individual denominator lengths. Thus the size parameter is polynomial in bits; no bound on its numerical value is needed. ◻

Proof. The pointwise upper inequality follows from \(1-t\le e^{-t}\). For \(0\le D\le E_0\), expansion of \(-\log(1-t)\), or integration of its derivative, gives \[0\le-d_0\log(1-D/d_0)-D \le\frac{D^2}{2d_0(1-D/d_0)}<\rho/100.\] The part of (60) where \(D>E_0\) has integral at most \(e^{K-E_0}\). Dividing by the lower bound in (57) makes its relative contribution at most \[\exp(K+N^{50000}-E_0)<\rho/100.\] These two errors prove (64).

For separation, first test the box inequalities and \(y\ge0\). Compute \(D(x)\) and choose an index \(a\) with largest \(y_a\). If \(D(x)+d_0y_a>d_0\), the attaining affine piece of \(D\) gives a rational hyperplane separating the point from \(\mathcal Q\). Otherwise all inequalities hold. The coefficient bounds follow from the integral tree map, the rank-answer bit bound, the rational scales, and the input port encodings. At a rational query, clearing denominators for the two submodular minimizations takes polynomial bit work as in Lemma 21. Each inequality, rather than the number of possible subsets, is the encoding parameter.

For the inner ball choose \[x^*=(z^*,q^*),\qquad z^*_e=\max\{c_e,1/4\},\qquad q^*_{ja}=1/2,\qquad y^*_a=1/4.\] All box coordinates have clearance at least \(1/4\). A Euclidean perturbation of radius \(1/32\) changes each free coordinate by at most \(1/32\) and each \(v_j\) by at most \(2b_0/32\). By (47) its change in \(D\) is at most \(L_0\max\{1,2b_0\}/32<1\). The near-center estimate (59) therefore gives \(D<N^{5000}+1<d_0/2\) throughout this ball. Also \(0<y_a\le9/32\), so \(D+d_0y_a<25d_0/32<d_0\). This proves the inner guarantee, including \(f=0\). Every point of \(\mathcal Q\) has \(x\in\mathcal B\) and \(0\le y_a\le1\). If \(d=f+6m+d_0\), the ball centered at the origin with rational radius \(d(R+2)\) is therefore an outer ball. Its binary encoding length is polynomial.

Finally, the numerical value of \(d_0\) is polynomial in \(N\) and \(\rho^{-1}\): the exponents in (61) are fixed. Thus even its explicitly added coordinates can be written and processed within one fixed polynomial bound. The original capacity appears only in the box endpoint \(R+1\) and the encoding lengths just verified. ◻

Proof. First evaluate a single smoothed block integral. Round \(\mathcal Q\) by the rational affine construction above, apply the volume theorem with relative error \(\rho/10\), and restore the exact determinant factor. Use the same parameter \(\rho\) in (61). By Lemma 22, its successful output is a relative \(\rho/2\) approximation to \(\widetilde I_G\).

For completeness, all resource bounds here are bounds on actual finite-bit executions. Let \(B\) be a furnished polynomial upper bound on the expected combined number of bit operations and oracle calls of one volume run, including the cost of its separation queries. If the chosen version already has a deterministic bound, use that bound instead. Interrupt the run after \(16B\) operations; Markov’s inequality increases the failure probability by at most \(1/16\). The resulting success probability is at least \(11/16\). On interruption, a declared failure (including a zero denominator), or an invalid or nonpositive output, substitute a fixed positive rational. Repeat independently \(O(1+\log\beta^{-1})\) times and take the median. The binomial tail bound gives failure probability at most \(\beta\). Cap construction, query lengths, arithmetic, and random-bit generation are all included. Clip each output to \[[2^{-2N^{50000}},\ 2^{2N^{50000}}].\] This interval has polynomial-bit endpoints and strictly contains all successful relative approximations from (57). Clipping therefore retains the success guarantee and ensures bounded positive outputs even on failed or interrupted runs.

Evaluate all rank penalties and the other rational exponents exactly, and allocate relative error \(\rho/(100(n+1))\) and failure allowance \(\beta/(n+1)\) to each of the at most \(n\) block integrals. Evaluate the remaining exponentials and all rational arithmetic to another \(\rho/(100(n+1))\) relative error per factor. The log bounds in Lemma 21 ensure that these relative accuracies require only polynomial absolute precision. One elementary implementation uses the exponential Taylor series and factorial tail bounds: an exponent of magnitude at most \(D_*\) and absolute precision \(2^{-k}\) require polynomially many terms and bits in \(D_*+k+1\). Negative exponents can be evaluated by inversion of a positive exponential approximation. Here \(D_*\) is a fixed polynomial in \(N\), not in \(R\).

Multiplying the factors gives a positive relative approximation to \(h\). Before taking any power, clip this product to \([2^{-3N^{60000}},2^{3N^{60000}}]\). This interval contains \(h\) by (58), so clipping cannot increase its relative error; it also gives valid bisection bounds even after failed block evaluations. On the simultaneous success event the sum of the factor logarithmic errors is below \(\rho/10\), after reducing the indicated constants if necessary. To obtain \(h^s\) for \(s=a_s/q_s\), apply bisection to the \(q_s\)th root and integer powering to \(a_s\), with positive rational endpoints whose binary exponents are bounded by \(3N^{60000}\). Each comparison is an integer-power comparison, and \(a_s\le q_s\); the number of bisections, lengths of operands, and bit work are polynomial in \(q_s\), \(N\), and \(\log\rho^{-1}\). Taking a power in \([0,1]\) cannot increase the preceding logarithmic error. Approximate the root to logarithmic error at most \(\rho/[100(q_s+1)]\) before taking the \(a_s\)th power; the resulting additional logarithmic error is at most \(\rho/100\). This proves the required relative bound. For \(s=0\) return one exactly. All steps have prescribed finite bounds; clipping the final output to \([2^{-3N^{60000}},2^{3N^{60000}}]\) gives the same positivity and encoding guarantee on every failure event. This proves the asserted evaluator without conditioning any future computation on its success.

To approximate \(J\), let \(k\) be the number of nonroot components, so \[J=\left(\sum_{j\in\mathbb Z}e^{-j^2/M^2}\right)^k, \qquad 0\le k\le n.\] For \(k=0\) return one. Otherwise truncate at the integer \(B_J=MN^{10}\), a polynomial in \(N\). The omitted two-sided tail is at most \[2\int_{B_J}^{\infty}e^{-x^2/M^2}\,\mathrm dx \le\frac{M^2}{B_J}e^{-B_J^2/M^2} =MN^{-10}e^{-N^{20}}.\] The sum is at least one. Approximate each of its \(2B_J+1\) retained terms to absolute error at most \(N^{-7}/[100(n+1)(2B_J+1)]\), keeping the term at zero exactly one and the remaining terms nonnegative. The elementary exponential procedure above is bounded since each exponent has magnitude at most \(N^{20}\). Adding the terms and raising to the integer power \(k\) gives a positive rational result whose logarithmic error is below \(N^{-7}\). No random choices or numerical grid of length \(R\) occurs. ◻

Proof. We give the factorial cancellation in (OpenAI 2026a, Lemma 4.2, “Signatures of the two lifts”), since it also explains the roles of the two weights. In an omission test for \(f\), the display has \(p+2\) elements. Group these by count coordinate and let \(n_u\) be the number in group \(u\). On the subspace of vectors constant within each group, the ordered-copy multiplicities \(n_un_w\) for \(u\ne w\) and \(n_u(n_u-1)\) for \(u=w\) cancel the factorial reductions from removing two elements. The quadratic form becomes \[\frac{\prod_u n_u!}{\prod_v d_v!} \sum_{u,w}k(n-e_u-e_w)t_ut_w,\] where invalid removals contribute zero. Its positive index is at most one by the integer removal signature. Vectors summing to zero within each group have nonpositive quadratic form and are orthogonal for this form to the group-constant subspace: within a group the matrix has constant nonnegative off-diagonal entries and zero diagonal. This proves the omission assertion. For \(\widetilde f\), group the elements available after fixing \(p-2\) inclusions. The remaining-capacity factorials cancel the same multiplicities, leaving a positive multiple of the integer addition matrix. This proves the addition assertion. The closure assertions are precisely (OpenAI 2026a, Lemma 4.1, “Binary contractions”); their hypothesis of positivity on the full domain has been checked here.

For the comparison, if the empty and full pair are in the same port, all ports remain balanced and the ratio is one. Otherwise the port containing the hole has \(a+b=d-1\), and contributes \((a+1)(b+1)\) to \(\widetilde f/f\). The port containing the full pair has \(a+b=d+1\) and contributes \(1/(ab)\). Both positive integer products lie between \(1\) and \((p+1)^2\). Their quotient proves (68). ◻

Source and applicability. These are (OpenAI 2026a, Propositions 5.2 and 5.4 and Lemmas 5.5–5.6), with \(q\) left as the comparison parameter in their proofs. Their structural inputs are Lemma 5.1 (one-hole transport) and Lemma 4.4 (pair inequalities for defect masses). We spell out why the stated hypotheses are the complete interface. For a partial transversal assignment \(\sigma\), let \(z_\sigma\) be its transversal mass and let \(\widetilde c_{il}^{\sigma}\) be the mass of its extensions in \(\mathcal A_{il}\) under \(\widetilde f\). Binary contraction, including the full-index cubic contraction clause of (OpenAI 2026a, Lemma 4.1), and the addition property give \[4\widetilde c_{il}^{\sigma}\widetilde c_{li}^{\sigma}\leq z_\sigma^2, \qquad \widetilde c_{il}^{\sigma}\widetilde c_{lk}^{\sigma} \leq z_\sigma\widetilde c_{ik}^{\sigma} \quad(i,l,k\text{ distinct and unassigned}).\] Agreement on transversals identifies \(z_\sigma\) for the two weights. The omission property supplies one-hole transport for \(f\), including its auxiliary displays outside \(\mathcal X\); this is why positivity and the signature were required on all \(p\)-subsets. Comparison on actual defect classes costs \(q^2\) in the transversal variance bound and \(q^3\) in the defect-mean bound, giving exactly \(C_{\rm p},C_{\rm d}\) above. The remaining observable and trace arguments use only these inequalities, reversibility, and laziness. They impose no condition on the origin of the count weight. This is the two-lift version of the transport, observable-Poincare, and trace-restart framework of (OpenAI 2026b, secs. 4–6). ◻

Proof. The logarithm of \(2^{-U}h\) lies between \(-U\log2-N^{60000}\) and \(-U\log2+N^{60000}<0\). Dividing by \(H_o=10U\) proves (78). Summing that bound within each type proves the multiplier comparison and domination. On a transversal the factorial factor is at least \(2^{-p}\), while \(k_j\geq2^{-H_o}\). Also \[C_j\leq C_0=\prod_{v\in\mathcal P}(d_v+1)\leq2^p\leq2^{K_o},\] which proves (79).

Here are explicit formulas for the initializer, as in (OpenAI 2026a, Lemma 7.1, “Exact initialization”). Fix \(i\ne l\). For each port put \[u_v=\mathbf1_{\{i\text{ lies in }v\}},\quad v_v=\mathbf1_{\{l\text{ lies in }v\}},\quad m_v=d_v-u_v-v_v.\] There are \(m_v\) singly occupied pairs left in this port, so \[ c_{il}(0)=\prod_{v\in\mathcal P} \left[\frac1{d_v!}\sum_{k=0}^{m_v} \binom{m_v}{k}(k+v_v)!(m_v-k+v_v)!\right]. \tag{80}\] All factorial arguments are at most \(p\). If \(i,l\) are in the same port, that port has at least two pairs, so \(m_v\geq0\) also in this case. Each bracket equals, respectively, \(d_v+1\), \(1\), \((d_v+1)(d_v+2)/6\), or \((d_v+1)/6\) according as the port contains neither designated pair, only \(i\), only \(l\), or both. Writing \(v(i)\) for the port containing pair \(i\), we can therefore use the particularly simple exact initial multipliers \[ w_{il}^{(0)}=\frac{C_0}{c_{il}(0)}= \begin{cases} 6,&v(i)=v(l),\\[1mm] \displaystyle\frac{6(d_{v(i)}+1)}{d_{v(l)}+2},&v(i)\ne v(l). \end{cases} \tag{81}\] The finite sums or these simplified expressions give polynomial bit bounds, including all \(p(p-1)\) initial multipliers. Finally choose \(a_v\) uniformly from \(\{0,\ldots,d_v\}\) and choose a uniform \(a_v\)-subset of that port’s pairs to use their \(a\)-elements. The probability of a particular transversal is \(\prod_v[(d_v+1)\binom{d_v}{a_v}]^{-1}=f_0(S)/C_0\). ◻

Proof. This is the reference experiment of (OpenAI 2026a, sec. 7.2 and Proposition 7.2). We include its probabilistic argument to specify the treatment of the restart caps. Fix a history of successful phases before \(j\). Its stored multipliers are now fixed and good. For this one phase, consider a virtual restart that ignores the transition cap, followed by its observation trajectory. At any trace stage \(a\), (79) and (75) bound the pointwise relative error after \(\tau\) steps by \[2^{H_o+p+K_o}\exp(-2(H_o+p+K_o+5))<1.\] The endpoint law is thus at most \(2\mu_a\). Stage one starts at \(\mu_0\leq2\mu_1\), and each later stage starts at a law bounded by \(2\mu_{a-1}\leq4\mu_a\). Trace stationarity preserves the bound \(4\mu_a\) at every deterministic trace index in that stage. By the return-cost assertion and (70), each such trace step has expected cost at most \(20p^2\). There are at most \(H_o\tau\) trace steps in a restart. Markov’s inequality therefore bounds its cap-failure probability by \[ \frac{20p^2H_o\tau}{B_{\rm ret}} \leq\frac1{100(H_o+1)}. \tag{85}\]

The virtual endpoint has law at most \(2\mu_j\), hence at most \(10p^2\pi_{j,w^{(j)}}\) on \(\mathcal X\). Under this stationary law, write \(p_T\) for the type probabilities and \(u_j=\mathbb E_\pi G_j\). Direct summation gives \[ \frac{u_j}{p_0}=\frac{C_{j+1}}{C_j},\qquad w_{il}^{(j)}\frac{p_0}{p_{il}}=\frac{C_j}{c_{il}(j)}. \tag{86}\] The type indicators and \(G_j\) are fixed by \(\mathcal Q\), take values in \([0,1]\), and have means at least \((20p^2)^{-1}\), by (70) and (78). The mean squared error of each average is at most \(20p^2K_{\rm obs}/N_{\rm av}\) by (74). There are \(p(p-1)+2\leq2p^2\) observables. Markov’s inequality applied to their squared errors and a union bound show that the probability some empirical mean has relative error greater than \(\eta\) is at most \[ \frac{16000p^8K_{\rm obs}}{N_{\rm av}\eta^2} \leq\frac1{100(H_o+1)}. \tag{87}\] These estimates concern the uncapped virtual phase. On the event that its cost meets the cap it agrees with the capped phase. Failure of the latter is contained in the union of the two failure events just bounded; no endpoint law is conditioned on meeting a cap.

On empirical success every type count is positive. Equation (86) shows that the update estimates the current ideal multiplier directly, with factor error at most \((1+\eta)/(1-\eta)\leq2\). Its ideal value changes by at most a further factor two for the next phase, so (69) holds there. The same empirical bounds give \[\left|\log\frac{\widehat R_j}{C_{j+1}/C_j}\right|\leq4\eta.\] The initial multipliers are ideal. Summing the probabilities of the first unsuccessful phase bounds total failure by \(2H_o/[100(H_o+1)]<1/50\). On success the ratios telescope and their log errors sum to (84). ◻

Proof. There are at most \(T_{\max}=H_o(B_{\rm ret}+N_{\rm av})\) underlying transitions. Each requires at most two weight calls and four outer draws (hold, two proposal choices, and acceptance). The observations require at most \(2H_oN_{\rm av}\) further calls, and the restarts at most \(2H_o|\mathcal P|\) initialization draws. Including transition counts, the number of these elementary actions is at most \[7T_{\max}+2H_oN_{\rm av}+2H_o|\mathcal P|<J_*.\] Counter initialization and arithmetic on all defect multipliers add only deterministic polynomial work.

For the coupling, expose the joint past immediately before each call or draw. Until a discrepancy, the states and multipliers agree. The new evaluation input is then fixed by that past, and fresh bits give conditional evaluation failure probability at most \(\xi\). This uses no conditioning on future successful evaluations. Conditional on accurate evaluations, a computed weight ratio \(r'\) and its exact value \(r\) satisfy \[\frac{1-\xi}{1+\xi}\leq\frac{r'}r \leq\frac{1+\xi}{1-\xi},\qquad |\min(1,r')-\min(1,r)|\leq\frac{2\xi}{1-\xi}<4\xi.\] Dyadic rounding contributes at most another \(\xi\). Couple reference and implemented acceptance decisions with a common uniform variable. Formally, the algorithm’s uniform \(b\)-bit integer can be supplemented, only in the proof, by an independent uniform point inside its dyadic interval. The resulting continuous uniform variable gives the exact reference marginal and realizes the stated probability of disagreement. Couple each other finite draw at its total variation cost, at most \(\xi\). A union bound over the action budget, including call failures, gives the generous bound \(20J_*\xi\). Matching paths have identical integer type counts; consequently (83) gives exactly identical stored multipliers, even though the ratio observations differ. Trace returns and cap decisions also agree. Successful positive ratios have log error at most \(4\xi\), as claimed. This is the bounded coupling argument of (OpenAI 2026a, Lemma 7.3 and Section 7.3), with the evaluator furnished here.

For the unconditional resource bound, \(|\mathcal P|\leq2n\) and \(d_v\leq N^{21}W=N^{20021}\), so \(p\leq2nN^{20021}\). All numerical quantities \(U,H_o,K_o,q,C_{\rm p},C_{\rm d},K_{\rm obs}\), the displayed caps, and \(\xi^{-1}\) are bounded by fixed polynomials in \(N\) and \(\varepsilon^{-1}\). Their exponents are absolute constants. Every state has a \(2p\)-bit representation; its count profile and type are recovered by a bounded scan. Factorials and binomial coefficients have \(O(p\log(p+1))\) bits and are computed by bounded integer arithmetic. Each weight evaluation has deterministic polynomial work and output length by Proposition 23, even on its failure event. The scale \(2^{-Uj/H_o}\) and rational powers have polynomial descriptions and evaluation precision; restoring \(2^U\) ultimately requires only \(U+1\) bits.

The sizes of the stored multipliers are controlled without any accuracy assumption. On a nonaborting history, \[w_{il}^{(a)}=w_{il}^{(0)} \prod_{j=0}^{a-1}\frac{n_0^{(j)}}{n_{il}^{(j)}}, \qquad1\leq n_T^{(j)}\leq N_{\rm av}.\] Thus each numerator and denominator has at most its initial bit length plus \(H_o\lceil\log_2(N_{\rm av}+1)\rceil\) bits, up to a fixed additive constant, even without fraction reduction. A zero count causes an abort before division. Acceptance thresholds therefore have polynomial-length operands on every history. Adding at most \(N_{\rm av}\) positive rational observations using a product denominator, and multiplying at most \(H_o\) phase estimates, also creates only polynomial-length integers. These estimates include the cost of writing the rational output. All outer loops have the specified caps, all evaluator loops are bounded, and every random draw uses finitely many fair bits. The resource conclusions are independent of successful coupling, good multipliers, and statistical accuracy. ◻

Proof of Theorem 1. First perform the exact feasibility test from Section 2. Its integrality guarantee makes an empty real intersection equivalent to \(Z=0\), in which case the algorithm returns zero on every execution. If \(R=0\), the only feasible vector is zero and the algorithm returns one; this includes the promised case \(n=0\). In all other feasible cases perform the partition and port constructions proved above.

If \(p\geq1\), let \(Y\) be the implemented ratio product. By Proposition 27 and Lemma 28, outside an event of probability at most \(1/50+20J_*\xi<1/4\), the run does not abort and \[\left|\log\frac{Y}{C_{H_o}}\right| \leq4H_o(\eta+\xi)<\varepsilon/100.\] Indeed the multiplicative bounds on each positive observation persist under summation, while the type counts agree exactly. Restore the scale by setting \(\widehat{\mathcal Z}_{\rm port}=2^UY\). If \(p=0\), evaluate its sole count profile directly with relative tolerance \(\varepsilon/100\) and failure probability \(1/16\); then \(|\log(\widehat{\mathcal Z}_{\rm port}/\mathcal Z_{\rm port})| \leq\varepsilon/50\) on success. This branch invokes none of the \(p\)-dependent chain parameters. When \(p=1\), the chain proof already applies: there are no defect classes or multipliers and every state is a transversal.

Obtain the deterministic positive rational estimate \(\widehat J\) from Proposition 23, with \(|\log(\widehat J/J)|\leq N^{-7}\), and output, for this run, \(\widehat Z=\widehat{\mathcal Z}_{\rm port}/\widehat J\). Aborted runs output zero. On the success event in either branch, (65) gives \[\left|\log\frac{\widehat Z}{Z}\right| \leq\varepsilon/50+101N^{-7}<\varepsilon/10.\] Here \(N\geq10^{10}\) and \(N\geq\varepsilon^{-1}\), so \(101N^{-7}\leq101\varepsilon N^{-6}<\varepsilon/100\). For \(0<\varepsilon<1\), \(e^{-\varepsilon/10}\geq1-\varepsilon\) and \(e^{\varepsilon/10}\leq1+\varepsilon\); hence a single run has the required relative accuracy with probability greater than \(3/4\).

For the requested failure probability, let \(s_\delta=\lceil\log_2(\delta^{-1})\rceil\) and take \(m_\delta=10s_\delta+1\) independent runs, returning their median. If \(F\) is their number of failures, independence implies \(\mathbb E2^F\leq(5/4)^{m_\delta}\). A bad median requires at least \(m_\delta/2\) failures, so \[\mathbb P\{\text{bad median}\} \leq\left(\frac5{4\sqrt2}\right)^{10s_\delta+1} \leq2^{-s_\delta}\leq\delta.\] The middle inequality follows from \((5/(4\sqrt2))^{10}<1/2\). Exact comparison of the rational outputs and median selection have polynomial bit cost.

Finally, \(N=10^{10}+n+\ell+\lceil\varepsilon^{-1}\rceil\) is bounded by a fixed polynomial in the parameters of the theorem. All construction, evaluation, and counting bounds established above are fixed polynomials in \(N\) and the input encoding length. Multiplying them by \(m_\delta=O(1+\log\delta^{-1})\) gives the required separate bounds on rank-oracle calls and other bit operations on every execution, including reading answers, writing queries and output, and generating random bits. The only explicitly constructed labelled set has \(2p\) elements, with \(p\) bounded by the short port ranges. The large expansion matroids, geometric subdivisions, and transport flows used in the proofs are never constructed or queried. This completes the algorithm and its approximation and bit-complexity proofs. ◻