Proof. We first prove the generating-function identity, then the exposure formulas and the assertion about positivity.

The matrix \(Q_j\) counts weighted nonbacktracking stub walks. A resolved traversal is deterministic; an unresolved traversal lands uniformly in \(S\), independently on each use. After landing, the arrival stub is excluded from the next departure. Thus every row sum is \(dq^{j-1}\) for \(j\ge1\). Since \(P_*^3=P_*\), \[CP_*^2(C^TC-I)P_*=(D_e-I)CP_*.\] Expansion gives \(Q_1=A_e\), \(Q_2=A_e^2-D_e\), and \(Q_j=A_eQ_{j-1}-(D_e-I)Q_{j-2}\) for \(j\ge3\). Consequently \[\sum_{j\ge0}(\sigma h)^jQ_j =(1-h^2)[I-\sigma hA_e+h^2(D_e-I)]^{-1}=W.\] For the exposure identities, write \(a=e_{v(u)}\), \(b=e_{v(v)}\) and replace \(t\) by \(t-a-b\) and \(l\) by \(l-2\) in \(\mathcal D=\operatorname{diag}(t)-tt^T/l\) and \(A_e=A+tt^T/l\). Direct expansion gives the displayed formulas. The Woodbury inverse formula [14] applies because \[[m_h(hI-\sigma F)B]^{-1}+G_0=H_0^{-1}.\] It remains to verify preservation of positivity. Both \(m_h(hI-\sigma F)B\) and \(H_0^{-1}\) have one positive and one negative eigenvalue, bounded away from zero uniformly in the prescribed range. The perturbation \(D_p=o(1)\) preserves the latter inertia.

We recall the block congruence behind the Schur-complement argument. For real symmetric blocks \(\mathsf A,\mathsf D\) with \(\mathsf A\) invertible, and a compatible real rectangular block \(\mathsf B\), define \[\mathsf L= \begin{bmatrix}I&-\mathsf A^{-1}\mathsf B\\0&I\end{bmatrix}.\] Direct multiplication gives \[\mathsf L^T \begin{bmatrix}\mathsf A&\mathsf B\\\mathsf B^T&\mathsf D\end{bmatrix} \mathsf L =\begin{bmatrix} \mathsf A&0\\0&\mathsf D-\mathsf B^T\mathsf A^{-1}\mathsf B \end{bmatrix}.\] Since \(\mathsf L\) is invertible, the inertia of the original block matrix is the sum of the inertias of \(\mathsf A\) and \(\mathsf D-\mathsf B^T\mathsf A^{-1}\mathsf B\); here inertia records the numbers of positive, negative, and zero eigenvalues. When \(\mathsf D\) is invertible, the same identity with the block order exchanged gives the other Schur complement.

With \(K=(hI-\sigma F)B\), apply the two Schur complements to \(\left[\begin{smallmatrix}M&U\\U^T&-K^{-1}\end{smallmatrix}\right]\). One complement is \(M'\) and the other is \(-m_h(H_0^{-1}+D_p)\), proving that the inertia of \(M'\) equals that of \(M\). ◻

Proof. We first construct the core accounts and bound their change under rejection in the early phase. These bounds give a global path count and, in particular, the short-return count needed to identify bad stubs. We then bound proximity, perform cleanup, and verify that cleanup preserves the same core and path estimates.

Initial core accounts. Suppressing degree-two vertices in a core leaves a bounded-size multigraph, apart from the separate case of a cycle. Its subdivisions with at most \(r_*J\) edges give \((1+\log n)^{O(r_*)}\) shapes. Cores with a vertex of degree exceeding \(d\) need not be included.

We use the following form of the perfect-hash-family theorem [25]: an \(n\)-element set has an explicitly constructible \(k\)-perfect family of maps to \(k\) colors, of size \(\exp(k) k^{O(\log k)}\log n\), constructible in \(\exp(k) k^{O(\log k)}n^{O(1)}\) time. This is the specialization \(\ell=k\) of their splitter theorem: splitting a \(k\)-element set equally among \(k\) colors makes the map injective on that set. The bounded case \(k=1\) uses a single constant map. For \(k=v_H\), sum the unrestricted completion probabilities over embeddings colorful for each map. Every embedding is included at least once. If an embedding is already incompatible with the partial pairing it contributes zero; if it has \(p\) demanded pairs still pending, it contributes \[f_p(l)=\prod_{i=1}^p(l-2i+1)^{-1}.\] For one coloring the number of colorful ordered vertex assignments is at most \(k!(n/k)^k\). At the empty pairing the proper stub assignments contribute \(\prod_x(d)_{\deg_H(x)}\), where \((d)_j\) is a falling factorial. Since \(e_H\ge v_H\) and \((d)_j\le dq^{j-1}\), \[\frac{\prod_x(d)_{\deg_H(x)}}{d^{e_H}} \le d^{v_H-e_H}q^{2e_H-v_H}\le q^{e_H}.\] Stirling’s estimate cancels the factor \(\exp(k)\) against \(k!/k^k\), leaving only a polynomial factor in \(k\). Since \(k=O_d(\log n)\), the remaining factor \(k^{O(\log k)}\log n\) is \(n^{o(1)}\). The initial account is therefore at most \(n^{1-r+o(1)}q^{s_H}\).

We use color-coding on a bounded-width tree decomposition, following Alon, Yuster and Zwick [3]; the states below also retain prescribed stub assignments and pending demanded-pair counts. These colorful sums do not require enumeration of \(n^k\) assignments. Choose a spanning tree of \(H\) and a width-one tree decomposition of that tree. Add the endpoints of the \(r\) non-tree edges to every bag. Every edge of \(H\) is then covered, the bags containing each vertex remain connected, and the width is at most \(2r+1=O(r_*+1)\). In a bag record its vertex and stub assignments, the subset of colors used in the processed part, and the number of pending demanded pairs. At a join the color subsets must be disjoint off the bag. At an edge check its two stub statuses and increment the pending count when appropriate. After totaling by that count, multiply by \(f_p(l)\). There are \(2^{O(k)}n^{O(r_*+1)}\) states and transitions, including joins; all counts and probabilities have polynomial bit length.

Change under rejection. Under unrestricted exposure this account is a martingale. It remains to bound the cost of restricting to accepted pairs. Conditional on an eventual matching containing \(p\) demanded pairs, the next exposed pair is one of these pairs with total probability \(2p/l\); otherwise it is a uniform pair on the other \(l-2p\) stubs. Deleting \(2p\) vertices from a rejected-pair graph of maximum degree \(D_g\) changes its rejected-pair proportion by \(O(pD_g/l^2)\). The contribution of demanded hits to a possible increase in acceptance probability is also \(O(pD_g/l^2)\). Bayes’ formula thus bounds the account’s conditional expectation by \(1+O(pD_g/l^2)\) times its present value. Summing to \(l_1\) costs \(\exp(O(r_*JD_g/l_1))=1+o(1)\). Normalize by \(n^{1-r}q^{s_H}\) and apply the joint account rule.

Global path diagrams and short returns. At every early-phase state, (4) with \(r_*>10\), increased if necessary, bounds a core of excess \(r_*\) and at most \(r_*J\) edges by \(n^{1-.1r_*+o(1)}<1\). Thus no such actual core occurs.

A connected union of a fixed number of actual nonbacktracking walks, with total length at most \(r_*J\) and a fixed number of marked endpoints, has excess less than \(r_*\). Otherwise retain a connected subgraph of excess \(r_*\) and prune its leaves, contradicting the absence of such cores just proved. Suppressing unmarked degree-two vertices leaves boundedly many vertices, so the number of diagram shapes is \(n^{o(1)}\). A diagram with \(e'\) edges and excess \(r\) has at most \[n^{1-r+o(1)}q^{e'}\] embeddings: apply (4) to the core and extend its bounded-leaf trees at cost \(Cq^{e'-s_H}\); for a tree use \(Cnq^{e'}\). The number of walk descriptions in an embedded diagram is bounded by a constant depending on the fixed parameters. Indeed, branching is possible only at boundedly many marked or branch vertices, and two visits to the same such vertex are separated by at least \(g_0\) steps. The ratio \(r_*J/g_0\) is bounded independently of \(n\).

In particular, the union traced by a nonempty nonbacktracking return of length \(k\) contains a cycle, so its excess is at least one and it has at most \(k\) edges. The global diagram count therefore gives at most \(n^{o(1)}q^k\) such return walks. Summing over \(k\le R_0\) and allowing at most \(d\) unresolved stubs at each vertex gives at most \(n^{o(1)}q^{R_0}\) return-bad stubs. This deduction uses only the early-phase core bound and girth exclusion already established.

Proximity at the end of the early phase. For proximity at \(l_1\), count simple paths of lengths \(0\) through \(R_0\) with two distinguished, distinct endpoint stubs required to survive until \(l_1\). For an assignment with \(p\) pending required pairs and \(r\) marked surviving stubs, its completion probability is \[\frac{(l_1)_r\,2^p((l-l_1)/2)_p}{(l)_{r+2p}},\] with value zero for incompatibility. This follows by assigning stubs to the future pair slots and the final surviving slots of a uniform permutation. Multiply the contribution by \(w^p\), with \(w=1+CD_g/l_1\). A demanded next hit removes one factor \(w\) and hence pays its entire rejection inflation. Conditional on a successful non-hit, the pair is uniform on the ordinary stubs; deleting the \(2p+r\) distinguished stubs costs only \(1+O((p+r)D_g/l^2)\). The initial normalized colorful sum is \(n^{o(1)}\): without normalization its expectation is \[n^{o(1)}O\left(q^{R_0}\operatorname{polylog}(n)l_1^2/n\right).\] For positive-length paths this follows by choosing proper incidences, paying \((dn)^{-j}(1+o(1))\) for the \(j\) edges and \(O((l_1/n)^2)\) for the two surviving flags; length zero obeys the same bound. Together with the return-bad count above, this bounds all bad stubs. Both contributions are \(o(b)\), since \[q^{R_0}l_1^2/n=n^{1/3+.34a+o(1)},\qquad b=n^{1/3+.345a+o(1)}.\]

Cleanup. The preceding bounds leave enough steps to resolve every bad stub. Fix the bad set at \(l_1\). Resolve each bad stub as first endpoint, choosing its partner uniformly among surviving initially clean stubs. Then use any surviving first stub and choose its partner uniformly among the eligible surviving initially clean stubs until \(l_0\); there are exactly \(b\) steps available. An untouched clean stub is initially farther than \(R_0\) from every other unresolved stub. A path of length at most \(R_0\) starting there cannot reach a new cleanup edge: before its first such edge it would already reach an initial unresolved vertex in the initial graph. Its short-path and short-return properties therefore persist. Every cleanup pair is admissible, and the asserted final separation follows.

It remains to preserve the core accounts during these cleanup steps. Multiply \(f_p(l)\) by \((1+Cb/l_0)^p\). If the fixed first stub is demanded, success requires its unique demanded partner; deletion of at most \(O(b)\) possible partners is paid by the lost weight. Otherwise a successful exposure has probability ratio at most \(f_p(l-2)/f_p(l)=1+O(p/l)\), irrespective of the omissions. The total discount cost is \(\exp(O(r_*Jb/l_0))=1+o(1)\), as is the change on reinitializing the weights. This completes the simultaneous account construction. The core bound and girth exclusion therefore hold through cleanup, so the global diagram and short-return estimates proved above remain valid there as well. ◻

Proof. Coefficient majorants and the first row sum. An entry involving at least one virtual traversal at length \(k\) is at most \(Ckq^k/l\): mark one such traversal, sum prefixes by the row sums, pay its uniform landing factor \(1/l\), and sum suffixes backwards using reversibility and the same row sums. This overcounts and hence is an upper bound. Vertex centering contributes \(dq^{k-1}/n\); averaging an endpoint against the unresolved stubs contributes at most \(Ckq^k/l\). The length-zero corrections are \(O(1/l+1/n)\). These estimates prove the coefficient majorants and the stated bound on \(\mathsf U_l(h)\). Reversing a walk proves symmetry. For (5), each vertex has at most \(d\) unresolved stubs, so the actual length-\(k\) row sum is at most \(C_dq^k\). Summing with weights \(h^k\) and adding \(l\mathsf U_l(h)\) proves the claim. These arguments use no core or girth hypothesis.

For the remaining estimates we use the stated structural hypotheses.

Actual-walk row squares. First consider actual walks from a fixed vertex to unresolved stubs. In the squared weighted sum, identical walks contribute at most \(d\): choose the initial departure uniformly among \(d\) stubs and successive departures uniformly among \(q\) alternatives, stopping at the first unresolved departure. A stopped walk of \(k\) actual steps has probability \(d^{-1}q^{-k}\), which dominates \(d^{-1}h^{2k}\).

For two distinct walks ending at the same unresolved stub vertex, remove their common terminal segment. Summing the possible common continuations with squared weights again costs at most \(d\) by the stopping argument. The remaining pair forms a cycle-containing diagram rooted at the initial vertex, with no other possible leaf. If its total length \(u\) is at most \(J\), the rooted-family argument above bounds its number by \(n^{o(1)}\), and \(u\ge g_0\) makes its total weighted contribution \(o(1)\). If \(J<u\le2L\), take a sufficiently large fixed \(p\)-th moment over roots. In a union of \(p\) such diagrams every edge-adding diagram increases excess, so a union of excess \(r\) has at most \(\min(p,r)u\) edges. The global embedding bound gives a moment at most \[n^{1+o(1)}(1+q^u/n)^p.\] Here \(r_*\) is chosen large enough to cover all \(p\) diagrams. Thus each root’s count is at most \(n^{1/p+o(1)}(1+q^u/n)\). After multiplication by \(q^{-u/2}\) this is bounded by \[n^{1/p+o(1)}(q^{-J/2}+q^L/n)=o(1)\] for, for example, a sufficiently large fixed \(p>4\). Summation over the polylogarithmically many length choices preserves the decay. This proves the actual row-square bound, with constant depending only on \(d\) once \(n\) is large enough.

Adding the virtual and centering terms costs \(O((1+L)^4q^L/l)=o(1)\) in row-square sum, by \(l\ge l_0\) and the prescribed relation between \(L\) and \(l_0\). Thus the actual-walk bound also proves the first estimate in (6).

Return bounds. The global number of return walks of length \(k\) is at most \(n^{o(1)}q^k\), proving the first-power bound on \(j\). For its square, pair two return walks of lengths \(k,k'\). Excess at least two costs at most \(n^{-1+o(1)}q^{(k+k')/2}\) after weighting, whose sum is \(o(1)\). At excess one the union consists of a root-to-cycle tail and the cycle. Each return covers all these edges, so their number is at most \(\min(k,k')\); its weighted embedding bound is \(n^{o(1)}\). This proves the return-square bound, after absorbing subpolynomial factors in the prescribed \(n^\eta\).

Decay at admissible pairs. For an admissible pair, girth and endpoint distance exclude all short nonconstant terms. Bounded fixed-endpoint multiplicity bounds the remaining sum by \(C\sum_{k\ge g_0}q^{-k/2}\), in addition to the power-small uniform errors. The degree-zero centered Gram error is \(O(1/l)\), even with other stubs at either vertex. Fixed powers of \(k\) do not change the resulting positive decay exponent. ◻

Proof. Operator bounds. On \(\mathbf1^\perp\) put \(F(z)=I-zA_e+z^2(qI-\mathcal D)\). For a complex unit vector \(v\), \(v^*F(z)v=1-xz+yz^2\) has real \(x,y\) and \(y\le q\). A nonreal pair of roots has modulus \(y^{-1/2}\ge q^{-1/2}\). A real root in \((-h,h)\) is also impossible. Endpoint positivity would require another root on the same side of zero in that interval, but their product would be less than \(h^2\le1/q\), contradicting \(1/y\ge1/q\). Linear polynomials and polynomials with roots of opposite signs are excluded directly by the endpoint signs. Thus every root has modulus at least \(h\). Factoring the scalar polynomial shows \[|v^*F(z)v|\ge(j+1)^{-2} \quad\text{when }|z|=h\left(1-\frac1{j+1}\right),\quad j\ge1.\] Since \(\|F(z)v\|\ge|v^*F(z)v|\), its inverse has norm at most \((j+1)^2\). Apply the Cauchy coefficient formula to \((1-z^2)F(z)^{-1}\); the extra radius ratio is at most a fixed constant. This proves (9). Moreover, \(\|\xi_x\|\le C\), so \[\sum_i|P_{i,\xi_x}|^2=\|P\xi_x\|^2 \le C\|P\|^2\le C(1+L)^6,\] where \(i\) ranges over global vertices. This proves the signed column-square bound from positivity alone.

Column and entry bounds. We now combine the operator estimate with the path bounds. For actual paths of length \(j\) to a fixed endpoint, bounded multiplicity and the total path count give an \(\ell^3\) norm \(O(q^{-j/6})\) after weighting, which is summable. Uniform errors have total cube sum \(O(n[(1+L)^2q^{L/2}/l]^3)=o(1)\). This proves the cubic bound. For the refined constant, paths shorter than \(g_0/3\) are unique in total at fixed endpoints; their cube sums are at most \(1+\sum_{j\ge1}dq^{j-1}q^{-3j/2}\). Longer actual paths have power-small supremum and absolute aggregate squared sum \(O((1+L)^2)\), so their \(p\)-power sums tend to zero. The uniform correction has vanishing \(p\)-power sum by its cube bound and vanishing supremum. Apply the triangle inequality in \(\ell^p\). The same short/long separation proves the \(1+o(1)\) entry bound. The cubic column bound has a constant depending only on \(d\). Combining it with the entry bound gives, for every fixed integer \(p\ge3\) and all sufficiently large \(n\) (depending on \(p\)), \[\sum_i |P_{i,\xi_x}|^p \le (1+o(1))^{p-3}\sum_i |P_{i,\xi_x}|^3 \le 2C_d.\] Here \(i\) ranges over global vertex coordinates. Thus the large-power column constants needed in the early transition argument can be fixed before its scalar moment order. The same short/long separation also shows that choosing a fixed distance radius from a fixed positive entry threshold does not require fixing the later structural losses first. ◻

Proof. Reduction to the closest primary. We begin with the norm and spectral tail. Positivity at the closest primary controls the other primary groups directly; the closest group will require the auxiliary trace bounds.

For every primary group except the closest one, positivity at the closest point and integration of \(-\partial_hM(h)\) give \[M(h)\succeq c_d\alpha(\mathcal D+\alpha I).\] Indeed the interval between these points has length comparable with \(\alpha\), and on a fixed subinterval its value of \(1-qt^2\) is comparable with \(\alpha\). The claim follows there with norm \(C/\alpha\) and an empty tail. It remains to control the closest point.

A positive finite-difference filter at the closest primary. At that point put \(R_h=M(h)^{-1}=m_hW\), \(X=(B_h^+)^{-1/2}M(h)(B_h^+)^{-1/2}\) and \(S=X^{-1}\). Positivity, (10), and \(\operatorname{Tr}W=O(n)\) give a polynomial upper bound on \(S\). The bounds \(B_h^+\succeq c_d\alpha_*I\) and \(\|M(h)\|=O(1)\) give an inverse-polynomial lower bound. Set \(k=k_h\) and \(b=b_h=n^{-c}\alpha_*\).

For the linear pencil \(X+xI\), the alternating trace difference at \(0,b,\ldots,kb\) is the nonnegative quantity \[ \mathcal B:=\sum_{\lambda\in\operatorname{spec}S} \lambda\prod_{j=1}^k\frac{jb\lambda}{1+jb\lambda}. \tag{14}\] For \(b\lambda\) small, the product suppresses the contribution of \(\lambda\); for \(\lambda\ge C/b\), it is bounded below by a positive constant depending only on \(k,C\). A bound on \(\mathcal B\) therefore bounds the spectral tail that we need. We will obtain that bound from the trace laws for the actual pencil, by comparing its alternating trace difference with this linear one.

Write the actual pencil in the form \(X+xI+\gamma(x)H_*\), where \[H_*=(B_h^+)^{-1},\quad \gamma(x)=z(h-x)-z(h)-h^{-2}\alpha_*x,\quad T(x)=\operatorname{Tr}[X+xI+\gamma(x)H_*]^{-1}.\] Taylor’s formula gives \(\gamma(x)=O(x^2)\), \(\gamma'(x)=O(x)\), and bounded higher fixed derivatives on the interval used. At \(x=jb_h\), \(0\le j\le k_h\), the trace laws imply \[T(x)=m_{h-x}[(l-1)+h^{-2}\alpha_*(n-1)] +O(n^{.12a}/\alpha_*).\] Consequently, \[\left|\sum_{j=0}^k(-1)^j\binom kjT(jb)\right| \le C_k(n^{.12a}/\alpha_*+nb^k).\]

Comparison with the linear pencil. We show that the preceding trace difference is \(\mathcal B+o(1)+o(\mathcal B)\). The matrices \(X\) and \(H_*\) need not commute, so the comparison retains the order of all matrix factors. For \(X_g(x)=X+xI+\gamma(x)H_*\) and \(R(x)=X_g(x)^{-1}\), the divided-difference product rule applied to \(RX_g=I\) gives \[R[x_0,\ldots,x_k] =\sum_{0=i_0<\cdots<i_p=k}(-1)^p R(x_0)\prod_{t=1}^p \left(X_g[x_{i_{t-1}},\ldots,x_{i_t}]R(x_{i_t})\right),\] where products retain their displayed order and \(x_j=jb\). At nonzero nodes expand about \(A_j=(X+jbI)^{-1}\). Because \(\|\gamma(jb)H_*A_j\|\le Cb/\alpha_*=Cn^{-c}\), every such Neumann series can be truncated at a fixed order \(K\) with residual norm at most \(C_Kb^{-1}(Cb/\alpha_*)^K\). After multiplication by \(b^k\), every remaining factor, rank, and initial inverse norm is bounded by a fixed power of \(n\). Choosing \(K\) sufficiently large makes the sum of all residual traces \(o(1)\).

After multiplication by \((-1)^kk!b^k\) and taking the trace, the term with all first divided differences equal to \(I\) and all nodes unperturbed is exactly \(\mathcal B\). It remains to show that all other terms have total absolute value \(o(1)+o(\mathcal B)\). Use a common decomposition into the \(O(\log n)\) dyadic spectral blocks of \(S\) for \(S\) and every \(A_j\), all of which are functions of \(S\). In a nonzero block tuple let \(\lambda_0\) be its largest scale, and let \(r_0\) be the rank of a block at that scale. A cyclic trace is bounded by \(r_0\) times the product of operator norms, by starting the trace at that block. This choice is available even when the largest block occurs in an intermediate inverse: cyclicity moves that block to the beginning of the trace while retaining the cyclic order of all factors. Write \(s_0=\min(\lambda_0,b^{-1})\). The corresponding main scale is, within constants depending on \(k\), \(r_0\lambda_0(bs_0)^k\). This is an upper comparison scale for a mixed block tuple, rather than the value of that tuple. The initial inverse block has norm at most \(C\lambda_0\), and every nonzero-node inverse block has norm at most \(C_k s_0\), irrespective of where the largest block occurs. The contribution to \(\mathcal B\) from that largest spectral block is comparable to this scale, since on its dyadic interval \(\lambda\prod_{j=1}^k jb\lambda/(1+jb\lambda) \asymp_k\lambda_0(bs_0)^k\).

A perturbed first divided difference costs an extra \(O(b/\alpha_*)\). Each Neumann correction costs at most the same. Replacing \(r\ge2\) first divided differences and their intermediate inverses by a single span-\(r\) divided difference costs, relative to that main scale, \[O\left(\alpha_*^{-1}s_0^{-(r-1)}\right).\] If \(\lambda_0\ge n^{c/2}/\alpha_*\), every non-main product therefore has at least one power-small factor, while the other replacement factors are bounded. Summing the fixed powers of \(\log n\) and charging to the largest block bounds these terms by \(o(\mathcal B)\).

Below this threshold, bound absolutely instead. A span-one block, its following inverse, and one assigned factor \(b\) cost \(O(n^{-c/2})\). A higher span \(r\) with its following inverse and \(b^r\) costs \[O(b^r\alpha_*^{-1}n^{c/2}/\alpha_*)=O(n^{-rc/2});\] the omitted extra factor \(\alpha_*^{r-2}n^{-(r-1)c/2}\) is bounded. Node corrections are bounded as well. The sum of all such tuples is at most \(n^{1+o(1)}(n^{c/2}/\alpha_*)n^{-kc/2}=o(1)\), by the choice of \(k\). This proves the comparison with the linear pencil.

Spectral tail and transfer to auxiliaries. It follows that \(\mathcal B\le C_kn^{.12a}/\alpha_*\). For \(\lambda\ge C/b\), the product in (14) is bounded below by a positive constant depending only on \(k\) and \(C\). Hence the sum above that threshold, and then the norm, are at most \(n^{v_*}/\alpha_*\) for all sufficiently large \(n\). Passing between \(S\) and \(S_h\) only changes a fixed factor \(m_h\). At lower auxiliary nodes, \(M(h-x)^{-1}\preceq M(h)^{-1}\) and \(B_{h-x}^+=(1+o(1))B_h^+\) in relative positive order. The min–max principle transfers the ordered eigenvalue bounds, increasing the constant in the tail cutoff.

Local quadratic estimate. The spectral norm bound is now available at all tracked points. We use it to compare the inverse at a primary with its nearby auxiliary. If \(f\) is a global coordinate or a centered stub, the path estimates give \(P_{ff}=\|f_\perp\|^2+O(n^{-c_0'})\) and a power-small derivative of the nonconstant part. Compare \(R_h\) and \(R_{h-b'}\), where \(b'=n^{-.16a}\alpha\). Their precision difference is \[b'(B_h^+)^{1/2}(I+O(b'/\alpha))(B_h^+)^{1/2}.\] The proven norm bound gives \(b'\|S_h\|\le n^{(.125-.16)a}\), a negative power. The resolvent identity therefore gives the positive quadratic-form comparison \[R_h-R_{h-b'} =b'R_h(B_h^+)^{1/2}(I+O(n^{-c'}))(B_h^+)^{1/2}R_h\] for some fixed \(c'>0\). On a diagonal, the entry error divided by \(b'\) is at most \(Cn^{.53a}/(\alpha_*\sqrt{l_0})=O(n^{-.045a})\). Using \(m_h'/m_h^2=1+h^{-2}\) yields (11) at the primary. For a lower auxiliary point at distance \(x\), the normalized precision increment is \(x(I+O(x/\alpha))\). Put \(\widetilde S=(B_h^+)^{1/2}R_h(B_h^+)^{1/2}\succeq0\). The map on the vectors \((B_h^+)^{1/2}R_hf\) has the form \([I+x\widetilde S T_x]^{-1}\), where \(T_x=I+O(x/\alpha)\) is positive definite. Indeed, \[[I+x\widetilde S T_x]^{-1} =T_x^{-1/2} [I+xT_x^{1/2}\widetilde S T_x^{1/2}]^{-1}T_x^{1/2}.\] The middle factor has norm at most one, so the full norm is at most \(\sqrt{\|T_x\|\|T_x^{-1}\|}=1+O(x/\alpha)\). Moreover, \(B_{h-x}^+\) and \(m_{h-x}\) differ from \(B_h^+\) and \(m_h\) by relative \(O(x/\alpha)\), respectively. Since \(x/\alpha\) is power-small at every auxiliary, these comparisons transfer (11) to its own normalization at \(h-x\), after reducing \(c_1\). In particular \(\sum_xw_i(x)^2\le C\), global unweighted row squares are at most \(C/\alpha\), and \([(\Xi^TW\Xi)^2]_{xx}\le C\).

Averaged trace identity. Take the \(\mathcal D\)-weighted trace of the same \(b'\) resolvent difference. Its trace-law error after division by \(b'l\) is at most \(Cn^{(.09+.16)a}/(l\alpha_*\alpha)\), a negative power. Positivity and the relative error in the quadratic-form comparison, together with (11), give (12). Summing the global and stub versions of (11) also gives \(\mathcal T\le C\min(n,l/\alpha)\).

Moment bounds. We now combine the local quadratic estimate with the spectral bulk and tail bounds. To express the remaining moments in a common matrix, introduce \(Y=[\Xi,h^{-1}\sqrt\alpha I]\), with the identity projected onto \(\mathbf1^\perp\), and \(\mathcal A=Y^TWY\). Its nonzero eigenvalues are those of \(S_h\). Its stub block is \(\Gamma\), and the stub block of \(\mathcal A^2\) is \(K_{\rm all}+h^{-2}\alpha Q_{\rm all}\), of trace \(O(l)\) by (11). Split \(\mathcal A\) into its bulk and tail spectral parts. The bulk norm is \(O(n^c/\alpha)\); the tail trace is \(O(n^{v_*}/\alpha)\). Their squared parts have norm \(O(n^{2c}/\alpha^2)\) and trace \(O(n^{2v_*}/\alpha^2)\), respectively. Positive compression preserves these bounds. For a positive bulk compression \(C_b\), use \(\operatorname{Tr}C_b^2\le\|C_b\|\operatorname{Tr}C_b\); for a tail compression \(C_t\), use \(\operatorname{Tr}C_t^2\le(\operatorname{Tr}C_t)^2\). This proves the first estimate in (13). For the mixed estimate, split also the stub block of \(\mathcal A\); its bulk contributes \(O(n^cl/\alpha)\), and all terms involving its tail are bounded by \(O(n^{3v_*}/\alpha^3)\), since \(c<v_*\). Positive order gives the last operator bound. Together these estimates prove (13). ◻

Proof. Centering gives \(\sum_{u\ne v}A_{uv}=-\operatorname{Tr}A\). Insert \(B=I+J_2/(l-2)\) and \(H_0=-\sigma h(F+J_2/(l-2))\) to obtain the first two identities. Expansion of the last trace gives \(A_{vv}C_{uu}+A_{uu}C_{vv}+A_{uv}(C_{uv}+C_{vu})\). Summing its three terms proves the formula. Each stub has at most \(D_g\) forbidden partners, and survival excludes at most two stubs; the assertion about restriction follows by counting the available ordered pairs. ◻

Proof. We first compute the two centered trace increments. We then obtain the three estimates on \(\mathcal T\) needed to bound its reciprocal: the lower drift, second moment, and maximum relative increment. The terms containing the possibly large matrix \(J\) require separate estimates.

The centered trace errors.

From \(\mathcal D'=\mathcal D-U B U^T\), \[\Delta F_1=-\operatorname{Tr}B G-\operatorname{Tr}H K+\operatorname{Tr}B G H G .\] Expand \(H=H_0-H_0 D_p H_0+\cdots\). In the increment of \(L_1\), the constant \(-2\) cancels the change in its baseline \(l-1\). This gives \[ \Delta L_1= 2\operatorname{Tr}H_0 D_p-(1+h^2)\operatorname{Tr}B D_p-\operatorname{Tr}H_0 K +\operatorname{Tr}H_0 D_p H_0 K+O(\|D_p\|^2). \tag{17}\] Here \(H_0 G_0 H_0=h^2 B\). Under full uniform distinct sampling, the linear \(H_0\) contractions vanish and \(\mathbb E\operatorname{Tr}B D_p=2L_1/(l-1)\). The swap-swap term has diagonal contribution \(2 h^2 L_1\operatorname{Tr}K_{\rm all}/[l(l-1)]\), with same-index corrections \(O(1/l)\). Its remaining cross contribution is bounded by \(C(\operatorname{Tr}\Gamma^3+l)/l^2\); the \(O(1/l)\) changes in swap entries also cost \(O(1/l)\).

To restrict these polynomial terms to valid pairs, subtract an absolute error \(O(D_g/l)\) and divide by \(1-O(D_g/l)\). The remaining inverse series has expectation \(O(n^\eta/l)\) by (16). Consequently, \[ \mathbb E\Delta L_1=a_l L_1+ O\!\left((n^\eta+D_g)/l+n^c/(l\alpha)+n^{3v_*}/(l^2\alpha^3)\right), \quad -C/l\le a_l\le n^{-c_3}/l \tag{18}\] for some \(c_3>0\). Before conditioning, the coefficient is \(\frac{2}{l-1}[h^2(\operatorname{Tr}K_{\rm all}/l-1)-1]\). Its stated bounds follow from the averaged upper bound in (11) and \(\|\xi_x\|^2=1+O(1/l)\). The positive normalization for valid pairs preserves these upper and lower bounds. Also, \[ \mathbb E(\Delta L_1)^2\le C\big(n^{2c}/(l\alpha^2)+n^{4v_*}/(l^2\alpha^4)+n^\eta/l\big). \tag{19}\] Indeed, the ideal \(K_{uv}\) term uses (13), while diagonal same-end ideal terms have coefficient \(O(1/l)\). All other terms use (16).

For the global trace, \(\Delta L_0=-\operatorname{Tr}H Q\). The ideal centered term has zero full mean. The term with a single \(D_p\) between pure swaps has diagonal main contribution at most \(C|L_1|/(l\alpha)\). Its cross contribution is bounded using \(\operatorname{Tr}(\Gamma+\Pi_l)Q_{\rm all}\), together with the same-index corrections. The remainder is \(O(n^\eta/(l\alpha))\). Thus, on valid choices, \[ \begin{split} |\mathbb E\Delta L_0|&\le C\big((|L_1|+n^\eta+D_g)/(l\alpha) +n^c/(l\alpha^2)+n^{3v_*}/(l^2\alpha^4)\big),\\ \mathbb E(\Delta L_0)^2&\le C\big(n^{2c}/(l\alpha^4)+n^{4v_*}/(l^2\alpha^6) +n^\eta/(l\alpha^2)\big). \end{split} \tag{20}\] The contractions used here can be read directly from Lemma 12: for \(K_{\rm all}=\Gamma^2\), \(\operatorname{Tr}(DK_{\rm all})= \operatorname{Tr}(\Gamma^3)-\operatorname{Tr}(\Gamma^2)\), and for \(Q_{\rm all}\succeq0\), \(\lvert\operatorname{Tr}(DQ_{\rm all})\rvert \le\operatorname{Tr}(\Gamma Q_{\rm all})+\mathcal T\). The diagonal exclusions are bounded using \(K_{xx}\le C\), \(Q_{xx}\le C/\alpha\), and \(\sum_x|D_{xx}|\le n^{\eta/2}\sqrt l\). Terms with two or more \(D_p\) factors have absolute value at most \(C\|D_p\|^2\), respectively \(C\|D_p\|^2/\alpha\), because the remaining inverse series is geometric. Their expectations are bounded by (16). The ideal variances are \(C\operatorname{Tr}(K_{\rm all}^2)/l^2\) and \(C\operatorname{Tr}(Q_{\rm all}^2)/l^2\), respectively; applying (13) gives exactly the first two summands of (19) and (20).

Lower drift of \(\mathcal T\). To prove (15), we will control the reciprocal statistic. We first bound \(\mathbb E\Delta\mathcal T\) from below. The exact update of \(\mathcal T\) is \[ \Delta\mathcal T= -\operatorname{Tr}\big[B(I-GH)Q(I-HG)\big]-2\operatorname{Tr}H J +\operatorname{Tr}H Q H K . \tag{21}\] Using \(G_0,H_0\) in the outer terms, their full-pair mean divided by \(\mathcal T\) is \[\frac{2}{l-1}\,[h^2(\operatorname{Tr}K_{\rm all}/l-1)-1] + O((1+\|\Gamma\|^2)/l^2).\] For the first outer term, expand \(I-G_0H_0=I+\sigma h F\). The centered \(F B\) term averages to zero, and the other contribution is \(-2(1+h^2)/(l-1)\). For the last term, use the same opposite-diagonal swap average. Its cross trace satisfies \(\operatorname{Tr}K_{\rm all} Q_{\rm all}\le\|\Gamma\|^2\mathcal T\); the diagonal exclusions and \(O(1/l)\) swap errors use \(K_{xx}\le C\).

At primaries, (12) therefore bounds this relative drift below by \(-C\alpha\mathcal T/l^2 -n^{-c_4}/l\). Pair smallness and (16) bound the change from the ideal outer terms, on valid pairs, by \(n^{-c_4}\operatorname{Tr}Q\), decreasing \(c_4>0\) if necessary. The invalid ideal contributions have average \(O(D_g\mathcal T/l^2)\).

For the \(J\) term, the ideal contraction \(H_0J\) has zero full mean. In the term with one deviation, \(H_0D_pH_0J\), diagonal factorization uses \(\operatorname{Tr}J_{\rm all}=\operatorname{Tr}\Gamma Q_{\rm all}\), and the cross trace uses \(D=\Gamma-\Pi_l\). The swap average is therefore bounded by \[C\bigl(|L_1|\|\Gamma\|+\|\Gamma\|^2+\|\Gamma\|\bigr) \mathcal T/l^2,\] apart from same-index exclusions, invalid pairs, and the \(O(1/l)\) changes in the swap coefficients. This main bound is power-small relative to \(\mathcal T/l\), since \(\lvert L_1\rvert\le n^{.075a}/\alpha_*\) and \(n^{2v_*}/(l\alpha_*^2)\ll1\).

To handle the exclusions and coefficient changes, including the invalid-pair part of the ideal \(J\) contraction, use \[|J_{xy}|\le C\sqrt{(Q_{\rm all}^2)_{yy}},\quad \sum_y\sqrt{(Q_{\rm all}^2)_{yy}}\le C n^{v_*}\alpha^{-3/2}\sqrt{l\mathcal T}.\] Their mean, divided by \(\mathcal T/l\), is at most \[\frac{C(D_g+1)n^{v_*}}{\alpha^{3/2}\sqrt{l\mathcal T}},\] which is power-small under the current lower bound (15). Finally, terms with at least two deviations use \(\mathbb E_{\rm valid}\|D_p\|^2\le Cn^\eta/l\) and \(\max|J_{xy}|\le Cn^{v_*}/\alpha^2\); their contribution is also power-small relative to \(\mathcal T/l\). Conditioning on valid pairs preserves the resulting lower drift bound. We have proved \[ \mathbb E\Delta\mathcal T/\mathcal T \ \ge\ -C\alpha\mathcal T/l^2-n^{-c_4}/l \tag{22}\] with some \(c_4>0\), for sufficiently small \(\theta,\eta\).

Second moment and maximum increment of \(\mathcal T\). In (21), the outer terms are bounded by \(C\operatorname{Tr}Q\), giving second moment \(C\mathcal T/(\alpha l)\). The off-diagonal \(J\) terms use \(\|\Gamma Q_{\rm all}\|_F^2\le Cn^{4v_*}\mathcal T/\alpha^5\). For a diagonal \(J_{uu}\), the coefficient \(H_{uu}\) has conditional squared average at most \(Cn^\eta/l\) over a uniform valid partner. Indeed, expansion around \(H_0\) gives \[ |H_{uu}|\le C(1/l+|D_{vv}|+|D_{uv}|) \tag{23}\] on valid pairs: the first pure swap from \(u\) touches \(v\), all other factors are uniformly small, and a non-pure initial swap costs \(O(1/l)\). The conditional claim follows from (16) and \(D_g\ll l\). Also, the norm bound times the trace gives \[\sum_u J_{uu}^2\le C\operatorname{Tr}Q_{\rm all}^2 \le Cn^{2v_*}\mathcal T/\alpha^3.\] Consequently, \[ \mathbb E(\Delta\mathcal T)^2\le C\left(\frac{\mathcal T}{\alpha l}+ \frac{n^{4v_*}\mathcal T}{\alpha^5 l^2} +\frac{n^{2v_*+\eta}\mathcal T}{\alpha^3 l^2}\right). \tag{24}\] Individually, \(\lvert\Delta\mathcal T\rvert\le Cn^{v_*}/\alpha^2\ll\mathcal T\) under (15). ◻

Proof. Trace-square accounts. Track \(1+L_i^2/S_i^2\), where \(S_1=n^{.065a}/\alpha_*\) and \(S_0=n^{.095a}/\alpha_*^2\). In (18), the coefficient contribution to square drift is at most \(2n^{-c_3}L_1^2/l\). Use \(2|L|/S\le1+L^2/S^2\) for each additive mean error. Since \(\sum l^{-1}=O(\log n)\), \(\sum l^{-2}=O(l_0^{-1})\), and \(\alpha_*^2l_0\asymp n^{1.15a}\), the normalized mean and variance budgets for \(L_1\) are bounded by fixed multiples of \[(n^{\eta-.065a}\alpha_*+n^{-.063a}\alpha_*+ n^{-.035a})\log n+n^{-.840a} \quad\hbox{and}\quad n^{-.070a}\log n+n^{-.780a}+n^{\eta-.130a}\alpha_*^2\log n.\] Both tend to zero. The \(L_0\) bounds follow from (20): the term involving \(L_1\) loses at most \(n^{-.020a}\log n\), and every other normalized term has a larger strict margin. This proves the two trace-square assertions.

The reciprocal account. Divide (24) by \(\mathcal T^2\) and sum using the current lower bound (15). The result is power-small; the particularly relevant bounds are \(n^{4v_*+\theta}(1/(n\alpha^5 l_0)+1/(\alpha^4 l_0^2))\ll1\). The maximum relative increment from Lemma 13 permits Taylor expansion of the reciprocal. Together with (22), this yields \[\mathbb E(1/\mathcal T')\le (1+u_l)/\mathcal T + C\alpha/l^2, \qquad \sum u_l=o(1)\] with deterministic nonnegative upper budgets under the caps. For \(f_l=1/n+\alpha/l\), use the account \(1+n^{-\theta/4}/(\mathcal T f_l)\). The scaled additive errors \(Cn^{-\theta/4}\alpha/(l^2f_{l-2})\) sum to \(o(1)\). This proves (15) with a positive power of slack. ◻

Proof. After item 1 is excluded, a swap changes an endpoint to its opposite. An intermediate diagonal \(T\) leaves that endpoint unchanged. An intermediate off-diagonal \(T\) puts the word in item 2. Exclude items 2 and 3. In a same-end word, the index immediately after the first swap and immediately before the last swap is \(\bar s\). If a local factor at \(\bar s\) never occurs, both these visits must be incident to the sole \(D_E\) factor. A swap between distinct intermediate positions changes the index, so a second intermediate position would force either another \(D_E\) or a local factor at \(\bar s\). Hence the sole intermediate is \((D_E)_{\bar s\bar s}\). In a distinct-end word consisting only of local factors, the number of intermediates is positive and even; the indices alternate, so both endpoints occur. These observations prove items 4 and 5 and their exhaustiveness.

For convergence, let \(\varepsilon_n\) bound the absolute entry sum of an intermediate \(T+D_E\) block on a valid pair. Equations (7) and the entry bootstrap imply \(\varepsilon_n\to0\). There are at most \(4^{m+1}\) endpoint index strings with \(m\) intermediates. If at most \(b\) positions are marked, summation of the unmarked positions is dominated by \[C_b\sum_{m\ge b}(m+1)^b(C\varepsilon_n)^{m-b},\] which is bounded for large \(n\). A non-pure swap at a marked position contributes \(C/l\). The coefficientwise absolute majorants of the tail have the same convergence after its degree restriction is discarded. This proves the final assertion and also justifies termwise expectation and the use of Minkowski’s inequality for second moments. ◻

Proof. First consider words without intermediate factors. Their exact \(H_0\) contraction is zero for a full ordered distinct pair by (3); the same statement holds coefficientwise for the pure-\(P\) tail. Omitting at most two labels costs \(C/l^2\), using their bounded entries and the squared row bounds in (3). If \(\mathcal B\) is the symmetric forbidden-pair indicator, then \(\|\mathcal B\|\le D_g\). Thus an opposite-outer product on forbidden pairs has sum at most \(D_g\|r_i\|_2\|r_j\|_2\le CD_g\). A same-end product has at most \(D_g\) partners and an extra \(1/l\) from its non-pure swap. After division by \(l(l-1)\), the forbidden-pair cost is \(CD_g/l^2\).

Next retain exactly one intermediate \(D_E\), no topology factor, pure swaps, and arbitrary \(W\) outers. This groups all outer choices without losing their signs. Write \[Y_E=\operatorname{Tr}(\Xi^TE\Xi),\qquad |Y_E|\le |L_1|+Q_a,\qquad \|\Xi^TE\Xi\|\le Cn^{v_*}/\alpha+C(1+L)^3.\] For same outer endpoint \(u\), the numerator sum is \[\sum_{u\ne v}w_i(u)w_j(u)e_v(v) =Y_E\sum_u w_i(u)w_j(u) -\sum_u w_i(u)w_j(u)e_u(u),\] whose magnitude is \(C(1+|Y_E|)\). For distinct outer endpoints it is a bilinear contraction of \(\Xi^TE\Xi\) with two bounded \(\ell^2\) rows, after a diagonal exclusion, and is bounded by \(C(1+\|\Xi^TE\Xi\|)\). On a surviving set \(I\) obtained by deleting at most two output labels, the same-end numerator is \[\left(\sum_{v\in I}e_v(v)\right) \left(\sum_{u\in I}w_i(u)w_j(u)\right) -\sum_{u\in I}w_i(u)w_j(u)e_u(u),\] and is still bounded by \(C(1+|Y_E|)\): the first diagonal sum changes by \(O(d_m)\), and the second factor is bounded by the two row norms. For distinct outer endpoints, deleting a bounded number of rows or columns changes the bilinear numerator by \(C\). The required bounded \(\ell^2\) rows of \(\Xi^TE\Xi\) follow from \(E=W-P\) and the stub-row square bounds for \(W\) and \(P\) in (11) and (6). Forbidden-pair subtraction costs \(CD_g\) by the preceding operator-norm argument; the extra intermediate entries are bounded. These estimates give the \(n^{v_*}/\alpha_*\) contribution in (25).

Every remaining word is covered by Lemma 15. A non-pure swap gives \(C/l^2\) in first moment. A cross-topology word gives \(CQ_a/l^2\). If there is no cross topology and at most one intermediate \(D_E\) factor, a same-end topology word contains \(j_{\bar s}\), giving \(CQ_a/l^2\), and a distinct-end topology word contains a local factor, giving \(Cn^\eta/l^{3/2}\). A word with at least two intermediate \(D_E\) factors gives \(Cd_m^2/l\). These statements apply also when an outer is \(E\), since it is bounded by \(r_i\). They also apply to the coefficient tail by absolute majorization. The geometric summation in the classification lemma gives the same bounds for the entire series.

Finally, for a surviving stub, \(\xi'_x=\xi_x+(\xi_u+\xi_v)/(l-2)\). The old-axis entries of the new \(E\) have sup \(Cd_m\): this follows from the difference series, in which every numerical word contains an \(E\), and from (8). For a fixed other output \(i\), \(\mathbb E|E'_{ui}|+\mathbb E|E'_{vi}|\le C/\sqrt l\). Indeed the old entry has this bound by its squared row sum. In every update word the selected-axis outer is bounded and the other outer is at \(u\) or \(v\); averaging that outer uses \(\sum_xr_i(x)\le\sqrt l\|r_i\|_2\). The formal tail is bounded coefficientwise by the same argument. Thus the two first-order recentering terms have mean \(Cl^{-3/2}\), and the term changing both axes has mean \(Cd_m/l^2\). Their pointwise total is \(Cd_m/l\). This proves the stated bound. ◻

Proof. For large \(n\), \(g_0>2k\), so the short path is unique. Expand the square of the remaining actual paths. A summand consists of that short path and two nonbacktracking alternatives of lengths \(a_1,a_2<L\). Its union has a cycle; the alternative equal to the short path was removed. If the excess is at least two, the structural diagram estimate gives, after multiplication by \(h^{a_1+a_2}\), at most \(n^{-1+o(1)}q^{(a_1+a_2)/2+k}\). Summing the logarithmically many lengths is still at most \(n^{-1+o(1)}q^{L+k}=o(1)\).

For excess one the union is unicyclic. Suppress its forced tree tails at the two endpoints. A nonbacktracking walk can only follow one of the two cycle arcs, possibly with complete laps. If the short path uses one arc, every alternative distinct from it covers the other arc or completes a lap. If the short path stays in an attached tree, every alternative reaches the cycle and completes a lap. Consequently all edges outside the short path belong to each alternative, and \(e_H\le\min(a_1,a_2)+k\). The weighted embedding bound is therefore \[n^{o(1)}q^{e_H-(a_1+a_2)/2} \le n^{o(1)}q^k.\] The number of shapes, length choices, and walk choices is absorbed by an arbitrarily small fixed power. Bounded stub multiplicities change only constants. Finally there are \(O_k(l)\) near pairs, and the per-entry uniform and centering error is \(C(1+L)^2q^{L/2}/l\). Its square sum has the displayed size. ◻

Proof. The surviving stub diagonal. The single-intermediate exception of Lemma 15, with both outers equal to \(P\), is the copy increment \[Z_x=h^2[p_x(u)^2e_v(v)+p_x(v)^2e_u(u)].\] There is a fixed \(C_4<q^2\) such that \[ \sum_{x\in S,\ x\ne u}|p_x(u)|^4\le C_4. \tag{27}\] Indeed, let \(s_u\) be the number of unresolved stubs at the vertex of \(u\). Short paths of length less than \(g_0/3\) are unique in total at each endpoint. The degree-zero contribution, excluding \(u\), is at most \(s_u-1\). The positive-length contribution is bounded by \[\sum_{j\ge1}d(d-s_u)q^{j-1}q^{-2j} =\frac{d(d-s_u)}{q(q-1)}.\] For \(q=2\), the sum is at most 3; for \(q\ge3\), its maximum over \(1\le s_u\le d\) is strictly below \(q^2\). The long-path and uniform terms have vanishing fourth norm by (6)–(9). This proves (27) with a strict constant margin.

Summing over surviving \(x\) before averaging gives \[ \mathbb E\sum_{x\ne u,v}Z_x^2 \le(1+o(1))\frac{2h^4C_4}{l}T_S+Cd_m^2/l. \tag{28}\] For its two squared summands use (27) and then sum the opposite diagonal square. For the cross product use \[\sum_x\left(\sum_u p_x(u)^2\right)^2\le Cl, \qquad |e_u(u)e_v(v)|\le d_m^2.\] The conditional restriction has density \(1+o(1)\), so it preserves the strict margin.

After subtracting \(Z_x\), the remainder obeys \[ \mathbb E\sum_{x\ne u,v}|\Delta e_x(x)-Z_x|^2 \le C(n^\eta/l+d_m^4). \tag{29}\] Here is the complete reduction to the index-word cases. A distinct-end word has second moment \(C/l^2\) for each \(x\), by the first row of the averaging table. A non-pure same-end word has second moment \(C/l^3\). A pure same-end word with topology and at most one intermediate \(E\) has an opposite local factor or a cross-topology factor; its second moment is \(Cn^\eta/l^2\) by the third or fourth row of the table. A word with at least two intermediate \(E\)’s has second moment \(Cd_m^4/l\). If exactly one intermediate is \(E\), no topology occurs, and an outer is also \(E\), use \[\sum_s |e_x(s)|^2r_x(s)^2\le Cd_m^2\] in addition to the intermediate bound \(d_m\); this again gives \(Cd_m^4/l\). The only same-end word left after these tests is \(Z_x\), already removed. The formal tail follows the same tests, with no \(E\)’s; its zero-intermediate pure-swap word is necessarily distinct-end. The recentering terms contribute at most \(Cd_m^2/l\) after summing over \(x\). Summing the per-output bounds over at most \(l\) outputs and using the geometric Minkowski bound in Lemma 15 proves (29).

Deletion removes \((1-o(1))2T_S/l\) in expectation. The existing first-order square term is at most \(2\mu_l\sqrt{lT_S}\). Since \(h^4C_4<1\), choose a fixed \(\varepsilon>0\) such that \((1+\varepsilon)h^4C_4<1\). Apply \((x+y)^2\le(1+\varepsilon)x^2+(1+\varepsilon^{-1})y^2\) to \(Z_x\) and its remainder and then Young’s inequality to the first-order term. Some fixed part of the deletion remains available to absorb it. The resulting upper drift is \[\mathbb E T_S'\le T_S+ C(l^2\mu_l^2+n^\eta/l+d_m^4).\] The non-logarithmic quantities controlling the sum are \[\frac{n^{2v_*}}{\alpha_*^2l_0}=n^{-.900a},\quad \frac{q^L}{l_0}=n^{-.580a+o(1)},\quad \frac{D_g^2}{l_0}=o(1),\quad nd_m^4=n^{-1/3+1.020a+o(1)}=o(1).\] The other term in \(\mu_l\) costs only \(n^{2\eta}\log n\). A slightly larger small-power normalization makes the complete additive budget summably small.

Global diagonals. No deletion is used. The copy squares have expected sum at most \(CT_S/l+Cnd_m^2/l^2\), by the bounded fourth columns in Lemma 9. The classification just proved gives \(Cn(n^\eta/l^2+d_m^4/l)\) for the other squares. The first-order term is at most \(2\mu_l\sqrt{nT_V}\). At scale \(S_V=n^{\eta'}n/l_0\), the corresponding multiplier is bounded by \(C\mu_l\sqrt{l_0}/n^{\eta'/2}\), using \(2\sqrt{T_V/S_V}\le1+T_V/S_V\). The sum \(\sqrt{l_0}\sum\mu_l\) is at most an arbitrarily small power, and the summed variance divided by \(n/l_0\) has the same property. Choosing \(\eta'\) larger than the input losses proves the global diagonal bound with an arbitrarily small final loss.

Existing near pairs. For a fixed \(k\), there are \(O_k(l)\) near outputs. All non-copy variance terms cost \(C_k(n^\eta/l+d_m^4)\). For a copy term, at a fixed endpoint \(u\), \[\sum_{i,x:\,\operatorname{dist}(i,x)\le k} A_i(u)^2A_x(u)^2\le C_k.\] This follows by summing first over the bounded ball around \(x\), using the bounded sup of \(A_i(u)\), and then its squared column sum over stub \(x\). Consequently the copy variance costs \(C_kT_S/l\), rather than a self term involving \(T_{XS,k}\). The existing first-order term is \(C_k\mu_l\sqrt{lT_{XS,k}}\), and \(\sum\sqrt l\mu_l\) is bounded by an arbitrarily small power.

New near pairs. A newly near pair has a short simple path using the new edge once. For one of its two orientations, \(i\) is at old distance \(k_1\) from \(u\), \(x\) at old distance \(k_2\) from \(v\), and \(k_1+1+k_2\le k\). Each choice has bounded multiplicity. The expected sum of the squared new entries is at most \[ C_k\left(n^\eta+T_S+ \sum_{X'\in\{V,S\},\ j<k}T_{X'S,j}\right)/l. \tag{30}\] To verify this without discarding an aligned large reference entry, expand the old entry plus every index word. An old entry, or an outer \(E\) whose endpoint is opposite the associated short neighborhood, is summed by its squared row bound over the free opposite stub; bounded reverse neighborhood multiplicity gives \(C_k/l\). An aligned outer \(e_i(u)\) or \(e_x(v)\) charges \(T_{XS,k_1}/l\) or \(T_{SS,k_2}/l\), respectively. An intermediate \(E\) charges \(T_S/l\) when diagonal and \(C/l\) when off-diagonal, again by its squared rows. Other factors have bounded sup and can be summed geometrically.

It remains to check a pure reference-tail word. Any intermediate topology factor has second moment at most \(n^\eta/l\), even with the bounded short-neighborhood multiplicities; a misaligned outer has the same bound by its squared rows. For aligned outers, split off their unique short monomials. Lemma 17 charges the residual squares by \(n^\eta+C(1+L)^4q^L/l\), and the free opposite endpoint supplies \(1/l\). If both outers are their short monomials and there are no intermediate factors, a pure swap has total degree \(k_1+1+k_2<L\), so contributes nothing to the tail. A non-pure swap has coefficient \(O(1/l)\), which is already within the claimed bound. This exhausts the reference-tail cases. Recentring costs a smaller term, since its sup is \(Cd_m/l\). Minkowski’s inequality and the geometric word summation prove (30).

Finally choose the losses in a fixed finite order. Start with a structural loss \(\eta_0>0\) so small that \((20+4R_c)\eta_0<\eta\). Choose the normalization and extraction exponents for \(T_S\), \(T_V\), and then successively for \(T_{XS,0},\ldots,T_{XS,R_c}\), increasing the available exponent by at least \(2\eta_0\) at each use of a preceding estimate. Enlarge the first normalization enough to exceed twice the exponent in its cumulative first-order budget. Every cumulative additive cost is then \(o(1)\) after normalization, and every multiplier has bounded sum. There are only \(2R_c+O(1)\) accounts per tracked point. All extraction losses fit below the prescribed \(\eta\) by taking \(\eta_0\) smaller if required. This proves (26). ◻

Proof. For \(t\le2\), the second moment and Hölder’s inequality give \(C n^{-\beta t/2}\). For \(2<t<p\), interpolation gives \[(n^{-\beta})^{(p-t)/(p-2)}M^{(t-2)/(p-2)}.\] The exponent of \(M\) is at most \(t/p\). Absorb fixed constants by halving the positive exponent of \(n\), proving (31). For the kernel inequality, apply Hölder to the measure with density \(K\): its mass, \(f\) integral, and \(g\) integral are at most \(b\), \(b\int f\), and \(b\int g\). For the stated kernel, its row sum is bounded by the squared row bound and the bounded entry sup. The column sum for \(k=2\) is polylogarithmic by (9); for \(k\ge3\) it is bounded. Since \(|X|\ge c_dl\), this proves the marginal claim. Finally Lemma 9 bounds the relevant large-power column sums uniformly in the fixed order, and the squared row bound gives \(C_d(1+o(1))^{k-2}\) for row sums. With \(k\) fixed, this is at most \(2C_d\) for large \(n\). ◻

Proof. Put \(T_P=I-PUH_PU^T\). The exact inverse-update difference identity is \[(W-\mathcal Q(W))-(P-\mathcal Q(P)) =T_P(E-EUH_WU^TE)T_P^T.\] It follows either by multiplying the two inverse-update formulas or by using \(H_W-H_P=-H_P(U^TEU)H_W\). Thus the linear old-axis increment is \(T_PET_P^T-E\). Replacing \(H_P\) by \(-\sigma hF\) gives (33) and (34). The difference \(H_P+\sigma hF\) is power-small by (7) and its geometric series. The leftover one-axis forms are \(p_i(s)z_{tj}\) and their transposes; the two-axis forms are \(p_i(s)p_j(t)z_{cd}\), with coefficient \((H_P)_{sc}(H_P)_{dt}\) minus its pure-swap value.

The nonlinear term is \(-T_PEUH_WU^TET_P^T\), whose entries have sup \(Cd_m^2\). Its complete second-moment classification is as follows. Distinct outer endpoints use two squared rows and cost \(C/l^2\). Same-end words with two intermediate \(E\) factors cost \(Cd_m^4/l\). If one intermediate and one outer are \(E\), use \(\sum_s|e_i(s)|^2r_j(s)^2\le Cd_m^2\) and the second \(E\) bound to get the same estimate. If both \(E\)’s are outer factors and no intermediate \(E\) occurs, a same-end word has either a non-pure swap or an opposite local/cross-topology factor; its second moment is at most \(Cn^\eta/l^2\) by the averaging table. These are all possible placements of at least two \(E\)’s in Lemma 15. For a tail word there are no \(E\)’s: distinct-end words cost \(C/l^2\), and same-end words have the non-pure or opposite-topology factor and cost \(Cn^\eta/l^2\). Recentring has squared sup \(Cd_m^2/l^2\). The geometric Minkowski bound now proves (32); the sup claim follows also from (8).

For (35), follow the first pure swap in the \((s,s)\) entry of \(H_P\). By Lemma 15, either a non-pure swap occurs, or a local factor at \(\bar s\), or a cross factor occurs. Hence \[|(H_P)_{ss}|\le C(1/l+j_{\bar s}+b_{s\bar s}).\] Its conditional second moment is \(Cn^\eta/l\); its sup is \(n^{-c'_0}\). Multiply the second-moment bound by the \((k-2)\)-th power of this sup. Omitting a bounded number of partners only changes the bounded density constant. ◻

Proof. We separate mixed powers from pure powers. The low-square estimates and interpolation make every mixed contribution a power-small multiple of \(M_p/l\), whose sum is small. Pure powers can transfer pair moments to diagonal moments at rate \(C_pF_p/l\); their reverse transfer has the smaller rate \(C_pD_p^{\rm mom}/l^2\). Weighting the diagonal family by \(\kappa_p\) makes the first coefficient bounded when \(\kappa_p C_p\le1\), while the reverse coefficient \(C_p/(\kappa_p l^2)\) remains summable for fixed \(p\). Thus we must bound each family’s own \(1/l\) drift independently of \(p\), and verify these two transfer rates. A fixed threshold on the outer path entries will distinguish the pure powers that need this uniform bound from terms that gain a small factor. All expectations of nonnegative quantities below may be taken over independent uniform endpoints, losing a bounded density factor. For signed first-order terms we retain the survival-conditional mean (25). Throughout this proof constants marked \(C_p\) may depend on \(p\), whereas \(C_0,C_1\) do not.

First-order and residual terms. In the even-power Taylor formula, the first-order term has absolute mean at most \(p(\mu_l/B_e)|z_{ij}|^{p-1}\). The sum \(\sum_l\mu_l/B_e\) tends to zero by a power. Write \(r_{ij}=\mathcal N_{ij}/B_e\). Its sup is a fixed negative power of \(n\). For \(2\le k\le p\), \[|z_{ij}|^{p-k}\mathbb E|r_{ij}|^k \le C(1+|z_{ij}|^p) \frac{n^\eta/l^2+d_m^4/l}{B_e^2}.\] The sum of the displayed coefficient tends to zero. For \(k<p\), finite-term splitting costs only \(C_p\). For \(k=p\), use \(|a+b|^p\le2|a|^p+C_p|b|^p\) when separating the retained linear part from the residual. This incurs a factor 2, independent of \(p\), on the retained part.

Intermediate powers of linear terms. Fix \(2\le k<p\). The minimum of the positive interpolation exponents in (31), for the finitely many powers used below, is positive. Choose the kernel loss \(\eta_0\) less than half this minimum. For the first term in (33), integrating \(u\) uses \(\sum_u|p_i(u)|^k\le C_p\), producing \(C_p/l\). For fixed \(j\), interpolation in the free \(v\) row gives \[\mathbb E_v|z_{vj}|^k \le n^{-\delta}(1+R_j)^{k/p},\qquad R_j=\mathbb E_v|z_{vj}|^p.\] Hölder in the remaining output indices bounds the result by \(C_p n^{-\delta}M_p/l\). This derivation covers each of the four orientations and also diagonal outputs \(j=i\).

For (34) with \(s=t\), discard one bounded outer factor. Integration of the other outer over \(s\) gives \(C_p/l\), and interpolation in the independent diagonal input \(z_{\bar s\bar s}\) gives the power saving. If \(s\ne t\), retain \(|p_i(s)|^k\) and discard the other bounded outer. Interpolation over \(t\), conditional on \(s\), yields \(n^{-\delta}(1+R_s)^{k/p}\). Average the output factor first over \(j\), and apply the kernel inequality in Lemma 19 to \((i,s)\), with exponents \((p-k)/p\) and \(k/p\). The cost is \(C_p n^{\eta_0-\delta}M_p/l\). For a diagonal output, use \(|z_{ii}|^p\) instead of its output-row average in that kernel inequality. This proves the same bound.

A leftover one-axis term whose input endpoint differs from its outer endpoint uses the preceding one-axis calculation. If these endpoints coincide, its coefficient is \((H_P)_{ss}\); integrate the other selected endpoint first by (35), then use the row interpolation in \(z_{sj}\). Here the structural loss \(\eta\) is chosen below the interpolation saving, including when \(k=2\) in (35). For a leftover two-axis term retain the outer at \(s\). If its input is \(z_{ss}\), the coefficient includes \((H_P)_{ss}\), so (35) and diagonal interpolation apply after discarding the bounded outers. An input \(z_{\bar s\bar s}\) uses independent diagonal interpolation; an off-diagonal input uses the kernel argument just given. These three input types exhaust \(\{u,v\}^2\). Thus every intermediate Taylor power costs \(C_p n^{-\delta_p}M_p/l\) for some \(\delta_p>0\).

Pure powers for independent output pairs. The two-axis pure powers can be charged at once: \[\mathbb E_{i,j,u,v} |p_i(s)p_j(t)z_{cd}|^p \le \frac{C_p}{|X||Y|}\mathbb E_{u,v}|z_{cd}|^p \le C_pM_p/l^2.\] This holds also for diagonal inputs \(c=d\), because the outputs \(i,j\) remain independent. The leftover one-axis pure powers have either the pointwise power-small coefficient and a row integration, or (35) when input and outer endpoints coincide. Hence they cost a power-small multiple of \(M_p/l\).

It remains to sum the leading one-axis terms without multiplying all their pure powers by \(C_p\). Choose a fixed threshold \(\varepsilon_p>0\). The sum of terms with \(|p_i(u)|\le\varepsilon_p\) has pure moment at most \[C_p\varepsilon_p^{p-2}F_p/l.\] This follows from \(|p_i(u)|^p\mathbf1_{|p_i(u)|\le\varepsilon_p} \le\varepsilon_p^{p-2}|p_i(u)|^2\) and the row-sum bound. The threshold will be chosen last to make this coefficient as small as required. Every outer above the threshold is at actual distance at most a fixed \(R_c=R_c(p,d)\) from its selected endpoint, by the short-path and long-entry estimates in Lemma 9. For sufficiently large \(n\), \(g_0>2R_c\), so an output axis has at most one such endpoint.

If both output axes have large outers at the same endpoint, say \(u\), the corresponding pure powers have an extra \(1/l\) gain even after a \(C_p\) splitting. To see it for \(p_i(u)z_{vj}\), sum \(|p_i(u)|^p\) over \(i\), using its bounded column sum. Each \(j\) has only \(C_{R_c,d}\) stubs \(u\) in its near ball. Therefore \[\mathbb E_{i,j,u,v} \bigl[|p_i(u)z_{vj}|^p\mathbf1_{j\text{ near }u}\bigr] \le C_p\Phi_{SY}/(|X|l)\le C_pF_p/l^2.\] This calculation remains valid when several unresolved stubs have the same vertex; there are at most \(d\) such labels.

If the two large outers occur at opposite endpoints, there are at most two retained terms. Expand their \(p\)-th power, keeping both pure summands with coefficient 1. Each mixed term has positive powers \(t,p-t\), with \(0<t<p\), and is at most \[\frac{C_p}{l^2} \left(\int|z_{iu}|^{p-t}\,d\mu_X\right) \left(\int|z_{jv}|^t\,d\mu_Y\right).\] By (31) and the near-pair bounds, this is at most \(C_p n^{-\delta_p}(1+F_p)/l\). A single large term has no mixed powers. Finally the pure powers of all retained one-axis terms satisfy \[\mathbb E\sum_{\rm orientations}|h p_i(u)z_{vj}|^p \le C_0h^pF_p/l.\] Here \(C_0\) is independent of \(p\): there are only four orientations and four output types, their squared row constants depend only on \(d\), and their row \(p\)-sums are bounded by \(C_d(1+o(1))^{p-2}\le2C_d\) for each fixed \(p\) and large \(n\). The Young splittings separate a number of groups independent of \(p\) and retain the principal part with only fixed relative factors (at most 2 per splitting), and conditioning costs a bounded density factor, not a \(p\)-th power. Thus these operations only enlarge \(C_0\) by a constant independent of \(p\).

Pure powers for diagonal outputs. For a diagonal \(i=j\), an above-threshold orientation, say at \(u\), has retained terms \[A=2\sigma h p_i(u)z_{vi},\qquad B=h^2p_i(u)^2z_{vv}.\] Their pure powers obey \[\mathbb E|A|^p\le C_pF_p/l, \qquad \mathbb E|B|^p\le C_0h^{2p}D_p^{\rm mom}/l.\] The first is explicitly a pair-to-diagonal transfer. The second uses a row \(2p\)-sum with a constant independent of the fixed order, as above. For a mixed power \(|A|^t|B|^{p-t}\), first sum over \(u\); the outer power is \(2p-t\ge p+1\), so that sum contributes \(C_p/l\). Interpolate over \(i\) at fixed \(v\) in the positive power \(|z_{vi}|^t\), and then apply Hölder in \(v\) against \(|z_{vv}|^{p-t}\). This gives \(C_p n^{-\delta_p}M_p/l\).

The other diagonal two-axis term has off-diagonal input \(z_{uv}\). At least one of its two outer factors is below the threshold. Keep the other column \(p\)-power and sum it over \(i\); this costs \(C_p\varepsilon_p^p\Phi_{SS}/l\). A below-threshold same-end diagonal input costs \(C_p\varepsilon_p^{2p-2}D_p^{\rm mom}/l\). Below-threshold one-axis terms cost \(C_p\varepsilon_p^{p-2}F_p/l\). For a leftover diagonal one-axis term \(a_{st}p_i(s)z_{ti}\), distinguish its input endpoint. If \(t=s\), its coefficient is \(a_{ss}=(H_P)_{ss}\). Average the opposite selected endpoint first using (35), discard the bounded outer factor, and then average \((i,s)\). This gives \[\mathbb E|a_{ss}p_i(s)z_{si}|^p \le\frac{C_p n^{\eta-c'_0(p-2)}}l\Phi_{SX}.\] If \(t=\bar s\), the leftover coefficient has sup \(n^{-c}\) for some fixed \(c>0\). At fixed \(i\), sum the row \(p\)-power \(|p_i(s)|^p\) over \(s\), obtaining \[\mathbb E|a_{s\bar s}p_i(s)z_{\bar s i}|^p \le\frac{C_p n^{-cp}}l\Phi_{SX}.\] For a leftover two-axis term, the input \(z_{cd}\) is independent of the output \(i\). Discard one bounded outer factor and sum the other column \(p\)-power over \(i\), which gives \(C_p n^{-cp}(F_p+D_p^{\rm mom})/l\). For sufficiently large fixed \(p\) and sufficiently small losses, all these bounds are \(C_p n^{-\delta_p}M_p/l\). Thus every diagonal pure-power term has now been accounted for.

Combining pair and diagonal moments. Collecting the self-drift, the two transfers between moment families, and the summable errors gives, for a fixed \(C_1\), \[\begin{split} \mathbb E F_p'&\le \left(1+\frac{C_1+C_0h^p+\epsilon}{l}\right)F_p +\frac{C_p}{l^2}D_p^{\rm mom}+v_lM_p,\\ \mathbb E(D_p^{\rm mom})'&\le \left(1+\frac{C_1+C_0h^{2p}+\epsilon}{l}\right)D_p^{\rm mom} +\frac{C_p}{l}F_p+v_lM_p, \end{split}\] where \(\epsilon>0\) is any prescribed constant after the threshold is chosen, and \(\sum_l v_l=o(1)\). To obtain \(v_l\), sum the first-order and residual budgets and the terms \(C_pn^{-\delta_p}/l\); all have summably small totals. The coefficient of the nonsummable transfer \(C_pF_p/l\) depends only on \(p,d\) and the uniform row bounds. Constants depending on the resulting near radius \(R_c\) occur only with \(l^{-2}\) or with the power saving \(n^{-\delta_p}/l\), and are included in \(v_l\). The change of a denominator \(|S|\) to \(|S|-2\) contributes at most \(1+C_1/l\), with \(C_1\) independent of \(p\). Deletion of labels only lowers their unnormalized moment sums.

Choose \(p_0\) so large that \(C_0q^{-p_0/2}\le1\). For each even \(p\ge p_0\), choose \(0<\kappa_p\le\min(1,(1+C_p)^{-1})\), then choose the threshold so that \(\epsilon\le1\). Since \(h\le q^{-1/2}\), multiplication of the second inequality by \(\kappa_p\) and addition give (36) with, for example, \(C_*=C_1+4\). The reverse leakage \(C_pD_p^{\rm mom}/l^2\) costs \(C_p/(\kappa_pl^2)\) in the multiplier and has sum \(o(1)\). The multiplier from \(v_lM_p\) is at most a fixed \(C_p\kappa_p^{-1}v_l\), whose sum also tends to zero. This proves the required independence of \(C_*\) from \(p\). ◻

Proof of Proposition 11. At the empty state the accounts have the asserted initial values. Assume their conclusions at the current state. Each stub has at most \(D_g=O_d(q^{g_0})=o(l_0)\) forbidden partners, so \(l-1-D_g>0\) throughout this phase and the candidate set is nonempty. The deterministic implications (10)–(13) give the row, trace, and operator estimates used in the transition lemmas. Every available pair is small in its two-by-two deviation, so its next precision is positive by the inverse-update inertia argument. The structural accounts, Lemma 14, Lemma 18, and Lemma 21 can therefore be included in the same discounted total.

The high-moment discount loss is at most \(n^{C_*+1}\) for large \(n\) since \(\sum_l l^{-1}=O(\log n)\). Extraction of one entry from a uniform pair average costs at most \(d^2n^2\), and from a diagonal average costs less. Fixed \(\kappa_p^{-1}\) is harmless. Choose the even order \(p\) large enough that \((C_*+4)/p<.02a\). Then the discounted total and (36) imply \(\max|E_{ij}|<B_en^{.02a}=d_m\), with a positive power of slack. The trace and low-square accounts have their own exponent cushions. Thus account extraction implies the required bounds at the chosen next state, closing the induction.

There is no reverse dependence in these choices. First fix a sufficiently large even \(p\) using the order-independent \(C_*\); then choose \(\kappa_p\), the threshold and its finite \(R_c\); then decrease the structural and low-square losses for the finitely many interpolations and near-radius inductions. Their constants can grow but remain independent of \(n\). This proves the proposition. ◻

Proof. Let \(G_*\) be the actual graph at the last state of the history segment. Every actual path present earlier is present in \(G_*\). The first endpoints are distinct initial stubs, and at most \(d\) such stubs lie at one vertex. Thus it suffices to bound an absolute weighted path row to all vertices of \(G_*\). In particular, the target stub need not remain unresolved in \(G_*\). At a fixed length \(k<L\), the total number of paths is at most \(Cq^k\) and their fixed-endpoint multiplicity is bounded. Since \(h^{2k}\leq q^{-k}\), the squared sum of the weighted row at that length is bounded. Cauchy–Schwarz over the \(O(\log n)\) lengths gives a polylogarithmic bound for the total row. This argument also applies with a fixed stub vertex as the starting point and the distinct \(u_t\) as targets.

The nonempty-return squared-sum estimate follows in the same way from the global return-square diagram bound in \(G_*\). Each uniform or centering contribution is at most \(n^{\eta_0}q^{L/2}/l_0\), with a preliminary loss \(\eta_0\). Even summing its square over all \(l_1\) initial stubs gives \[O\!\left(n^{2\eta_0}q^L/l_0\right)=o(1).\] Finally, \(\sum_t|e_i^t(u_t)|^2\leq bB_m^2=o(1)\) under the entry bootstrap. Choosing \(\eta_0\) small enough proves all the assertions. ◻

Proof. We keep the trace errors \(L_1=F_1-(l-1)\) and \(L_0=F_0-(n-1)\) at the intermediate scales \[S_1=n^{.085a}/\alpha_*,\qquad S_0=n^{.115a}/\alpha_*^2.\] At each primary, we reinitialize \(\mathcal T\) with its deviation from its value at \(l_1\), rather than continue the reciprocal account used in the early phase. As in the trace calculation there, \(K,Q,J\) denote the current pair blocks of \(K_{\rm all},Q_{\rm all},\Gamma Q_{\rm all}\).

The stub trace \(L_1\). In the expansion (17), the signed conditional mean of all terms other than the ideal term \(-\operatorname{Tr}H_0K\) is bounded in absolute value by \[C\left(j_u+B_m+\frac{n^\eta}{\sqrt l}+\frac1l\right).\] Here the bounds (16) control the endpoint factors, and averaging the random endpoint uses the row cross norms and \(T_S\). Its cumulative bound is \[C\left(n^\eta\sqrt b+bB_m+ \frac{n^\eta b}{\sqrt{l_0}}+f_b\right).\] For the pure-swap cross term, the full partner sum cancels by centering when the artificial partner \(v=u\) is included. The full coefficient \(H_0\) has a finite-size remainder. More precisely, since \(H_0=-\sigma h(F+J_2/(l-2))\), uniform averaging over the distinct partners gives \[\mathbb E_{v\ne u}[-\operatorname{Tr}(H_0K)] =\sigma h\frac{\operatorname{Tr}K_{\rm all}-lK_{uu}} {(l-1)(l-2)}.\] Here \(\sum_v(K_{\rm all})_{uv}=0\) was used. The remainder is \(O(1/l)\) because all diagonal entries of \(K_{\rm all}\) are bounded. For the actual eligible set \(I\), its complement has \(O(b)\) stubs, and \[\|(K_{\rm all})_{u,*}\|_2\leq Cn^{v_*}/\alpha.\] Indeed \(K_{uu}\leq C\), and the operator bound for the relevant positive Gram matrix controls its row norm. The centered cross sum over \(I\) is the negative omitted-row sum. Cauchy–Schwarz bounds this sum, while the non-pure diagonal contribution is \(O(1/l)\) directly. Thus the absolute signed mean is at most \[C\left(\frac{\sqrt b\,n^{v_*}}{\alpha l}+\frac1l\right).\] The sum of conditional second moments is at most \[C\left(b+f_b\frac{n^{2v_*}}{\alpha^2}\right).\] All these mean bounds divided by \(S_1\), and all second-moment bounds divided by \(S_1^2\), tend to zero by a fixed power of \(n\).

The global trace \(L_0\). For \(L_0\), the nonideal mean bound above acquires a factor \(C/\alpha\). The ideal \(Q\) row has norm at most \(Cn^{v_*}/\alpha^2\), by (13) and \(Q_{uu}\leq C/\alpha\). The same fixed-endpoint calculation has finite-size remainder \(C/(\alpha l)\), and omitted-row contribution \(C\sqrt b\,n^{v_*}/(\alpha^2l)\). The corresponding cumulative second-moment bound is \[C\left(\frac b{\alpha^2}+ f_b\frac{n^{2v_*}}{\alpha^4}\right).\] Division by \(S_0\) and \(S_0^2\) gives the same power savings for the mean and second-moment budgets. For extraction, if a scalar increment has signed mean bounded by \(\mu_t\) and second moment bounded by \(\nu_t\), the account \(1+L^2/S^2\) has expectation factor at most \(1+2\mu_t/S+\nu_t/S^2\), using \(|L|/S\leq1+L^2/S^2\). The pathwise sums just established therefore give bounded discount loss. The gaps from \(.085a\) to \(.09a\) and from \(.115a\) to \(.12a\) accommodate the total-account extraction factor. Initial trace values satisfy the smaller early-phase bounds.

The lower bound for \(\mathcal T\). We now control \(\mathcal T-\mathcal T(l_1)\). By (15), a uniform lower comparison scale at a primary is \[T_{\min}\asymp n^{-\theta/2}l_0/\alpha.\] This comparison uses \(\alpha n/l_0\to\infty\), uniformly over the primary points. In (21), the non-\(J\) terms cost at most \(C/\alpha\) per step. For the ideal \(J\) term, the relevant row and column norms are at most \(Cn^{2v_*}/\alpha^3\), its entries are at most \(Cn^{v_*}/\alpha^2\), and its full sums are centered. Thus its cumulative absolute signed-mean bound and second-moment bound are, respectively, \[C\left(\frac{n^{2v_*}b^{3/2}}{\alpha^3l_0} +\frac{n^{v_*}b}{\alpha^2l_0}\right), \qquad C\left(f_b\frac{n^{4v_*}}{\alpha^6} +\frac{bn^{2v_*}}{\alpha^4l_0^2}\right).\] The nonideal \(J\) coefficient is bounded using \(j_u+B_m+|D_{vv}|+|D_{uv}|\). Its cumulative mean is at most \[\frac{Cn^{v_*}}{\alpha^2} \left(n^\eta\sqrt b+bB_m+ \frac{n^\eta b}{\sqrt{l_0}}\right),\] and the crude cumulative second bound \(Cbn^{2v_*}/\alpha^4\) suffices. Dividing the means by \(T_{\min}\) and the seconds by \(T_{\min}^2\) gives fixed power savings. One of the potentially tight ratios is bounded by \[C\frac{b^{3/2}n^{2v_*+\theta}} {l_0^2\alpha_*^2}=o(1).\] Choose a small fixed \(\kappa>0\) and apply the deviation-square account at scale \(n^{-\kappa}T_{\min}\), taking \(\kappa\) smaller than the established margins. Its initial deviation is zero, its discount loss is bounded, and its extracted deviation is \(o(T_{\min})\). This proves the stated lower bound, with the additional \(n^{-\theta/2}\) cushion. All conclusions are uniform on their stated parameter sets: the trace-error estimates hold at every tracked point, and the lower bound for \(\mathcal T\) holds at the primaries. ◻

Proof. Expand \[H=H_0\sum_{k\geq0} \bigl(-(T+E_{\mathrm{pair}})H_0\bigr)^k\] and the analogous reference coefficient. Every factor is either a pure swap, a non-pure swap, a diagonal topology entry, a cross topology entry, or an endpoint \(E\) entry. If a non-pure swap occurs, assign the word to class 1. Otherwise first separate the number of endpoint \(E\) entries, and then whether any off-diagonal topology entry occurs. The listed classes cover all resulting cases. The terms with no endpoint or outer \(E\) that cancel numerically leave precisely the formal tail; their endpoint classification is unchanged by restricting total degree.

To see the useful grouping in class 3, first write the difference of the two numerical updates as outer differences with the reference coefficient, together with \[WU H_P E_{\mathrm{pair}} H U^TW.\] Replacing both coefficients in this expression by their pure-swap parts gives the asserted single-\(E\) term with \(W\) outers. The remainders contain topology, a non-pure swap, or a second endpoint \(E\), and belong to the other classes.

A pure swap changes \(u\) to \(v\) and \(v\) to \(u\). A local topology entry preserves its endpoint. If both outers are at \(u\), the first and last intermediate positions of a pure-swap word are at \(v\). With no endpoint \(E\), the first such position supplies \(j_v\). With one endpoint \(E\) and at least one local topology entry, there are at least two intermediate positions, so at least one of the first and last positions is a local topology entry at \(v\). With distinct outers and no endpoint \(E\), a nonempty local-only word has at least two intermediate positions and visits both endpoints. This proves the locality assertions, including the cases in which the endpoint \(E\) itself is off diagonal.

Finally the uniform small bound for each endpoint error makes the absolute sum over additional factors geometric. Marking one or two factors of a specified type introduces at most a fixed power of the word length, still summable. The coefficientwise majorants used for the formal tail have the same property. Therefore all the estimates below can be proved for the displayed factors and then multiplied by a fixed constant. ◻

Proof. We first estimate the vector of signed means \(m\), retaining the cancellations of the zero-intermediate and single-\(E\) terms. We then bound \(V_t\) by absolute squares.

Survival and recentering. We initially work on the old centered axes. If \(x\) is an eligible partner, survival excludes the choice \(v=x\). Inserting this value into the partner average and subsequently removing it changes its \(x\)th component by at most \(CB_m/l\); an ineligible \(x\) needs no such correction. There are \(O(l)\) components, so the vector cost is \(CB_m/\sqrt l\) per step. The recentering formula \(\xi_x'=\xi_x+(\xi_u+\xi_v)/(l-2)\) gives the same bound. The old-axis error after a candidate update is \(O(B_m)\) by the convergent update expansion and the tail bound. Thus these corrections sum to \(O(bB_m/\sqrt{l_0})=o(1)\).

Signed means. Let \(I\) be the eligible partner set, and write a bar for its uniform average. Full sums of every centered \(p\) or \(e\) row vanish. The omitted set has size \(O(b)\), so the pure-swap terms with no intermediate factor have the following vector bounds: \[\begin{split} \|(p_x(u)\overline{e_x(v)})_x\|_2 &\leq CbB_m/l,\\ \|(e_x(u)\overline{e_x(v)})_x\|_2 &\leq CbB_m/l,\\ \|(e_x(u)\overline{p_x(v)})_x\|_2 &\leq CB_m(1+L)^3\sqrt b/l. \end{split}\] The first two use the omitted-entry bound \(B_m\) and bounded column norms. For the third, multiply the sum of omitted \(P\) columns by the diagonal matrix with entries \(e_x(u)\); its norm is at most \(B_m\), while (9) bounds the norm of the column sum by \(C(1+L)^3\sqrt b\).

The pure \(P\)–\(P\) zero-intermediate tail cancels over the full partner set coefficient by coefficient. For its omitted part, apply the same coefficient operator estimate to the omitted indicator vector, multiply by the bounded opposite outer entry, and sum the polynomially many degree choices. Its vector bound is \(n^\eta\sqrt b/l\). Non-pure swaps contribute \(C/l\) per step: the pointwise product of two fixed columns has bounded \(\ell^2\) norm, as does the averaged product. The cumulative costs just listed are small, using (37) and \(b^2B_m/l_0=o(1)\).

For the pure single endpoint \(E\) term of Lemma 25, the two fixed outers give the vector \((w_x(u)^2)_x\) times \(\overline{e_v(v)}\). Its norm is bounded, and \[|\overline{e_v(v)}| \leq C\frac{|Y_E|+\sqrt{bT_S}}l, \qquad Y_E=\operatorname{Tr}(\Xi^TE\Xi).\] The omitted diagonal sum was bounded by Cauchy–Schwarz. For two random outers the averaged-square vector has norm \(C/\sqrt l\), and its scalar factor is \(e_u(u)\). With distinct outers, the average row dot against the \(u\)th row of \(E\) is \(O(1/l)\); multiplication by the bounded-norm fixed column gives a vector bound \(C/l\). These contributions sum to small quantities, since \[|Y_E|\leq n^{.09a}/\alpha_*+Q_a,\qquad f_bQ_a=o(1),\qquad b^{3/2}\sqrt{T_{\mathrm{cap}}}/l_0=o(1).\]

It remains to bound the absolute-mean classes. With a cross topology factor, two fixed outers cost \(CQ_a/l\): use the \(\ell^1\) bound on the \(u\)th cross row and the bounded norm of the squared outer column. Two random outers cost \(C/l\): apply the bounded operator \((r_x(v)^2)_{xv}\) to the bounded-norm cross row \((b_{uv})_v\), and divide by \(|I|\asymp l\). Distinct outers also cost \(C/l\), by taking the row dot at the random endpoint before the fixed-column norm.

For local-only topology, two fixed outers require \(j_v\) and therefore cost \(CQ_a/l\). Two random outers require \(j_u\) and cost \(Cj_u/\sqrt l\). With distinct outers and no endpoint \(E\), both endpoint local factors occur; bound the random factor and use the \(\ell^1\) bound \(C\sqrt l\) for its outer row, obtaining \(Cj_u/\sqrt l\). With exactly one endpoint \(E\) and local topology, the same-outer cases still contain the opposite local factor, while the distinct case is bounded by \(CB_m/\sqrt l\). Two endpoint \(E\) factors cost \(CB_m^2\) per step. These cases are exhaustive by Lemma 25; outer \(E\) choices are already included in \(r\). Their sums are bounded by \(n^\eta\), using Lemma 23, \(bB_m^2=o(1)\), and (37).

Squared increments. For the budget \(V_t\), a distinct-outer product gives \[\frac{C}{l}\sum_x r_x(u)^2 \sum_{v\in I}r_x(v)^2\leq C/l.\] With two fixed outers, an opposite local or cross factor has conditional squared mean at most \(n^\eta/l\), and the fourth sum of the fixed column is bounded. The single opposite diagonal \(E\) factor contributes \(CT_S/l\) instead. Two endpoint \(E\) factors give \(CB_m^4\).

With two random outers, a fixed local factor gives \(Cj_u^2\), using the bounded fourth-column sum for each partner; a cross factor gives \(C/l\) by its squared row bound. Any remaining endpoint \(E\) factor can be bounded by \(B_m\), giving \(CB_m^2\) per step. The no-intermediate same-end case already contains a non-pure swap. Thus there is no untreated same-end term without either the stated opposite factor, the single opposite diagonal \(E\), or at least two endpoint \(E\) factors.

Squares of the finite sums are bounded by the corresponding sums of squares up to constants. The infinite remainder is handled by weighted Cauchy–Schwarz using its geometric decay, as in Lemma 25. Centering and tail terms obey the same majorizations. Summing gives \(n^\eta+Cf_bT_{\mathrm{cap}}\), by (38); all \(bB_m^2\) and \(bB_m^4\) terms are small. This proves the lemma. ◻

Proof. In the linear part of (40), replacing output axis \(i\) by selected stub \(x\) has coefficient \[-\sum_{s\in\{u,v\}}p_i(s)(H_P)_{sx}.\] Every transfer whose input level is at least the replaced output level has coefficient at most \(n^{-\beta_R}\) for some fixed \(\beta_R>19\rho\). A surviving initially clean axis is farther than \(R_0\) from every selected endpoint, so both outer entries are small by the path decay and centering estimates. For a surviving bad axis, the only possible input of equal or higher level is a bad first endpoint \(u\). Its outer entry at the clean partner \(v\) is small. The remaining contribution uses \((H_P)_{uu}\), which is small by the opposite clean return/cross bound and the pure-swap expansion (23). Global axes have only lower-level selected inputs. The fixed separation margin permits the choice \(\beta_R>19\rho\) by taking \(\rho\) small enough.

Consequently, apart from the persisting identity term, transfers that all decrease level cost \(CB_{k-1}\) when \(k\geq1\). Any term with a nondecreasing transfer costs \(Cn^{-\beta_R}B_m\). The nonlinear part of (40) costs \(CB_m^2\), and output recentering costs \(CB_m/l\). The remaining formal tail costs \(B_{\rm tail}\). After division by \(B_k\), the first bound is \(Cn^{-4\rho}\), the second is at most \(Cn^{-\beta_R+16\rho}\), and the last three are smaller than \(n^{-2\rho}\) by the parameter margins. There is no decreasing transfer when \(k=0\). This proves the claim after absorbing fixed constants. ◻

Proof. Conditional on nonspecial survival, the partner is uniform in a set omitting \(O(b)\) stubs. All estimates below hold for such sets, even when the omitted set changes with the history. We give bounds at the smallest scale \(B_c\); since \(B_k\geq B_c\), they imply the displayed assertions.

Signed means. For zero-intermediate pure swaps with an outer \(E\), use the centered full partner sum. An omitted average of an \(E\) row has magnitude at most \(CbB_m/l\), and an omitted average of a \(P\) row has magnitude at most \(C\sqrt b/l\) by its row norm. Lemma 23 therefore gives cumulative absolute signed-mean bounds \[Cn^\eta b^{3/2}B_m/l_0,\qquad Cb^{3/2}B_m/l_0,\qquad Cb^2B_m^2/l_0\] for \(p_i(u)\overline{e_j(v)}\), \(e_i(u)\overline{p_j(v)}\), and the two-outer-\(E\) term, respectively. For the first term use \(\sum_t A_i^t(u_t)\leq n^\eta\sqrt b\); for the second and third it suffices to use the entry cap on the prescribed endpoint. The pure \(P\)–\(P\) zero-intermediate tail cancels coefficientwise over all partners. In the omitted part, Cauchy–Schwarz gives \(C\sqrt b\) for the omitted absolute row sum, and the prescribed-endpoint path sum is \(n^\eta\sqrt b\). Summing degree choices yields the bound \(Cn^\eta b/l_0\).

For the single endpoint \(E\) term with \(W\) outers, two fixed outers contribute at most \[Cn^\eta\frac{|Y_E|+\sqrt{bT_{\rm cap}}}{l_0}.\] Indeed their product sums over the prescribed endpoints to at most \(n^\eta\), and the signed opposite diagonal mean is bounded as in Lemma 26. Two random outers cost \(Cf_bB_m\), by the bounded outer row dot divided by \(l\). Distinct outers cost \(Cn^\eta\sqrt b/l_0\), taking the random row dot first and then summing the fixed outer.

For a cross topology factor, the cumulative bounds for fixed, random, and distinct outer endpoints are, respectively, \[Cn^\eta Q_a/l_0,\qquad Cf_b,\qquad Cn^\eta\sqrt b/l_0.\] The first uses its row \(\ell^1\) bound and the summed product of the fixed outers; the second uses the bounded random outer row dot and the bounded cross-entry supremum; the third uses the bounded cross row norm against the random outer before summing the fixed one.

For local-only topology, two fixed outers require the opposite local factor and have the same \(Cn^\eta Q_a/l_0\) bound. Two random outers cost at most \(Cf_b\). With distinct outers and no endpoint \(E\), both local factors are present; bound the random local factor by its supremum and average its outer with cost \(C/\sqrt l\). The remaining prescribed sum \(\sum_t r_i^t(u_t)j_{u_t}^t\) is at most \(n^\eta\), so the total is \(Cn^\eta/\sqrt{l_0}\). With one endpoint \(E\) and local topology, the same-outer requirements persist; the distinct case instead costs \(Cn^\eta B_m\sqrt{b/l_0}\).

Terms with at least two endpoint \(E\) factors have the combined bound \[Cn^\eta B_m^2 \left(1+b/l_0+\sqrt{b/l_0}\right).\] For two fixed outers this follows from their pathwise product sum; for two random outers their conditional product mean is \(O(1/l)\); for distinct outers average the random row and sum the fixed one. Non-pure swaps have instead the combined bound \[Cn^\eta\left(l_0^{-1}+bl_0^{-2} +\sqrt b\,l_0^{-3/2}\right),\] by the same three outer configurations and the additional \(1/l\) factor. Centering contributes \(Cf_bB_m\). Lemma 25 proves that these bounds cover every mean term, including the tail.

Second moments. We next bound the cumulative second moments, keeping the same three outer configurations. With distinct outers, averaging the random outer square gives \(C/l\), and (38) bounds the sum of prescribed outer squares. The resulting budget is \(Cn^\eta/l_0\). With two fixed outers, an opposite local or cross factor has conditional squared mean at most \(n^\eta/l\); the pathwise sum of outer product squares is at most \(n^\eta\). The resulting bound is again \(Cn^\eta/l_0\), after adjusting the preliminary loss. The single opposite diagonal \(E\) factor costs \(Cn^\eta T_{\rm cap}/l_0\), while two endpoint \(E\) factors cost \(Cn^\eta B_m^4\).

With two random outers, a fixed diagonal \(E\) or another otherwise unestimated endpoint \(E\) contributes at most \(Cf_bB_m^2\). A fixed local factor contributes \(Cn^\eta/l_0\), because its pathwise squared sum is bounded and the random outer fourth-product average is \(O(1/l)\). The remaining cross topology term with two random outers requires a joint sum over steps and partners: its outer squares must be retained. Separate its actual-path and uniform parts by writing \[b_{uv}^t\leq b_{uv}^{t,\mathrm{act}}+U, \qquad U=Cn^{\eta_0}q^{L/2}/l_0,\] where \(\eta_0\) is a sufficiently small preliminary loss and the centering term \(C/l\) is included in \(U\). The squares of these two parts can be estimated separately, up to a fixed factor. For the actual-path part, bound one outer by its constant supremum and write the other squared outer as \(C(A_i^t(v)^2+B_m^2)\). The numerator of the cumulative partner average is thus bounded by \[C\sum_v\sum_t \bigl(A_i^t(v)^2+B_m^2\bigr) (b_{u_t v}^{t,\mathrm{act}})^2.\] Dominate every \(A_i^t(v)\) by its terminal actual-path row plus \(U\). This majorant has squared sum at most \(n^\eta\) over the initial stubs; its added uniform squared mass is at most \(Cl_1U^2=o(1)\). For each fixed \(v\), the sum \(\sum_t(b_{u_t v}^{t,\mathrm{act}})^2\) is at most \(n^\eta\) by Lemma 23. Choosing the preliminary loss smaller gives a total \(n^\eta\). The \(B_m^2\) part is at most \(CbB_m^2\), using the bounded current cross-row squared sum at every step. Division by \(l\asymp l_0\) gives \(Cn^\eta/l_0+Cf_bB_m^2\).

For the uniform part, retain both outer squares. At each step their sum is bounded: \[\sum_{v\in I}r_i^t(v)^2r_j^t(v)^2 \leq \bigl(\sup_v r_j^t(v)^2\bigr) \sum_{v\in I}r_i^t(v)^2\leq C.\] Its cumulative partner-average contribution is consequently at most \[CbU^2/l_0=Cn^{2\eta_0}bq^L/l_0^3.\] This can be absorbed into the preceding \(n^\eta/l_0\) budget. Directly, its ratio to \(B_c^2\) is \[Cn^{2\eta_0}\frac{bq^L}{l_0^3B_c^2} =n^{-1/3-1.085a+2\eta_0+o(1)},\] which tends to zero by a fixed power.

Non-pure swaps and recentering yield smaller bounds. As before, geometric summability handles the longer endpoint words, and the same-endpoint configurations without an opposite topology factor are exactly the zero-intermediate non-pure term, the single opposite diagonal \(E\) term, or a term with at least two endpoint \(E\) factors. This verifies exhaustiveness of the square estimates as well.

Comparison with the target scales. All displayed mean budgets are smaller than \(B_c\) by a fixed power, and all square budgets are smaller than \(B_c^2\) by a fixed power. Some of the direct comparisons that control the smaller margins are \[\begin{aligned} \frac{f_b}{B_c}&=n^{-.08a+o(1)},& \frac{l_0^{-1/2}}{B_c}&=n^{-.35a},\\ \frac{l_0^{-1}}{B_c^2}&=n^{-.70a},& \frac{Q_a/l_0}{B_c}&=n^{-.64a+\eta+o(1)}. \end{aligned}\] The bound on \(Y_E\) gives another power saving, and the terms with \(B_m\), \(b^{3/2}/l_0\), or \(B_m^2\) have additional margins from (37). Choose all preliminary losses, the exponent of \(T_{\rm cap}\), and \(\rho\) within these strict margins. A common positive \(c_5\) then gives (41). ◻

Proof. Short paths and row tails. Put \(t_0=\lfloor R_0/4\rfloor\). Two boundary endpoints within distance \(t_0\) of a given vertex would give a boundary-to-boundary path of length at most \(2t_0\). Two distinct nonbacktracking paths of length less than \(t_0\) from a boundary endpoint to a fixed vertex give, after cancellation of a common terminal segment, a nonempty nonbacktracking boundary return of length less than \(2t_0\). Both possibilities are excluded. This proves uniqueness of the short summand in (43).

For \(t_0\le k<L\), fix a path prefix of length \(k-t_0\) starting at \(i\). There is at most one boundary endpoint within distance \(t_0\) of its last vertex. The bounded fixed-endpoint multiplicity estimate gives at most a constant number of nonbacktracking suffixes of length \(t_0\) to that endpoint. Consequently there are at most \(Cq^{k-t_0}\) actual paths of length \(k\) from \(i\) to the boundary. Applying the same fixed-endpoint multiplicity estimate to the complete paths yields \[\sum_{s\in S_0} \left|\sum_{t_0\le k<L}\varphi(k/L)(\sigma h)^k Q_{k,\mathrm{actual}}(i,s)\right|^2 \le C L\sum_{t_0\le k<L}q^{-k}q^{k-t_0} \le n^\eta q^{-t_0}.\] The virtual and centering contribution to this row has norm at most \(C(1+L)^2q^{L/2}/\sqrt{l_0}=C(1+L)^2n^{-.29a}\). Projection onto \(\mathcal H_0\) is a contraction. These bounds prove (43); insertion of factors \(k/h\) proves the derivative statement. The same argument for a boundary input, and symmetry, gives \[\max_{s\in S_0}\|\widehat D_0\Pi_{l_0}e_s\|_2 +\max_{s\in S_0}\|\partial_h\widehat D_0\Pi_{l_0}e_s\|_2 \le n^{-r_P'}\] with a possibly smaller exponent. This completes the row estimates.

Moments on boundary contrasts. For the operator estimate, we use the stronger consequence of separation \(V_0^TQ_jV_0=0\) for \(1\le j\le R_0\). To verify this also for paths with virtual traversals, observe that the first virtual traversal must be the first step: a positive actual prefix would already join a boundary vertex to a missing departure. After a virtual traversal the sole missing stub at its landing vertex is excluded as the next departure. Any later virtual traversal, or an actual endpoint on the boundary, would therefore require a positive actual boundary-to-boundary segment of prohibited length. The only remaining possibility is the single virtual traversal; its averaging operator vanishes on \(\mathcal H_0\).

To express this vanishing in terms of spectral moments, introduce, for a formal variable \(t\), the matrix series \[\begin{align*} G_{\rm gen}(t) &=V_0^T(1-t^2) [I-tA_e+t^2(qI-V_0V_0^T)]^{-1}V_0,\\ G_{\rm reg}(t) &=V_0^T(1-t^2)[I-tA_e+qt^2I]^{-1}V_0. \end{align*}\] The formal Woodbury identity and the preceding vanishing give \[G_{\rm gen}(t)=I+O(t^{R_0+1}),\qquad G_{\rm reg}(t) =G_{\rm gen}(t) \left(I+\frac{t^2}{1-t^2}G_{\rm gen}(t)\right)^{-1} =(1-t^2)I+O(t^{R_0+1}).\] Let \(\mathcal U_k\) denote the Chebyshev polynomial of the second kind, normalized by \(\mathcal U_k(\cos\vartheta) =\sin((k+1)\vartheta)/\sin\vartheta\). For every complex unit vector \(f\in\mathcal H_0\), the spectral measure \(\mu_f\) of \(A_e/(2\sqrt q)\) at \(V_0f\) therefore satisfies \[\int\mathcal U_0\,d\mu_f=1, \qquad \int\mathcal U_k\,d\mu_f=0 \quad(1\le k\le R_0).\] This follows on dividing by \(1-t^2\) and using \((1-2xy+x^2)^{-1}=\sum_{k\ge0}\mathcal U_k(y)x^k\) with \(x=t\sqrt q\). Hence \(\mu_f\) agrees, through polynomial degree \(R_0\), with the semicircle measure of angular density \((2/\pi)\sin^2\vartheta\,d\vartheta\).

Positivity at the two closest signed precisions implies \(\|A_e|_{\mathbf1^\perp}\|\le2\sqrt q+C\alpha_*^2\). For example, multiplying the positive precision by \(h\) and adding the positive term \(h^2V_0V_0^T\) gives \(I-\sigma hA_e+qh^2I\succ0\). The claimed support bound follows from \(z(h)=2\sqrt q+O(\alpha_*^2)\).

Edge mass and the smooth cutoff. The moment identities give the following bound: for every \(u\ge C'/R_0\), the mass within angular distance \(u\) of either edge, including mass outside \([-1,1]\) at that edge, is at most \(Cu^3\). For its proof, choose \(m=\lfloor c/u\rfloor\) with a sufficiently small positive constant \(c\), so that \(2m\le R_0\), and put \(K_m(y)=\sum_{k=0}^m(k+1)\mathcal U_k(y)\). Moment matching and orthonormality give \[\int K_m(y)^2\,d\mu_f(y) =\sum_{k=0}^m(k+1)^2\le C(m+1)^3.\] For \(0\le\vartheta\le c_0/(m+1)\) every summand satisfies \(\mathcal U_k(\cos\vartheta)\ge c_1(k+1)\); hence \(K_m\ge c_2(m+1)^3\) there. For \(y\ge1\) the same inequality follows from \(\mathcal U_k(\cosh v)=\sinh((k+1)v)/\sinh v\ge k+1\). Markov’s inequality gives mass \(O((m+1)^{-3})=O(u^3)\). Reflection proves the estimate at \(-1\). Values of \(u\) bounded away from zero are covered by increasing the constant.

Put \(x=t\sqrt q\) and write \(H_b(x)=G_{\rm reg}(t)-(1-t^2)I=\sum B_kx^k\). Its coefficients vanish for \(k\le R_0\). Choose a smooth function \(\psi(k/L)\) supported in \(R_0/2<k<C L\) and equal to one for \(R_0<k\le L\). The ratio \(L/R_0\) is bounded above and below by fixed positive constants, so all derivatives of this cutoff, in the variable \(k/L\), have fixed bounds. For \(x_0=\sigma h\sqrt q\) and \(\xi\in\mathbb R\), we claim \[ \left\|\sum_{k>R_0}B_kx_0^k\psi(k/L)e^{i\xi k/L}\right\| \le \frac{C(1+|\xi|)^{J_0}}{R_0} \tag{44}\] for a fixed integer \(J_0\).

For \(k>R_0\), \(B_k\) is the compression to \(\mathcal H_0\) of \(\mathcal U_k(A_e/(2\sqrt q))-q^{-1}\mathcal U_{k-2}(A_e/(2\sqrt q))\). Thus each quadratic form in (44) is the integral of a tapered Chebyshev kernel against \(\mu_f\). The cubic edge-mass bound will control the kernel’s \(O(L^2)\) edge peaks, up to a fixed power of \(1+|\xi|\); smoothness of the cutoff will give summable decay away from the edges. We now establish these kernel bounds.

Extend the coefficient sequence by zero to all integers. For \(b_k=\psi(k/L)|x_0|^ke^{i\xi k/L}\) and every fixed integer \(J\ge0\), the \(J\)th finite difference has \(\ell^1\) norm at most \(C_JL^{1-J}(1+|\xi|)^J\). This follows by the fundamental theorem of calculus applied \(J\) times to the smooth interpolation of \(b_k\); derivatives of \(|x_0|^k\) are harmless because, on the support \(k\ge cL\), \((L|\log|x_0||)^j e^{-cL|\log|x_0||}\) is bounded. Summation by parts, or the trivial \(\ell^1\) bound when the denominator is small, yields \[\left|\sum_kb_ke^{ik\omega}\right| \le C_J L(1+|\xi|)^J (1+L\operatorname{dist}(\omega,2\pi\mathbb Z))^{-J}.\] The sine formula for the two Chebyshev terms, the preceding bound, and \(|\mathcal U_k(\cos\vartheta)|\le k+1\) imply, after increasing \(J\) if necessary, \[|\mathcal K(\cos\vartheta)| \le C_JL^2(1+|\xi|)^J (1+L\min(\vartheta,\pi-\vartheta))^{-J}.\] If \(y\) lies just outside \([-1,1]\), its hyperbolic angle is \(O(\alpha_*)\); since \(L\alpha_*=o(1)\), the corresponding bound is \(C_JL^2(1+|\xi|)^J\).

Integrate first over the edge bins of angular width \(C'/R_0\). Their mass is \(O(R_0^{-3})\), so their contribution is \(O(L^2R_0^{-3})(1+|\xi|)^J=O(R_0^{-1})(1+|\xi|)^J\). The subsequent bins, with angular distance between \(2^jC'/R_0\) and \(2^{j+1}C'/R_0\), contribute at most \[C L^2(1+|\xi|)^J (2^{j+1}/R_0)^3(1+c2^jL/R_0)^{-J}.\] For \(J>3\) their sum is again \(O(R_0^{-1})(1+|\xi|)^J\). This holds for every complex unit \(f\). The numerical-radius inequality \(\|T\|\le2\sup_{\|f\|=1}|f^*Tf|\) proves (44). If \(x_0<0\), replace \(y\) by \(-y\) in this argument; the two edge bounds are symmetric.

Return to the configuration pencil. The preceding bound concerns the regular pencil. To recover the desired smooth truncation of the configuration pencil, eliminate in the opposite direction: \[G_{\rm gen}(t) =I+\sum_{j\ge1}\frac{t^{2(j-1)}}{(1-t^2)^{2j}}H_b(x)^j.\] Only \(j\le L/(R_0+1)\) can contribute below total degree \(L\). Choose once and for all an integer \(J_*\) larger than all these upper bounds. Insert \(\psi(k/L)\) into each factor \(H_b\): this does not change any coefficient contributing after the final taper \(\varphi(k/L)\). Fourier inversion expresses that taper as \[\varphi((k_1+\cdots+k_j+m)/L) =\frac1{2\pi}\int_{\mathbb R}\widehat\varphi(\xi) e^{i\xi(k_1+\cdots+k_j+m)/L}\,d\xi.\] At \(|t|\le1/\sqrt q\) the scalar series \(t^{2(j-1)}(1-t^2)^{-2j}\) has a bounded absolute sum for each \(j\le J_*\). The \(j\) matrix factors inside the integral are bounded by (44). Choose the finite smoothness of \(\varphi\) so that \(\int |\widehat\varphi(\xi)|(1+|\xi|)^{J_0J_*}\,d\xi<\infty\). The tapered \(j\)th term then has norm \(O(R_0^{-j})\). Summing the finitely many terms proves (42). ◻

Proof. Expand \(H=H_0-H_0AH_0+H_0AH_0AH_0-\cdots\). Separate \(H_0=-\sigma hF+O(l^{-1})\) in each word. For a diagonal coefficient starting at \(u\), a word of pure swaps with at least one \(A\) must touch either \(D_{vv}\) or \(D_{vu}\) at its first \(A\) position. Every remaining \(A\) factor has norm \(O(\epsilon)\). Words whose first swap is not pure contribute \(O(l^{-1})\), with the remaining series uniformly bounded. This proves the pointwise diagonal estimate and, without the zero-\(A\) term, the corresponding estimate for \(H-H_0\). The same first-position argument gives a row bound for the off-diagonal coefficient; symmetry gives the column bound. Use \[\sum_v|D_{uv}|\le \sqrt{lC_0},\quad \sum_v|D_{vv}|\le\sqrt{lT},\quad \sum_v D_{uv}^2\le C_0\] to obtain the asserted averages and sums. A word with at least two \(A\) factors has a further factor \(C\epsilon\). Omitting a bounded number of coordinates changes these absolute averages by at most a fixed density factor for large \(l\).

For the signed formula expand the two-coordinate expression as \[x_uy_uD_{vv}+x_vy_vD_{uu} +(x_uy_v+x_vy_u)D_{uv}\] and sum over \(u\ne v\) in \(\mathcal I\). The three remaining identities follow by exactly the same expansion, respectively with the second matrix \(D^2\), with both matrices \(D^2\), and with the rank-one matrix \(rr^T\). No independence of entries is used. ◻

Proof. List the primary gaps increasingly as \(t_0<t_1<\cdots<t_N\), with \(1<r_{\min}\le t_{j+1}/t_j\le r_{\max}\) for fixed constants \(r_{\min},r_{\max}\). The closest gap is less than \(e/20\), and the largest gap is bounded below by a positive constant. For \(2e\le w\le c_d\), choose the least \(j\) with \(t_j\ge w\), and set \(w_-=t_j\), \(w_p=t_{j+1}\). Choose \(c_d\) small enough that this successor always exists. Then \(w\le w_-<w_p\le r_{\max}^2w\) and \(w_p-w_-\ge(r_{\min}-1)w\). In particular both resolvents are positive. On each eigenspace, \[\frac{1}{(x_i^\sigma+w_p)^2} \le \frac{(x_i^\sigma+w_-)^{-1}-(x_i^\sigma+w_p)^{-1}} {w_p-w_-}.\] The identity \(z(h)-s=(1-\sqrt q\,h)^2/h\) gives \(|h-h_-|=O(\sqrt w)\) for the corresponding primary parameters. The diagonal comparison and its derivative bound therefore give \[ \bigl[R_\sigma(s+w_p)^2\bigr]_{pp} \le \frac{[R_\sigma(s+w_-)-R_\sigma(s+w_p)]_{pp}}{w_p-w_-} \le \frac{C}{\sqrt w}. \tag{64}\] Here the entry error contributes \(O(B_B/w)=o(w^{-1/2})\) uniformly because \(w\ge2e\). If \(x_i^\sigma\le w\), the positive denominator \(x_i^\sigma+w_p\) is at most \(Cw\). Multiplying the preceding estimate by \(Cw^2\) proves (63). For \(w\) bounded below by \(c_d\), use \(\sum_i|v_i(p)|^2\le1\) and enlarge the constant. ◻

Proof. Fix one admissible bulk cutoff for each sign. We will bias the distribution of an edge pair so that its expected switch improves the near spectrum at both edges. Second moments control the error from using only \(M\) switches and from eliminating the bulk. Finally, we realize the draws in a polynomial finite sample space and test every candidate exactly.

Step 1: reduce positivity to the near subspace. A draw consists of two oriented edges \(g=(u,v)\) and \(j=(x,y)\) of \(G\). With \(U_{g,j}=[e_u-e_x,e_v-e_y]\), replace \(\{u,v\},\{x,y\}\) by \(\{u,y\},\{x,v\}\). This is a valid switch when its four endpoints are distinct and both inserted edges are absent from \(G\). Figure 2 illustrates the operation. Degree-preserving switches are classical in regular-graph sampling [22]. Switching arguments for local Green-function comparison appear in [5] and [16]; the distribution here is chosen to improve both signed near-edge forms. For a vertex-disjoint collection of \(M\) valid switches, concatenate their columns to obtain \(U\). The change of the signed precision is \[sI-\sigma A_{G'}=sI-\sigma A_G+UC_\sigma U^T,\] where \[C_\sigma=\operatorname{blockdiag}(\sigma F,\ldots,\sigma F), \qquad F=\begin{pmatrix}0&1\\1&0\end{pmatrix}.\] All columns of \(U\) lie in \(\mathbf 1^\perp\).

For the fixed cutoffs, put \(E_0^\sigma=\operatorname{span}\{v_i:x_i^\sigma<w_B^\sigma\}\), and let \(U_E\) denote the coordinates of \(U\) in this subspace. Define \[ S_B=C_\sigma^{-1}+U^TR_B^\sigma U. \tag{66}\] The two original edges in a draw each contribute one endpoint block to \(U^TR_B^\sigma U\). Replacing these by their tree blocks and setting the cross-edge entries to zero gives the ideal \(2\)-by-\(2\) block \[\sigma F+2P_{\mathrm{tree}}^\sigma =\frac1{d-2} \begin{pmatrix}s&\sigma d\\ \sigma d&s\end{pmatrix}.\] It has determinant \(-1\), one eigenvalue of each sign, and inverse \[ K_\sigma= \frac{d}{d-2}\begin{pmatrix}-s/d&\sigma\\ \sigma&-s/d\end{pmatrix}. \tag{67}\] If \(S_B\) is sufficiently close in norm to the block diagonal matrix of these ideal blocks, it has the same inertia as \(C_\sigma^{-1}\). To see why this suffices even when some old near slacks are negative, let \(D_B=\operatorname{diag}_{(E_0^\sigma)^\perp}(x_i^\sigma)>0\) be the old bulk precision within \(\mathbf1^\perp\), and let \(U_B\) be the bulk coordinates of \(U\). The two Schur complements of \[\begin{pmatrix}D_B&U_B\\ U_B^T&-C_\sigma^{-1}\end{pmatrix}\] give \[\operatorname{In}(D_B)+\operatorname{In}(-S_B) =\operatorname{In}(-C_\sigma^{-1}) +\operatorname{In}(D_B+U_BC_\sigma U_B^T),\] where \(\operatorname{In}\) records positive, negative and zero eigenvalue counts. The equal middle inertias cancel, proving that the updated bulk precision \(D_B+U_BC_\sigma U_B^T\) is positive definite. Eliminating this bulk leaves the exact near Schur complement \[ \operatorname{diag}_{E_0^\sigma}(x_i^\sigma) +U_ES_B^{-1}U_E^T. \tag{68}\] This is the Woodbury identity on the positive old bulk [14]; no positivity of the old near block is required.

Step 2: give the near spectrum a positive mean shift. The inverse \(K_\sigma\) in (67) determines the ideal contribution of one switch after the bulk has been eliminated. Let \(U_{E,g,j}\) denote the near coordinates of the two columns of \(U_{g,j}\), and put \[H^\sigma=U_{E,g,j}K_\sigma U_{E,g,j}^T.\] Thus replacing \(S_B^{-1}\) in (68) by the block diagonal matrix with blocks \(K_\sigma\) replaces the near correction by \(\sum_{r=1}^M H_r^\sigma\). Since \(K_\sigma\) is indefinite, we must control this sum through the choice of the edge-pair distribution.

First let \(\nu_0\) be the law of two independent uniformly chosen oriented edges. For \(g=(u,v)\) and nonconstant indices \(i\), write \[z_i(g)=(v_i(u),v_i(v))^T,\qquad M_i=\begin{pmatrix}1&\lambda_i/d\\ \lambda_i/d&1\end{pmatrix}.\] Regularity and orthogonality give \[\mathbb E_{\nu_0}z_i(g)=0,\qquad \mathbb E_{\nu_0}[z_i(g)z_k(g)^T]=\frac{\delta_{ik}}n M_i.\] For indices in \(E_0^\sigma\), the entry of the single-switch correction is \[H_{ik}^\sigma=(z_i(g)-z_i(j))^TK_\sigma(z_k(g)-z_k(j)).\] Its uniform mean is \[\mathbb E_{\nu_0}H_{ik}^\sigma =\frac{2\delta_{ik}}n\operatorname{Tr}(K_\sigma M_i) =-\frac{4\delta_{ik}x_i^\sigma}{(d-2)n}.\] Consequently the uniform mean correction only multiplies each old slack by \(1-4M/((d-2)n)>0\). It cannot turn a negative slack into a positive one. We therefore bias the correlations between the two edges on the modes closest to either threshold.

Choose cutoffs \(t_T^\tau\in[2e,3e]\) avoiding the signed slacks \(\{x_i^\tau:2\le i\le n\}\), and set \[T_\tau=\{i:x_i^\tau<t_T^\tau\},\qquad J_T\asymp n^{3a/2+a/10}.\] Define the tilted law \(\nu\) by multiplying the \(\nu_0\) probabilities by \[ 1+\frac1{B_*}\left[-\frac{2n}{J_T} \sum_{\tau=\pm1}\sum_{i\in T_\tau} z_i(g)^TK_\tau z_i(j)\right], \tag{69}\] where \(B_*>0\) is a sufficiently large fixed constant. This is a positive probability density. Indeed, (63) and Cauchy–Schwarz bound the absolute value of the bracket by \[C\frac{n e^{3/2}}{J_T}=O(n^{-a/10})=o(1).\] Every nonconstant eigenvector has mean zero on either endpoint of a uniform oriented edge. The bracket therefore has mean zero under \(\nu_0\) even when either edge is fixed. The density is normalized and both edge marginals under \(\nu\) remain uniform.

Expansion under this tilted law gives \[ \mathbb E_\nu H_{ik}^\sigma =\delta_{ik}\left[ -\frac{4x_i^\sigma}{(d-2)n} +\frac4{B_*J_Tn} \sum_{\tau:\,i\in T_\tau} \operatorname{Tr}(K_\sigma M_iK_\tau M_i) \right]. \tag{70}\] The first term is the uniform mean computed above. In the tilt correction only the two cross-edge terms in the expansion of \(H_{ik}^\sigma\) survive. Each forces the two near indices to agree with the tilting index, and each contributes the same trace divided by \(n^2\). Their negative signs cancel the negative sign in (69), giving the displayed factor \(4/(B_*J_Tn)\).

For a \(\sigma\)-near mode, only \(T_\sigma\) can occur in the sum, since the two signed slacks add to \(2s\) and \(2W_b+3e=o(1)\). On these modes \(M_i\) is uniformly positive definite, because \(s<d\), and \[\operatorname{Tr}(K_\sigma M_iK_\sigma M_i) =\|M_i^{1/2}K_\sigma M_i^{1/2}\|_{\mathrm F}^2\ge c_d.\] The positive bias satisfies \(M/(J_Tn)\asymp n^{-2/3+8.4a}\gg e\). It overwhelms the possible slack \(-e/20\) on \(T_\sigma\). Outside \(T_\sigma\), the slack is at least \(2e\), and multiplication by \(1-4M/((d-2)n)=1-o(1)\) preserves a fixed fraction of it. Thus the same law improves both signed forms: \[ \operatorname{diag}(x_i^\sigma)+M\mathbb E_\nu H^\sigma\succeq ceI \quad\text{on }E_0^\sigma. \tag{71}\]

Step 3: restrict the draws to typical edges. For the bulk cutoffs fixed in Step 1, keep only oriented edges whose endpoint blocks have the required accuracy for both signs. The numerical implementation below includes every edge with the proven \(n^{-.024}\) accuracy and includes only edges with \(Cn^{-.02}\) accuracy. Condition \(\nu\) on both sampled edges lying in this set. The removed probability is \(O(n^{-.1})\). Approximate the resulting law in total variation by \(n^{-C}\), for a sufficiently large fixed \(C\), retaining a bound \(C_d/(dn)^2\) for every point probability.

For any draw, the projector estimate at scale \(2W_b\) gives \[\|U_{E,g,j}\|_{\mathrm F}^2\le CW_b^{3/2},\qquad \|H^\sigma\|_{\mathrm F}\le CW_b^{3/2}.\] Consequently, the restriction and the probability approximation change the left side of (71) by at most \[CM(n^{-.1}+n^{-C})W_b^{3/2}=o(e).\] Denote the approximating law, including the probability rounding in Step 7, by \(\mu\). Unlike \(\nu\), it need not have exactly uniform marginals; the pointwise density bound is what the remaining estimates use.

Step 4: control fluctuations and collisions. Take \(M\) draws with law \(\mu\), requiring only pairwise independence between draws. The bulk inverse error will be sandwiched by \(U_E\), so a bound \(\|U_EU_E^T\|=O(M/n)\) makes \(o(en/M)\) the bulk error scale needed to obtain an \(o(e)\) error in the near form. We prove that, with probability \(1-o(1)\), simultaneously for both signs, \[ \begin{split} &\left\|\sum_{r=1}^M H_r^\sigma-M\mathbb E_\mu H^\sigma\right\|=o(e),\\ &\|U_EU_E^T\|\le CM/n,\\ &\left\|S_B-\operatorname{blockdiag} (\sigma F+2P_{\mathrm{tree}}^\sigma)\right\|=o(en/M). \end{split} \tag{72}\] Here and below a block diagonal notation in this display has \(M\) blocks. We supply all three second-moment estimates.

Pairwise independence makes the cross terms in the squared Frobenius norm of a centered sum vanish. Hence \[\mathbb E\left\|\sum_{r=1}^M (H_r^\sigma-\mathbb E_\mu H_r^\sigma)\right\|_{\mathrm F}^2 \le CM W_b^3.\] For the sum \(U_EU_E^T\) the same estimate applies to its centered version. Uniform-density domination gives its mean the positive-order bound \(CMI/n\): for any unit vector in the near subspace, average the squares of its four endpoint values and use that an endpoint of a uniform oriented edge is uniform on vertices. Since \[\sqrt M\,W_b^{3/2}=n^{-5/6+155a+o(1)} \ll e,\ M/n,\] Markov’s inequality proves the first two assertions.

To prove the third, first retain the two endpoint blocks belonging to each separate sampled edge. They have error \(O(n^{-.02})\) by construction; after forming the difference columns this is still a block-diagonal operator error \(O(n^{-.02})\). All the other entries concern endpoints in different edge slots. This includes the two edge slots within a draw. Such a pair of edge slots has joint density bounded by a constant relative to two uniform oriented edges: within one draw this is the pointwise bound for \(\mu\), and between draws it follows from pairwise independence and the bounded marginal densities. For any prescribed endpoint in each slot, (65) therefore gives \[\mathbb E\left| (R_B^\sigma)_{pq}\right|^2 \le \frac{C}{n^2}\sum_{p,q}|(R_B^\sigma)_{pq}|^2 \le \frac{C}{n\sqrt{W_b}}.\] There are \(O(M^2)\) such entries. Passing from the endpoint columns to their differences has operator norm \(\sqrt2\), so the total squared Frobenius budget is at most \(CM^2/(n\sqrt{W_b})\) up to a fixed factor. Its square root obeys \[\frac{M}{\sqrt n\,W_b^{1/4}} =n^{b_*-t_*/4+o(1)}=n^{-15a+o(1)} \ll en/M=n^{-9a+o(1)}.\] This is exactly the strict inequality \(t_*>8b_*-4a\). Also \(n^{-.02}=o(en/M)\). Markov’s inequality now proves the third assertion of (72). All the displayed separations have a fixed power margin, so the \(o(1)\) probability bounds can be imposed simultaneously.

The same density estimates show that endpoint coincidences within or between draws, or a proposed new edge already present in \(G\), have total probability \(O_d(M^2/n)=n^{-1/3+20a+o(1)}=o(1)\). Indeed each particular coincidence or adjacency has probability \(O_d(1/n)\); there are \(O(M^2)\) pairs of slots. Original edges have distinct endpoints by simplicity. On the complementary event all four endpoints of every switch are distinct and different switches are vertex-disjoint. Thus the switches are simultaneously valid, introduce neither loops nor repeated edges, and preserve every degree.

The following ratios collect the margins used above. Fixed factors and integer rounding do not change their powers of \(n\). The first ratio grows; every error ratio tends to zero for \(a=10^{-4}\).

Since \(e=o(M/n)\), the near-fluctuation estimate also supplies the second line of (72). No common exceptional edge set over different cutoff pairs is used: the cutoffs were fixed before the law was conditioned.

Step 5: conclude strict positivity at both edges. For a collection satisfying all these conclusions, the inverse perturbation identity and the bounded inverse in (67) give \[\left\|S_B^{-1}-\operatorname{blockdiag}(K_\sigma)\right\| =o(en/M).\] Write \(\mathcal K_\sigma=\operatorname{blockdiag}(K_\sigma,\ldots,K_\sigma)\). The near Schur complement is exactly \[\operatorname{diag}(x_i^\sigma)+\sum_{r=1}^M H_r^\sigma +U_E(S_B^{-1}-\mathcal K_\sigma)U_E^T.\] The last term has norm \(o(e)\) by the second line of (72). The centered fluctuation and the change from \(\nu\) to \(\mu\) each cost another \(o(e)\). The positive mean bound (71) therefore makes this Schur complement positive definite. The updated bulk was already positive definite. Thus the full signed precision is positive definite on \(\mathbf 1^\perp\), for both signs. This proves the asserted strict spectral bounds for at least one collection.

Step 6: compute rational approximations to the law. It remains to find such a collection deterministically. All accuracies in this paragraph can be \(n^{-C}\) for any sufficiently large fixed \(C\). Use the rational matrix \[A_\perp=A_G-d\mathbf 1\mathbf 1^T/n,\] which agrees with \(A_G\) on \(\mathbf 1^\perp\) and has eigenvalue zero on the constant direction. For each sign, choose rational cutoffs for the eigenvalues of \(\sigma A_\perp\), with the corresponding slack thresholds in the interiors of \([W_b,2W_b]\) and \([2e,3e]\), respectively. These cutoffs can have a gap at least an inverse polynomial from the spectrum. To see this, approximate \(s\) to much greater precision, place more than \(2n\) rational candidates at spacing comparable to the interval width divided by \(n\), and put disjoint small neighborhoods around them. At most \(n\) neighborhoods can contain eigenvalues. Exact rational inertia tests at the endpoints, together with a zero-eigenvalue test at an endpoint, identify an empty neighborhood. Choosing the candidates in a fixed interior subinterval ensures that the error in approximating \(s\) does not change the required slack interval.

The projectors onto \(T_\tau\) and the operators \(R_B^\sigma\) can now be approximated in operator norm without resolving any internal eigenvalue spacings. On a fixed rational interval containing \([-d,d]\), define a continuous cutoff function equal to its required zero or one value outside the separating gap, with linear interpolation inside the gap. For the bulk reciprocal use a very accurate rational \(\widetilde s\): set the function equal to \(1/(\widetilde s-t)\) on the bulk side and zero on the excluded side, and interpolate through the empty gap. These functions have polynomially bounded Lipschitz constants and rational values of polynomial bit length at rational arguments. The reciprocal approximation has an additional error at most \(C|\widetilde s-s|/W_b^2\), which is made negligible by the chosen precision.

After affine scaling to \([0,1]\), a function with Lipschitz constant \(L_f\) has Bernstein polynomial [6] of degree \(D\) with uniform error at most \(L_f/(2\sqrt D)\). This follows by writing the Bernstein polynomial as \(\mathbb E f(X/D)\) for \(X\sim\operatorname{Bin}(D,t)\) and applying Cauchy–Schwarz to \(\mathbb E|X/D-t|\). Take a polynomially large degree \(D\) to obtain the desired inverse-polynomial accuracy, and evaluate these rational polynomials at \(\sigma A_\perp\). The spectral theorem transfers the scalar error to operator norm. Sandwich the resulting operators by \(I-\mathbf 1\mathbf 1^T/n\) to remove the artificial constant eigenvalue. Rational matrix-polynomial evaluation has polynomial bit complexity: the degree is polynomial, its coefficients have polynomial bit length, and direct products and sums increase bit lengths by at most polynomial factors.

Use the approximate bulk blocks and approximate \(P_{\mathrm{tree}}^\sigma\) to accept all edges with the proved \(n^{-.024}\) accuracy and only edges with \(Cn^{-.02}\) accuracy. For example, use a rational entrywise threshold between these two scales; the approximation error is much smaller than either threshold. The sum in the tilt is basis-invariant: for endpoint indices \(g_r,j_t\) it equals \[\sum_{r,t=1}^2(K_\tau)_{rt} (\operatorname{Proj}_{T_\tau})_{g_r,j_t}.\] Thus the approximate projectors and rational approximations to \(K_\tau\) give rational positive weights for every accepted edge pair. Normalize these weights. Errors can be made small enough, including the factor \(n/J_T\), that the law is within \(n^{-C}\) in total variation of the conditional tilted law. Its point probabilities remain bounded by \(C_d/(dn)^2\).

Step 7: enumerate a polynomial sample space. Choose a prime \(P\) between \(n^{C'}\) and \(2n^{C'}\), up to immaterial rounding, where \(C'\) is a sufficiently large fixed constant and \(P>M\). Bertrand’s theorem and deterministic trial search provide such a prime in time polynomial in \(n\). There are \(O_d(n^2)\) accepted ordered edge-pair outcomes. Floor their probabilities times \(P\), then distribute the remaining counts among the largest fractional remainders. The counts are nonnegative, sum to \(P\), and differ by at most one from their unrounded values; outcomes outside the accepted support retain count zero. Assign that many residues of \(\mathbb F_P\) to each outcome. The total variation error is \(O_d(n^2/P)\) and the maximum probability increases by at most \(1/P\); both are within the stipulated bounds for large enough \(C'\). Choose the preceding approximation precision and \(C'\) so that their combined total-variation error is at most \(n^{-C}\). The resulting rounded law is a choice of \(\mu\) with all the properties used in Steps 3–5.

Use the standard affine construction of pairwise-independent variables (see [27]). Enumerate all \(P^2\) seeds \((\gamma,\beta)\in\mathbb F_P^2\) and use the residues \[\gamma r+\beta\qquad(1\le r\le M)\] to select the draws. Under a uniform seed, any two residues are independent and uniform: for \(r\ne t\), the map \((\gamma,\beta)\mapsto(\gamma r+\beta,\gamma t+\beta)\) is bijective since \(r-t\ne0\) in \(\mathbb F_P\). Mapping residues to outcomes preserves pairwise independence. The estimates above therefore prove that a positive fraction, indeed a fraction \(1-o(1)\), of these seeds satisfy all the required events.

For each seed, discard collections with intersecting endpoint sets or an invalid switch, build the candidate graph, and test its spectrum exactly. A rational contrast basis tests the positivity of \[4qI-A_{G'}^2\quad\text{on }\mathbf 1^\perp\] by exact rational congruence and inertia. Positive definiteness gives the strict conclusion of the theorem. Symmetric elimination uses a nonzero diagonal pivot if available, otherwise an invertible off-diagonal \(2\)-by-\(2\) pivot, with a remaining zero block contributing zero eigenvalues. Fraction-free arithmetic or determinant bounds keep all intermediate bit lengths polynomial: Schur-complement entries are ratios of minors of the original pivoted rational matrix. The same procedure implements the cutoff tests above. A passing seed exists by the preceding argument, and the number of seeds and all work per seed are polynomial in \(n\).

Finally, \(d>2\sqrt{d-1}\). A disconnected regular graph has an additional \(d\)-eigenvector orthogonal to \(\mathbf 1\), and a bipartite regular graph has a \(-d\)-eigenvector. The verified strict bound excludes both possibilities. ◻