Proof. Put \(A_A=|O(A)|^{-1}\sum_{e\in O(A)}b_eb_e^T\) and \(f_A(D)=\mathop{\mathrm{tr}}(A_AD^{-1})\). These functions are convex, since \[b^TD^{-1}b=\sup_x(2b^Tx-x^TDx).\] The conic constraint is \(L_G-D\in\mathcal N^*\). Choose \(D_0=\delta I_{\mathsf E}\) with \(0<\delta<\lambda_{\min}(L_G|_{\mathsf E})\). Then \(L_G-D_0\succ0\) lies in the interior of \(\mathcal N^*\), because the positive semidefinite cone is contained in \(\mathcal N^*\). Taking an epigraph height above all \(f_A(D_0)\) makes the other inequalities strict as well.

For completeness, finite-dimensional separation gives the needed strong duality even if the infimum is not attained. Separate \((0,0,p_*)\) from the open convex set of \((a,M,z)\) for which some \(D\succ0\) and \(t\in\mathbb R\) satisfy \[f_A(D)-t<a_A,\qquad M-D+L_G\in\operatorname{int}\mathcal N^*,\qquad t<z.\] Monotonicity in the three coordinates makes the separating coefficients \((\lambda,Z,\gamma)\) satisfy \(\lambda\ge0\), \(Z\in\mathcal N\), and \(\gamma\ge0\). The strictly feasible point just constructed rules out \(\gamma=0\): one may take all \(a_A<0\) and \(M\) in \(-\operatorname{int}\mathcal N^*\), making the pairing strictly negative for every nonzero \((\lambda,Z)\). Normalize \(\gamma=1\). The unrestricted variable \(t\) then forces \(\sum_A\lambda_A=1\). Taking limits to the boundary of the open set, and using weak duality for the reverse inequality, gives \[ p_*=\sup_{\substack{\lambda\ge0,\ \sum_A\lambda_A=1\\Z\in\mathcal N}} \left[\inf_{D\succ0} \{\mathop{\mathrm{tr}}(A(\lambda)D^{-1})+\mathop{\mathrm{tr}}(ZD)\}-\mathop{\mathrm{tr}}(ZL_G)\right], \quad A(\lambda)=\sum_A\lambda_AA_A. \tag{6}\]

For any \(A,Z\succeq0\), \[ \inf_{D\succ0}\{\mathop{\mathrm{tr}}(AD^{-1})+\mathop{\mathrm{tr}}(ZD)\} =2\mathop{\mathrm{tr}}\bigl((Z^{1/2}AZ^{1/2})^{1/2}\bigr). \tag{7}\] When \(A,Z\succ0\), set \(H=Z^{1/2}DZ^{1/2}\) and \(C=Z^{1/2}AZ^{1/2}\). The objective minus \(2\mathop{\mathrm{tr}}(C^{1/2})\) is \(\norm{H^{-1/2}C^{1/2}-H^{1/2}}_{\mathrm F}^2\), and vanishes at \(H=C^{1/2}\). For singular \(A\) or \(Z\), add \(\eta I_{\mathsf E}\) to both. The positive definite identity at each fixed \(D\), followed by \(\eta\downarrow0\), proves the lower bound. The unperturbed infimum is at most the perturbed infimum, whose limit gives the upper bound. These are auxiliary perturbations for the identity, not extra dual feasibility assumptions.

For \(Z\ne0\) in \(\mathcal N\), connectivity gives \(\mathcal E=\mathop{\mathrm{tr}}(L_GZ)>0\). Writing \(N_0=\mathop{\mathrm{tr}}((Z^{1/2}A(\lambda)Z^{1/2})^{1/2})\), optimization over the scale \(\tau Z\) gives \[\sup_{\tau\ge0}(2\sqrt\tau N_0-\tau\mathcal E) =N_0^2/\mathcal E.\] The zero multiplier contributes zero. Represent \(Z\) as the centered Gram matrix of points \(p_v\), and put \[w_e=\sum_{A:e\in O(A)}\frac{\lambda_A}{|O(A)|}.\] Then \(N_0\) is the nuclear norm of the matrix with columns \(\sqrt{w_e}(p_u-p_v)\). The singular value decomposition, after adding zero coordinates if needed, gives \[N_0=\max_{UU^T=I}\sum_e\sqrt{w_e}\ip{u_e}{p_u-p_v}.\] Changing individual row signs preserves row orthonormality, so take the displayed contributions nonnegative. For such a maximizing \(U\), \[\begin{align*} N_0 &\le\sum_A\sqrt{\frac{\lambda_A}{|O(A)|}} \sum_{e\in O(A)}a_e,\\ N_0^2 &\le\sum_A\frac1{|O(A)|} \left(\sum_{e\in O(A)}a_e\right)^2. \end{align*}\] The first line uses \(\sqrt{\sum_jx_j}\le\sum_j\sqrt{x_j}\) and the second uses \(\sum_A\lambda_A=1\). Overlapping boundaries are allowed. Substitution into [tg:lagrange] proves the claim. ◻

Proof. Take \(R>2\max_{x,y}d(x,y)\) and two copies \(x^+,x^-\) of each point. On the doubled set define \[\widehat d(x^+,y^+)=\widehat d(x^-,y^-)=d(x,y),\qquad \widehat d(x^+,y^-)=R-d(x,y).\] This is a metric. A triangle with all signs equal is an original triangle. A triangle with two equal signs has two cross-copy sides; an inequality with a cross-copy side on the left reduces to an original triangle inequality. The remaining inequality follows from \(d(x,y)+d(x,z)+d(z,y)\le3\operatorname{diam}(d)<2R\).

For a doubled point \(a\), let \(c_a=(\widehat d(a,z))_z\) be its distance profile in \(\ell_\infty\), and set \(Q=\mathop{\mathrm{conv}}\{c_a\}\). The triangle inequality and coordinate \(a\) show \(\norm{c_a-c_b}_\infty=\widehat d(a,b)\). More generally, for \(q=\sum_b\theta_bc_b\), \[ \norm{q-c_a}_\infty =\sum_b\theta_b\widehat d(a,b)=q_a, \qquad \theta_b\ge0,\quad\sum_b\theta_b=1. \tag{9}\] Indeed, convexity of the norm gives the upper bound, and coordinate \(a\) gives the lower bound. Thus the radius is the restriction of a linear coordinate function, independently of the representation of \(q\). Set \(c_x=c_{x^+}\) and \(c_x^-=c_{x^-}\). The identity \(\widehat d(x^+,b)+\widehat d(x^-,b)=R\) for every doubled point \(b\) proves [tg:opposite-radii].

If \(\rho=\rho_x(q)\), the segment \(q_t=(1-t)q+tc_x\) has \(\norm{q_t-q}=t\rho\) and \(\rho_x(q_t)=(1-t)\rho\). The segment \(q_t^-=(1-t)q+tc_x^-\) has \(\norm{q_t^--q}=t(R-\rho)\) and \(\rho_x(q_t^-)=\rho+t(R-\rho)\). These formulas prove the exact-motion assertion, including the endpoint cases. Convexity of \(Q\) keeps all segments in \(Q\); the final assertion follows from [tg:affine-radius] and clamping. ◻

Proof. We follow the constructions in Sections B.2–B.4 of (OpenAI 2026), keeping their scale choices and scalar potentials. All balls, shells, and intersections now lie in the continuous polytope \(Q\). New shells inherit vertex centers, so [tg:affine-radius] remains available. We first obtain the bags, then explain how each of the two charging constructions operates in this realization.

Extraction and the spectral step. The two truncations and homogeneity arguments in (OpenAI 2026, sec. B.2.2) use only \(a_e^2\le d_e\), nonnegative boundary sums, and multiplicity at most two. They select nonempty subsets \(O'(A)\subseteq O(A)\) retaining a fixed fraction of each squared boundary sum, and group the nodes so that both positive quantities \(a_e^2\) and \(d_e\) vary by a factor less than four within \(F=\bigcup_AO'(A)\). For one such group put \(N=\sum_A|O(A)|\), \(N'=|F|\), \(c_1=\min_{e\in F}a_e^2\), and \(c_2=\max_{e\in F}d_e\). The truncation and grouping estimates give \(c_1N'\ge\sigma Nc_2\). For the Euclidean points \(Y_v=Up_v\) and \(\widetilde\alpha=\sigma N/N'\) this implies \[(\mathbb E_{e\in F}a_e)^2\ge c_1 \ge\widetilde\alpha c_2 \ge\widetilde\alpha\mathbb E_{e\in F}\norm{Y_u-Y_v}_2^2.\] This is the exact hypothesis of the Euclidean spectral-packing Lemma B.3 of (OpenAI 2026); that lemma places no binary restriction on its points. Its selected centers have squared Euclidean separation at least \(4r\). Since \[ \norm{Y_u-Y_v}_2^2\le d(u,v)=\norm{c_u-c_v}_\infty, \tag{12}\] the corresponding \(Q\)-balls of radius \(r\) are disjoint. If \(b_0\) is their number, the spectral lemma gives \(b_0r\ge\widetilde\alpha^\epsilon c_1N'/C_1\). Shrink their common radius to \(\delta\) defined by \(b_0\delta=\widetilde\alpha^\epsilon c_1N'/C_1\). Only the selected vertex labels pass from the Euclidean geometry to \(Q\); a map on intermediate points is unnecessary.

The rest of the one-family construction uses a maximal disjoint collection of balls of radius \(D=\max\{\delta,2c_2\}\), centered at images \(c_u\) for which \(u\in A\) and \(uv\in O'(A)\) for some \(A\). Maximality puts every candidate center within \(2D\) of a selected center: intersection of two relative balls implies this distance bound by the triangle inequality. Every endpoint center is within \(c_2\) of an assigned endpoint, hence within \(3D\) of a selected center. Grouping by those centers gives diameter at most \(6D\) in the compact case. In the assigned case the witnessing edge has length at most \(c_2<D\). The cardinality estimates of (OpenAI 2026, Lemma B.6) give compactness, assignment strength, and radius range \([\sigma c_1,12c_1/\sigma]\). Its final grouping by dyadic size and then by residue class modulo \(H_0\) is numerical: each scale lies between \(\sigma2^j\) and \(24\,2^j/\sigma\), so scales in the same residue class meet the stated geometric separation. The losses \(C_2\), \(L\), \(2H_0\), and \(192\beta C_1/\sigma^\epsilon\) are exactly those in [tg:captured-mass]. This proves (i).

Length charging and compact radial objects. The resource charged by both arguments is one fixed straight segment \([c_u,c_v]\) of length \(d_e\) for each graph edge, retaining parallel edges as separate resources. For a radial object with numerical radii \(a<b\), its clamped radial function is \(f(q)=\min\{b,\max\{a,\norm{q-c}\}\}\). It is \(1\)-Lipschitz and piecewise affine on each edge segment. If the object has vertex witnesses at radius at most \(a\) and at least \(b\), all its intermediate radial cuts are nontrivial. Consequently \[k(b-a)\le\int_a^b|\delta_G\{v:\norm{c_v-c}<t\}|\,dt =\sum_{uv\in E(G)}|f(c_u)-f(c_v)|.\] For disjoint radial objects, subdivide an edge segment at the finitely many breakpoints of these functions. At most one clamped function is nonconstant on each open subsegment, and its variation is bounded by that subsegment’s length. The total charge is therefore at most \(d_e\), including edges along a boundary or of zero length. This proves the length bound of (OpenAI 2026, Lemma B.9) in \(Q\). For an ordinary ball, nonconstant portions of the clamped function lie at strictly positive radius. Its center contributes no charged length, but remains part of the ball in membership tests.

For compact bags, process the families in decreasing order of radius, as in (OpenAI 2026, Proposition B.8). An input ball inserted at the current scale is called fresh and is left intact until the next scale; all other live objects are called old. Thus a fresh ordinary ball becomes an old ordinary ball at the next scale unless a subsequent operation restricts it. Disjoint equal-radius balls have centers separated by at least \(2\delta\), since their midpoint belongs to \(Q\). For any live object with center \(c\) and numerical radii \(a,b\), call \(B(c_u,\delta)\) interior when \[a+\delta+\Delta\le\norm{c_u-c}\le b-\delta-\Delta.\] This conservative two-sided test also applies when the object is an ordinary ball, with \(a=0\). If one ball of a compact bag is interior, its containing object is old, since fresh balls and unprocessed balls belong to the same disjoint family. All bag centers have radial values in an interval \([l,u]\subseteq[a+\delta,b-\delta]\) of width at most \(\Delta\). Replacing the old object by the strict shells with intervals \((a,l-\delta)\) and \((u+\delta,b)\) leaves room for all the new balls, including when the old object was ordinary. The extremal centers supply the new outer and inner witnesses; the previous witnesses supply the other two. Every inserted ball has its own center and a different bag center as witnesses. All supports are disjoint by \(1\)-Lipschitzness of radius. When no interior bag remains, shrinking each old interval at both ends by \(2\delta+\Delta\) separates it from every remaining ball. Indeed, failure at the lower margin puts the entire candidate at radius less than \(a+2\delta+\Delta\), and failure at the upper margin puts it beyond \(b-2\delta-\Delta\). This includes candidates near the center of an old ordinary ball: the shrink removes that center neighborhood. Witnesses are preserved because the inner radius increases and the outer radius decreases; an inner witness need not belong to the remaining strict shell. The capacities \([w-6\Delta_i]_+\) for all old objects and \(\delta_i-6\Delta_{i+1}\) for fresh balls depend only on widths and the inequalities \(2\delta_i\le\Delta_i\), \(6\Delta_{i+1}\le\delta_i/2\), and \(|\mathrm{Bag}|\delta_i\ge36\Delta_i\), all verified here. The split loses numerical width \((u-l)+2\delta\), and the shrink loses \(2(2\delta+\Delta)\), with the same positive-part accounting when a residual is discarded. Removing the center alone adds no width loss. A retained fresh ball has the same capacity after becoming old. Thus the split and scale-transition inequalities in the cited proof retain at least one quarter of the input mass as final radial-object width. Applying the preceding length bound proves (ii).

Assigned labels, pruning, and path charging. Assigned bags require the labeled records of (OpenAI 2026, sec. B.4.1). We give their definitions because geometric overlap is allowed. Write \(\mathcal T[A]\) for the hierarchy subtree rooted at \(A\), identifying its leaves with the vertices in \(A\). A record \(H\) has an ordinary ball or shell as its support, an owner \(A_H\), a set \(\mathcal P_H\) of strict descendants of \(A_H\), and optionally one avoided strict descendant \(D_H\). Define its conflict domain and leaf set by \[C(H)=\mathcal T[A_H]\setminus \left(\bigcup_{P\in\mathcal P_H}\mathcal T[P] \ \cup\ \mathcal T[D_H]\right), \qquad L(H)=C(H)\cap V,\] omitting the final subtree when there is no avoided label. The record is called avoiding precisely when \(D_H\) is present. For center \(c\) and numerical radii \(a<b\), validity means:

1. the labels have the stated form, so \(A_H\in C(H)\);

2. both endpoints of every edge of \(\delta_G(P)\), for every \(P\in\mathcal P_H\), have radius at least \(b\) from \(c\);

3. some \(u\in L(H)\) has radius at most \(a\) and starts at least \(k/4\) edge-disjoint paths to vertices of radius at least \(b\). These paths lie in \(G[A_H]\), or in \(G[A_H\setminus D_H]\) for an avoiding record;

4. geometrically intersecting records have disjoint conflict domains.

The initial paths in (c) need not avoid the predecessor subtrees in \(\mathcal P_H\); condition (b) will remove those subtrees from the portions used for charging. Its inner witness is a graph vertex in \(L(H)\), not necessarily a point of the support: for a strict shell it can lie on or inside the excluded inner boundary.

For a node \(A\) assigned at scale \(\delta_i\), its predecessors are the strict descendants assigned at earlier, larger scales. An input ball is noninsertable if it contains an endpoint of a boundary edge of any predecessor. Otherwise give it owner \(A\), no avoided label, and excluded set equal to the predecessors.

At one scale, disjoint center-inclusive balls contain at most \(2|P(A)|\) endpoint vertices of \(P(A)\). Thus a predecessor \(A\), whose own scale is \(\delta_i\), deletes mass at most \(4\rho\delta_i|P(A)|\), which the boundary ratio and assignment bound pay as in the source’s Lemma B.13. Deleting noninsertable balls and bags losing more than half their balls retains mass at least \(\mathsf M/2\) and assignment at least \(12C_3/k\). Insertability puts the designated center vertex in its conflict domain: otherwise its witnessing edge in \(O(A)\) would be a forbidden predecessor-boundary edge whose endpoint lies in the ball. Another ball of the bag supplies an outer vertex; local connectivity supplies the required paths. The retained bag has more than one ball, since \(|O(A)|\ge k\) and its assignment is at least \(12C_3/k\). Thus the resulting input records satisfy (a)–(c), including when distinct vertices have coincident images.

For a valid collection, stop each witnessing graph path at its first outer vertex. It cannot enter an excluded predecessor subtree earlier, because the entering edge would have an endpoint inside the outer radius. On the resulting continuous path keep the portion from the last inner-radius point to the first outer-radius point. Its length is at least the record’s numerical width by \(1\)-Lipschitzness. Apart from endpoints it lies in \(a<\norm{q-c}<b\), which is contained in either type of support. For an ordinary ball \(a=0\) and the center carries no charged length. Paths within one record are edge-disjoint. Both endpoints of every edge in a stopped path belong to \(L(H)\): an entrance into an excluded subtree, even at the stopping vertex, would have a preceding endpoint inside the outer radius, contradicting (b). Two records charging the same graph edge therefore have intersecting conflict domains, so (d) makes their actual supports disjoint and they charge disjoint open portions of that edge. This proves the source’s Lemma B.14 in \(Q\), at rate \(k/4\).

It remains to construct a valid arrangement with enough total width. Start with the empty arrangement and process scales in decreasing order and, within each scale, bags in increasing depth of their assigned nodes. As in the compact construction, original balls inserted during the current phase are fresh and remain intact until the next phase; all other records are old. A candidate \(J=B(c_u,\delta_i)\) is interior to a current record \(H\) with center \(c\) and numerical radii \(a,b\) when \[C(J)\cap C(H)\ne\varnothing, \qquad a+C_3\delta_i<\norm{c_u-c}<b-C_3\delta_i.\] A candidate interior to no current record is called a border candidate. In particular old ordinary balls participate in this test with \(a=0\), including its lower margin. A record containing an interior candidate has width greater than \(2C_3\delta_i\), so it cannot be a fresh ball of width \(\delta_i\). An interior candidate is contained in \(H\). The processing order implies that the owner of any conflicting current record is an ancestor of the candidate’s owner \(A\), and that \(A\in C(H)\). Two conflicting records therefore cannot both contain this candidate, by (d). The strict concentric restrictions defined above retain (a)–(c) with the old labels: the old inner witness still has radius at most the new inner radius, and the old paths still reach the smaller outer radius. This remains true when an ordinary ball is replaced by a shell and its center witness no longer lies in the support. Restricting both support and conflict domain preserves (d). Discard any proposed radial interval of nonpositive width. Such restrictions cannot turn a border candidate into an interior candidate. These are the order and inheritance properties of (OpenAI 2026, Lemmas B.17–B.20).

Meeting a record and carving its interior. The following consequence of 4 identifies the record affected by a carving operation. If a live record \(H\) with center \(c\) and numerical radii \(r_1<r_2\), and a vertex center \(z\), satisfy \[r_1-\delta<\norm{z-c}<r_2+\delta,\] then \(B(z,\delta)\) meets the actual support of \(H\). Choose a radius in \((r_1,r_2)\) less than \(\delta\) away from \(\norm{z-c}\) and use the exact inward or outward motion to reach it. Its traveled distance is less than \(\delta\). There is no radius-range obstruction: condition (c) provides an outer vertex witness, so \(r_2\le\operatorname{diam}(d)<R\). For an ordinary ball \(r_1=0\); the chosen radius is positive and belongs to that ball, even when \(z=c\) and outward motion is needed. This replaces motion toward the binary center or its opposite cube vertex in (OpenAI 2026, sec. B.4.3).

At scale \(\delta\), process the interior candidates of a bag assigned to \(A\) while at least half its original balls remain interior and untreated. Candidates that cease to be interior are kept as border candidates. Carving an avoiding shell around an interior candidate replaces its radial interval \((r_1,r_2)\) by \((r_1,q-\delta)\) and \((q+\delta,r_2)\), and inserts the candidate. Here \(q\) is its center’s radius from the shell center. Every avoiding record is indeed a strict shell: input records are nonavoiding, only the central shell \(H_4\) below introduces an avoided label, and later restrictions are strict shells. Radial Lipschitzness gives disjointness; witnesses and labels survive in the restrictions. If no remaining interior candidate belongs to an avoiding shell, the other two operations first split \(G[A^*\setminus A]\) into \(j\le2|O(A)|/k\) induced subgraphs that are \(k/4\)-edge-connected. This count follows by successive cuts smaller than \(k/4\) and the \(k\)-connectivity of \(G[A^*]\); it is independent of the embedding. Assignment and the half-bag loop condition give one piece adjacent along edges of length less than \(\delta\) to at least \(3C_3\) candidate centers. Radial coordinates of these neighbors differ by less than \(\delta\) from those of their candidate centers.

Choose a nonavoiding record \(H\) containing one of those candidates in its interior, with center \(c\) and numerical radii \(r_1,r_2\), and write \(\varrho(v)=\norm{c_v-c}\). It may be an old ordinary ball, in which case \(r_1=0\). Let \([a,b]\subseteq[r_1,r_2]\) be the radial range of the neighbors in the selected piece, clipped to this numerical interval. Select for treatment the \(m\) still-interior candidates whose centers have radii in \((a-\delta,b+\delta)\). Each meets the chosen record by the preceding exact-motion argument. All candidates of the bag have the same labels, so each has conflict domain meeting \(C(H)\). If such a candidate is interior to another record \(H'\), its entire ball lies in \(H'\), so \(H\) and \(H'\) intersect. The processing-order property puts its owner \(A\) in both conflict domains, contrary to (d). Thus every selected candidate is interior to \(H\) itself. The radial count in the cited proof gives \(m\ge3(C_3-1)\) in the dense case below and \(b-a\ge(C_3-1)\delta\) in the sparse case. It uses only the \(3C_3\) adjacent centers, their interior margins, and the fact that neighbor radii differ by less than \(\delta\).

For the dense case, with \(m\delta>3(b-a)\), retain intervals \((r_1,a-2\delta)\) and \((b+2\delta,r_2)\) and insert the \(m\) balls. The expanded radial interval and Lipschitzness give every required separation. For the sparse case \(m\delta\le3(b-a)\), retain \((r_1,a)\) and \((b,r_2)\) and create the central shells \(H_3=B(c;a+\delta,b-\delta)\) and \(H_4=B(c;a,b)\). Give \(H_3\) owner \(A\), no avoided label, and the old excluded nodes strictly below \(A\). Give \(H_4\) the old owner and excluded set, and avoided label \(A\). Their domains are respectively \(C(H)\cap\mathcal T[A]\) and \(C(H)\setminus\mathcal T[A]\). The old owner is a strict ancestor of \(A\). An original ball with owner \(A\) cannot come from an earlier scale, since assigned nodes are distinct across families; at the current scale it is disjoint from every unprocessed candidate. A synthetic shell with owner \(A\) can only have been created while processing this same bag. It has already treated every then-interior candidate in its expanded interval; later restrictions only reduce its support, and border candidates never become interior. Hence neither an original ball nor a synthetic shell with owner \(A\) can be the chosen record. Thus both new labels have the required form. For the changed-label path witnesses, extremal neighbors \(v_1,v_2\) in the selected piece and their adjacent candidates \(u_1,u_2\in A\) satisfy \[\varrho(v_1)\le a,\quad \varrho(v_2)\ge b,\qquad \varrho(u_1)<a+\delta,\quad \varrho(u_2)>b-\delta.\] Connectivity of \(G[A]\) supplies \(k\) paths for the inner central shell; connectivity of the selected piece supplies at least \(k/4\) paths for the avoiding shell. Their initial vertices avoid excluded subtrees: membership in one would make the short edge \(u_1v_1\) an excluded boundary edge with an endpoint inside the old outer radius, or make that excluded subtree an ancestor of \(A\), contradicting \(A\)’s conflict membership. The sparse-case width bound gives \(a+\delta<b\le r_2\), so the initial vertices used here lie strictly inside the old outer radius. This verifies (c) for both new labels; (b) follows from the smaller outer radii and excluded sets. Other records inherit separation by support and conflict-domain inclusion. Remaining interior candidates have centers outside \((a-\delta,b+\delta)\), so miss both central shells. If \(a=0\), \(H_4\) excludes its center but may still use \(v_1\) at radius zero as its inner witness, as condition (c) permits.

The scalar accounting and the phase transition. The potentials in Section B.4.3 are \(\delta_i-C_4\delta_{i+1}\) for fresh balls, \([w-C_4\delta_i]_+\) for other nonavoiding records, and the latter divided by \(2(C_4+2)\) for avoiding records. An original ball becomes old when its phase ends and then uses the second formula with width equal to its radius; if retained unchanged, it still has its center-inclusive support. These functions use the same numerical widths and radii in \(Q\). The three replacements have formal width losses \(2\delta\) across the two avoiding residual shells in the first operation, \((b-a)+4\delta\) across the two nonavoiding residual shells in the second, and \(2\delta\) across the three nonavoiding pieces in the third. Its numerical inequalities preserve old credit and supply \(C_4\delta/(6C_3)\) per treated candidate, counting sparse-case candidates as treated even though their balls are not inserted. Finally, Section B.4.4 either retains every record when the gain from changing scale supplies the required border credit, or shrinks every old object, including old ordinary balls, at both ends by \((C_3+1)\delta_i\) and inserts remaining border balls when the gain is insufficient. For a conflicting old object, border status means the candidate center has radius at most \(a+C_3\delta_i\) or at least \(b-C_3\delta_i\). Its whole ball therefore lies below the new inner radius or above the new outer radius, respectively. This proves separation also at the center of an old ordinary ball; fresh balls are disjoint within the current family. Restrictions retain witnesses. Each old width decreases by \(2(C_3+1)\delta_i\), unless the object is discarded, while the potential threshold decreases from \(C_4\delta_i\) to \(C_4\delta_{i+1}\). These are the same changes for a ball and a shell. The source’s width calculation bounds the lost potential by half the inserted mass, leaving at least \(C_4/(6C_3)\) of each border ball’s radius for its node. The half-bag stopping rule leaves final width at least \(C_4/(12C_3)\) times the retained mass. Combined with the pruning factor \(1/2\) and the path-charging rate \(k/4\), this is exactly [tg:assigned-charge].

Thus the inherited constructions give (i)–(iii), with the same scalar losses and with every length charge measured by \(\mathcal E=\sum_e d_e\) in the profile realization. ◻

Proof of 2. If \(\mathcal M\) is empty, a sufficiently small positive centered identity satisfies [tg:shortcut]. Otherwise use 3. Fix one of its embeddings and row-orthonormal systems, with \(\mathcal E>0\), and set \[\alpha=h^{-4/5},\qquad \epsilon=1/10,\qquad \beta=36,\qquad \rho=(2h^2)^{-1},\qquad C_3=10^4,\qquad C_4=3.\] Let \(T\) consist of the marked nodes with positive \(N_A\) and \(N_A\ge\alpha\sum_{e\in O(A)}d_e\). Boundary multiplicity at most two gives \[ \sum_{A\in\mathcal M\setminus T}N_A\le2\alpha\mathcal E. \tag{13}\] If \(T\) is nonempty, apply 5(i). Its parameters obey \[C_2=O((1+\log h)^4),\quad L,H_0=O(1+\log h),\quad \sigma=h^{-4/5}/C_2.\] The smallness condition holds for all sufficiently large absolute \(h\). So does the assignment requirement, because \[h\sigma^{1+2\epsilon} =h^{1/25}/C_2^{6/5}\longrightarrow\infty, \qquad \sigma^{1+2\epsilon}\ge24C_3/h.\] The marked-node condition implies \(|O(A)|\ge|P(A)|/h\ge h\rho|P(A)|\). For large \(h\), \(\rho\le1/18\); also \(10^4\ge2(4+4\cdot25)=208\). Both charging conclusions of 5 therefore apply, according to the family type, and give the common bound \[\mathcal E\ge c_*h\mathsf M, \qquad c_*=\frac{C_4}{96C_3}=\frac{1}{320000}.\] Together with [tg:captured-mass], this yields \[\frac{\sum_{A\in T}N_A}{\mathcal E} \le \frac{384\beta C_1C_2LH_0}{c_*h\sigma^\epsilon} =O\bigl(h^{-23/25}(1+\log h)^7\bigr).\] Indeed \(\sigma^\epsilon=h^{-2/25}C_2^{-1/10}\), so the exact logarithmic exponent before rounding upward is \(32/5<7\). Including [tg:good-nodes], or using it alone when \(T\) is empty, every ratio in [tg:dual-ratio] is at most \[ 2h^{-4/5}+O\bigl(h^{-23/25}(1+\log h)^7\bigr) =o(h^{-31/40}). \tag{14}\] The exponent margins are \(1/40\) and \(29/200\), respectively. Increase \(h_0\) so the bound is at most \(h^{-31/40}/2\). Then \(p_*\le h^{-31/40}/2\), and the defining property of the infimum supplies a feasible positive definite \(D\) with marked averages less than \(h^{-31/40}\). No attainment assumption is used. ◻

Proof. Use the dyadic assembly of (OpenAI 2026, Lemma 4.2), with the hierarchy estimate and threshold just proved; we give the counting argument to specify both constants. In each occupied bin \(2^a\le |E_G(\mathcal P)|<2^{a+1}\) choose the finest partition. List these representatives from fine to coarse as \(\mathcal P_0,\ldots,\mathcal P_{\ell-1}\), and append \(\mathcal P_\ell=\{V\}\). Put \(B_i=E_G(\mathcal P_i)\) and \(M_i=|B_i|\), with \(M_\ell=0\). Distinct parts of these representative partitions, together with \(V\) and singleton leaves, form a locally \(h\)-connected hierarchy. Mark precisely the nodes with \(|O(A)|\ge|P(A)|/h\), and take \(D\) from 2. Then \[Y=L_H+D\in\mathcal K_H,\] because \(Y\succeq L_H\) and, for every \(Z\in\mathcal N\), \(\ip{Y}{Z}\le\ip{L_H+L_G}{Z}\le2\ip{L_H}{Z}\).

At transition \(j\) to \(j+1\), the parent of each changing part is the part of \(\mathcal P_{j+1}\) containing it. Every disappearing edge in \(B_j\setminus B_{j+1}\) belongs to parent boundaries of changing parts, whose total full-boundary size is at most \(2M_j\). Unmarked parts therefore cover at most \(2M_j/h\) such edges. For marked parts, [tg:resistance-order] and Markov’s inequality give \[|\{e\in O(A):R_Y(e)>1/(6s)\}| \le6s\,h^{-31/40}|O(A)|.\] Thus at most \(2(h^{-1}+6s h^{-31/40})M_j\) disappearing edges fail [tg:response-edge]. Double counting only increases this upper bound.

There is at most one representative per dyadic bin, and its bin index strictly decreases. Hence \(\sum_{j=i}^{\ell-1}M_j<4M_i\). Each edge of \(B_i\) disappears at exactly one subsequent transition, so its bad-edge count is at most \(8(h^{-1}+6s h^{-31/40})M_i\). For a skipped partition with positive crossing count \(M\), its representative is finer and has \(M_i<2M\). Consequently its bad-edge count is at most \[ 16(h^{-1}+6s h^{-31/40})M =O(r^{-1}+r^{-21/40})M\le r^{-1/3}M \tag{18}\] for a sufficiently large absolute cutoff. The final inequality uses \(21/40-1/3=23/120>0\). Partitions with no crossing edges need no estimate. One matrix \(Y\) therefore works for the whole nested sequence. ◻

Proof. Let \(\mathcal C\) be the compact convex set of admissible \((Y,y)\) before the partition inequalities are imposed. It is nonempty: take \(Y=L_H\) and \(y=0\). Put \(q=Q-grt>0\) and let \[S_{\mathcal P}(y)=\sum_{e\in E_H(\mathcal P)}a_e(y) -q(|\mathcal P|-1).\] Each slack is continuous and concave. Its vector image need not be convex, but the downward set \[\mathcal D=\{v:\ v_{\mathcal P}\le S_{\mathcal P}(y) \text{ for some }(Y,y)\in\mathcal C\}\] is convex and closed. Convexity follows coordinatewise from concavity; closedness follows by taking a convergent subsequence of witnesses in \(\mathcal C\). The set \(\mathcal D\) is unbounded downward. If it does not meet the nonnegative orthant, its distance from that orthant is positive: the norm of the negative part of \(S(y)\) has a positive minimum on the compact set \(\mathcal C\), and passing downward cannot reduce that norm. Separation therefore supplies nonnegative weights \(w_{\mathcal P}\), normalized to sum to one, for which \[ F(w):=\max_{(Y,y)\in\mathcal C} \sum_{\mathcal P}w_{\mathcal P}S_{\mathcal P}(y)<0. \tag{30}\]

There are finitely many partitions. Hence \(F\) is continuous on their probability simplex and has a minimizer. Among minimizers choose one maximizing \(\sum_{\mathcal P}w_{\mathcal P}|\mathcal P|^2\). Its support is a chain under refinement. To prove this, suppose incomparable \(\mathcal P,\mathcal Q\) have positive mass. Move equal mass from them to their common refinement \(\mathcal P\wedge\mathcal Q\) and finest common coarsening \(\mathcal P\vee\mathcal Q\). For each edge, \[\mathbf 1_{E_H(\mathcal P\wedge\mathcal Q)}+ \mathbf 1_{E_H(\mathcal P\vee\mathcal Q)} \le \mathbf 1_{E_H(\mathcal P)}+\mathbf 1_{E_H(\mathcal Q)}.\] Moreover, \[|\mathcal P\wedge\mathcal Q|+|\mathcal P\vee\mathcal Q| \ge |\mathcal P|+|\mathcal Q|.\] For the second inequality, form the bipartite graph whose vertices are parts of \(\mathcal P\) and \(\mathcal Q\) and whose edges are their nonempty intersections. Its edges count refinement parts, and its connected components count coarsening parts; edges plus components are at least vertices. Since \(a_e\ge0\) and \(q>0\), uncrossing decreases the weighted slack for every \((Y,y)\), hence cannot increase \(F\). Writing \(a=|\mathcal P|\), \(b=|\mathcal Q|\), \(c=|\mathcal P\wedge\mathcal Q|\) and \(d=|\mathcal P\vee\mathcal Q|\), incomparability gives \(c>\max(a,b)\) and \(d<\min(a,b)\). Thus \[c^2+d^2-a^2-b^2 =(c-a)(c-b)+(d-a)(d-b)+(a+b)(c+d-a-b)>0.\] This contradicts the tie-breaking choice. The one-part partition has zero slack and is comparable with every partition, so it creates no exception.

It remains to satisfy [eq:ta-strong-target] simultaneously on any chain. Let the old slack in [eq:ta-invariant] be \(\sigma_{\mathcal P}\ge0\). If \(\sigma_{\mathcal P}>1\), the worst possible loss \(4tm<1\) already leaves the desired inequality. Retain only partitions with \(\sigma_{\mathcal P}\le1\), omitting the one-part partition. Every part of every retained partition induces an \(h\)-edge-connected graph in \(G\), where \(h=\lfloor r/2\rfloor\). Indeed, split one such part by any nontrivial internal cut. Subtracting the old partition capacity from the invariant for the refined partition shows that the internal cut has capacity at least \(Q-1\). Removing all baselines loses less than \(\kappa m<1\), and \(u_e\le1\) then shows that the active internal cut has more than \(Q-2\ge h\) edges. The same argument using a two-part partition at the root gives more than \(Q-1\) active edges across every root cut. Singleton parts require no check.

Apply 6 to this chain, with its root, and set \(y_e=1\) on edges satisfying \(Y\succeq6s b_eb_e^T\), and \(y_e=0\) otherwise. These choices satisfy [eq:ta-response-LMI]. Fix a retained partition, write \(d=|\mathcal P|\ge2\) and \(M=|E_G(\mathcal P)|\), and call its at most \(r^{-1/3}M\) exceptional crossing edges bad. Good edges never lose capacity; bad edges lose at most \(4t\) each. If \(M\le8r(d-1)\), the total loss is at most \[4t r^{-1/3}M\le32tr^{2/3}(d-1)\le grt(d-1)\] for sufficiently large \(r\), as required.

If \(M>8r(d-1)\), near-tightness gives \(\sum_{E_G(\mathcal P)}u_e\le Q(d-1)+1\le r(d-1)+1\). Fewer than half of these \(M\) edges can have \(u_e>1/2\): their number is at most \(2r(d-1)+2<M/2\) for the chosen cutoff. Each good edge with \(u_e\le1/2\) gains exactly \(t\), since \(t<1/2\). The total gain minus loss is therefore at least \[t\bigl(M/2-r^{-1/3}M\bigr)-4tr^{-1/3}M\ge0.\] This also proves the desired inequality. Every chain thus admits a simultaneous nonnegative slack vector, contradicting [eq:ta-separated]. The lemma follows. ◻

Proof. The partition inequalities are equivalent to \[ z\cdot\ell\ge q\,\operatorname{MST}(\ell) \qquad(0\le\ell_e\le1), \tag{35}\] where \(\operatorname{MST}(\ell)\) is minimum spanning tree length in \(H\). For one direction, assign length one to edges crossing a partition and zero to all other edges. Every spanning tree has at least \(|\mathcal P|-1\) crossing edges. Conversely, let \(\mathcal P_a\) be the components of the subgraph of edges of length less than \(a\). Kruskal’s algorithm gives \[\operatorname{MST}(\ell)=\int_0^1(|\mathcal P_a|-1)\,da.\] Every edge crossing \(\mathcal P_a\) has length at least \(a\), so integration of the partition inequalities gives \(q\operatorname{MST}(\ell)\le\sum_e z_e\ell_e\).

To separate [eq:ta-MST-inequalities], solve the rational linear program \[ \max\bigl\{qv-z\cdot\ell:\ 0\le\ell\le1,\ 0\le v\le n, \ v\le\ell(T)\ \text{for all spanning trees }T\bigr\}. \tag{36}\] All facet coefficients have polynomial encoding length. A minimum spanning tree supplies exact separation for the exponentially many tree constraints. The rational polyhedral optimization theorem (Grötschel et al. 1988, Theorem 6.4.9) therefore computes the exact optimum and a rational optimizer in polynomial work. The optimum is nonnegative. If it is zero all inequalities hold; if positive, the returned length vector gives a violated valid linear inequality in \(z\).

The scalar constraints have immediate rational separators. Exact symmetric elimination either certifies a rational symmetric matrix as PSD or produces a rational vector of negative quadratic form. Applied to an affine matrix constraint, that vector supplies a rational linear separator of polynomial encoding length. This completes the oracle. ◻

Proof. We give deliberately loose uniform bounds. Put \(P=n+m+2\ge5\) and use the upper-triangular entries of the upper-left \((n-1)\times(n-1)\) block as free coordinates of a centered symmetric matrix. If that block is \(A\), its full completion is \(CAC^T\), where \(C=[e_1-e_n\ \cdots\ e_{n-1}-e_n]\). Thus a free-coordinate perturbation of Euclidean norm \(\eta\) changes the full matrix in operator norm by at most \(2P\eta\). Include \(\lambda,y,z\) as ordinary scalar coordinates. Their total number \(D\) is at most \(P^3\).

A connected unweighted multigraph has \[ \lambda_{\min}(L_H|_{\mathbf 1^\perp})\ge P^{-3}=:\mu, \qquad \|L_H\|_{\mathrm{op}}\le2m. \tag{37}\] For the first bound, for a centered unit vector choose its largest and smallest coordinates and a path between them of length at most \(n-1\). The coordinate range is at least \(n^{-1/2}\), so Cauchy–Schwarz along that path already gives energy at least \(1/(n(n-1))\ge P^{-3}\).

Consider an auxiliary point, without requiring its partition constraints: \[ Y_0=2L_H,\qquad \lambda_{ijk,0}=P^{-8},\qquad y_{e,0}=P^{-8},\qquad z_{e,0}=\kappa/2. \tag{38}\] There are at most \(P^3\) generators, each of norm at most \(6\), so their weighted sum has norm at most \(6P^{-5}<\mu/2\). Since \(s\le r^{1/4}\le m+1<P\) and \(\|b_eb_e^T\|=2\), the response LMI at this point has margin at least \(2\mu-12P^{-7}>\mu\). The other two LMIs have margins at least \(\mu/2\). The \(\lambda\) and lower \(y\) faces have margin \(P^{-8}\), the upper \(y\) face has margin at least \(1/2\), and the \(z\) lower and upper faces have margins at least \(\kappa/2\) and \(1\), respectively. Finally \[\kappa+u_e+t(5y_{e,0}-4)-z_{e,0} \ge\kappa/2-4t=3\kappa/8.\] All scalar normal norms and affine matrix Lipschitz constants are at most \(20P^3\) in these coordinates. It follows that the entire ball of radius \[ \rho_0=P^{-20} \tag{39}\] about this auxiliary point satisfies all non-packing constraints. In particular these estimates are uniform even when an active \(u_e\) is extremely small.

By 8, choose a stronger feasible point \(x_*\), using \(z_e=a_e(y)\) and any representation [eq:ta-conic-representation]. Let \(\beta=grt\). Every nontrivial partition has slack at least \(\beta(|\mathcal P|-1)\ge\beta\) at \(x_*\) relative to [eq:ta-computational-packing]. Moreover, \[\beta\ge\frac1{32(m+1)}\ge\frac1{32P}.\] At the auxiliary point every such slack is at least \(-P^2\), because all capacities are nonnegative and \(Q^+\le r\le m\). Mix a fraction \(\theta=P^{-8}\) of the auxiliary point into \(x_*\). Since \(P\ge5\), the new partition slacks are at least \((1-\theta)\beta-\theta P^2\ge\beta/2\). Convexity gives a ball of radius \(\theta\rho_0=P^{-28}\) satisfying the non-packing constraints about the mixture. A partition normal has at most \(m\) unit coefficients in the \(z\) coordinates, so its norm is at most \(\sqrt m\). Thus the smaller ball of radius \[ \rho=P^{-30} \tag{40}\] satisfies every partition constraint as well. Their exponential number does not change this uniform estimate.

There is also a uniform outer ball. Testing [eq:ta-K] against the centered identity gives \(\mathop{\mathrm{tr}}Y\le6m\). Taking traces in the second LMI of [eq:ta-conic-representation] gives \(\sum\lambda_{ijk}\le3m\). Together with \(0\le y_e\le1\) and \(0\le z_e\le\kappa+1\le2\), these bounds place all free coordinates in the ball of radius \(P^3\). We may impose the larger radius \(2P^3\) with slack. This ball also has an exact rational separator: for a rational query \(a\) with \(\|a\|>R\), the inequality \(a\cdot x\le(R^2+\|a\|^2)/2\) contains the radius-\(R\) ball and strictly excludes \(a\), by Cauchy–Schwarz and the arithmetic–geometric mean inequality. All ball constants have logarithmic encoding length in \(P\). The rational central-cut ellipsoid procedure, using 9, now finds an exactly feasible point in polynomial work (Grötschel et al. 1988, Theorem 3.2.1 and its proof). Indeed, use our exact membership test at every oracle query and choose the enclosing-volume cutoff below \((2\rho/D)^D\), the volume of a coordinate cube contained in the proved radius-\(\rho\) inner ball. The small-volume outcome is impossible, so the algorithm must terminate at an exactly accepted rational point. This argument uses the displayed positive inradius; it does not assume exact solvability of an arbitrary semidefinite feasibility problem.

To bound the returned denominators independently of those in \(u\), put \(L=\lceil\log_2P\rceil\), \(\eta=2^{-32L}\) and \(\gamma=2^{-36L}\), and instead find \(x\) such that \[ x\pm\eta e_j\in\mathcal F \qquad(1\le j\le D), \tag{41}\] where \(\mathcal F\) is the full step feasible set, including the outer bound. The intersection of these \(2D\) translates still contains a ball of radius at least \(\rho-\eta\ge3\rho/4\), and has a separation oracle by translating the queries. Use the corresponding volume cutoff with \(3\rho/4\) in place of \(\rho\). Convexity implies that the cross-polytope \(\{x+v:\|v\|_1\le\eta\}\) lies in \(\mathcal F\). Round each coordinate of \(x\) to the fixed dyadic mesh \(\gamma\). Its total rounding error is at most \(D\gamma/2\le\eta/(2P)<\eta\), so the rounded point remains feasible. The outer bound gives at most \(39L+O(1)\) bits per coordinate. This argument does not round a boundary solution without a margin.

Finally \(s\) and \(Q\) have polynomial encoding length throughout the prescribed schedule. At a rational \(X\succeq L_H\), its centered inverse and all old \(u_e\) are computed exactly with polynomial bit operations. Every new \(Y\) lies on the fixed grid just described. Forming \(X^+=(1-t)X+tY\) increases encoding length by only a polynomial additive amount per step. Over the polynomial number of steps neither denominators nor oracle work can cascade beyond polynomial size. ◻

Proof of 7. Apply [lem:ta-continuation,lem:ta-bits] at every step. The computed capacities satisfy [eq:ta-computational-packing]; [eq:ta-ramp-lower] therefore preserves [eq:ta-invariant] with target \(Q^+\). At termination \(s\ge r^{1/4}\), and every active edge has \(R_e(X)<1/s\le r^{-1/4}\). Dropping the baselines loses less than one across any partition, and \(u_e\le1\) gives \[|E_G(\mathcal P)|\ge Q(|\mathcal P|-1)-1 \ge (Q-1)(|\mathcal P|-1) \quad(|\mathcal P|\ge2).\] Hence [eq:ta-integer-packing] supplies \(\lfloor Q-1\rfloor\) disjoint spanning trees. Construct them by the graphic-matroid union procedure stated above. By [eq:ta-target-bound], their number is \(r(1-O(r^{-1/8}(1+\log r)))-O(1)\), which is at least \((1-Ar^{-1/16})r\) after enlarging \(A\) and \(r_0\). All steps have the claimed polynomial bit complexity. ◻