Deterministic nonbipartite Ramanujan graphs in every fixed degree

Proof. Apply Theorem 1.1 to the least even integer n\ge N.□

Proof. For each index, D_i'\mathbb EZ_i(x')\le D_iZ_i(x) by definition of r_i. Sum with weights a_i and use that a minimum is no larger than its average. The discount product follows from r_i\le1+c_{i,t}.□

Proof. For real x and |y|\le1, Taylor’s formula on the positive half-line, including the possible crossing of zero, gives

Substitute x=(X-T)/b and y=\Delta/b, take expectations, and use x_+^j\le1+x_+^p for 0\le j\le p. On other surviving transitions the account is bounded by its old value, and on death it is zero. Averaging these alternatives gives the same bound without conditioning.□

Proof. Apply Lemma 3.2 with b=\lambda B_s separately to the quantity and its negative.□

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_*,

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

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 [HS81] applies because

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

Direct multiplication gives

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 [NSS95, Section 4.4, Theorem 3(iii)]: 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

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},

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 [AYZ95, Section 6, Theorem 6.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.3) 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

embeddings: apply (4.3) 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

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

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

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 (4.4), 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

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

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 (4.5).

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

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 (4.8). Moreover, \|\xi_x\|\le C, so

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),

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

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, (4.9), 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

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

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

Consequently,

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

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,

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

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 (4.13) 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

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

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 (4.10) 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,

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 (4.10) 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 (4.10), give (4.11). Summing the global and stub versions of (4.10) 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 (4.10). 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 (4.12). 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 (4.12).□

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,

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

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 (5.2). Consequently,

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 (4.10) and \|\xi_x\|^2=1+O(1/l). The positive normalization for valid pairs preserves these upper and lower bounds. Also,

Indeed, the ideal K_{uv} term uses (4.12), while diagonal same-end ideal terms have coefficient O(1/l). All other terms use (5.2).

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,

The contractions used here can be read directly from Lemma 5.2: 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 (5.2). 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 (4.12) gives exactly the first two summands of (5.5) and (5.6).

Lower drift of \mathcal T. To prove (5.1), we will control the reciprocal statistic. We first bound \mathbb E\Delta\mathcal T from below. The exact update of \mathcal T is

Using G_0,H_0 in the outer terms, their full-pair mean divided by \mathcal T is

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, (4.11) therefore bounds this relative drift below by -C\alpha\mathcal T/l^2 -n^{-c_4}/l. Pair smallness and (5.2) 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

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

Their mean, divided by \mathcal T/l, is at most

which is power-small under the current lower bound (5.1). 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

with some c_4>0, for sufficiently small \theta,\eta.

Second moment and maximum increment of \mathcal T. In (5.7), 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

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 (5.2) and D_g\ll l. Also, the norm bound times the trace gives

Consequently,

Individually, \lvert\Delta\mathcal T\rvert\le Cn^{v_*}/\alpha^2\ll\mathcal T under (5.1).□

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 (5.4), 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

Both tend to zero. The L_0 bounds follow from (5.6): 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 (5.10) by \mathcal T^2 and sum using the current lower bound (5.1). 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 5.3 permits Taylor expansion of the reciprocal. Together with (5.8), this yields

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 (5.1) 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 (4.6) 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

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 (4.2); 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 (4.2). 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

For same outer endpoint u, the numerator sum is

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

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 (4.10) and (4.5). 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 (5.11).

Every remaining word is covered by Lemma 5.5. 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 (4.7). 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

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 5.5, with both outers equal to P, is the copy increment

There is a fixed C_4<q^2 such that

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

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 (4.5)–(4.8). This proves (5.13) with a strict constant margin.

Summing over surviving x before averaging gives

For its two squared summands use (5.13) and then sum the opposite diagonal square. For the cross product use

The conditional restriction has density 1+o(1), so it preserves the strict margin.

After subtracting Z_x, the remainder obeys

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

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 5.5 proves (5.15).

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

The non-logarithmic quantities controlling the sum are

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 4.4. 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,

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

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 5.7 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 (5.16).

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 (5.12).□

Proof. For t\le2, the second moment and Hölder’s inequality give C n^{-\beta t/2}. For 2<t<p, interpolation gives

The exponent of M is at most t/p. Absorb fixed constants by halving the positive exponent of n, proving (5.17). 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 (4.8); for k\ge3 it is bounded. Since |X|\ge c_dl, this proves the marginal claim. Finally Lemma 4.4 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

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 (5.19) and (5.20). The difference H_P+\sigma hF is power-small by (4.6) 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 5.5. 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 (5.18); the sup claim follows also from (4.7).

For (5.21), follow the first pure swap in the (s,s) entry of H_P. By Lemma 5.5, either a non-pure swap occurs, or a local factor at \bar s, or a cross factor occurs. Hence

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 (5.11). 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,

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 (5.17), 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 (5.19), 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

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 (5.20) 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 5.9 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 (5.21), then use the row interpolation in z_{sj}. Here the structural loss \eta is chosen below the interpolation saving, including when k=2 in (5.21). For a leftover two-axis term retain the outer at s. If its input is z_{ss}, the coefficient includes (H_P)_{ss}, so (5.21) 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:

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 (5.21) 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

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 4.4. 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

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

By (5.17) 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

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

Their pure powers obey

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 (5.21), discard the bounded outer factor, and then average (i,s). This gives

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

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,

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 (5.22) 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 5.1. 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 (4.9)–(4.12) 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 5.4, Lemma 5.8, and Lemma 5.11 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 (5.22) 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

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

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 (5.3), the signed conditional mean of all terms other than the ideal term -\operatorname{Tr}H_0K is bounded in absolute value by

Here the bounds (5.2) control the endpoint factors, and averaging the random endpoint uses the row cross norms and T_S. Its cumulative bound is

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

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

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

The sum of conditional second moments is at most

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 (4.12) 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

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 (5.1), a uniform lower comparison scale at a primary is

This comparison uses \alpha n/l_0\to\infty, uniformly over the primary points. In (5.7), 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,

The nonideal J coefficient is bounded using j_u+B_m+|D_{vv}|+|D_{uv}|. Its cumulative mean is at most

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

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

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

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 xth 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:

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 (4.8) 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 (6.1) and b^2B_m/l_0=o(1).

For the pure single endpoint E term of Lemma 6.4, the two fixed outers give the vector (w_x(u)^2)_x times \overline{e_v(v)}. Its norm is bounded, and

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 uth 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

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 uth 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 6.4; outer E choices are already included in r. Their sums are bounded by n^\eta, using Lemma 6.2, bB_m^2=o(1), and (6.1).

Squared increments. For the budget V_t, a distinct-outer product gives

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 6.4. Centering and tail terms obey the same majorizations. Summing gives n^\eta+Cf_bT_{\mathrm{cap}}, by (6.2); all bB_m^2 and bB_m^4 terms are small. This proves the lemma.□

Proof. In the linear part of (6.4), replacing output axis i by selected stub x has coefficient

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 (5.9). 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 (6.4) 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 6.2 therefore gives cumulative absolute signed-mean bounds

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

Indeed their product sums over the prescribed endpoints to at most n^\eta, and the signed opposite diagonal mean is bounded as in Lemma 6.5. 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,

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

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

by the same three outer configurations and the additional 1/l factor. Centering contributes Cf_bB_m. Lemma 6.4 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 (6.2) 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

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

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 6.2. 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:

Its cumulative partner-average contribution is consequently at most

This can be absorbed into the preceding n^\eta/l_0 budget. Directly, its ratio to B_c^2 is

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

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 (6.1). Choose all preliminary losses, the exponent of T_{\rm cap}, and \rho within these strict margins. A common positive c_5 then gives (6.5).□

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 (7.2).

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

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 (7.2); insertion of factors k/h proves the derivative statement. The same argument for a boundary input, and symmetry, gives

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

The formal Woodbury identity and the preceding vanishing give

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

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

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

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 (7.3) 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 Jth 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

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,

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

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 (7.3). 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:

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

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 (7.3). Choose the finite smoothness of \varphi so that \int |\widehat\varphi(\xi)|(1+|\xi|)^{J_0J_*}\,d\xi<\infty. The tapered jth term then has norm O(R_0^{-j}). Summing the finitely many terms proves (7.1).□

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

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

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,

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

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 (8.1). For w bounded below by c_d, use \sum_i|v_i(p)|^2\le1 and enlarge the constant.□

Proof. Partition the bulk slacks into dyadic intervals [2^jW_b,2^{j+1}W_b). Their contributions to [(R_B^\sigma)^2]_{pp} are at most C(2^jW_b)^{-1/2} by (8.1). Their sum, followed by the bounded contribution from slacks bounded below by a constant, proves (8.3).

On the excluded subspace the diagonal mass of R_\sigma(s+w_p) is at most CW_b^{3/2}/W_b=C\sqrt{W_b}, since x_i^\sigma>-e/20 and W_b\gg e. On the included subspace the positive difference of the reciprocal weights is

Its diagonal mass is O(\sqrt{W_b}) by (8.3). Cauchy–Schwarz, applied separately to these two positive operators, gives the entry comparison.

For the typical-edge assertion, the edges added after the separation stop contribute only O(l_0) exceptions. Set r_n=\lfloor .08\log_q n\rfloor+2=.08\log_q n+O(1). At that stop, the global diagram estimate for one return shows that only n^{.08+o(1)} vertices have a nonempty nonbacktracking return of length at most r_n. For an old edge with neither endpoint in this set, the direct edge is the only nonbacktracking path between its endpoints in the short range 1\le k\le r_n-1: an alternative, closed with the direct edge, would give a nonempty endpoint return of length at most k+1\le r_n, after stripping any terminal reversal. The diagonal short-path term is the identity. Bounded fixed-endpoint multiplicity bounds the remaining weighted actual paths, whose lengths begin at r_n, by

The virtual and projection terms are smaller. Thus the stop reference has the normalized endpoint block

The frozen correction is -p_{p,0}^TH_fp_{p',0}, with \|H_f\|\le C. The coefficient bound (4.8) gives

Consequently, outside a fraction at most n^{-.2} of the vertices, the squared row norms are at most n^{-.03}. Take the union of the exceptional sets for the two signs at their comparison points. Fixed degree transfers these vertex exceptions to the same order of edge exceptions, and the frozen correction is then O(n^{-.03}). Finally, h-h_c=O(\sqrt{W_b}), the final entry error is O(B_B), and the bulk entry comparison costs O(\sqrt{W_b}). These errors are smaller than n^{-.024}. All the exceptional fractions just counted are O(n^{-.1}), as asserted.□

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 [MW90]. Switching arguments for local Green-function comparison appear in [BHY19, Sections 7 and 11] and [HY24, Sections 3 and 5]; 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

where

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

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

It has determinant -1, one eigenvalue of each sign, and inverse

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

give

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

This is the Woodbury identity on the positive old bulk [HS81]; no positivity of the old near block is required.

Step 2: give the near spectrum a positive mean shift. The inverse K_\sigma in (8.5) 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

Thus replacing S_B^{-1} in (8.6) 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

Regularity and orthogonality give

For indices in E_0^\sigma, the entry of the single-switch correction is

Its uniform mean is

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

Define the tilted law \nu by multiplying the \nu_0 probabilities by

where B_*>0 is a sufficiently large fixed constant. This is a positive probability density. Indeed, (8.1) and Cauchy–Schwarz bound the absolute value of the bracket by

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

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 (8.7), 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

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:

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

Consequently, the restriction and the probability approximation change the left side of (8.9) by at most

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,

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

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

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, (8.3) therefore gives

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

This is exactly the strict inequality t_*>8b_*-4a. Also n^{-.02}=o(en/M). Markov’s inequality now proves the third assertion of (8.10). 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 (8.10). 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 (8.5) give

Write \mathcal K_\sigma=\operatorname{blockdiag}(K_\sigma,\ldots,K_\sigma). The near Schur complement is exactly

The last term has norm o(e) by the second line of (8.10). The centered fluctuation and the change from \nu to \mu each cost another o(e). The positive mean bound (8.9) 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

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 [Ber12] 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

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 [PR08, Section 2.2]). Enumerate all P^2 seeds (\gamma,\beta)\in\mathbb F_P^2 and use the residues

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

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.□

Proof. Rational parameters. Choose dyadic rational representatives for all power scales, within the fixed factors allowed above. Comparisons for a fixed rational exponent can be made by integer powers, so these representatives require O_d(\log n) bits and are computable in polynomial time. Integer power comparisons similarly determine the logarithmic radii. Approximate the primary h values to sufficiently high inverse-polynomial precision, strictly below 1/\sqrt q; choose the small auxiliary spacings rationally and exactly equally spaced where required. The strict exponent margins preserve every estimate. The piecewise-polynomial cutoff for the smooth reference can have rational breakpoints and coefficients and fixed finite smoothness, for example by rescaling the integral of t^j(1-t)^j at its transition intervals. Its Fourier transform is used only in the proof of an estimate, never by the algorithm.

Candidate computations. There are at most O_d(n^2) choices at a pairing step and O_d(n) steps. Distances, stub eligibility, and exceptional-event flags are finite graph computations. The precision matrices have rational entries of polynomial bit length. Their inverses on \mathbf1^\perp can be computed in a rational contrast basis or after adding the constant projection. The coefficients of the path series are computed from the displayed matrix recurrence, of length O_d(\log n). The frozen reference is evaluated from its explicit Woodbury formula at the current matching, rather than through an uncontrolled sequence of rational expansions.

The structural completion estimators are computed with the colorful dynamic program described in the structural section. Its shapes have O_d(\log n) vertices and bounded treewidth once the fixed excess cutoff has been chosen. The factor 2^{O(k)} for the color subset and the \exp(k)k^{O(\log k)}\log n hash-family size are polynomial in n when k=O_d(\log n). Pending-edge probabilities are rational products with O_d(\log n) factors. These observations give polynomial time and bit length for every such estimator.

All moments have fixed integer order. Traces, squares, even powers, positive parts of rational numbers, comparator values, and uniform conditional expectations are therefore rational and computable in polynomial time. There are polynomially many accounts, including the fixed contrast labels and their pairs.

Discounts. At a step the expectation ratio for an account is computed from its undiscounted local statistic, its fixed phase baseline, and its comparator and event flags. It is not computed recursively from the discounted total. A sum over the polynomially many candidates has polynomial bit length. A discount is a product of polynomially many such ratios; consequently it too has polynomial bit length. Dynamic comparators are explicit rational functions or products of polynomially many polynomial-bit factors. Sums and comparisons of the discounted accounts can thus be carried out exactly.

For completeness, the polynomial bit bounds for static matrix inverses follow from the determinant formula: after a common denominator is cleared, minors of a polynomial-bit matrix of dimension O_d(n) have polynomial bit length by the determinant bound. Exact rational symmetric inertia can be computed by a nonzero diagonal pivot, or, if all diagonals vanish and a nonzero off-diagonal remains, by an invertible 2-by-2 pivot. The remaining zero block contributes zero eigenvalues. Fraction-free elimination [Bar68, Section I] or the minor formulas give the same bit bound for intermediate quantities.

Repair and verification. The repair section constructs inverse-polynomially separated cutoffs, rational polynomial approximations to the required spectral functions, and a polynomial-size prime-field sample space. Enumerating that sample space and performing the graph updates therefore takes polynomial time. The precision exponent is fixed after the analytic margins have been chosen. In particular, after affine rescaling to [0,1], if a spectral cutoff function has a known Lipschitz bound L_f\le n^c and the target error is n^{-C}, its Bernstein approximation may be taken of degree D=\lceil n^{2(c+C)}\rceil, polynomial in n for fixed c,C. Its rational sample values and polynomial coefficients have polynomial bit length. Increasing the fixed precision and prime-denominator exponents pays for both the tilt factor n/J_T and the total probability-rounding error.

For each simple regular candidate, take the explicit rational contrast basis

Its columns are linearly independent and span \mathbf1^\perp. The condition

is equivalent to the strict nontrivial spectral bound and is decidable by exact rational inertia. Indeed, this congruence tests the quadratic form on all of \mathbf1^\perp; an orthonormal basis is unnecessary. Regularity makes that subspace invariant under A_G, so the form is positive exactly when every eigenvalue there has square less than 4q. The repair theorem guarantees that the search finds a passing candidate with a strict spectral inequality.

All constants, polynomial degrees, moment orders, and approximation exponents depend only on d. A sufficiently large finite exponent k_d bounds their combined bit cost. This bound holds once the finitely many large-n requirements are met.□

Proof of Theorem 1.1. Start with d distinguishable stubs at each of n vertices. Apply Proposition 5.1, rejecting stub pairs whose vertices have distance at most the girth exclusion radius. The rejected-pair graph has maximum degree O_d(q^{g_0})=o(l_0), so the candidate set is nonempty throughout this phase. Apply Proposition 6.1 to reach l_0 unresolved stubs. The structural estimates guarantee that these stubs lie at distinct vertices and are mutually separated, with no nonempty short nonbacktracking return at any remaining vertex.

The reference construction and Proposition 7.1 then complete the configuration to a simple d-regular graph. For every primary parameter and both signs, its precision is positive; at the closest parameter this gives

The final entry comparison and the diagonal derivative bound for the same frozen reference give the local spectral mass estimate by Lemma 8.1. The retained path estimates at the separation stop, together with that entry comparison, give the typical bulk edge blocks by Lemma 8.2. These are precisely the remaining hypotheses of Theorem 8.3. Apply that theorem. This produces a simple d-regular graph on the same n vertices with every nonconstant eigenvalue strictly in (-s,s).

The exact-repair theorem also proves connectedness and nonbipartiteness. Proposition 9.1 supplies a finite exponent k_d for the bit cost. Choose n_0(d) to satisfy the finitely many large-n requirements in the construction. This proves all parts of Theorem 1.1.□