A counterexample to the Colin de Verdière chromatic conjecture

Proof. Take the constructed examples in Theorem 1.1 and put m=|V(G)|. They have \alpha(G)\le2. Every well-signed one-negative matrix on these graphs has rank greater than m/2+1, so rank–nullity gives corank less than m/2-1. Maximizing in the larger matrix class yields \kappa(G)+1<m/2. Every matrix admitted in the definition of \mu(G) is admitted for \kappa(G), so \mu(G)\le\kappa(G). The inequality h(G)\le\mu(G)+1 was established above. Combining these bounds with the fractional-colouring estimate proves the chain.□

Proof. That theorem gives \chi_{\mathrm{list}}(G)\le Ch(G). Combining this with h(G)\le\mu(G)+1, proved above, gives the result.□

Proof. Put q=[x_P,x_P]. Then [x_\perp,x_\perp]=-1-q, and y=x_\perp/\sqrt{1+q} is future unit timelike. For z\in F_P, the hyperbolic coordinates above, now in P^\perp, give

with equality at z=y. This proves (2.2).

Use the common point as the time coordinate. For the basis matrix A_i, let t_i be its time-coordinate row and S_i its spatial-coordinate matrix. The projection formula gives \|t_i\|\le\sinh R, and orthonormality gives

For the concatenated matrices S,t, Cauchy–Schwarz over the k blocks gives \|S\|_{\mathrm{op}}^2\le k\cosh^2R and \|t\|^2\le k\sinh^2R. Since [A,A]=S^{\mathsf T}S-t^{\mathsf T}t, this proves (2.3). Finally, if P_i\perp P_j, their sum is positive, and its orthogonal complement contains a future unit timelike vector perpendicular to both.□

Proof. Take z_1 as origin and write z_i=(\cosh r_i,\sinh r_i\,u_i). A direction with r_i=0 can be chosen arbitrarily. For distinct indices set

with -\log0=+\infty, and set a_{ii}=r_i. The exact identity

implies

Here is a dimension-free verification. If \min(r_i,r_j)<1, the triangle inequality and its reverse put both (r_i+r_j-d_{\mathbb H}(z_i,z_j))/2 and a_{ij} between zero and \min(r_i,r_j), giving error at most two. Otherwise, writing

the two terms in (2.5) give e^D/4\le\cosh d_{\mathbb H}(z_i,z_j)\le2e^D. Use \log u\le\operatorname{arcosh}u\le\log(2u) for u\ge1 to obtain an error at most \log4<4.

For i\ne j, define A_{ij} as the largest bottleneck value \min_{0\le t<k}a_{i_ti_{t+1}} over chains i=i_0,\ldots,i_k=j, and put A_{ii}=r_i. Deleting loops never decreases a bottleneck, so only simple chains of at most \ell-1 edges are needed. If a chain has bottleneck h, its endpoint radii are at least h, and the triangle inequality for the direction chords gives q_{ij}\le(\ell-1)e^{-h}. Consequently

Concatenating chains also gives A_{ij}\ge\min(A_{it},A_{tj}) for every t. Take intervals [0,r_i], identifying their points of equal height t whenever t\le A_{ij}. The last inequality makes this an equivalence relation at every height. These equivalence classes are nested as height decreases; their finitely many splitting heights therefore form a rooted finite tree. The distance between the two marked upper endpoints is r_i+r_j-2A_{ij}. Equations (2.6)–(2.7) prove (2.4). Restricting to the hull of the marked points preserves their distances.□

Proof. We first record an identity valid in any metric tree. If p\in[a,b]_T and q\in[c,d]_T, then

Every term is at most the left side by the triangle inequality. If p\ne q, choose an endpoint e whose path from p does not enter the component toward q, and an endpoint f whose path from q does not enter the component toward p. Such choices exist because p,q lie on their respective segments; an endpoint equal to the segment point is allowed. Then the path from e to f passes through p,q, giving equality. If p=q, either choose an endpoint equal to this common point, or choose endpoints in different components of its complement; again equality holds.

A second exact tree identity will locate the new marked points. If P_\theta is at fraction \theta of [A,B] and X is any point of the tree, then

Indeed, if the projection of X onto [A,B] is at distance u from A and at distance h from X, both sides equal h+|u-\theta d(A,B)|. This also holds for a degenerate segment.

Apply Lemma 2.2 to the original configuration together with \widehat p,\widehat q, obtaining a tree T' with error K'=K(\ell+2). Denote their marked points by p',q'. Suppose \widehat p is at fraction \theta of the hyperbolic segment [a,b], and let \widetilde p have that fraction on [a',b']_{T'}. The two exact hyperbolic distances from \widehat p to its endpoints are \theta d_{\mathbb H}(a,b) and (1-\theta)d_{\mathbb H}(a,b). In (2.10), each corresponding difference is therefore at most 2K'. Thus

Together with the K' distance error for the pair \widehat p,\widehat q, this gives

Between the original endpoint sets, distances in T and T' differ by at most K(\ell)+K'\le2K'. Distances from an endpoint to its fractional segment point are that fraction, or its complement, times the segment length. Each term in (2.9) therefore changes by at most 6K', and hence

The total error is at most 11K'. All identities remain valid when an endpoint segment has length zero.□

Proof. For every required pair, choose a point in each of its two flats at distance at most D+1; an infimum need not be attained. Choose also one point in each flat. This gives \ell=k+2|\mathcal D|\le k^2 marked representatives. Apply Lemma 2.2 and work in their tree hull K_s. Let H_{i,s} be the hull of representatives chosen from the i-th flat, and set

The R-neighborhood of a subtree in a tree is a closed subtree: the segment between two of its points lies in the union of their paths to the original subtree and the subtree itself, and stays within distance R of it. For a required pair, the midpoint of its two witness representatives belongs to both neighborhoods. Thus every required contact is preserved inside K_s.

Suppose x\in U_{i,s}\cap U_{j,s}. Choose h_i\in H_{i,s}, h_j\in H_{j,s} at distance at most R from x. Every point of a finite tree hull lies on a segment between two of its defining representatives, allowing a repeated representative when the hull is a point. For example, after fixing one representative the union of its segments to all the others is already their hull. Lift h_i,h_j at their fractional parameters along the corresponding actual hyperbolic segments. Their lifts z_i,z_j belong to their respective flats by convexity, and Lemma 2.3 gives

For any nonempty bag, fix one of these lifts. It has distance at most R_* from every flat in the bag. By Lemma 2.1, their joint Gram norm is at most k(\cosh^2R_*+\sinh^2R_*).

It remains to obtain a single finite combinatorial pattern. Suppress the degree-two vertices of K_s except marked representatives; there are at most 2\ell vertices and at most 2\ell edges. Each U_{i,s} meets an edge in an interval or the empty set. Subdivide every edge at all endpoints of these intervals. This adds at most 2k vertices per edge, so the resulting tree has at most 2\ell(2k+1) vertices. Each U_{i,s} is now a subcomplex. There are only finitely many trees of this bounded size with k specified nonempty connected vertex sets. Along a subsequence the labelled pattern is constant. Take this pattern for T,S_i. Equation (2.11) proves the uniform bag assertion. The final assertion follows from Lemma 2.1 with D=0.□

Proof. Take a maximal matching of size k in the family. Its 2k endpoints cover every edge, so the load bound gives W\le2k. In the second assertion, k\ge m/20 would violate Property (a) with each matching edge given its own class. Hence k<m/20, proving the claim.□

Proof. At a tree vertex x, each subtree missing x is wholly contained in a unique component of T-x. No two components can each contain at least q whole subtrees: taking q labels from each would give two vertex sets with no cross hole, contrary to Property (c). If there is a component with at least q whole subtrees, orient the first edge from x toward that component. Each vertex has at most one outgoing edge. An edge cannot be oriented both ways, since its two orientations would again supply two separated sets of q labels. Following arrows in a finite tree must therefore end at a sink r.

Every component of T-r contains at most q-1 whole subtrees. If q=1, no subtree misses r. If q\ge2 and at least 3q-2 labels missed r, greedily unite components until their total first reaches q. This total is at most 2q-2; the remaining components contain at least q labels. These two separated families contradict Property (c). The sink thus misses fewer than 3q-2, and in particular fewer than 3q, labels.□

Proof. Assign every edge’s weight to one chosen vertex of its subtree. Every finite tree with an assigned nonnegative mass has a vertex whose removal leaves each component with at most half the total mass. To see this, minimize the sum of mass times graph distance from the vertex. Moving to a neighbor in a component of mass greater than half the total would strictly decrease that sum. Such a minimizing vertex is a weighted centroid.

Starting with T, cut at a weighted centroid in every current component whose assigned mass exceeds am/10, and repeat. At depth j each component has mass at most m/2^{j+1}, since the original mass is at most m/2. Consequently at most D_a rounds are needed. At each depth there are at most \lceil5/a\rceil components requiring a cut, because their masses sum to at most m/2. Thus at most K_a cut vertices are used. Mass located at a cut vertex is removed at that cut.

Suppose every bag has edge weight less than cm. Delete every edge whose subtree meets a cut vertex. The deleted weight is less than K_acm=m/40, so the surviving weight W' satisfies W'>m/4. Each surviving subtree is wholly contained in one component of the cut tree; its assigned vertex lies there too. The total surviving weight in each such component is at most am/10. Use the components as classes of surviving edges. Subtrees of different classes are disjoint, so edges in different classes cannot conflict.

Put Q=\lfloor am\rfloor, so Q\ge am/2. Greedily choose a matching, with at most Q selected edges from any class, until no further edge can be added. If k edges have been selected, every surviving edge either meets one of their 2k endpoints or belongs to a class with Q selected edges. The first family has weight at most 2k. There are at most k/Q saturated classes, each of weight at most am/10. Therefore

It follows that k>5m/44>m/20. Its class sizes are at most Q\le am, but it has no conflict between different classes. This contradicts Property (a).□

Proof. Let r be the vertex bag from Lemma 2.6, let z be the edge bag from Lemma 2.7, and let A=\{v\in V_0:r\in S_v\}. Along the path from r to z, each S_v with v\in A is an initial interval. Thus the number of absent labels from A is nondecreasing. If fewer than 2q are absent at z, use x=z. It misses fewer than 3q+2q supplied vertex labels and has edge weight at least cm.

Otherwise let xy be the first edge of this path, in the direction from r to z, for which fewer than 2q labels of A are absent at x, and at least 2q are absent at y. Set

Every subtree indexed by A_- is contained in the x-side of T-xy: it contains r and avoids y. Every subtree indexed by \mathcal E_+ is contained in the y-side: it contains z and avoids x. In particular these two families are disjoint. This uses all root labels absent at y, including labels that ceased to occur earlier on the path; it does not require many labels to disappear on the single edge xy. See Figure 2.

If the bag weight at x were less than cm/2, then \sum_{e\in\mathcal E_+}w_e>cm/2. By Lemma 2.5, \mathcal E_+ has a matching of size greater than cm/4, hence at least q since q\le cm/4. Also |A_-|\ge2q. No selected edge conflicts with any label in A_-, because such a conflict would force intersecting subtrees. Taking any q of these labels violates Property (b). Thus the bag at x has weight at least cm/2; it misses fewer than 5q supplied labels.

Finally, the load bound shows that removing all edges incident with these missing vertices costs less than 5q weight. If q\le cm/30, the surviving bag weight is at least cm/2-5q\ge cm/3, as asserted.□

Proof. For (i), choose c>\lambda_{\max}(D) and put A=I-D/c. All entries of A are nonnegative, and its eigenvalues lie in [0,1). The convergent binomial series gives

Every term is entrywise nonnegative, and the constant term has positive diagonal.

For (ii), take c>\lambda_{\max}(D) and consider A=cI-D. It is symmetric and entrywise nonnegative, with positive diagonal and connected off-diagonal support. A unit vector maximizing its Rayleigh quotient may be replaced by its coordinatewise absolute value, so a nonnegative maximizing eigenvector exists. Its eigenvalue is positive. The eigenvector equation and connectivity imply that it has no zero coordinate: a zero coordinate would force zeros at every adjacent coordinate and then everywhere. Moreover, every vector for the largest eigenvalue has one sign. Indeed, equality in the absolute-value Rayleigh inequality forces equal signs across each positive edge, while its absolute value is a nonnegative maximizing eigenvector and thus has full support. If the largest eigenspace had dimension at least two, it would contain a nonzero vector orthogonal to the positive eigenvector; that vector could not have one sign. The largest eigenvalue is therefore simple.

When D is singular and positive semidefinite, this largest eigenvalue of A is c, so the asserted kernel description follows. If a proper principal submatrix were singular, extend a nonzero vector of zero quadratic form by zero coordinates. Its quadratic form under D is zero, hence it belongs to \ker D by the spectral theorem. This contradicts full support.□

Proof. By Lemma B.1, all measures have bounded mass and support in a common compact interval, so every subsequence has a weakly convergent further subsequence. Fix such a limit \nu, and write \theta=\nu(\mathbb R)\le1. At most one eigenvalue of B_j exceeds 1, hence \nu is supported on (-\infty,1]. For every integer k\ge0, entrywise nonnegativity gives \Tr B_j^{2k+1}\ge0, and therefore \int x^{2k+1}\,d\nu(x)\ge0. If \nu gave mass h>0 to (-\infty,-1-\varepsilon], this integral would be at most \theta-h(1+\varepsilon)^{2k+1}, which is negative for large k. This proves the support assertion. The zero diagonal gives \int x\,d\nu(x)=0. The asserted eigenvalue count follows by applying these facts to any putative subsequence on which the normalized exceptional count stays positive.

For the additional assertion, pass to a subsequence realizing the limsup in (3.2) and then to a weak limit as above. The nullity assumption supplies at least d_j-v_j/2-1 eigenvalues equal to 1. Since singleton sets are closed, weak convergence gives r:=\nu(\{1\})\ge\theta-1/2. Consequently

For -1\le x\le1 we have (1-x^2)^2\le1-x^2\le2(1+x), and the first expression vanishes at x=1. Polynomial integrals converge on the common compact support, so

In this argument the bound on \|B_j\| is fixed before j tends to infinity. It removes the contribution of any exceptional eigenvalue to each fixed moment; it does not enter the resulting bound.□

Proof. Put

The diagonal entries of B^2-I show that \sum_i(d_i-1)^2\le\varepsilon v. Nonnegativity also gives

Call row i good when |d_i-1|\le\tau and r_i\le\tau^2. There are at most 2\tau^2v bad rows. In a good row, let a_i=\max_j B_{ij}^2. Then

Because \tau\le1/8, it follows that

For the last inequality, use 1-\tau-\tau^2/(1-\tau)\ge(1-\tau)^2 and a_i\le1+\tau\le(1+\tau)^2. There is a unique entry attaining a_i. If its other endpoint is good, symmetry forces it to be the dominant entry there as well, since its square is at least 6/7 whereas every nondominant squared entry in a good row is at most 8\tau^2/7. These good–good pairs form the required matching.

For any set S of rows, Cauchy–Schwarz gives

Thus the total squared row mass at bad rows is at most (2+\sqrt2\tau)\tau^2v. Every good row whose dominant endpoint is bad contributes at least 6/7 to this mass, by symmetry. The total number of omitted coordinates is consequently at most

For a retained row, its contribution to \|B-W\|_{\mathrm F}^2 is at most \tau^2+8\tau^2/7=15\tau^2/7. By (3.6), the omitted rows contribute at most (5+\sqrt5\tau)\tau^2v. Since d\le v and \tau\le1/8, the sum is less than 8\tau^2v. The remaining assertions have already been proved.□

Proof. Let J_j be the joint Gram matrix. Its negative part has rank at most one and norm at most K. Replacing J_j by its positive part changes any normalized trace by O(K/v_j) and changes a Frobenius norm divided by \sqrt{v_j} by O(K/\sqrt{v_j}). Write the resulting positive semidefinite matrix as

A rank-one perturbation changes the number of eigenvalues above any fixed threshold by at most one, by the variational characterization of eigenvalues. Thus the spectral projector E_{\mathrm{hi}} of D_j for (2+\varepsilon,\infty) has rank o(v_j). Put E_{\mathrm{lo}}=I-E_{\mathrm{hi}}. Factor P_j as a Euclidean Gram matrix, say A_j=U_j^{\mathsf T}U_j, D_j=V_j^{\mathsf T}V_j and C_j=U_j^{\mathsf T}V_j. Since \|V_jE_{\mathrm{lo}}\|^2\le2+\varepsilon,

On the other spectral subspace, \|C_jE_{\mathrm{hi}}\|_{\mathrm F}^2\le K^2 \rank E_{\mathrm{hi}}=o(v_j). Divide by v_j and take the limsup. This first bounds \|C_j\|_{\mathrm F}/\sqrt{v_j}. The original cross block differs by Frobenius norm at most K, so it has the same squared normalized limsup bound, at most (2+\varepsilon)\eta. Finally let \varepsilon\downarrow0. In particular the hypotheses force \eta\ge0, since the normalized trace of the original H_j block has nonnegative liminf.□

Proof of Theorem 3.1. Use the constant c=c(a)>0 from Lemma 2.7; explicitly we may take

Fix a,\beta,m,G as in the theorem with these choices, and put

These choices imply

Suppose the conclusion fails. There is then an unbounded sequence of integers s and corresponding well-signed matrices M_s with one negative eigenvalue such that, writing v=ms,

All subsequences below keep a,\beta,m and the graph G fixed, and s\to\infty is the only limiting operation. An expression o(v) has ratio to v tending to zero in this limit; its constants may depend on the fixed graph and subsequence. The displayed constants in the errors involving \delta or \tau are absolute.

Represent M_s by Lorentz Gram vectors, one for each blow-up vertex. An original vertex label u\in V(G) specifies its s-column clique block. By passing to a subsequence, the set of labels whose clique blocks have a negative eigenvalue can be fixed. Two such labels cannot be a hole: zero cross Gram would make their negative directions orthogonal and give two negative eigenvalues of M_s. These labels therefore form a clique in G. There are fewer than 2q of them, since two disjoint q-element subsets of a larger clique would violate condition (iii). Discard these labels.

The other clique blocks are positive semidefinite. They have strictly negative off-diagonal entries; Lemma 3.2 shows that deleting at most one coordinate makes each positive definite. Work with s\ge2, and apply Proposition 2.4 to their positive spans. For every hole between two labels the blocks are orthogonal, so their tree subtrees intersect. By Lemma 2.6, there is a bag missing fewer than 3q of the supplied single labels. Keep the labels in this bag and denote their set by U. There are fewer than 5q missing original labels. The retained coordinate dimension d_s satisfies

The tree and the chosen bag are fixed on a further subsequence.

Normalize each retained clique block by its positive inverse square root, and denote the resulting column lists by X_u, u\in U. Their diagonal Gram blocks are identities. By Lemma 3.2, the normalizing coefficient matrices are entrywise nonnegative with positive diagonal. Thus cross blocks remain zero on holes and strictly negative on base edges. The full Gram matrix of the X_u is

The bag bound from Proposition 2.4 and Lemma 2.1 makes \|B_s\| uniformly bounded in s. The rank is at most that of M_s, and its negative index is at most one. Consequently Lemma 3.3 gives

Since \delta>0 is fixed, the left-hand quantity before taking a limsup is at most 3\delta=\tau^4 for all sufficiently large s. Apply Lemma 3.4 to obtain a coordinate matching with p_s^0 pairs and adjacency matrix W_s. Then

Every pair connects two different adjacent base labels, because B_s vanishes within each original block and on base holes.

Group the pairs by their unordered label pair e=\{u,w\}\in E(G). If group e contains k_e(s) pairs, pass to a subsequence on which every k_e(s)/s converges, and put

There are only finitely many types, so we may also fix whether each group is empty or its endpoint Gram block is positive definite, singular positive semidefinite, or has a negative eigenvalue.

Groups in the last category will not be candidates for the second normalization. Their types are pairwise touching: a conflict between two of them would make their cross Gram zero and give two orthogonal negative directions. Choose a maximal ordinary matching of these types in the base graph, of size k. If k\ge m/20, putting each edge in its own class contradicts (i), since am\ge1. Thus k<m/20. The 2k endpoints of this maximal matching cover all the types under consideration. The load bound in (3.15) therefore gives

Their coordinate pairs are retained in the first matching.

For every group of positive weight with positive semidefinite endpoint Gram, that Gram has the form

The graph of negative entries is connected. If the group is singular, delete one whole matching pair. By Lemma 3.2 its remaining Gram block is positive definite. Positive weight ensures that the group is eventually nonempty after this deletion. There are at most \binom m2 groups, so these deletions cost O(m^2)=o(v) coordinates. Call the resulting positive definite groups of positive weight the candidate groups. Groups of zero limiting weight need not be candidates and keep their pairs in the first matching. By (3.14), (3.16) and \tau\le1/8, the total candidate weight satisfies

3.3 A common bag for both normalizations

Apply Proposition 2.4 again, this time to the single-label positive spans for all u\in U together with the positive spans of all candidate groups. These spans are allowed to overlap. The required subtree contacts hold in each of the following cases: two single labels form a hole; two group types conflict; or a group type and a single label conflict. In each case all cross Gram entries vanish, so the positive spans are orthogonal and their flats intersect.

The candidate weights satisfy Lemma 2.7, so a bag has group weight at least cm. Apply Proposition 2.8 to the supplied single labels U and these groups, using q\le cm/60. It yields a bag containing all but fewer than 5q labels of U, and containing candidate group weight at least cm/2. The common-bag proof uses all root labels absent after its threshold edge, so it applies equally when the losses occur one label at a time.

Discard from the remaining coordinate matching every pair incident to one of the missing labels of U. This removes whole label-pair groups and at most 5qs pairs. Denote the surviving total number of pairs by p=p_s. Let \mathcal T be the candidate groups in the common bag whose endpoints both remain, and let t=t_s be their total number of pairs. Since the load at a missing label is at most one, the limiting weight lost from the bag is at most 5q. Thus

For the last inequality in (3.18), use 5q/m\le\delta=\tau^4/3 and \tau\le1. All group counts have limits after the earlier subselection, so t/v does as well.

Write X for the list of the 2p surviving matched endpoint columns, still in the first normalization. For e\in\mathcal T, let k_e denote its remaining number of pairs and write X_e for its 2k_e-column sublist, D_e=\langle X_e,X_e\rangle, and

The common bag gives a uniform operator bound for the joint Gram of the first-normalized single blocks and all Q_e. Passing to the sublist X does not increase this bound. This point controls Q_e even when some eigenvalues of D_e tend to zero and the coefficients in D_e^{-1/2} become large.

3.4 The additional positive directions

For each surviving pair j=\{i,i'\} choose an order of its endpoints and form

The coefficient maps producing either list from X are Euclidean isometries. The restriction of I-W_s to retained pair endpoints has Gram 2I on the difference coefficients. Hence (3.4) and contraction of Frobenius norm give

Also \langle H_j,H_j\rangle=1-(B_s)_{ii'}, so

These statements persist after all the pair deletions: they are restrictions of the original matching estimates.

The coefficients in each D_e^{-1/2} are entrywise nonnegative. Distinct groups have disjoint endpoint coordinates, and all cross Gram entries between such coordinates are nonpositive. Coordinates with the same base label have zero interaction, since the first diagonal blocks are identities. Therefore

It is bounded in operator norm and has at most one negative eigenvalue. By Lemma 3.3, its limiting spectral support lies in [0,2]: more precisely, for every fixed \varepsilon>0 there are o(v) eigenvalues outside [-\varepsilon,2+\varepsilon]. The joint Gram of (H,Q) is bounded by the common bag. Applying Lemma 3.5 to (3.22) yields the absolute estimate

In particular, no factor depending on the norm of the common bag appears here.

Fix a candidate group e\in\mathcal T. Let U_e be the 2k_e\times k_e Euclidean isometry whose columns are the coefficient vectors of its pair differences. Then

Because D_e is positive definite, T_e has rank exactly k_e. Choose a 2k_e\times k_e matrix L_e whose columns are an orthonormal basis of (\im T_e)^\perp. Thus

This uses the full span of all the group’s original difference directions; no small singular direction is discarded. Write L=\diag(L_e)_{e\in\mathcal T} and Y=QL. The list Y has exactly t columns.

For a pair j outside group e, each of the two numbers x=\langle X_i,(Q_e)_k\rangle and y=\langle X_{i'},(Q_e)_k\rangle is nonpositive. Consequently

This includes pairs in noncandidate groups. Let Z be \langle R,Q\rangle with the entries between each R_e and its own Q_e replaced by zero. Then \|Z\|_{\mathrm F}^2\le\|\langle H,Q\rangle\|_{\mathrm F}^2, and (3.25) gives \langle R,Y\rangle=ZL. Since L is an isometry, Frobenius contraction and (3.24) imply

Put E_s=\langle Y,Y\rangle=L^{\mathsf T}\langle Q,Q\rangle L. Every diagonal group block of E_s is an identity, so

This is a Euclidean coefficient compression. The variational characterization of eigenvalues shows that the number of eigenvalues of E_s above 2+\varepsilon is at most that for \langle Q,Q\rangle, hence is o(v). Its norm is bounded. If k_s denotes its number of eigenvalues greater than 1/4, use the cutoff 2+\varepsilon=5/2 to obtain

Possible negative eigenvalues only decrease the left-hand trace contribution in this upper estimate. Rearranging gives

Finally consider the joint Gram matrix of (R,Y). By (3.21), the number of eigenvalues of \langle R,R\rangle at most 1/4 is at most

Restrict the two diagonal blocks to their spectral spaces above 1/4. This leaves at least p-(128/49)\tau^2v dimensions on the R side and t/3-o(v) on the Y side. The restricted cross matrix has squared Frobenius norm at most \|\langle R,Y\rangle\|_{\mathrm F}^2. Delete from the first side its left singular directions with singular values greater than 1/8. The number deleted is at most 64\|\langle R,Y\rangle\|_{\mathrm F}^2. The remaining diagonal blocks are greater than I/4, and the cross operator norm is at most 1/8. For their coefficient vectors x,y, the joint quadratic form is bounded below by

so this remaining space is positive definite. Using (3.27), the positive index of the joint Gram is at least

Every column used here is a linear combination of the original Lorentz Gram columns for M_s. The joint Gram is therefore a coefficient pullback of M_s, and its positive index is at most \rank M_s. This argument does not require the combined list (R,Y) to be linearly independent.

Combine (3.18), (3.19) and (3.30). Since \tau\le1/8,

where the last inequality uses \tau\le c/2340. This contradicts (3.11), whose normalized right-hand side tends to 1/2. Hence only finitely many s can violate the stated rank bound. The positive gap also shows directly why the literal additive +1 is harmless for all sufficiently large s.

Every matrix in the definition of \mu(G[K_s]) is among the matrices just considered. Rank–nullity gives \dim\ker M<ms/2-1, and taking the maximum yields \mu(G[K_s])+1<ms/2 as asserted.□

Proof. Fix a base coordinate in O_{d,t}. It is allowed at exactly (g-1)/2 tags. A strict majority therefore contains a tag where that coordinate is disallowed. Every row and column involving it is zero in W_l for that tag. A matrix in the intersection consequently has zero rows and columns at all O-coordinates.

The coordinate projection that sets all O-variables to zero sends each point moment to a point moment defining W_*. Applied on both matrix factors, it fixes the matrix just described. That matrix is therefore in W_*, proving the nontrivial inclusion.

If w,w' give the same differences, then w_l+w'_l=w_{l'}+w'_{l'} for every pair of tags. Their difference is a constant tuple. Its value belongs to every W_l, hence to W_*. Conversely every such constant tuple lies in the kernel of the cut map.□

Proof. Symmetry follows by interchanging the endpoints. A loop would have U_i\lambda_i=U_i\lambda_j, hence \lambda_i=\lambda_j by injectivity, contradicting the last equation of Equation (4.17).

Suppose that three distinct raw vertices have holes on all three pairs. For a directed incidence ij, let x_{ij} be its witness at i. For distinct i,j,k, evaluate the gradient identity for ij on x_{ik}:

Sum over the six ordered choices of (i,j,k). For fixed j, the two arguments on the left are equal by the sharing equation for the remaining edge ik, so they cancel. For fixed i, the two bilinear terms cancel by symmetry of T. The remaining sum is

a contradiction.□

Proof. Write \Phi=B\trans:V\to W^* and \Phi'=(B')\trans:V\to W^*. Both are surjective. The based map f:A(U)\to A'(U) given by f(Au)=A'u satisfies \Phi'f=\Phi. It therefore maps A(U)\cap\ker\Phi isomorphically onto A'(U)\cap\ker\Phi'. Extend this restriction to an isomorphism L_0:\ker\Phi\to\ker\Phi'.

Choose a complement U_0 of A(U)\cap\ker\Phi in A(U). Its images under \Phi are independent. Extend a basis of \Phi(U_0) to a basis of W^*, and choose lifts of the added basis vectors under \Phi and \Phi', respectively. For the basis vectors in \Phi(U_0), choose the lifts in U_0 and their images under f. Define L to equal L_0 on \ker\Phi and to carry each chosen lift to its primed lift. These are direct-sum decompositions of V, so L is an isomorphism. It extends f and satisfies \Phi'L=\Phi, which is equivalent to the two required frame identities.□

Proof. The raw law is invariant under L on each V_e^+ and L^{-\mathsf T} on V_e^-, independently at vertices and components. For primal tuples, their restricted Gram is fixed by E. By Lemma 5.1, all based realizations with that Gram and individual injectivity lie in one orbit. Projection of an invariant uniform raw law is uniform on this orbit: an element carrying one partial realization to another bijects their full-frame completions. There is at least one completion because these tuples are restrictions of a raw frame. After fixing X_e\trans Y_e, the same argument applies to arbitrary full-frame coefficient tuples. Independence over raw draws and components proves (a).

For (c), the action is transitive on injective plus frames, so their marginal is uniform. Given a plus frame, each column of Q has specified evaluations against P,X, while each column of Y has zero evaluations against P. There is no other constraint until full minus injectivity is imposed. The remaining allowed set is therefore the product of those affine column spaces restricted to full rank.

Each column space contains the common translation space \operatorname{ann}(\im[P,X]), of dimension N-d-h. For a nonzero coefficient vector c\in\F^{d+h}, the corresponding linear combination of minus columns is consequently uniform on an affine space containing that translation space. Its chance of being zero is at most 2^{-(N-d-h)}. Union over the fewer than 2^{d+h} nonzero coefficient vectors gives the asserted bound 2^{2(d+h)-N}.

Alternatively, condition first on P,Q. The allowed X-columns lie in \ker Q\trans, the allowed Y-columns in \ker P\trans, and their two full-rank restrictions are separate. This proves the stated conditional independence. For example, before imposing injectivity of [P,X], any dependence with a nonzero X-coefficient has probability at most 2^{-(N-d)}; union over its at most 2^{d+h} coefficient choices gives a bound 2^{2d+h-N}. The estimate for Y is identical.

The marginal of X alone is invariant under \GL(\F^N) and supported on injective maps; transitivity gives its uniformity, and likewise for Y. Before conditioning independent channel columns to be injective, their evaluations on a fixed independent q-tuple form a uniform h-by-q matrix. For each nonzero coefficient vector in \F^q, the chance that its evaluation is zero is 2^{-h}. Union over those coefficient vectors gives at most 2^{q-h}, and channel injectivity has probability at least 1/2 for large N. This proves Equation (5.3). To compare their joint marginal with completely independent columns, condition on G=X\trans Y. The conditional marginal is uniform on the orbit of two individually injective h-frames having Gram matrix G. Under independent uniform columns that orbit has probability at least 2^{-h^2-2} for large N, by the argument for (d) below. Since the raw probability of any G is at most one, the density ratio on every such orbit is at most 2^{h^2+2}. Multiply over the fixed number of components to obtain the joint channel bound. Its possible dependence on h is harmless: h is fixed before n grows.

We next prove (b), keeping explicit the dependence on the rank. Replace each tested tuple by a basis of its nominal span; inconsistent dependent prescriptions have probability zero. For the plus directions at the two endpoints, start with completely independent uniform plus columns and then impose individual full-frame injectivity. The image of a rank-t_+ tuple in the joint nominal direct sum is exactly uniform on t_+ independent ambient vectors before this conditioning. Indeed, at each ambient coordinate the coefficient map is a surjective linear map onto \F^{t_+}, and different ambient coordinates use independent input bits. Full injectivity has probability 1-2^{-\Omega(N)}, uniformly over the given construction, so the plus prescription costs at most (1-2^{-\Omega(N)})^{-1}2^{-t_+N}.

Now condition on all plus frames. At a component let S be the span of both endpoints’ plus columns; then \dim S\le2(d+h). Before minus injectivity, every minus column has an affine distribution whose translation space contains S^\perp. Split off an independent uniform S^\perp-part of each column and condition on the remaining parts. For a rank-t_- tuple of minus coefficient combinations, the S^\perp-parts of its images are independent uniform vectors in S^\perp, because the coefficient map has rank t_-. Thus prescribed minus images have probability at most

The additional conditioning on the two minus frames being injective changes this by a factor 1+2^{-\Omega(N)}, by (c). Perform this argument componentwise. There is a fixed total conditioning factor bounded, for example, by 4^{|\cE|}, and the resulting bound is

Choose M_0 so that 2(d+h)/N<\epsilon/2 for large n, and then increase n so that the fixed prefactor is at most 2^{\epsilon N/2}. Since t=t_++t_-\ge1, this proves Equation (5.2) uniformly for every allowable t. In particular, mixing the two endpoints in a direction causes no loss of an entire N-bit image constraint.

Finally, to prove (d), the plus columns are independent with probability at least 1-2^{p-N}: each nonzero coefficient dependence has probability 2^{-N}. Given their independence, each minus column takes its required evaluations with probability 2^{-p}, independently, so the Gram costs 2^{-pq}. Under this Gram conditioning, every nonzero combination of minus columns is uniform on an affine space of dimension at least N-p. Its probability of vanishing is at most 2^{-(N-p)}. Union over fewer than 2^q combinations gives failure probability at most 2^{p+q-N}. This proves the lower bound. For the upper bound with plus injectivity required, condition on the plus columns and use the exact 2^{-pq} Gram probability whenever they are independent. A partially specified consistent Gram contains some full specification; for bounded p,q, the same positive lower bound for that full specification proves the last assertion.□

Proof. Include every ambient vector in each A_e^\pm independently with probability p=2^{-\rho N}; subsets for different components and signs are independent. Fix a complete primal frame f, and let \nu_f be the original conditional channel law. Define its survival fraction Z_f=\nu_f(\text{\text{Equation (5.5)}}), a random variable in the random subsets. Channel injectivity makes the q_h nonzero values in each component and sign distinct. Consequently

For any transpose-rank test T, or any union of at most N such tests, the numerator Z_{f,T}=\nu_f(T\cap\text{\text{Equation (5.5)}}) similarly has expectation p^{k_h}\nu_f(T).

We establish simultaneous concentration of these fractions by the bounded-differences method [1, 22], with the needed exponential-moment estimate included below. By Lemma 5.2(c), a prescribed nonzero channel combination, conditional on f, has probability at most 2^{-(N-d)+1} of taking any prescribed value for all sufficiently large N. Indeed before full-frame injectivity it is uniform on the appropriate annihilator, and injectivity has probability 1-2^{-\Omega(N)}, uniformly in f. Changing one membership bit of a subset can therefore change any such fraction by at most

where C_h is fixed in n. There are 2e_*2^N membership bits, so the sum of their squared influence bounds is at most

For clarity, expose these independent bits and use the Doob martingale of any one fraction. A centered increment whose conditional range has length at most c has exponential moment at most \exp(t^2c^2/8). To see this, the second derivative of its log moment generating function is the variance under an exponential tilt, at most c^2/4; integrate twice using value and derivative zero at the origin. Multiplication of the conditional bounds and Markov’s inequality give

Take u=\epsilon_N=2^{-N/10}. Since d/N can be made arbitrarily small by increasing M_0, these tails are at most 2\exp(-c_{g,h}2^{N/2}). There are 2^{O(N^2)} primal frames and 2^{O(N)} primitive transpose tests, since their tuple lengths are bounded by the fixed q_{\rm test}. The unions of at most N primitive tests therefore number at most 2^{O(N^2)} as well. A union bound gives simultaneous error at most \epsilon_N for all these denominators and test numerators. The same argument for 2^{-N}|A_e^\pm|, whose bit influences are 2^{-N}, gives |A_e^\pm|/2^N=(1+o(1))p.

We include the translated numerators in this simultaneous estimate. Fix f,e,\pm,v\ne0, and let Z_{f,v}^{\pm,e} be the original conditional probability of survival and of the event in Equation (5.7). Consider, for example, sign +. If X_ec+v coincides with another already required nonzero channel value X_ec', then v=X_e(c+c') is a nonzero channel value. The original probability of this possibility is at most C_h2^{-N+d}, by the point bound and a union over the nonzero coefficients. On that exceptional event we bound the extra test by one; the survival probability over the random subsets is still p^{k_h}. In every other case X_ec+v is a new membership bit and supplies an additional factor p. This includes the case X_ec+v=0, since zero is not among the required nonzero channel values. Union over c yields

A changed membership bit can affect this numerator only by being an original channel value or a translated channel value. Both have point probability at most C_h2^{-N+d}; hence the same influence and concentration estimates apply. The additional 2^N choices of translate do not affect the union bound. We may therefore fix one realization of all subsets for which every displayed concentration statement holds simultaneously.

Our choice of \rho gives k_h\rho<1/100. Thus

uniformly, and the relative error tends to zero exponentially. The pointwise density of \pi with respect to \rawlaw is the survival indicator divided by Z_f. Consequently

for large N; the primal law was left unchanged by definition. Division of Z_{f,T} by Z_f gives \pi(T\mid f)=\nu_f(T)+O(\epsilon_N/p^{k_h}), uniformly in every specified fixed test. Average over the original primal marginal and apply Equation (5.3) to prove (b). Every fixed finite union is among our tested unions once N is large enough; applying the same numerator estimate directly to that union gives its raw probability plus the stated error, without replacing the union probability by the sum of its constituent probabilities. Finally, dividing the translated numerator by Z_f bounds it by

for all sufficiently large N. This proves (c) and the lemma.□

Proof. If the summed intersection dimension exceeds 2D, choose 2D independent common-image vectors, componentwise. Write each as P_{1,e}a=P_{2,e}b. Their nominal relation directions (a,b) are independent in the direct sum of the two primal coefficient spaces at that component. Indeed a dependence between the pairs would, after applying P_{1,e}, be the corresponding dependence between the selected common-image vectors. Across components their ranks add.

There are at most 2^{O(n)} ways to choose this bounded number of coefficient pairs and their component indices. For each choice, Equation (5.2) bounds the probability of their zero images by 2^{-(1-\epsilon)2DN} under \rawlaw^2. After paying 2^{DN} for \sigma, and making the coefficient count a sufficiently small fraction of N by the choice of M_0, the union bound is 2^{-\Omega(N)}.

Suppose U_1\lambda_1=U_2\lambda_2=\xi. The column space of \xi_e lies in both primal plus spans. Since multiplication by the two injective frame maps preserves matrix rank,

This proves the total-rank assertion.

Take any representation (w_l)_l of one of the profiles. A component w_l+w_{l'} is nonzero whenever w_l\ne w_{l'}, so there are at most 2D unequal unordered pairs. If no value occurred at a strict majority of tags, write c_v for its multiplicities. Then

a contradiction. Let the majority have size g-z. There are at least z(g-z)\ge zg/2 unequal pairs, hence z\le4D/g. Its common value belongs to W_* by Lemma 4.1, so subtract it from every coordinate. The resulting representation vanishes at a strict majority. It is unique: two such representations differ by a constant, and their two majority zero sets intersect.

Finally, equality of the component tensors gives equality of their ambient traces. By cyclicity of trace and Equation (4.12),

For e=\{l,l'\}, it follows that

This value is independent of the tag. The two sparse representations together have at most 8D/g=32000<g nonzero coordinates, so some tag has both entries zero. The common value is therefore zero. Summing over tags proves equality of the two specified \chi_*-values.□

Proof. We give the finite procedure and its quantitative bounds. Work first with the original, unnormalized restriction of \sigma obtained by removing the intersection exception. In particular its density is still at most 2^{DN} relative to \rawlaw^2. Let R be its residual support. As long as its residual mass exceeds 2^{-\zeta N}, begin with its normalized restriction and no pins. If Equation (5.10) fails, condition on a violating image constraint and add its nominal directions to the pins. Given the existing pins, a consistent tuple constraint can be reduced to a basis of its span modulo the pins. The other prescriptions are either automatic or inconsistent; an inconsistent event cannot violate a positive probability bound. Thus every step adds positive rank.

If the cumulative added rank is u, the unnormalized mass of the current part is greater than

The cumulative directions are independent after taking a basis, so the absolute density cap and Equation (5.2) give the upper bound

Comparing the bounds yields

This is strictly below the rank budget K_1. The same comparison applies to a whole violating tuple at once, so a large tuple cannot jump beyond that budget. The rank therefore cannot increase indefinitely. The process reaches a part with no violating constraint; remove that entire part as a leaf and restart on the residual. The underlying raw unit space is finite, and every leaf is nonempty, so the procedure terminates with residual mass at most 2^{-\zeta N}.

A leaf of rank u\le K_1 has mass greater than 2^{-\zeta N-(1-\zeta)uN}. Dividing the original density cap by this lower bound shows, for example,

This proves (a), including uniformity of its density constant.

For (b), write the current normalized mixture as \sum_\lambda w_\lambda\sigma_\lambda. Let q_\lambda be the relative mass retained by the combined restriction in leaf \lambda, and let q=\sum_\lambda w_\lambda q_\lambda=2^{-o(N)}. Discard leaves for which q_\lambda<2^{-\zeta N}. Their mass in the restricted law is at most

On every other leaf, division by q_\lambda multiplies probabilities by at most 2^{\zeta N}. For t\ge1,

This proves the claimed min-entropy and density bounds. It also explains why the small mass bound is needed for the mixed law, rather than separately asserted for every old leaf.

Throughout these operations, disintegration over the finite parts is exact. Multiplying each normalized part by its actual mass recovers the retained law. This proves the last assertion as well.□

Proof. The palette size is fixed, so deleting light colours costs at most a fixed multiple of 2^{-\zeta N}. Every retained conditional colour law has absolute density at most 2^{(3000g+\varepsilon_{\rm ch}+\zeta)N}\rawlaw^2, which is below 2^{DN}\rawlaw^2. The intersection exception and the residual mass in Lemma 5.6(a) are exponentially small uniformly over these laws. Multiply each normalized leaf by its actual colour mass and its mass within that colour. Summing recovers exactly the retained restriction of the original law, so its endpoint marginals are bounded by the original ones divided by the total retained mass. This proves the asserted pooled bounds. The final assertion is precisely Lemma 5.6(b), applied to this mixture. In particular no inverse colour mass enters the pooled marginal constant.□

Proof. Under the raw primal law, each P_e is uniform injective. Two independent such images have nonzero intersection with probability at most (2^d-1)^2/(2^N-1), by a union bound over nonzero coefficient pairs. The primal marginals under \theta have density at most L relative to those laws. Union over components therefore bounds the probability of any plus-span intersection by O_g(L^22^{2d-N})=2^{-\Omega(N)}. If the plus spans are disjoint in every component, a tensor common to the two endpoint primal tensor spaces has every component zero: each of its column spaces lies in the corresponding plus-span intersection. Injectivity of the primal frame maps then makes the sharing witnesses zero, contrary to the parity sum one in Equation (4.17). A hole is thus included in the exceptional event just bounded.

Before deleting internal holes the pair law is at most L^2\pi^2. For a rank-t exact-image event, Equation (5.2) and Equation (5.6) bound its probability by

Take \epsilon<\zeta/4. Since \varepsilon_{\rm ch}<\zeta/4 and t\ge1, division by the nonhole probability 1-2^{-\Omega(N)} leaves this at most 2^{-(1-\zeta)tN} for large N, uniformly for all ranks. The same normalization gives the endpoint caps. Empty pin spaces have zero primal projections, which gives the assertion about C_i.□

Proof. Let H be the 2^d-square matrix with entries H_{xy}=(-1)^{x\cdot y}. For x,x'\in\F^d,

The second value is zero by pairing y with y+e_j at any coordinate where x+x' is nonzero. Thus the Euclidean operator norm of H is 2^{d/2}.

For (b), set a_x=\alpha(x)f(x) and b_y=\beta(y)g(y). Then

and similarly for b, proving the result.

For (a), invertible changes of coordinates reduce the form to the dot product on its d active coordinates. Average each bounded weight over its inactive coordinates. Apply (b) to the uniform probabilities p_1=p_2=2^{-d}. A bounded-density change can be absorbed into the weights after dividing their bounds by C_1,C_2.

Finally, the matrix of the full bit form in (c) is C\otimes I_N. Choose bases reducing C to \operatorname{diag}(I_{\rank C},0); the tensor matrix then has rank N\rank C. Apply (a), absorbing any within-group phases into the corresponding bounded weight.□

Proof. Every point matrix has the stated identities. Conversely the space specified by these identities has a basis consisting of the matrix supported at (0,0), the matrices supported at (0,i),(i,0),(i,i), and the matrices supported at (i,j),(j,i) for 0<i<j. The first is the point matrix at zero. The second is the sum of the point matrices at zero and at the ith unit vector. The third is the sum of the point matrices at zero, at the ith and jth unit vectors, and at their sum. This proves the first assertion.

To isolate a selector s among u distinct selectors, for each other selector choose a coordinate on which it differs from s, and take the product of the corresponding affine bit functions that equal one at s and zero at the chosen other selector. This polynomial has degree at most u-1 and evaluates to the indicator of s on the specified set. Applying these interpolating linear functionals to a relation among the evaluation vectors proves independence.□

Proof. Choose a linear combination of point matrices representing w. It defines a linear functional \Lambda on the Boolean functions of selector degree at most 2j_* and base degree at most two. The matrix w is the matrix of the pairing B(f,g)=\Lambda(fg) on functions of base degree at most one and selector degree at most j_*. Products and degrees here are in the Boolean algebra, so each variable satisfies x^2=x.

Let V_j denote the subspace with selector degree at most j, and let r_j be the rank of B|_{V_j\times V_j}. The sequence r_j is nondecreasing and bounded by R_*. Because j_*\ge 6R_*+4, there is j\ge4R_*+2 such that

Indeed, if no such three successive values occurred between levels 4R_*+2 and j_*, every two successive increments in that interval would contain a strict increase, giving more than R_* increases.

Let Q be the quotient of V_{j+2} by the radical of its restricted pairing. The induced pairing on Q is nondegenerate. Equality of the first and last ranks in (6.3) means that the image of V_j is all of Q: its dimension is at least r_j=\dim Q. Since the quotient pairing is nondegenerate, a vector of V_j pairing to zero with V_j consequently pairs to zero with V_{j+2}. For a selector coordinate s_a, define M_a[f]=[s_a f] using f\in V_j. This is well defined: if [f]=0, then for every g\in V_j,

and V_j spans Q. The same identity proves that M_a is self-adjoint. Replacing s_bf by a representative in V_j and transferring s_a to the other argument gives

All representatives needed in this comparison lie in V_{j+2}. Thus M_aM_b=M_bM_a and, since s_a^2=s_a, M_a^2=M_a.

Commuting idempotents over \F have a simultaneous eigenspace splitting

For completeness, a single idempotent splits its space into kernel and image; all the other commuting maps preserve both summands, so iteration proves the assertion. Distinct joint eigenspaces are orthogonal, by self-adjointness of a coordinate on which their labels differ. Each nonzero summand has positive dimension, so |L|\le\dim Q\le R_*. Define Z_s by pairing the projections onto Q_s of the affine base coordinates. Then Z_s is symmetric and \rank Z_s\le\dim Q_s.

Repeated application of the M_a gives the class of a base coordinate times any selector monomial of degree at most j. It follows that (6.2) reproduces all moments of selector degree at most 2j. To verify the diagonal identity separately on a label, use an interpolating selector polynomial e_s of degree at most |L|-1. Its operator on Q is the projection onto Q_s. The Boolean identities give

which is (Z_s)_{ii}=(Z_s)_{0i}. The interpolation degrees are within j.

Extend the right side of (6.2) to the full row and column indexing. Its rank is at most \sum_s\dim Q_s\le R_*. By Lemma 6.1 it belongs to W. If its difference from w were nonzero, choose a nonzero difference moment of minimal selector degree d'>2j. Write its selector monomial as the product on a set U of size d', and keep the two affine base coordinates in that moment fixed. Index rows by the subsets A\subset U of size \lfloor d'/2\rfloor and columns by the complementary monomials U\setminus A' with the same indexing. The union A\cup(U\setminus A') is U exactly when A=A'; otherwise its degree is smaller than d'. The difference on this square submatrix is therefore the identity. Both its row and column degrees are at most j_*, whereas its rank is \binom{d'}{\lfloor d'/2\rfloor}>2R_*. This contradicts the rank bound 2R_* for the difference and completes the proof.□

Proof. For one projected space, choose a basis from its members admitting such sparse representations, for the span of all these members. There are at most K chosen members. Comparing any further sparse member with its expression in this basis uses at most (K+1)(R_*+14) labels. Their evaluation vectors are independent by Lemma 6.1 and (6.1). Consequently every label of the further member occurs in one of the chosen basis representations. There are at most K(R_*+14) such labels per projected space. Summing over signs and components proves the stated, deliberately generous, bound.□

Proof. A symmetric rank-r matrix x on a d_B-dimensional coordinate space can be written ZHZ\trans, where Z has r independent columns and H is a nonsingular symmetric r-by-r matrix. To verify the factorization, take a left inverse L of the chosen column basis Z and put H=LxL\trans. The projection ZL fixes x on the left and, by symmetry, on the right; hence ZHZ\trans=x. Its rank forces H to be nonsingular. Neither H nor the original matrix is required to have nonzero diagonal. For a fixed component rank tuple of total at most K, counting Z,H gives at most 2^{d_BK+K^2+K} choices. There are at most (K+1)^{|\cE|} such rank tuples. Therefore the number of profiles under consideration satisfies

for all sufficiently large n, since d_B=p_*(1+(g^2+3)n).

Choose all L,R matrices independently and uniformly. Fix a nonzero profile and write x_e=Z_eH_eZ_e\trans, with r_e=\rank x_e. For a tag-l atom the contribution from a single indexed matrix uses the forward forms Z_e\trans L v when l\in f, and the reverse forms v\trans L Z_f when l\in e, and the corresponding forms for R. Regard these initially as separate formal variables. Across all indices their number is at most

Each forward or reverse pair contributes a bilinear product with nonsingular middle matrix H_e or H_f. These products use disjoint formal variables. Since x\ne0, for each j there is at least one such nonzero product, so the formal quadratic has polar rank at least 2J.

We justify the distribution of their linear parts on Z even when forward and reverse restrictions overlap. For a fixed matrix L, specifying Z_e\trans L and LZ_f imposes at most r_er_f compatibility bits, namely their common Z_e\trans LZ_f block. After restriction to the free Z directions, the resulting list remains uniform on a linear subspace of codimension at most r_er_f in the space of all lists. Equivalently its law is dominated by 2^{r_er_f} times the completely uniform law. Over all matrices the domination factor is at most 2^{2JK^2}; only matrices with both relevant incidences contribute a compatibility term.

For a uniform m-by-n matrix, the probability of corank at least s_0+1 is at most 2^{m(s_0+1)-(s_0+1)n}: choose s_0+1 independent row relations and require all their n evaluations to vanish. If m<s_0+1 the probability is zero. The preceding domination therefore bounds the bad probability for a fixed profile, tag and label by

There is no union over non-Z values or flavors in this estimate: they affect affine shifts, not these linear parts on the always retained Z block. A union over at most 2^{An}g2^b choices tends to zero. On the complementary event the image of the Z inputs in the formal variable space has codimension at most s_0. Restricting a bilinear form to a subspace of codimension s_0 reduces rank by at most 2s_0: in a basis extending that subspace one deletes s_0 rows and s_0 columns, each deletion decreasing rank by at most one. This proves (i). The formal list itself supplies the claimed bounded space of linear forms. The term T^0 has no Z variables and does not affect this argument.

For (ii), distinct labels have independent selector evaluation vectors. Their two Z direction spaces are therefore disjoint. Restricting a random matrix to these two spaces in the two orders reads independent off-diagonal blocks. Any nonempty parity involving ordered L,R evaluations is consequently a uniform n-by-n matrix on these directions, even after all other matrices and E have been fixed.

For the parities using only E, choose its matrices M_a independently and uniformly. On the two \# direction spaces, E restricts to

which is uniform because s\ne s'. The reverse gives A_{s,s'}\trans, and their sum is alternating. An \lfloor n/2\rfloor square block with disjoint row and column indices is uniform also in this last case. A uniform d_1-by-d_2 matrix has probability at most 2^{(d_1+d_2)r-d_1d_2} of rank at most r, by representing such a matrix as a product of a d_1-by-r and an r-by-d_2 matrix. Taking r< n/5 gives probability 2^{-\Omega(n^2)} in all the preceding cases, including the square block of side \lfloor n/2\rfloor.

There are at most 2^{2b} ordered label pairs and 2^{4J|\cE|^2+2} parities to check. These counts are fixed in n. The Z and \# restrictions also show that the tester part of E and the choice of flavor cannot reduce the ranks just proved. A union bound establishes both properties simultaneously. Fix one successful choice for each sufficiently large n.□

Proof. A pin image is fixed on its leaf. A cross entry with a pinned first argument therefore depends only on the other unit’s orientation, and conversely for a pinned second argument. Entries with both arguments pinned are numerical tests on the leaf pair. This proves the first assertion about filters. Use bases of the projected pin spaces to encode tensors of C_i: their coordinates lie in spaces of dimension at most K^2, and there are at most K^2 basis tensors. The pin, projection and channel relationships and the table are bounded-dimensional matrices. The nominal bases themselves have O(K\dim\cB)=O(n) coefficients.

For the second assertion, project a purported dependence onto an individual primal coordinate block. It expresses a sum of at most fourteen attack rays as an element of S_{i,e}^{\pm}. Any nonzero such vector would have a sparse representation on attack labels and is forbidden by Lemma 6.3. Independence of those label factors and the nonzero constant coordinate of each point then makes all coefficients zero. The channels introduce no relation because the table space is the direct sum of its individual primal and channel blocks.

For the last assertion, at one endpoint let I_1,I_2 be its two disjoint nonempty lists. The matrix of T on its atoms must be symmetric, with diagonal a on each atom. Prescribing the two list sums of its rows is possible exactly when their self-pairings equal the corresponding diagonal sums and their mutual pairings agree. To see sufficiency, subtract any symmetric matrix with the required diagonal. The remaining task prescribes an alternating form on the span of the two independent list indicators and its pairings with the whole coordinate space. Extend those indicators to a basis, retain the prescribed entries in their rows and columns, and assign the remaining alternating entries arbitrarily.

For (7.3), the self-pairing requirements hold because T(v,v)=a(v). Mutual consistency is

The coupled equation at the opposite unit gives the left side as a(v_{zi})+a(v_{z'i}), which equals the displayed right side by the two role-sum equations in (7.2). Thus the symmetric matrix exists.

Every off-diagonal entry can be implemented by formal L,R bit prescriptions on that pair of atoms. The value of T^0 is already determined by their tester summaries. Choose one indexed product term in T^1 linking a component of the first star to a component of the second star; set its two factors to give the desired correction and set all other product factors to zero. Forward and reverse evaluations are distinguished. The two labels at this endpoint differ, so these are the indexed ordered evaluations covered by Lemma 6.5. This argument specifies the bits; their occurrence in parameter tests will be supplied by Lemma 11.9. It makes no assumption about independence of arbitrary actual evaluations at fixed points.□

Proof. Equal keys imply U_iv_{iz}=U_zv_{zi}, and the role sums in (7.2) supply the witness parity. It remains to construct the gradients. We distinguish abstract Gram entries from the random event that the actual entries agree with them.

A baseline of bounded primal rank. At each component and sign choose a splitting of the table space as \mathcal J=D\oplus\mathcal J', append the key space, and append an additional primal complement. The independence in Lemma 7.2 makes these splittings possible. Retain the small table on the product of the two table spaces and the actual frozen entries in any pin or key row or column. These prescriptions agree on their overlaps by admissibility. Set the free blocks from an additional primal complement to the opposite \mathcal J' to zero, in both orientations, and set the additional-primal by additional-primal block to zero. This defines baseline cross bilinear forms.

Fix an opposite endpoint z. Let

be evaluation against its Y_z,X_z channels. On additional primal inputs, evaluation of an opposite channel factors through its projection from \mathcal J onto D; hence the rank there is at most \dim D. The remaining primal inputs are in bounded-dimensional projected pin and key spaces. It follows that the ranks of both baseline maps on all primal inputs are bounded independently of r_0,h,n. Arbitrary channel-channel entries of the small table do not affect this bound. A uniform bound for either map on the combined primal inputs of the two endpoints is

the opposite pin projection costs at most K dimensions, the two individual projected primal spaces cost at most 2K, and the two endpoints have at most twenty-eight key rays.

Let u_z^0U_i denote the resulting contractions. They give the table values on C_i. On an attack atom toward z they are zero, since its tensor is the equal-key tensor at z and u_zU_z=0. On an attack toward z' they equal p_{z'} of its matched atom, since that tensor is the corresponding tensor at z'. These are precisely the values in (7.3).

Allowed changes. Let \mathcal A_{O,e}^{\pm} be the span of all key directions on the indicated side of the unit, and put

Write bars for the quotients

We may change F_z^0,G_z^0 by any maps

Here each map is extended to a bilinear change supported on its opposite channel block and zero on the opposite primal blocks. It vanishes on all frozen entries: the domain quotient kills frozen directions on one side, while on the other side a pin’s channel projection lies in H_{z,0} and is annihilated by the allowed values. A reciprocal-role change in the same Gram block contributes nothing on this map’s primal inputs, because it is supported on a channel argument there. On private-by-private blocks both changes are zero. They may add further channel-channel values, which are irrelevant to the primal contractions. Thus all choices below may be made independently for opposite endpoints and for the reciprocal unit roles as far as primal-input values are concerned.

The unrestricted linear response. Fix z and solve simultaneously for the two i\in O. Consider the linear space of responses formed by

and all bilinear forms on \overline{\cL}_{O,e}\times\overline{\cR}_{O,e}, with their contractions summed over components on each individual cut profile. We claim that the pair of target forms

belongs to this response space.

Let (x_i)_{i\in O}\in\cX^O annihilate all responses. Annihilating the arbitrary pure bilinear forms says that at each component the sum of the two nominal tensors has zero image in the product of barred quotients. Project further onto the individual primal spaces modulo S_{i,e}^{\pm} and the individual key spans. This projection is well defined on the barred spaces, since every pin projects into S_{i,e}^{\pm}. It shows that x_{i,e} vanishes after both such quotients. A matrix killed after quotienting its two factors by spaces of dimensions d_+,d_- has rank at most d_++d_-: in bases extending those spaces all entries outside their rows and columns vanish. Consequently

Apply Lemma 6.2 to every component.

For an attack label at i, compare its label summand with all key directions in that component. Their combined label set has at most R_*+14 elements, whose direction spaces p_s\otimes\F^{1+d_{\mathrm b}} form a direct sum. Any vector of S_{i,e}^{\pm} in this sum has zero attack-label component, by Lemma 6.3. Thus the attack summand projects to zero modulo just its individual key ray if the atom uses this component, and is zero if there is no such ray. In the former case, writing its affine base vector as v=(1,y), a symmetric matrix killed in the two quotients by v has the form

Indeed choose v as the first basis vector: the surviving matrix can be supported only on its first row and column. The moment identities in the original affine coordinates now give

so d_i=d_0v_i and Z=cvv\trans.

The cut relation on any triangle of tags separates label by label: the union of the three supports has at most 3R_* labels, within the interpolation bound. At this attack label the nonzero components lie on its tag star; the triangle relation forces their scalar coefficients to be equal. Subtract that scalar multiple of the attack atom from x_i. Do this for every attack label. Each subtracted atom annihilates the response space, because both its factor directions are keys. The remaining profiles still annihilate the response and have only nonattack label support. Removing these separated label blocks does not increase their component ranks or label support sizes.

At one component contract a remaining x_{i,e} on the minus side by a primal functional \phi at i annihilating S_{i,e}^- and all individual key directions. Extend \phi by zero on other endpoint and channel blocks; it is a functional on \overline{\cR}_{O,e}. Pure annihilation shows that the resulting individual plus vector d is a sum of a pin, key directions, and private channel directions. In this representation all key coefficients vanish. To see this, project onto each individual primal block. At the other endpoint the projected pin would be a sparse sum of attack rays. At endpoint i it is the difference of the nonattack vector d, supported on at most R_* labels, and a sum of at most fourteen attack rays. In both cases the label exclusion prevents any attack coefficient. The channel components of the pin lie in the protected spaces H_0, whereas the remaining channel term lies in their chosen complements H_1. They must both vanish. Therefore

Test the derivative response using \delta G_{z,e}=\phi\otimes c for arbitrary c\in(H_{z,0}^+)^\perp. It gives F_{z,e}^0(d)\cdot c=0. Hence the table evaluation of d is zero modulo H_{z,0}^+, and injection in (7.1) yields d=0. The reciprocal contraction proves the same assertion in the minus mode.

It follows that the remaining component tensors lie in the products of the individual projected pin plus key spaces. Their nonattack support removes the key directions by the same sparse-label argument. Thus the remaining profiles belong to C_i. We have proved that every annihilator is a sum of effective-space profiles and attack atoms. The target (7.7) vanishes on the former by (7.2) and on the latter by (7.3) and the baseline values. In a finite-dimensional vector space the image of a linear map is the annihilator of the kernel of its dual: this follows by extending a basis of the image to a basis of the target space. It proves the claimed linear solvability.

A low-rank representation of the target. For one i, the form r(v_{iz}) has a matrix representation on the components of rank at most

per component. Here is an explicit routing for its tester part. Let w=(w_t) be the representation given by its atom list. The list condition gives \chi_*(w)=\sum q=1. On an allowed O_{d,t} block at any tag the coefficient in a+T^0(v_{iz},\cdot) is

There are at most seven tags t with nonzero \eta_S(w_t). Route this tester from each allowed tag l\in I_d to d through the component \{l,d\}. It contributes nothing at d, where O_{d,t} is disallowed. At a component this uses at most fourteen ordinary testers, allowing either endpoint as center. For the shared tester, route a star centered at t with coefficient a_t(v_{iz}). Its contribution at the center is (g-1)a_t(v_{iz})=0, and at any other tag it gives the desired term in a_t(v_{iz})b_t. Consolidating gives at most one shared tester per component. Each ordered tester matrix has rank r_0, proving the 15r_0 bound.

For T^1(v_{iz},\cdot), each of the two orientations of an indexed term supplies a matrix of rank at most the component rank of v_{iz}. This profile is a sum of at most seven atoms, so its total component rank is at most 7(g-1). The total contribution per component has rank at most 14J(g-1)\le14J|\cE|. This proves (7.8).

Removing the bounded-dimensional obstructions. Let M_{i,e} be the preceding representing matrices. On each individual primal factor choose a projection A_{i,e}^{\pm} whose kernel is the sum of its projected pin and key spaces. The matrix (A_{i,e}^+)\trans M_{i,e}A_{i,e}^-, extended by zero outside that individual block, is a permitted pure quotient form. Its sum over i has rank at most twice (7.8). Moreover

Subtract these pure forms from the linear task. Its residual, including the baseline contraction, has a per-individual matrix representation of bounded rank independent of r_0,h,n, and remains linearly soluble.

In any unrestricted solution, replace the derivative output maps by bounded-rank maps in the same allowed value spaces, preserving all their dot products with the opposite baseline values on primal inputs. Such replacement is possible as follows. The map from the allowed value space to the dual of the span of those baseline values has bounded rank. Choose a linear section of its image and compose with that map. This has bounded-dimensional image and preserves every observed pairing. Postcomposing the original derivative map with this value projection leaves its primal derivative response unchanged and preserves its domain quotient. The two new derivative maps have bounded rank. Their extra product \delta F_z\cdot\delta G_z is also a bounded-rank pure form, which we include with opposite sign in the remaining pure task. That task still has an unrestricted pure solution. Its per-individual target matrices have rank at most

Here the first term bounds the projection difference, one B_{\mathrm{lin}} bounds the baseline contraction, two bound the derivative terms, and one bounds their extra product.

Compression of the remaining pure task. We show that the latter task has a pure solution of bounded rank. At endpoint i, expand all projected pin and key vectors, and all row and column forms in its bounded-rank target representation, along selector coordinates and base blocks. Their counts depend on earlier construction parameters but not on r_0,h,n. On each ordinary base block let U be the span of the vectors to fix and K_0 the common kernel of the forms to preserve. Choose a complement in K_0 to U\cap K_0, and project along that complement onto a subspace containing U. The resulting endomorphism fixes U, preserves all the forms, and has rank at most \dim U+\codim K_0. There are at most 2|\cE|(K+14) vectors to fix and at most 2|\cE|R_{\mathrm{res}} forms to preserve at one endpoint before selector expansion. Thus an explicit bound for the rank on an ordinary block is

Use these endomorphisms blockwise, fix the constant base coordinate, and act trivially on the selector factor. Use the same resulting map at every component and in both modes at this endpoint. It sends each allowed point to an allowed point and therefore preserves all W_l and the cut domain. It fixes the individual projected pin and key vectors. Taking identity on channels consequently fixes every mixed pin itself and preserves private channel subspaces. The map descends to the barred spaces and has bounded rank there: only the bounded protected channel dimensions survive their quotients. On either barred space a uniform bound is

The first term counts the two compressed primal blocks and the second bounds their surviving channel projections.

Precompose an unrestricted pure solution on its two arguments with these maps. Its rank per component becomes bounded. On individual cut profiles its value is unchanged, because the compressed profile remains in that cut domain and every form in the target representation is preserved. It is therefore the required bounded-rank pure solution.

Factoring the pure forms through channels. Restore the earlier projected pure forms. Their sum with the compressed correction has rank at most

per component for the fixed opposite endpoint. In particular the additive constant is independent of r_0,h,n. In the two allowed channel value spaces impose, in addition, orthogonality to the opposite baseline and bounded derivative values on primal inputs. These are only boundedly many linear restrictions. Each remaining value space has codimension at most K+2B_{\mathrm{lin}}, so their dot pairing has rank at least h-2K-4B_{\mathrm{lin}}: restricting a nondegenerate pairing by codimensions c_1,c_2 loses at most c_1+c_2 in rank. With h=1000r_0, the sufficient requirement is

Every quantity on its right is fixed before r_0, so this is one of the permitted requirements on that choice.

Factor a rank-r desired pure bilinear form as \sum_{a=1}^r\ell_a\otimes m_a. Choose vectors f_a,g_a in these remaining channel spaces with f_a\cdot g_b equal to the Kronecker delta; they exist by the pairing rank. The changes \sum_a\ell_af_a and \sum_am_ag_a realize that form as their dot product. Their cross terms with the baseline and the previous small derivative changes vanish on primal inputs by the additional orthogonality conditions. They obey (7.6) and hence preserve every frozen entry. This realizes the target exactly for both endpoints i\in O.

Repeat for both opposite endpoints and both unit roles. The independence of primal-input changes already proved ensures that the resulting two cross Gram blocks realize all equations (7.4) simultaneously. Only primal-channel entries have been used. In each of the two blocks there are at most 8h\dim\cB such entries per component, proving the asserted count. Actual agreement with them gives all gradient equations; equal keys and the role sums give the other witness conditions. All four cross pairs are therefore holes.□

Proof. First note where thinning enters the hypotheses. By Lemma 5.3, with \varepsilon_{\rm ch}=10|\cE|2^h\rho, the projected unit laws satisfy

The choice of \rho leaves this exponent strictly below D=4000g, also after a restriction of mass 2^{-o(N)}. Thus the reference image estimates and first peeling are charged against the original law \rawlaw; they supply the all-rank leaf hypothesis used here. No uniform conditional channel law under \sigma_O or \pi is used in this proof.

We first work with one shape of vector slots and one option per leaf pair. A bounded number of shapes or options will be handled at the end. We count only leaf pairs with J_n=1, and every accepted measure already contains its filters enforcing \Psi on these pairs. Leaves are drawn independently from their two actual mass distributions; none of the following estimates requires those distributions to be equal.

The numerical records. Fix two leaves, a key q\in\cK_n, and point parameter values a,b on the two sides. Freeze the images of all pin and key directions. The pin images are known from the leaves and the key images are the entries of q. At each unit record the pairings of all its nominal columns with these opposite frozen images. Record any numerical statuses in Equations (7.2) and (7.3) not already fixed by the query conditions. For fixed parameters these records, together with acceptance, partition the unit’s orientations into unary cells. A partition is allowed to depend on the opposite parameters; it does not depend on the opposite orientation once its frozen images have been specified.

There are at most

cells on either side, for a constant C fixed before M_0. To verify the count, there are O(\dim\cB+h)=O(n) columns and only boundedly many pin and key vectors to pair against. Nominal projected-pin bases use O(n) coefficients. The basis tensors of C_i are encoded in their bounded projected pin bases, rather than as full matrices on \cB; this uses boundedly many further coordinates. Parameter values require O(n) bits and the remaining table and status information has bounded size. The ambient pin and key images are already fixed and are not charged again as new records.

The numerical records determine every frozen cross entry. Together with the fixed algebraic data, leaves, parameters, and table, they determine a choice of the abstract solution in Theorem 7.3. One can make this choice deterministic by taking the first solution in fixed coordinate orders on the finite spaces. Its unknown entries need not be encoded as additional records. In particular, a global signature cylinder or a complicated orientation filter is only an acceptance predicate, not an input requiring a new coordinate description for this solver.

Pruning at a fixed parameter pair. Put

For the fixed parameter pair (a,b) and key q, let \alpha_a^b(c;q) be the mass of a first-side accepted orientation in record cell c, measured in its normalized leaf law. Define \beta_b^a(d;q) similarly. Denote their sums over records by \alpha_a(q),\beta_b(q); these sums do not depend on the opposite parameter, since it only refines the record partition. Their sums over all keys are at most one.

Discard for this fixed pair only cells of mass less than \tau_n. The product mass lost from small first-side cells at key q is at most

Sum over keys and average the independent parameter weights. The loss in collision probability is at most L_n\tau_n, since \sum_q\beta_b(q)\le1 for every b. Discarding small second-side cells loses at most the same amount. Because \nu_n is uniform, the overlap integral is |\cK_n| times the probability of an accepted key collision. Thus the total overlap loss, for any fixed leaf pair and also after averaging leaf pairs, is at most

for the chosen sufficiently large M_0 and all sufficiently large n.

Every retained cell is its original unary cell and has mass at least \tau_n. We have not intersected the retained sets over different opposite parameter values; such an intersection could reduce a cell below its threshold. Instead all subsequent estimates are made for this fixed parameter pair and its unaltered cells, and then averaged. This preserves both their mass bounds and the product of the two conditional orientation laws.

Image entropy inside a retained cell. By Lemma 7.2, the k nominal key directions are jointly independent modulo the pins, with rank computed separately by component and sign and jointly across the two endpoints. Suppose a further tuple has rank t\ge1 modulo pins and these key directions. Apply (5.11) to the combined tuple of rank k+t, prescribe the known key images and any images of the further tuple, and divide by the cell mass at least \tau_n. Its largest conditional point mass is at most

Here k\le k_{\max} and \zeta=1/(1000k_{\max}), so .01+2\zeta k\le .012. The inequality holds for every t\ge1, including tuples whose rank grows with n. Further restrictions defining the cell cause no additional loss: the numerator was bounded by an event containing the entire cell and the prescribed images, and only the original cell mass has been divided out.

Testing the remaining scalar Gram entries. For a retained cell pair the abstract target is fixed. Let s_n be the number of its tested primal-channel entries in the two cross Gram blocks. By Theorem 7.3 and the final choice of M_0,

Expand the indicator that all these entries agree with the target as a sum of 2^{s_n} binary characters, with the factor 2^{-s_n}.

A character has a coefficient tensor in the direct sum of the two cross nominal tensor products, over all components. Take its image after quotienting every nominal factor by pins and keys. If this image is zero, its value depends only on frozen cross entries. More explicitly the kernel of a tensor-product quotient is the sum of tensors with a frozen factor on at least one side; all their pairings have been recorded. The actual and target Grams agree there, so the disagreement character is identically one.

Otherwise let t\ge1 be the sum of the ranks of the quotient coefficient matrices, over components and the two cross orientations. A rank factorization expresses its phase, up to a constant and two separate phases involving frozen images, as

On each unit the corresponding coefficient directions have joint rank t modulo its frozen space. The two different cross orientations use opposite nominal signs, so their ranks add. By (8.8), each tuple of actual images has largest point mass at most 2^{-.95tN} under its conditional cell law. The two laws are independent. Absorb the separated phases into bounded weights. Lemma 5.9, in dimension tN, bounds the absolute character mean by

There is at least the trivial character with value one, and all other zero-quotient characters also have value one. Consequently the conditional agreement probability on every retained cell pair is at least

for all sufficiently large n. No independence of the individual tested Gram bits is asserted or required.

Averaging and the exponent. The assumed overlap is subexponentially large. The error in (8.7) is exponentially small, so the retained collision probability, after averaging leaves and independent parameters, is at least 2^{-o(N)}/|\cK_n|. Integrating the preceding scalar agreement bound gives four holes with probability at least

under \widetilde\sigma_A\otimes\widetilde\sigma_B, with \Psi satisfied. This implication is valid even if many successful queries certify the same orientation pair: the fresh query experiment is a probability space, and its successful event is contained in the event that the underlying orientations satisfy \Psi and have all four holes. Each original law dominates its restricted normalized law by its own restriction mass. The product of those two masses is at least 2^{-o(N)}, which gives the same additional cost even when the laws and restrictions are different.

If there are boundedly many options, sum the corresponding overlap quantities and choose one whose expectation is at least the sum divided by their number, or partition into these fixed cases. Shapes of \cK_n and varying finite numerical formats can likewise be separated into boundedly many cases. These constant factors are absorbed by the slack from .02 to .03 in (8.4). Finally

so (8.4) contradicts a sequence whose probability of four holes satisfying the required predicate \Psi is less than 2^{-100gN}. In particular, failure of a filtered distribution test forces vanishing overlap only for its permitted options; the argument makes no assertion about the overlaps of excluded colour or type pairs.□

Proof. Regard all components as blocks in the direct sums of the two mode spaces. Their column and row spaces are direct sums of componentwise spaces, so that every cover obtained in this proof is componentwise. We first make a deterministic observation about any realized list of tensors.

Expose a subset E of the indices and quotient the two modes by the column and row spans of the exposed tensors. If b=s-|E| indices remain, let C_j,R_j be their projected original column and row spaces. Define their span deficits by

The projected sum has rank at least

Indeed, before adding the mode spaces, place the projected tensors on the separate formal summands C_j\otimes R_j. Their block diagonal sum has rank at least the displayed number of nonzero tensors. Applying the two addition maps can decrease rank by at most their kernel dimensions, which are \delta_C,\delta_R.

There is an exposed set leaving b=s/2^j indices for some 0\le j<m_r such that \delta_C+\delta_R\le b/4. To prove this, order the realized direction spaces by a uniform random permutation. In either mode, let a_t be the expected increase of their span dimension at the t-th step. Submodularity and exchangeability give

For b_j=s/2^j, set

Each remaining index has expected projected dimension f_j immediately after the first s-b_j exposures. Consequently its mode’s expected deficit divided by b_j is v_j. The average increment on the first half of this tail is at least f_{j+1}. It follows that

Summing for 0\le j<m_r yields

The two modes therefore have total expected deficit ratios at most 4r across these m_r scales. Some scale has expected ratio less than 1/4, and some permutation realizes a ratio at most 1/4, as claimed.

If the original sum has rank less than q_rs/4, its projection at this exposed set has no larger rank. By Equation (9.3), at most q_rs/4+b/4\le b/2 remaining tensors have nonzero projections. At least q_rs/2 of them thus belong to the cover formed by the exposed column and row spans. Both cover dimensions are at most rs.

For fixed disjoint index sets E,J, with |J|=\lceil q_rs/2\rceil, condition only on the tensors indexed by E. The cover is then fixed, and the tensors indexed by J are still independent. The probability that all are covered is at most p^{|J|}. There are at most 2^s choices for each index set. Taking their union proves Equation (9.2).□

Proof. We first choose the parameters and treat the case with no large cover. In the cover case we pass to offset records. A tiny cover either makes F identically zero or permits a gain from thinning; in the absence of a tiny cover, a fresh-direction count gives mixing.

Write

and let s be the largest power of two not exceeding c_sN. For large n, it satisfies the size requirement of Lemma 9.2 and s\ge c_sN/2. Choose p_0>0, using only these early parameters, so small that

When the channel size is chosen, require also

Further lower bounds for h arising below will again involve only early parameters.

No large cover. Suppose no fixed cover of dimension at most rs in each mode has mass at least p_0. Fix a candidate value \xi of \Delta_B, a nonempty S, and a set R. Define the unit-side sign \psi(A)=(-1)^{u_{A,R}(\xi)}. Against completely iid channel columns at the endpoints selected by S, expansion of the even s-th moment gives

For one channel pair the expectation of its bilinear character on a tensor \xi is 2^{-\rank\xi}. Independence over channels and components proves this assertion; selecting both endpoints only squares the factor. The signs \psi(A_j) have absolute value one and can be removed for an upper bound. By Lemma 9.2, the last expression is at most

The channel marginal comparison in Lemma 5.2 multiplies this bound by a constant depending on h and the number of components, but independent of n. Markov’s inequality and Equations (9.4) and (9.5) bound the probability that the inner mean has magnitude at least \theta by C_h2^{-\Gamma N}.

There are at most C_r2^{2rN} tensors of total component rank at most r: choose their component ranks, then factor each matrix through that rank. The component-rank choices and the overcounting factors are bounded independently of n. Take a union over these candidate values and the bounded choices of S,R, and then pay the joint-law density 2^{(D+.01)N}. The exceptional B-mass is exponentially small. On all other B’s the conditional A-mean is at most \theta, even after inserting the actual value \Delta_B. Every required phase mean is therefore at most \theta+2^{-\Omega(N)}<.005. Interchanging A,B deals with S=\varnothing. This proves the first alternative without a further restriction.

A large cover and its offsets. Otherwise retain mass at least p_0 in a fixed cover (T_e^+,T_e^-) of dimension at most rs in each mode. Each individual primal frame span avoids these fixed subspaces except on exponentially small mass. Indeed its dimension is \dim\cB, its location is uniform under \rawlaw, and

the same estimate holds for the minus mode. Here rs\le rc_sN and \dim\cB/N is sufficiently small. The primal marginal bound \Lambda\operatorname{pr}_*\rawlaw permits deletion of these exceptions; this step does not use a full-frame bound against \rawlaw. Normalize the retained law, still denoted \sigma. Its marginal bound \sigma_i\le L\pi has L\le2\Lambda/p_0 for all sufficiently large n. Thus this fixed bound may also depend on the given \Lambda, whereas the retained-mass bound remains independent of \Lambda.

Project both modes of each component modulo T_e^\pm. Because \Delta is covered, the two endpoint tensors have the same quotient. The projections are injective on the individual primal spans, so they preserve each tensor rank. Choose a shortest outer-product factorization of the common quotient tensor and lift each factor to the two endpoint primal spans. Componentwise, the difference has the form

The first endpoint is the reference here; its factors are p_\alpha,q_\alpha, and those at the second endpoint are p_\alpha+a_\alpha,q_\alpha+b_\alpha. The factor lists at either endpoint are independent in their respective modes.

Choose bases for the spans of the offsets a_\alpha,b_\alpha in each component. Their combined ordered list is denoted \omega_O, and its size is t_O, with

The lower bound follows from \Delta\ne0. Collect the companions of these offset basis vectors in a tuple Z_O: minus companions pair with plus offsets and vice versa. The companions are independent within each component and mode. For example, writing b_\alpha=\sum_kc_{k\alpha}\omega_k^- gives a full-row-rank matrix (c_{k\alpha}), so the vectors \sum_\alpha c_{k\alpha}p_\alpha are independent. Using the second endpoint as reference changes each companion by a known combination of offsets, and preserves independence.

An offset record consists of these basis vectors, their component and sign assignments, and the bounded coefficient arrays in Equation (9.7). Its logarithmic count is at most

for sufficiently large n. Choosing a nominal representation of a companion tuple in one endpoint’s primal frame costs 2^{O(r\dim\cB)}=2^{O(n)} possibilities. This last cost has an arbitrarily small ratio exponent after choosing M_0. Fix deterministic conventions for all these records and factorizations; their choices can be arbitrary functions of the marked unit.

For a linear tensor functional u, let \Phi_u(\omega) be the tuple obtained by contracting u with the offset basis vectors. In particular, on a plus offset a its corresponding plus output is X(Y\trans a); on a minus offset b the minus output is Y(X\trans b). At fixed two offset records the phase in the theorem is, up to a sum of two unary phases,

The unary phases are evaluations of the last term of Equation (9.7); fixed offset records make them separate functions of A and B.

Singleton phase estimates. All record laws in the following calculation are unnormalized subprobabilities of \sigma. For any record, the companion tuple alone has point masses at most

To obtain this, enumerate its nominal primal representations, apply the individual primal frame-image estimate and the unchanged primal marginal bound L\operatorname{pr}_*\rawlaw, and choose M_0 large enough to absorb the coefficient count and lost primal codimensions.

Suppose S=\{j\}, and use endpoint j as the reference for the B-companions. For fixed \omega_A, discard pairs on which the coefficient lists Y_j\trans a or X_j\trans b, for its independent offsets, fail full rank in any component. Under the original law, comparison with iid columns bounds the transpose-rank failure on d independent ambient vectors by 2^{d-h+1} for large n. The fixed-list assertion of Lemma 5.3 bounds the same event under \pi by 2^{d-h+1}+o(1), uniformly over the fixed list. For each fixed A, the list being tested is fixed before drawing B. Consequently the discarded pair mass is at most

on making h sufficiently large in terms of the fixed marginal cap and the early rank bound.

On the remaining pairs, the tuple (Z_B,\Phi_{u_{B,j}}(\omega_A)) has point masses at most

Here is a direct conditional count. Enumerate a nominal representation of Z_B, first test its values, and condition on the primal frames at endpoint j. The two channel maps are independent uniform-column draws in the appropriate annihilators, apart from a bounded injectivity conditioning. Freeze the values of Y\trans a and X\trans b. Their number of possibilities is bounded in n, and their lists have full rank on the retained event. Ignore the equations that originally defined these coefficient values. Prescribing their images under X and Y then costs at least (N-\dim\cB)t_A bits, up to a bounded factor. This is a count under \rawlaw, conditional on its primal frames. Replacing its channel law by that of \pi costs at most 2^{\varepsilon_{\rm ch}N}; applying the endpoint marginal bound costs the fixed factor L. Together with the primal companion test this gives Equation (9.11). The ignored equations only enlarge the event, so no independence between a coefficient list and the map defining it has been assumed.

Apply Lemma 5.9 to Equation (9.9), on (t_A+t_B)N bits. On the A-side the point-mass bound for the entire tuple is no larger than Equation (9.10); on the B-side use Equation (9.11). Separate unary phases have absolute value one. The contribution for two fixed records is at most

There are at most 2^{.004N} record pairs. By Equation (9.8), their total is at most 2^{-.480N}. Thus every singleton phase mean is bounded by 10^{-4}+2^{-.480N}. The same proof applies when |R|=1.

A tiny cover or mixing of the full endpoint sum. Put \delta=.0005. If a cover of total dimension at most d_0 contains the whole offset list with probability at least \delta/4, restrict to those units. Intersect its spaces componentwise with the preceding large cover. This preserves every captured offset list and does not increase its dimension. Each individual primal span therefore still avoids it. Delete units whose channel transpose at either endpoint is not injective on a fixed basis of any component and sign of this tiny cover. By Lemma 5.3 and the endpoint bound, the deleted relative mass is at most

Take h so this is less than 1/2. This leaves relative mass at least \delta/8 in the large-cover law. All future offset lists in this tiny cover now pass the singleton rank tests.

Repeat Equation (9.7) with the tiny cover as the quotient directions. Fix an offset record: the actual offset basis, its component and sign assignments, and its bounded binary coefficient arrays. These data have at most

possibilities. Indeed at most 2r vectors are chosen from a fixed space of dimension d_0, at most 2r component/sign assignments are made, and all coefficient arrays have bounded sizes in terms of r,|\cE|. The deliberately generous exponent bounds the product of these finite counts. Retain a record of mass at least 1/R_0. This fixes a common ordered tuple \omega, of length 1\le t\le2r, but fixes neither the companions nor any frame image. In particular this restriction is not an additional pinning step.

Split once more, retaining at least half the mass, according as \Phi_{u_{O,\{1,2\}}}(\omega) is zero or nonzero. All normalizations in this paragraph are bounded by early constants. In the zero case each term in Equation (9.7) has one factor from \omega, so

This includes the last, offset–offset term of the lift. The singleton count already proved, with no rank discard because the whole tiny cover passes the transpose tests, gives exponentially small singleton means under this fixed restriction. Thus alternative (ii) holds.

In the nonzero case we claim the stronger full-sum point bound

Here \sigma denotes the normalized retained law; its endpoint marginals are at most L''\pi for an early constant L''. To verify the claim, choose endpoint one as reference in the lift. Enumerate all nominal primal descriptions of its t independent companions; their count is 2^{O(n)}. For each description, prescribing the companion images z has probability at most 2^{-tN+O(n)} under the primal marginal of \pi, which is exactly the primal marginal of \rawlaw. Choose a nonzero coordinate d of the prescribed output \phi. The corresponding contraction of each endpoint’s channel form is a nonzero channel combination, because its transpose is injective on the fixed cover basis. Call these combinations v_1,v_2. They lie in the same prescribed component/sign subset, and v_1+v_2=d\ne0. Necessarily, therefore, endpoint one has a nonzero channel combination in the translate by d of its allowed subset. Conditional on all its primal frames, this endpoint-one event has \pi-probability at most 2^{-\rho N/2}, by Lemma 5.3.

This is a necessary event on endpoint one alone. Consequently its probability under the dependent two-endpoint law is bounded using only the endpoint marginal L''\pi: no independence of the endpoints, and no conditional density bound for endpoint two, is used. Sum the nominal descriptions to obtain

for a constant C fixed before M_0. Choose M_0 so C/M_0<\rho/12, and then n so \log_2 L''/N<\rho/12. This proves Equation (9.12).

For the other side of the Walsh estimate the companion-only bound can now be sharpened to

Its errors are solely O(n) primal image and nominal-description costs plus a fixed normalization, so increasing M_0 after \rho proves this bound. There is no full-frame thinning loss in Equation (9.13). For a phase containing a full-sum term, apply Lemma 5.9 to Equation (9.9), using Equation (9.12) on that term’s side and Equation (9.13) on the other. Both records are already fixed, so there is no exponential record union. The absolute value is at most

When the other phase term is absent, its output coordinates are zero; the companion bound still bounds the full tuple. Phases containing a singleton have the previous exponential estimate. Every nontrivial phase is of one of these types, so the nonzero case gives alternative (i).

Assume instead that no such cover captures mass \delta/4. Fix an A-offset list v=\omega_A, and use endpoint 1 as reference throughout the next calculation. Call B frequent for this list if its offset record m, its companion value z, and its output \phi=\Phi_{u_{B,\{1,2\}}}(v) have joint point probability greater than 2^{-(t_B+.5)N}. For fixed m,z, define the deterministic list

By Equation (9.10), \abs{{\cal F}_v(m,z)}\le2^{.51N}.

We claim that the frequent-pair mass is at most \delta. Otherwise a set of B’s of mass at least \delta/2 has frequent A-mass at least \delta/2. Draw L_0 independent A-probes. At each stage the spans of all past offsets have total dimension at most 2rL_0<d_0. The mass of a probe whose whole offset list lies in those spans is less than \delta/4. Thus each stage has conditional probability at least \delta/4 of being frequent and having a fresh offset vector. Select one fresh vector by a fixed rule using only the probe lists. Averaging fixes a probe collection with independent selected witnesses in each component and mode, and with successful B-mass at least

This lower bound is independent of selector and channel sizes. Require

By Lemma 5.3, the successful B’s can then be trimmed so that the channel transpose at endpoint 1 has full rank on all these fixed witness vectors, while leaving mass at least q_*/2, after absorbing the uniform o(1) error in a strict version of Equation (9.16).

Now estimate this event under the raw law \rawlaw^2. Condition on all of endpoint 2 and on the primal frames at endpoint 1. Enumerate the offset record m, and enumerate a nominal primal tuple representing Z_B at endpoint 1. There are at most 2^{.002N+O(n)} such choices. For each choice the ambient value z, all the lists in Equation (9.14), and their endpoint-2 translations are fixed. The event defined by the adaptive marks is contained in the union of these raw events. This uses no conditional density assertion about the marked law, and does not enumerate 2^{t_BN} arbitrary ambient companion values.

Project each of the L_0 lists onto the coordinate of its chosen fresh witness. Their total product size is at most 2^{.51L_0N}. Freeze the bounded lists of channel coefficient values on the witnesses. On their full-rank event, prescribing the corresponding endpoint-1 output tuple costs at least .99L_0N bits, by the same annihilator count as in Equation (9.11). The upper probability under \sigma, after paying its joint density, is therefore at most

Choose M_0 to make the O(n)/N term small. Because L_0\ge100(D+10), this is exponentially small, contradicting the mass q_*/2. The claim follows.

Discard the frequent events in a full-sum phase test. For fixed records, this is a restriction on B alone once the A-offset record is fixed. The B-tuple point bound is now 2^{-(t_B+.5)N}; the A-tuple bound is 2^{-(t_A-.01)N}. Walsh on (t_A+t_B)N bits gives 2^{-.245N}, before the 2^{.004N} record count. Thus every phase with S=\{1,2\} has magnitude at most \delta+2^{-\Omega(N)}. Interchanging the units covers the cases with R=\{1,2\}. Together with the singleton estimates, all nontrivial means are less than .005.

All retained laws have relative mass at least

The large-cover span deletion leaves at least p_0/2; the tiny-cover restriction, transpose deletion, record restriction and zero/nonzero split retain at least p_0\delta/(32R_0) in total. This proves the stated, slightly smaller uniform bound. The lower bounds on h depend on the fixed marginal caps after these early restrictions. Only after h do we choose the thinning rate \rho; the new full-sum estimate then requires M_0 large relative to 1/\rho. No inverse mass depending on n or on a numerical table is paid.□

Proof. In alternative (i), Fourier inversion of the four bits gives every prescribed pattern probability at least (1-15\cdot .005)/16>1/32. The even-sum condition and each single-bit condition have probability at least (1-.005)/2>.49. In alternative (ii), both full endpoint sums are zero identically. Among the sixteen Fourier characters, the four with even support in each endpoint pair therefore equal one. Their coefficients for the common pattern (c,c,c,c) are all one, for either value of c. Each of the other twelve characters contains a singleton and has mean 2^{-\Omega(N)}. Thus the probability in Equation (9.18) is 1/4+O(2^{-\Omega(N)}). The remaining assertions follow from the same zero sums and singleton means.□

Proof. It suffices to treat one component, endpoint pair and sign, and then sum over at most 16|\cE| tests. All copies of A used below are drawn from \sigma_A independently of B\sim\sigma_B. The argument uses only this independence and the separate marginal bounds, and does not require the two unit laws to coincide. Let V_A be the image of the individual pinned primal space D_{A,e}^+\cap\cB_i, and let H_B\subseteq\F^h be the protected coefficient space at the opposite tested endpoint. Both have dimension at most K. Failure means that some 0\ne v\in V_A has Y_B\trans v\in H_B. Both the pins and H_B may depend on their entire units.

Put \ell=\lfloor N/(10(K+1))\rfloor. The probability that an independent new individual primal span meets a fixed space of dimension at most K\ell is at most

This uses only the unchanged primal marginal, and tests the whole primal span, so it is uniform over the adaptive pin choices. If a fixed B has failure probability greater than \eta>0, successive independent draws A_1,\ldots,A_\ell can each witness failure while the spaces V_{A_j} remain mutually independent, with conditional probability at least c=\eta/2 at every step. The probability of this complete test is at least c^\ell.

Conversely fix any such independent spaces. There are at most 2^{K\ell} choices of one nonzero witness in each, and the chosen witnesses are independent. For iid Y_B columns their transpose images are independent uniform elements of \F^h. For a fixed H_B of dimension at most K, the probability that all these images belong to it is at most 2^{-(h-K)\ell}. There are at most (K+1)2^{Kh} possible subspaces H_B, independently of n. The original channel marginal comparison in Lemma 5.2 therefore bounds this event under \rawlaw by C_{K,h}2^{-(h-2K)\ell}. Here the tested list has length proportional to N; we use this absolute reference-law count, rather than the bounded-list rank assertion of Lemma 5.3.

The endpoint bound against \pi and the absolute thinning density loss multiply this upper bound by \Lambda2^{\varepsilon_{\rm ch}N}. Fubini and the lower bound c^\ell give

Take h>2K+\log_2(1/c)+30(K+1), before choosing \varepsilon_{\rm ch}<10^{-4}. The right side is exponentially small. The unconditional failure probability for this test is at most \eta+2^{-\Omega(N)}. Choose \eta<\eps/(32|\cE|), sum the tests, and then take n sufficiently large. This proves the assertion.□

Proof. Empty status gives \alpha_i=1 and f_i\simeq\gamma_iq for a fixed \gamma_i\in\F. Restriction to any fixed positive population only changes the primal marginal bound by a fixed factor, which is all the proof uses. At any fixed tag, label and parameter point, the key depends only on the primal frames. Under \pi its law is therefore the same as under \rawlaw: the single-key reference up to an exponentially small injectivity error, by Lemma 5.2. The bounded primal marginal density transfers the reference disagreement of f_i and \gamma_iq to an average o(1) parameter error on the marked population. No channel coordinate is tested in this comparison. There are only finitely many endpoint, tag and label choices. Markov’s inequality therefore allows deletion of o(1) unit mass so that this error tends to zero uniformly on the remaining units and choices. Combining it with Equation (10.1) gives, at every nonexceptional label,

with parameter error tending to zero in the generic flavor.

For fixed label and tag the left side is a Boolean polynomial of base degree at most two. A nonzero Boolean polynomial of degree at most k has nonzero probability at least 2^{-k} under uniform bits. For completeness, this follows by induction: choose a coordinate with a nonzero derivative; the derivative has degree at most k-1, and whenever it is nonzero at least one of the two values on that coordinate is nonzero. The constant nonzero polynomial is the initial case. Thus the displayed relation, once its error is below 1/4, is exact for every allowed base value.

For any fixed allowed base value its dependence on the selector has degree at most 2j_*. It vanishes at every selector outside a set of size at most B_*. The choice of b gives B_*<2^{b-2j_*}, so the same polynomial bound forces it to vanish at the excluded labels also.

Use one shared-only base point with \eta_S=1, the same at every tag. The sum of its g star atoms is zero in the cut space. Summing the exact relation over these atoms gives 0=\gamma_i g=\gamma_i, because g is odd and the first three terms are linear on \cX. Consequently \gamma_i=0. The point atoms span the cut space by its definition, proving Equation (10.3).□

Proof. The Z-coefficients remain independent uniform bits after the conditioning. The columns of C are independent except with probability O(2^{d-n}). For two independent conditioned maps C,C', a relation

has a=a', by its constant coordinate. Its Z-part is

The matrix [z_0+z_0',L_Z,L'_Z] is a uniform n\times(2d+1) bit matrix. A union over its nonzero coefficient vectors bounds the failure of combined independence by (2^{2d+1}-1)2^{-n}. In particular, the two translation columns do not share a forced nominal constant direction.

For fixed independent nominal columns, the restricted-image transitivity in Lemma 5.2 gives the uniform injective law with its specified Gram. One batch consequently has the claimed reference law, independently of the remaining nominal coefficients. For two batches, compared with two independent copies of this reference law, the actual images have finitely many additional mutual Gram entries prescribed. Joint injectivity contributes only O(2^{-N+O(d)}) to the comparison: under independent uniform vector slots, a dependence among a fixed number of columns has this probability, and the fixed Gram conditioning has bounded reciprocal probability.

Expand the mutual Gram indicator in binary characters, collapsing any repeated identical entries. A nonzero character has a nonzero coefficient matrix on at least one interaction between the two batches. More explicitly the coefficient blocks pairing first-batch plus vectors with second-batch minus vectors and first-batch minus vectors with second-batch plus vectors give cross-batch bit rank N(\rank A+\rank B)\ge N. The internal Gram constraints, individual injectivity indicators, and the two arbitrary tests are separate bounded weights on the two batches; their normalization factors are fixed. Lemma 5.9 bounds every nontrivial character contribution by O(2^{-N/2}). The same computation without the tests gives the normalization of the mutual Gram conditioning. There are only a fixed number of characters. Thus the conditional two-batch product expectation differs from the product of the one-batch expectations by O(2^{-N/2}), uniformly over the nominal mutual Gram values.

Averaging the coefficients, and including the probability of nominal dependence, proves the asserted second-moment estimate. The one-batch mean differs from the reference mean only by the already bounded nominal-dependence error.□

Proof. Suppose otherwise. By Lemma 5.5, the two canonical sparse representations w^{(i)}=(w_l^{(i)})_l of the marked \lambda_i’s have the same value of \chi_*. Each has at most 4D/g nonzero tag entries. As \alpha_1\ne\alpha_2, on every unit exactly one endpoint has \chi_*(w^{(i)})+\alpha_i=1. Fix an endpoint i on a positive fraction of the units. Pigeonhole the set

and choose a single selector outside the stored exceptions on a positive fraction of this remaining population. The latter is possible by averaging over selectors, since B_*<2^{b-1}. All these restrictions have fixed positive mass in n; their endpoint primal marginal is at most \Lambda_0\operatorname{pr}_*\rawlaw for a fixed \Lambda_0. No restriction made solely for this contradiction will be used later to choose a channel-size threshold.

At each tag l, use the pure flavor retaining exactly the allowed O_{d,t} blocks with t\notin T_0, setting all S bits to zero and retaining the \#,Z blocks. For a pure tag atom, a(x)=q(x) and every b_t(x)=0. The coefficient of its tester \eta_{d,t} in T^0(\lambda_i,x)+\alpha_i a(x) is

on the retained t’s. Hence Equation (10.1) gives

with uniform o(1) parameter error.

The right side of Equation (10.4) is a sum of at most

products of affine functions of the base variables. Indeed p_i contributes at most h products in each of the g-1 star components. Factoring the old \lambda_i’s, whose total component rank is at most K_1, gives at most 2J(g-1)K_1 products for T^1. The selected pure tester retains at least

disjoint ordered bit pairs. To check the last inequality, use D=4000g and h=1000r_0. After division by (g-1)r_0, the left side is (g-16000)/2 and the right side is at most 2000+4JK_1/r_0+o(1). The fixed value g=10^9+1 and the later choice of sufficiently large r_0 make the inequality hold.

Put m_1=2gs_1+1, and introduce synthetic variables \xi,\upsilon\in\F^{m_1} and

For every component independently, choose uniform injective maps of the affine coefficient columns (1,\xi,\upsilon) into the plus and minus ambient spaces with full paired Gram

Such maps exist for large n, since the number of columns is fixed. Their point evaluations form one synthetic array of global component keys; all tag stars use the corresponding entries of this same array.

We next prove two properties of this array with probability tending to one.

Shared-only parity. In a local shared-only test use the fixed selector and the same point at every tag. The sum of the tag atoms is zero in \cX. Summing Equation (10.1) therefore gives

except on o(1) parameter mass, uniformly on the retained units. Both tester bits have probability at least 1/4: the bias of the sum of r_0 independent bit-pair products is 2^{-r_0}.

Apply Lemma 10.3 with no affine variables (d=0), the shared-only flavor, and internal Gram (q). The Gram event depends only on the fixed tester coordinates and has probability at least 1/4. The common test is the displayed parity predicate of the global keys in all components. Its empirical frequency under the primal reference law concentrates at its global reference probability. The endpoint primal marginal bound \Lambda_0\operatorname{pr}_*\rawlaw, and its frequency 1-o(1) on the retained population, force that reference probability to tend to one. At every point of the synthetic array the point-key marginal is this reference, up to the exponentially small nonzero-vector conditioning. There are a fixed finite number of points. Thus, with probability tending to one,

Affine-product representations on every small slice. Fix sets I,J\subseteq\{1,\ldots,m_1\}, each of size at most 2s_1+1, and set all \xi and \upsilon coordinates outside I,J, respectively, to zero. There are d=|I|+|J|\le4s_1+2 remaining variables. At a given tag, map this slice into its selected local pure flavor by independent uniform affine functions for every retained base bit, including independent translations. Condition their full oriented Gram to equal the synthetic slice Gram.

This conditioning has a fixed positive probability. At the fixed selector E^\# vanishes on pairs. There are at most 2s_1+1 active terms \xi_j\upsilon'_j in the target Gram, so Equation (10.6) lets us route them into distinct retained ordered tester pairs, and set all other tester affine coefficients to zero. If t_0 scalar tester coordinates are prescribed, this assignment alone has probability 2^{-t_0(d+1)}>0, independent of n. The Z-affine coefficients remain iid. At every fixed slice point the unconditioned base input is uniform; after conditioning, its density is bounded by the fixed reciprocal Gram probability.

Consequently Equation (10.4) holds simultaneously at all points of the slice except on o(1) of these parametrizations, uniformly on the marked population. Its right side pulls back to a sum of at most s_1 affine products. Consider only the event

This is a common test of the image column arrays. It contains neither the mark \lambda_i nor any coefficients of the unit-specific representation. Its empirical success probability is 1-o(1) on the retained population. Lemma 10.3 and the bounded primal marginal therefore force its probability under the synthetic slice law to tend to one. That law is also the marginal of the corresponding slice in the full synthetic array, by restricted frame transitivity.

There are only finitely many choices of tag and slice, with the number fixed independently of n. We may therefore require all these events and Equation (10.7) simultaneously. Notice that we embedded only the small slices locally; no local realization of the entire synthetic tester was required.

Choose one synthetic array on which all these properties hold, and define

For each tag define its Boolean cross-coefficient matrix by

On a coordinate slice where F_l is a sum of s_1 affine products, this is the matrix of \xi_j\upsilon_k coefficients. One affine product contributes a sum of two rank-one matrices to this cross matrix. Every (2s_1+1)-square minor of C_l is therefore singular, so \rank C_l\le2s_1. On the other hand Equation (10.7), together with odd g, gives \sum_lF_l=q_* and hence

Rank subadditivity would imply m_1\le\sum_l\rank C_l\le2gs_1, contradicting m_1=2gs_1+1. This proves \alpha_1=\alpha_2.□

Proof. Consider first the pooled law after the first peeling and intersection deletion. If no prediction exists on any subsequence, apply Lemma 9.5 to independent draws with no additional acceptance condition. Its failure tolerance can be chosen below 1/128, so the success probability is greater than .99 for large n. The actual table is automatically admissible. Later leaf trimming removes only o(1) mass. A prediction on the trimmed law with mass bounded strictly above 10^{-6} would give one on the preceding law, by multiplying its mass by the retained proportion and preserving its common functions and unitwise error. This is the form of the no-prediction conclusion used below.

Otherwise retain a prediction population and pigeonhole \alpha_1,\alpha_2,c and the indicator \Delta=0, as above. Its relative mass is at least 10^{-6}/16. If the statuses are empty, perform the o(1) deletion in Lemma 10.2. All subsequent restrictions then preserve the exact identities Equation (10.3).

Suppose \Delta=0. By Lemma 10.4, \alpha_1=\alpha_2. If precisely one status is active, its first bit cannot be 1: that would give \alpha_i=0 there and \alpha_{i'}=1 at the inactive endpoint. Thus the right side of the first line of Equation (10.8) is zero. With two equal active statuses it is also zero, because 2d=0 over \F. Every left side vanishes when \Delta=0, so all these conditions hold automatically.

If both statuses are empty and c=1, then U_1\lambda_1=U_2\lambda_2, while the two identities Equation (10.3) give the affine-gradient equations for an internal hole and c=1 gives its unequal a-values. This contradicts the assumption that the pair is a unit. Consequently c=0, and all four required phase bits vanish. Thus compatibility is automatic also in this case.

Suppose next that \Delta\ne0. Apply Theorem 9.3 to the pooled marked law. It retains at least the early fraction \delta_{\mathrm{ph}}, and gives either full mixing or the identity

together with exponentially small singleton character means. For clarity, write the four phase bits as

Full mixing bounds the absolute mean of every nonconstant character of (X_1,X_2,Y_1,Y_2) by .005. Binary Fourier inversion therefore gives every prescribed four-bit pattern probability at least

Each condition in Equation (10.8) admits such a pattern. In particular the empty-status pattern is exactly (c,c,c,c).

In the other alternative, X_1=X_2 and Y_1=Y_2 identically. If there is one active status, the required bit is X_i+Y_i=d; its nontrivial character has singleton support in both units, so its probability is 1/2+o(1). If two active statuses coincide, the condition is F(A,B)+F(B,A)=0, which holds identically. With empty statuses put X=X_1=X_2 and Y=Y_1=Y_2. The characters of X,Y,X+Y all have singleton representatives. Hence

This explicitly requires the same fixed c on both sides. The remaining status cases impose no condition. Thus all branches have conditional compatibility probability at least 1/32 for large n, in agreement with Corollary 9.4.

Apply the unconditional form of Lemma 9.5 to this retained law, with failure below 1/128. The probability of a compatible injecting actual table is then at least

This is subtraction of exceptional mass; it makes no independence assumption about injection and compatibility. The injection estimate uses the endpoint bound relative to \pi, together with the unchanged primal marginal and the allowed thinning loss in the full-frame estimates. Its tolerance is fixed before h.

We now justify the claimed leaf estimates without adding any pins. Let w_\lambda be the original actual weights of the first leaves, and let q_\lambda be the fraction of leaf \lambda retained by all restrictions just made. Discard the retained parts with q_\lambda<2^{-\zeta N}. Their total unnormalized mass is at most

On each remaining leaf, division by q_\lambda weakens Equation (5.10) to

as required. Its joint density gains at most 2^{\zeta N} and remains 2^{O(N)}\rawlaw^2. The pin spaces and all old marks are unchanged. This exponentially small deletion changes the successful pair probability by o(1), already allowed above.

The first peeling loses o(1) mass. On a predicted branch, the finite initial selection costs at most 16\cdot10^6, and the phase restriction costs at most 1/\delta_{\mathrm{ph}}. All further losses tend to zero; for large n their combined retained factor, including first peeling, is at least 1/4. This proves the unit-mass lower bound \delta_* in Equation (10.9). The no-prediction branch retains 1-o(1) mass and satisfies the same lower bound. Multiplying the conditional pair-success bound by \delta_*^2 proves the original-scale bound c_*. The density statements follow by dividing the initial bounds by the retained unit mass and using Equation (5.6). All marginal constants required by the phase and injection steps are fixed in advance, for example below 2M/\delta_*, so their channel-size thresholds can be imposed after these early margins have been selected.

Finally, every numerical table has bounded coordinate dimensions. The marked tensors are recorded by their coordinates in the first effective bases, and the exception sets have bounded descriptions. For a fixed leaf pair and a fixed numerical option, the two admissibility conditions are separate unary orientation flags, since the pin images are fixed on each leaf. Fixing numerical mark coordinates is also a unary flag. The phase requirements then depend only on the table entries and those coordinates. An actual successful table supplies at least one successful option in this finite list. This proves the asserted finite-data form without selecting one table during preparation or conditioning the two draws jointly on table success.□

Proof. Two independent original draws have equal colours with probability

Subtract this upper bound from the original-scale successful mass c_*. Equivalently, in a restriction of mass \delta, the equal-colour probability is at most \eta_{\mathrm{col}}/\delta^2. This calculation applies also to randomized colours, which are simply part of the original marked probability space. It uses actual colour probabilities and imposes no lower bound on them.□

Proof. The plus slots are linearly independent with probability \prod_{j=0}^{a-1}(1-2^{j-N})=1-O(2^{-N+a}). Given such plus slots, each minus slot has probability 2^{-a} of satisfying its prescribed values. Conditional on those values the minus slots are independent uniform vectors in specified affine cosets of one common annihilator of dimension N-a. For any nonzero combination of the b slots, the resulting vector is uniform in an affine coset of that annihilator. Its probability of being zero is at most 2^{-(N-a)}. A union bound over fewer than 2^b combinations proves the claimed injectivity error. Multiplication over independent groups gives the last assertion.□

Proof. By Lemma 5.2, the image laws are uniform laws on the indicated independent vectors with their same-endpoint Gram entries prescribed. Relative to the product of the two separate batch laws, the union law adds only the mutual Gram entries and joint injectivity. The latter may be omitted at an exponentially small error because the number of columns is bounded.

Expand the indicators of the mutual Gram entries into binary characters. Their values, which are determined by the nominal inputs, enter this expansion only as signs. In a nontrivial character, after identical descriptions of an unordered slot pair have been collapsed, the coefficient matrix between the two batches is nonzero. Its bit rank is at least N. The individual batch Gram densities can be included in the two separate bounded weights. Lemma 5.9 bounds this character by a constant times \norm{F}_\infty\norm{G}_\infty2^{-N/2}. There are only boundedly many characters. Applying the same expansion with F=G=1 controls the normalization, while Lemma 11.1 bounds all internal normalization factors. The zero character gives the product of separate expectations.□

Proof. Start with \overline\Omega_n and expand the off-position Gram conditions. For any nonzero character, choose an interacting pair of positions and fix all other positions. The remaining phase has rank at least N between the two selected position groups. The prescribed single-position diagonal densities and the unary functions are separately bounded weights. Lemma 5.9 gives the error above. The identical expansion with all functions one gives the normalization of the off-position Gram event. Its zero-character contribution is a fixed positive constant, and all other contributions are exponentially small. Dividing proves the assertion.□

Proof. Let k bound the number of vector slots in one draw, enlarging it by a fixed factor when convenient. At any endpoint and component, a new point column contains the component p_s\otimes Z with a fresh uniform n-bit vector Z. Its probability of lying in a previously exposed space of dimension v is at most 2^{-n+v}: the projection of that space onto its p_s\otimes Z direction space has dimension at most v. This remains valid with repeated labels, and also after the input is conditioned on q or a tester summary. A union bound, with k\ell a small fraction of n, proves the independence assertion.

Fix independent nominal inputs. The raw image law is an iid global slot law conditioned on all required same-endpoint Gram entries and on injectivity. Divide the Gram entries into those within a draw and those between draws, after collapsing duplicate entries. Write their numbers as b_{\mathrm{in}} and b_{\mathrm{cross}}, respectively. We have b_{\mathrm{in}}=O(\ell). The normalization in the denominator is at least a fixed constant times 2^{-b_{\mathrm{in}}-b_{\mathrm{cross}}} by Lemma 11.1. In the nonnegative numerator, drop injectivity and the within-draw conditions, and expand only the cross-draw conditions. It remains to bound

where the zero character has contribution \prod_jw_j.

Represent a nonzero character by a symmetric binary matrix on the distinguished slot indices, grouped into \ell draw blocks of size at most k. Its diagonal draw blocks are zero. A coefficient records one unordered interacting slot pair; in particular there is no nontrivial character represented by the zero matrix. Let t\ge1 be the maximum rank of a coefficient rectangle whose row draw-block set and column draw-block set are disjoint.

We claim that the number of such patterns with this value of t is at most 2^{Ck^2\ell t} for an absolute constant C. Choose a nonsingular t by t minor witnessing the rank, with row-block set I and column-block set J. Each of I,J has at most t blocks. Specify all entries incident with those blocks. If u,v lie in two distinct unselected blocks, border the chosen minor by row u and column v. The enlarged row and column block sets are still disjoint. Its rank cannot exceed t, so its bottom-right entry is uniquely determined by the other entries and the invertible minor. Entries in a single unselected diagonal block are already zero. Thus the specified entries determine the whole pattern. Their number is O(k^2\ell t); the choices of the minor add at most 2t\log_2(k\ell) bits, which is absorbed in the asserted bound.

For one pattern, fix slots outside the draw blocks I\cup J. Across I and J the phase has bit rank at least tN. Phases internal to each group or involving the fixed slots are separate weights, and the cell indicators within the two groups are bounded by one. The Walsh estimate gives 2^{-tN/2}. Integrating the other cell indicators gives

where w_{\min}=\min_jw_j. This argument treats components and modes as distinguished slots; their only effect is to constrain which coefficient entries may be nonzero.

The sum of nonzero characters, divided by \prod_jw_j, is therefore at most

Choose c_1 small enough both for nominal independence and for Ck^2c_1<M_0/8. For any fixed positive weight bound, the displayed sum is at most \sum_{t\ge1}2^{-tN/4} for all sufficiently large n. It can consequently be absorbed in the within-draw factor 2^{O(\ell)}. This proves (11.1) with a constant independent of the partition and its positive weight bound.□

Proof. We first obtain a uniform bound for coarse conditional information. Fix a partition with a bounded number r of cells and with every nonempty reference weight bounded below by a positive constant. At an orientation O, let H_O(C) be its input probability of cell C. Repeated queries are independent with this cell law. Uniformly over probability vectors on the fixed r-simplex, the empirical histogram of \ell=\lfloor c_1n\rfloor samples converges to H_O. Relative entropy against the fixed positive reference weights is uniformly continuous on that simplex: each cell frequency has variance at most 1/(4\ell), and u\log u is continuous at zero. Consequently, on orientations with D_2(H_O\Vert w)>T+1, the empirical histogram has entropy greater than T with probability 1-o(1), uniformly over those orientations. The nominal independence event of Lemma 11.4 can be imposed simultaneously at a further o(1) loss, also uniformly over orientations.

There are at most (\ell+1)^r empirical types. For a type v, the multinomial bound gives

Indeed the probability of that same type under cell probabilities v is at most one, which bounds its multinomial coefficient by \prod_Cv_C^{-\ell v_C}. Apply (11.1) for each cell sequence of a type, and then pay (11.4). We obtain

Choose T>c_2+C_LM_0/c_1+2. This bound is exponentially small. The density cap has been applied only on the event of nominal independence. Its failure was removed in the uniform per-orientation lower bound, not multiplied by 2^{C_LN} as an additive raw exceptional probability.

Since D_2(H_O\Vert w)\le\log_2(1/w_{\min}), it follows that

for a constant C_H independent of the fixed partition size and its positive weight bound. The onset of the bound may depend on both. The constant may depend on C_L,M_0 and the query shape.

Let V denote the flag vector, let C_{\cP}(K) denote the cell of \cP containing the key K, and let p_{O,V} be its cell law conditional on O,V. Average this law with the actual joint distribution of (O,V); flag values of probability zero may be given any conditional law. The entropy chain rule gives

Indeed, split each logarithm \log_2(p_{O,V}(C)/w_C) through H_O(C). The first term averages to I(C_{\cP}(K);V\mid O); the second averages to \E D_2(H_O\Vert w) because averaging p_{O,V} over the conditional flag law gives H_O. The information term is at most the entropy of the F-bit flag vector, hence at most F. Thus (11.6) holds for these conditional histograms with C_H+F in place of C_H.

For the small-set assertion, suppose by contradiction that \omega_n(A_n)\to0 but the averaged query probability of A_n is bounded below by a>0 on a sequence of leaves. Fix 0<\delta<1/2 and enlarge A_n to a set of reference weight tending to \delta; the uniform slot atoms tend to zero, so this is possible. On the resulting two-cell partition, the binary entropy inequality gives

Taking expectations and limits in (11.6) yields a\log_2(1/\delta)\le C_H+1. Sending \delta to zero is a contradiction. This proves (i), and the same assertion holds for every filtered submeasure by domination.

We next prove the net assertion. For a partition \cP, write \Pi_{\cP}d for its conditional-average density relative to \omega_n. If some filtered density d satisfies \norm{d-\Pi_{\cP}d}_1>\eps, split every cell by the set where d-\Pi_{\cP}d is positive. On the refined partition the filtered cell masses differ in \ell^1 by more than \eps from their parent masses subdivided in reference proportions. Since the filter is a function of (O,V) with values in [0,1], the triangle inequality implies that the expected corresponding discrepancy of the unfiltered conditional vectors p_{O,V} is at least \eps.

For any refinement, the relative entropy chain rule and (11.3) give

Here \operatorname{split}_{w} divides each parent mass among its children in their reference proportions. To see the last step, apply the usual conditional relative entropy identity inside each parent, then Pinsker, and then Jensen first with the parent masses and then over (O,V).

A bounded number of refinements must suffice uniformly asymptotically. For otherwise choose any large fixed depth d and a sequence of leaves with d successive witnessing refinements. Their final partitions have at most 2^d cells. Pass to a subsequence on which the reference weights of the entire finite tree converge and the laws of the conditional histogram vectors converge. A final cell of zero limiting reference weight has zero limiting expected conditional mass by (i), and hence zero conditional mass almost surely. Delete these zero-weight cells in the limit. For a positive-weight parent, reference subdivision ratios converge. For a zero-weight parent, both the actual and subdivided total masses tend to zero in expectation. The positive discrepancy at every refinement consequently persists in the limit, at least as \eps/2 if needed.

The limiting final conditional entropy is at most C_H+F. Indeed, before taking limits merge all zero-limiting-weight final cells into one positive cell, and use the conditional version of (11.6) on that partition. All its limiting weights are positive, so entropy is continuous. This merging is used only for the final upper bound. The remaining positive limit cells still form a genuine refinement tree, on which () telescopes. That identity forces the final entropy to be at least d\eps^2/8, a contradiction for large fixed d.

Apply the preceding argument with \eps/2. On a partition of bounded size r_0' that approximates every family member, quantize each cell mass downwards in increments \eps/(2r_0'). The L^1 error in the piecewise-constant density is the sum of the cell-mass errors, at most \eps/2. There are at most (1+2r_0'/\eps)^{r_0'} possible quantized mass lists. They form the required net, proving (ii).

For (iii), the restriction of a density d relative to \omega_n has density \omega_n(\cK_n)d on \cK_n relative to \nu_n. Restriction therefore cannot increase the L^1 distance. A \nu_n-small set is also \omega_n-small, so (i) transfers as well. Every resulting subdensity has integral at most one; its superlevel set above R has reference measure at most 1/R. Assertion (i), applied along any contrary sequence, makes the integrals on those superlevel sets tend to zero uniformly as R\to\infty. This is uniform integrability.□

Proof. Every empirical integral and exceptional event used in this proof is measurable with respect to the primal maps. We can therefore work throughout with the projected law, paying only the projected marginal bound in (11.8). Raw expectations are unchanged by this projection. Rescale the test to have absolute value at most one. First consider one raw endpoint and duplicate its parameter batch. The two batches have jointly independent nominal columns except with 2^{-\Omega(n)} probability, because their Z inputs are independent and their total number of columns is bounded. With the nominal inputs fixed on this event, Lemma 11.2 compares the product of the two tests with the product of their separate raw expectations, at error O(2^{-N/2}). Averaging the two independent input batches and bounding the dependent-input event trivially proves

All these estimates are uniform in a fixed external datum, since it only changes the separate bounded test functions. Chebyshev’s inequality proves the one-endpoint assertion at every fixed tolerance.

For the paired assertion, assume that both endpoints are used; the other case follows at once from the marginal bound. Let D_2 denote the second endpoint’s input-and-image data under its raw model, and for a first primal orientation o define

Fix a small constant \eta>0. By (11.9), uniformly in D_2, \PP_{\rawlaw^{\mathrm{pr}}}\{\abs{h_o(D_2)-\bar h(D_2)}>\eta\} is exponentially small. Fubini and Markov show that, outside an exponentially small set of first primal orientations, the raw-model probability of the bad data set

is at most 2^{-c n} for some c>0. The projected marginal cap in (11.8) still makes the discarded first-endpoint mass exponentially small.

Fix any of the remaining first orientations. We claim that a raw second orientation o' has empirical input probability at least \eta of B_o only with probability 2^{-\Omega(n^2)}. Draw \ell'=\lfloor c_2'n\rfloor independent second-endpoint input batches. For an orientation with empirical bad probability at least \eta, at each step success and nominal independence of the new columns modulo the previous ones have conditional probability at least

The failure bound depends only on fresh uniform Z coordinates and holds for any past inputs. Thus all successes together with joint nominal independence have probability at least (\eta/2)^{\ell'}.

For independent nominal columns, the joint raw image law of these batches has density at most 2^{C_2(\ell')^2} relative to the product of the individual raw batch laws. Indeed it adds only O((\ell')^2) mutual Gram conditions and injectivity; count their normalizations by Lemma 11.1 and bound the indicator in the numerator by one. After averaging the inputs, the all-success probability on the independence event is consequently at most

Choose c_2'>0 small enough that C_2(c_2')^2<cc_2'/2 and that nominal independence is available. Dividing by (\eta/2)^{\ell'} proves the claim.

This quadratic-exponential estimate is uniform in the fixed good first primal orientation. Hence the set of paired primal orientations with a good first endpoint but a bad oversampling second endpoint has (\rawlaw^{\mathrm{pr}})^2-mass 2^{-\Omega(n^2)}. Multiplying by the projected joint density 2^{CN}=2^{CM_0n} still leaves quadratic-exponentially small mass. On every remaining pair,

Finally, \bar h is a common input-and-key test of the second endpoint. Apply the one-endpoint estimate again and its projected marginal cap to compare its empirical integral with its raw mean to within \eta. Taking 4\eta<\eps proves the lemma.□

Proof. Collapse all identical Gram entries, including the repeated same-endpoint entries that equal the same E evaluation, and impose only one copy of each. Consistency means that their prescribed values respect these repetitions. Expand the resulting binary indicators into characters. The zero character has coefficient \kappa=2^{-b}, where b is the number of the resulting specified bits. We show that every nonzero character has an exponentially small integral against the product of unary weights.

If an interacting pair of positions belongs to the same endpoint, their labels are distinct. The second property of Lemma 6.5 says that every nonzero parity of its ordered L,R bits, with its possible E bits in either order, has bilinear rank at least n/5 on the retained free variables. This includes characters involving only E bits.

For positions from opposite endpoints, we establish the analogous claim for their global Gram bits except on a 2^{-\Omega(n^2)} raw exceptional set. Write d=\dim\cB+h for the full plus-frame dimension. At one component, an intersection of dimension at least v=\lfloor n/10\rfloor between the two full plus spans gives v independent image relations. Their coefficient choices number at most 2^{2dv}, and the frame image estimate bounds each event by 2^{-(1-\epsilon)vN}, for a fixed small \epsilon. The choice of M_0, hence d/N small, makes this 2^{-\Omega(n^2)}. There are only boundedly many components.

Condition on plus frames off this exception. Choose a nonzero pair pattern and a component where, after exchanging the endpoints if necessary, it uses a plus slot at endpoint 1 paired with a minus slot at endpoint 2. At least n-v of the first position’s Z directions are independent modulo the second endpoint’s full plus frame. The second position’s nominal minus Z directions are independent. Conditional on the plus frames, the latter minus columns have independent uniform values on the appropriate affine annihilator spaces, before their full-rank conditioning. Their evaluations on these n-v directions therefore form a uniform rectangular matrix, up to a fixed translation. Terms in the reverse order and other components may be frozen first; they use separate minus-frame randomness. The final injectivity conditioning costs only a bounded multiplicative factor.

A uniform a by b binary matrix has rank at most r with probability at most 2^{(a+b)r-ab}, by writing it as a product of an a by r and an r by b matrix and counting. With a\ge n-v and b=n, this shows that the bilinear rank is greater than n/5 except with probability 2^{-\Omega(n^2)}. Union over the boundedly many nonzero pair patterns. The joint density in (11.8) preserves this exceptional scale.

For any nonzero full character, choose a pair with nonzero coefficient pattern and fix the other position inputs. The remaining terms become separate unary phases. The selected pair has rank at least n/5 by one of the preceding two arguments. Lemma 5.9 gives an error O(2^{-n/10}) against the two remaining bounded unary weights. Input conditioning costs only the fixed reciprocal probabilities of the diagonal values or tester summaries; those events can be absorbed into the respective weights. Summing the bounded number of characters proves (11.10). All estimates were uniform in the unary weights, so the exceptional set does not depend on them.□

Proof. Squaring the mean sign and translating one variable gives

where B is the polar form. Its absolute value is at most the kernel proportion 2^{-2r}. Restricting a bilinear form to a codimension-c subspace in each of its two factors can decrease rank by at most 2c. Apply the first assertion on that affine subspace, where translation affects only the linear and constant terms.□

Proof. For each fixed point parameter, the raw key law is the single-key reference up to an exponentially small injectivity error, by Lemma 5.2. The first conclusion therefore follows from the one-endpoint part of Lemma 11.7, also after conditioning on a feasible summary.

Fix a nonzero profile x\in\cX of total component rank at most K, and consider the sign

By the first property of Lemma 6.5, its dependence on Z factors through a bounded-dimensional space of linear forms, independent of the other input values, and its Z-polar rank is at least 2(J-s_0). Put

The strict inequality follows from the chosen lower bound on J.

Apply a uniform G\in\GL_n(\F) simultaneously to the Z input coordinates in all primal frames at the queried endpoint. This preserves the raw primal law because E has no Z rows or columns. We perform this averaging on \rawlaw^{\mathrm{pr}}, not on the thinned conditional channel law. It also preserves the empirical mass of a global key cell: change variables in the uniform Z input and leave the other coordinates unchanged. After this change of variables the cell event is fixed and the sign’s bounded row-bit space is moved by the inverse transformation.

Fix a starting orientation for which the cell, conditional on the summary, has input mass at least \delta/2. We claim that at most 2^{-2An} of the transformations can make its conditional absolute sign bias exceed \gamma, for sufficiently large n. Suppose the contrary and retain one bias sign, losing at most a factor two. For any fixed integer u, choose u such transformations successively so that each new row-bit space meets the span of the previous ones in dimension at most s_0. This is possible for large n. Indeed, for a uniformly moved space of bounded dimension and a fixed space of bounded dimension, the probability of an intersection of dimension greater than s_0 is O_u(2^{-s_0n}): choose s_0 independent vectors in the former and bound the probability that their uniformly independent images all lie in the latter. The number of such choices and target vectors is bounded independently of n. Since s_0=4\lceil A\rceil>2A, this excluded fraction is smaller than the retained fraction at each of the fixed number of choices.

Let E_0 be the fixed cell event in the conditional input probability space and let \delta'=\PP(E_0)\ge\delta/2. Denote the chosen signs, with their common bias sign adjusted to be positive, by s_1,\ldots,s_u. Let \mathcal F_{j-1} contain all non-Z inputs and the row bits of the preceding chosen spaces, and put

Conditioning the current row bits on the past imposes at most s_0 linear conditions on their distribution. The polar rank can therefore lose at most 2s_0 further dimensions. By Lemma 11.10,

pointwise, including after the non-Z inputs are fixed. The D_j are martingale differences with second moments at most one, so \norm{u^{-1}\sum_jD_j}_2\le u^{-1/2}. On the other hand every selected sign has conditional mean greater than \gamma on E_0. Consequently

Here the intrinsic bias costs b_*\delta', because its conditional mean is bounded pointwise; it does not cost an absolute b_* before division by the cell mass. Taking u>2/[\delta(\gamma-b_*)^2] contradicts (11.13). This proves the transformation claim with J fixed independently of the cell mass.

Integrate that claim over the starting raw primal orientation, using frame-law invariance. The first part of the lemma makes the cell mass at least \delta/2 outside an exponentially small set. More precisely, the transformation estimate is used only on orientations with this mass; that property is itself invariant under the transformations. This cell-mass exceptional set is common to all profiles and is discarded only once. For a fixed x, the event that the cell mass is at least \delta/2 and the conditional sign bias is bad has raw probability at most 2^{-2An}. There are at most 2^{An} nonzero profiles of the required rank for all sufficiently large n, by Lemma 6.5. Union over them, and over the bounded numerical position and summary choices. The resulting event is still exponentially small, also after the projected marginal inflation in (11.8). This union is taken before making any channel-dependent choice of effective space or basis: its exceptional event is a function of the primal frames alone.

On its complement every nonzero linear combination of a basis of C_i has conditional sign bias at most \gamma, regardless of how the space and basis were selected from the unit. Fourier inversion, for d_i=\dim C_i, gives for every assignment

This also covers d_i=0.

It remains to check the uniform generic constant. For one retained tester block, the sum of r_0\ge1 independent bit-pair products has probabilities (1\pm2^{-r_0})/2, both at least 1/4. Distinct tester blocks use disjoint input bits. There are at most g^2+1 such blocks, so every feasible summary has probability at least 4^{-(g^2+1)}. Conditional on its compatible value of q, its probability is no smaller. Its empirical key-cell mass, conditional on that summary, is at least (3/4)\Omega_{l,q,n}(A_n) outside an exponentially small set by the first part. Combining this with the basis lower fraction gives (11.12), since (3/4)(7/8)>1/2. In the generic flavor there is at least one retained O tester and the independent shared tester. Prescribing their parities realizes either a role at either fixed q, and a feasible summary for each has the same lower probability bound.□

Proof. Let \Gamma be the finite list of crossing Gram bits generating the twists. Begin with the trivial partitions of the two groups. For any current pair of finite partitions, condition W on their cells and on \Gamma; call the resulting conditional expectation S. Then \norm{S}_\infty\le B and \norm{W-S}_\infty\le2B.

If D=W-S has twisted cut norm greater than \delta, choose a twist and witnesses f,g giving correlation greater than \delta. Quantize f,g uniformly within their bounds finely enough, with a mesh depending only on B,\delta, that their quantized product times the twist still correlates with D by more than \delta/2. Refine the group partitions by the values of these quantized functions. The witness product is measurable for the new conditioning algebra and has L^2 norm at most one. Thus the new conditional expectation of D has L^2 norm at least \delta/2. Since D is orthogonal to the old conditioning algebra, the squared L^2 norm of the new conditional expectation of W increases by at least \delta^2/4. It is bounded above by B^2. At most 4B^2/\delta^2+1 refinements are possible. Each increases the partition sizes by a factor bounded in terms of B,\delta, so the final partitions have bounded size.

On each product of group cells, the final conditional expectation is a bounded function of \Gamma. Assign value zero to any impossible combination of a cell pair and Gram bits. Its finite Fourier expansion on the Gram bits has coefficients of absolute value at most B. Multiplying by the two cell indicators gives (12.5). The decomposition is exact everywhere on the product key space, regardless of which Gram bit values occur in a particular cell pair.□

Proof. For one fixed orientation, put U(I,J)=D_n(K_I,K_J)\psi_n(I,J) and use independent copies of the parameter groups I,J. Cauchy–Schwarz in I gives

Expand the square, and apply Cauchy–Schwarz in the two J variables. The factors g(J_0)g(J_1) have bound one. We obtain

In particular Q_n(O)\ge0: it is the expectation over J_0,J_1 of the square of \E_IU(I,J_0)U(I,J_1). All separate weights, including their orientation dependence, have disappeared.

The right-hand side is a bounded common input-and-key test, involving two fresh copies of each original position. It depends only on the primal maps: the channel-dependent weights and all marks have disappeared in (12.7), and the nominal L,R signs involve only the displayed fresh parameters. Repeated labels across these copies are permitted by Lemma 11.7. It follows that, outside an exponentially small mixed exceptional set,

We bound the raw mean by C_3\delta+o(1).

Fix the nominal inputs of the four groups. Their columns are jointly independent within each endpoint, component, and mode except with 2^{-\Omega(n)} probability, since all copies have fresh Z inputs. The dependent-input contribution is o(1) by the fixed sup bound. On the independence event, Lemma 5.2 gives the uniform image law with prescribed same-endpoint Grams and injectivity. Ignore injectivity at an exponentially small error and express this law relative to the product of all the individual single-key references. There are only boundedly many additional Gram bits, and their normalization is bounded uniformly in the nominal inputs by Lemma 11.1. Expand their indicators into characters. The nominal L,R phases are now constants. The global Gram phases already in the four copies of \psi_n can be combined with the expansion characters.

For completeness, distinguish a slot by its group I or J, its copy, its position, component, and sign. Remove the diagonals already in the reference and collapse repeated descriptions of the same unordered slot dot. Every remaining Gram coefficient belongs to exactly one of the following classes:

1. (a)

   both slots lie in one of I_0,I_1,J_0,J_1;

2. (b)

   the slots join I_0 to I_1, or J_0 to J_1;

3. (c)

   the slots lie in one of the four I_a–J_b quadrants.

Class (a) contributes bounded separate group phases. Suppose a nonzero class-(b) pattern between I_0,I_1 remains. Fix both J groups. The four D_n factors split into two bounded functions of I_0 and I_1. The class-(c) phases become separate functions of those two groups, as do all class-(a) phases. Their only remaining interaction is the nonzero coefficient rectangle between I_0 and I_1, whose bit rank is at least N. The individual diagonal densities may also be absorbed into the respective bounded weights. Lemma 5.9 bounds this term by O(2^{-N/2}). The same argument applies to a nonzero J_0–J_1 pattern.

If neither class-(b) pattern remains, attach each class-(c) pattern as an available twist to its corresponding D_n(K_{I_a},K_{J_b}). Fix I_1,J_1. The remaining integral in I_0,J_0 has one factor D_n times an available twist, tested against bounded separate functions. The two other unfixed D_n factors have bound B_1 and the fixed factor has bound B_1. The twisted cut estimate therefore bounds this term by B_1^3\delta, with the harmless fixed normalization factors included in the constant.

These cases exhaust the character expansion. The groups I and J may each contain positions from both endpoints of the unit: this only removes some same-endpoint Gram bits from the expansion and does not create a new class. A nonzero coefficient rectangle has rank at least one in distinguished global slots, hence bit rank at least N. The two dots P_a\cdot Q_b and P_b\cdot Q_a, for example, use different slots and are not duplicates. The prescribed nominal Gram values affect character coefficients only by signs.

Summing the bounded number of terms and averaging the nominal inputs gives \E_{\rawlaw^2}Q_n\le C_3\delta+o(1). Combine this with (12.7) and (12.8). The same Q_n(O) bounds every choice of separate weights, so the exceptional set is independent of them.□

Proof of Theorem 12.1. If r=1, quantize the values of W_n in [-B,B] with mesh at most \eps/2, choosing representatives in the same interval. The resulting S_n satisfies \norm{W_n-S_n}_\infty\le\eps/2 and is a linear combination of at most 1+\lceil4B/\eps\rceil global level-set indicators, with coefficients bounded by B. Both required errors are at most \eps/2, since the reference measure is a probability measure and the actual-query indicator and weights have bound one. This includes B=0, when S_n=0. For r\ge2, apply Lemma 12.2 to a nontrivial split of the full set of positions. Recursively apply it to group factors in the structured terms until every factor is unary. Whenever a remainder is produced, leave that whole term terminal; do not expand its other factors. We obtain the exact decomposition, on the unconditioned product reference,

Each structured term is a product of unary global functions times available Gram twists. Each terminal term has the form

where I,J partition one group, the groups H are disjoint outside I\cup J, all outside functions are bounded, \tau_{v,n} is a product of available Gram signs, and D_{v,n} has a specified small twisted cut norm on I|J. The sup bounds, numbers of terms, and partition complexities are all bounded independently of n.

Here is an explicit way to organize the tolerance choices. Along any structured branch a split replaces one group by two, so at most r-1 splits are needed before all groups are unary. At any fixed depth the number of pending terms and all their coefficient and factor bounds have already been bounded using previous choices. Allocate at most \eps/(2r) of each desired final error to that depth, dividing this budget among its pending terms and their known outside bounds. Choose the next cut tolerances small enough for the reference estimates below and for the fourth roots in Lemma 12.3. These choices determine a finite bound on the next level’s number of structured terms. Continue for at most r-1 levels. The empirical tolerance \varepsilon_{\mathrm{emp}} for each terminal test is chosen at the same stage, sufficiently small for its allotted fourth-root error. All choices are constants; none requires a change in the construction parameters or in M_0.

On \cK_n, every Gram twist in S_n^{\mathrm{tw}} equals one. Removing them gives the function S_n in (12.1). Its unary factors are indicators of the finite partitions used in the recursion; coefficients and term counts have the asserted bounds.

To prove the reference assertion, multiply a terminal term (12.10) by a product of arbitrary bounded unary tests and expand the off-position Gram event defining \nu_n. Fix all positions outside its remainder. Their group factors are bounded constants. Gram phases internal to I or J and phases involving a fixed outside position are separate bounded group weights. The only other phases are available crossing twists. Thus the integral is bounded by the twisted cut norm of D_{v,n} times a constant depending only on its known bounds and the fixed Gram normalization. The tolerance allocation makes the sum of these errors at most \eps, proving (12.2). This estimate is uniform over all unary reference test functions.

For the actual-query assertion, expand \mathcal A_n into its Gram and nominal L,R characters. The number of terms is bounded. Consider a terminal term and fix the outside position parameters. All phases internal to I or J, or involving an outside position, can be absorbed into separate group weights. The remaining crossing phases are a product \psi_n(I,J) of precisely the form in Lemma 12.3. It is independent of the outside parameter values: a binary bit involving an outside position has already been put into a separate weight. All original unary weights, even when they depend on the orientation, can also be included in these two weights.

Apply Lemma 12.3, scaling the known outside bounds as necessary. Its common four-copy test is independent of the fixed outside parameters, so one exceptional orientation set controls every such fixation. Integrate the outside parameters, sum the bounded binary-character expansion, and sum the terminal terms. The chosen cut and empirical tolerances make the total at most \eps for sufficiently large n. The union of the finitely many exceptional sets is exponentially small. Since each four-copy estimate is uniform over its separate weights, the final exceptional set is independent of all unary input weights and of orientation-only filters. This proves (12.3).□

Proof. Apply Lemma 11.9 to each structured term, with f_{a,j,n}(K_j)w_j as its unary weights. The number of terms and their bounds are fixed at the chosen approximation accuracy, so the sum of the exponentially small errors tends to zero. The exceptional set in that lemma is independent of these weights.□

Proof. We may truncate net representatives to [0,R]. Since \norm{f-g}_2^2\le R\norm{f-g}_1 for functions in this interval, we obtain L^2 nets with uniformly bounded size, say at most m. Pad shorter nets by zero functions. Write their members as f_{L,a} and g_{L',b}, and form the positive operators on L^2(\nu_n)

Here (f\otimes f)v=f\pair{f}{v}. Both traces are at most T=mR^2.

Fix \delta>0. There are at most T/\delta eigenvalues of C_A larger than \delta. A unit eigenfunction e for such an eigenvalue \lambda satisfies, pointwise,

Quantize these finitely many bounded eigenfunctions with a common finite partition. Its conditional expectation P can be made to satisfy \norm{(1-P)e}_2\le\varepsilon for every one of them. With Q=1-P, the spectral decomposition gives

The number of partition cells is bounded in terms of m,R,\delta,\varepsilon. If P' is a refinement and Q'=1-P', then Q'=Q'Q=QQ', so the same operator bound holds for Q'C_AQ'.

For net representatives, independence of the leaves gives

This estimate permits pairwise-adaptive choices: the squared error for any chosen pair of representatives is pointwise at most the displayed sum. Cauchy–Schwarz bounds its expected absolute error. Approximating arbitrary family members by their net representatives costs at most a constant times R times the L^2 net error, since orthogonal projections are contractions. Choose the net accuracy, then \delta and \varepsilon, sufficiently small in terms of \eta. This proves (13.4), also for refinements. The final indicator assertion follows from the absolute-value bound before the indicator is applied.□

Proof. Choose countable lists of global binary tests on each \Omega_{l,q,n}. Include every imposed global predictor bit, if there is one. A key’s values under this list form its unary signature. For each key shape also choose countably many binary tests on \cK_n, including the pullbacks of all unary tests at its positions. Their values form a tuple signature.

The lists are constructed by countable closure. For every numerical option, positive integer truncation height, and successively improving fixed accuracy, include the cells of a partition provided by Lemma 13.3. For every tuple cylinder test and successively improving accuracy, include all unary indicator factors needed in Theorem 12.1; close under the finite Boolean operations needed to record them. Repeat these operations. Every finite stage has bounded complexity independent of n, so it defines sequences of tests for all sufficiently large n; finitely many missing initial values may be assigned arbitrarily. Bounded coefficients in the approximations are also included among the scalar coordinates that will converge. Crucially, regularity in Theorem 12.1 is performed on key spaces. Its new unary factors remain global key functions. Nominal input phases handled in the proof of that theorem are not added to the signature lists.

At an orientation, and for every unary type t, record the empirical mass of each finite signature cylinder together with each numerical status outcome. Include the finite metadata needed for the chosen C_i bases and all numerical options; in predicted cases include the old marked profiles in these bases, the fixed role coefficients, and their exception sets. Call this array \theta_n. The cylinder masses lie in [0,1] and obey consistent finite additivity identities. Their closed consistency space, together with the finite metadata, is compact and metrizable.

For each pair of leaves retain its permitted-pair bit J_n and, as part of the same random record, the conditional measures of (\theta_n,\text{flag vector}) on each side. Also retain the full and truncated successful-query measures on all tuple cylinders, for each option. These are measures of mass at most one on compact bit-sequence spaces; their spaces are compact for weak convergence. Take a common subsequence of the laws on the resulting countable product, and simultaneously of the deterministic reference laws and the bounded approximation coefficients. Consistent limiting cylinder masses define countably additive measures on the bit-sequence spaces, for example by first defining the measure on finite prefixes and taking the unique measure with those finite-dimensional laws.

Cylinder evaluation is continuous because bit cylinders are clopen. For each fixed unary cylinder, Lemma 11.7 says that the sum of its empirical status masses differs in probability from its reference mass by a quantity tending to zero. This test uses only primal images. The projected primal marginal assumption on the actual mixture is the one needed here; no original full-frame marginal bound and no assertion about every individually normalized leaf is used. The status bits may depend arbitrarily on channels: summing all statuses removes those bits. Countably many limiting cylinder equalities imply that the total status measure is m_{l,q} almost surely. Each status measure is therefore dominated by m_{l,q}, giving (13.5). Versions jointly measurable in (\theta,\xi) are obtained by taking the limits of their conditional density averages on increasing finite cylinder partitions, as in Lemma B.2. An exceptional null set for the base law also has \Lambda_A- and \Lambda_B-mass zero for almost every stored record on the respective side, because averaging these conditional laws recovers that side’s base law. The same is true after any flag restriction.

For a generic role/basis assignment, apply Lemma 11.11 to each fixed cylinder of positive limiting reference weight. The lower fraction is independent of the cell; the onset of the estimate may depend on its positive weight. All profiles of the relevant rank are covered by that lemma before the profile is selected, so the chosen C_i may vary with the entire orientation, including its channels. The p_i flag is summed over in this positivity statement; no value of p_i is prescribed as a positive base coordinate. Its lower inequalities pass to the limiting cylinder masses. Zero-reference cylinders already have zero total status mass. The cylinder inequalities extend by finite unions and monotone approximation to all measurable sets, giving the claimed almost-everywhere lower densities. This argument does not condition on arbitrary nominal input cells.

By Lemma 11.3, every finite collection of unary signature tests has its product reference law in the tuple limit. Therefore the unary projections under \rho are independent with the stated marginal laws.

There is no need to interchange disintegration and weak convergence. The conditional laws themselves were retained as random coordinates. For bounded continuous tests, taking their product is continuous in these two laws. Consequently sampling from \Lambda_A\otimes\Lambda_B conditional on the limiting record Z reproduces the limiting joint orientation tests. Before flags are applied, the two base orientations were independent under their respective mixture laws at every n, so independence with those respective laws remains true after averaging Z and dropping flags. If the laws agree, their limits agree as well. Finite metadata are discrete coordinates, hence all their incidence and compatibility identities are retained. This proves the table assertions and their mass statements. Finally the prediction errors tend uniformly to zero on the retained orientations. Since the predictor bits are included as unary tests, each such error is a finite status-cylinder mass and becomes zero in the limit.□

Proof. For each integer R, cylinder inequalities give 0\le\eta_R\le R\rho, and the measures increase with R. The uniform small-set conclusion of Lemma 11.5 also gives uniform integrability of the successful-query densities. Indeed, since their masses are at most one, \nu_n\{d_n>R\}\le1/R; uniform small-set control bounds the mass on this set by a quantity tending to zero as R\to\infty, uniformly asymptotically in the leaf and in its orientation filter. Thus there is a deterministic function \varepsilon_R\to0 such that, in the limit,

It follows that \eta=\sup_R\eta_R. In particular it has a density which is the increasing supremum of the truncated limiting densities.

Fix R. The prelimit inner product of the two truncated densities, multiplied by J_n and usability, tends to zero because it is bounded above by (13.2). Choose a global partition with projection error at most \varepsilon in Lemma 13.3. For that finite partition the inner product of the projected densities is

This expression passes to its limiting counterpart in expectation, jointly with the discrete permitted-pair and usability indicators. A cell whose reference weight tends to zero contributes at most R^2\nu_n(C) and may be omitted. On the other cells ordinary continuity applies.

Take increasing cylinder partitions which generate all tuple tests and include global projection partitions at accuracies tending to zero. The refinement assertion in Lemma 13.3 preserves the error estimate. Conditional expectations of the limiting bounded densities on these partitions converge in L^2(\rho): this follows, for instance, by approximating an L^2 function by cylinder-simple functions and using that conditional expectation is an L^2 contraction. Their inner products therefore converge in expectation, being bounded by R^2. We obtain

All terms are nonnegative. Taking the countable intersection of the resulting almost-sure assertions, then increasing R, proves the same product-zero conclusion for the full densities on J=1. Multiplication by J is legitimate at the projection step because the projection error bound is in absolute value and permits every leaf-pair indicator. There are only finitely many options.□

Proof. The displayed expression is jointly measurable and nonnegative, by Lemma 13.4. We prove equality against every tuple cylinder indicator W.

At a fixed accuracy \varepsilon, apply Theorem 12.1 to its prelimit global key test W_n. On the reference key space its structured approximation has the form

where the number of terms and all bounds are fixed at this accuracy. The unary factors may be taken to be finite linear combinations of indicator factors already in the common test lists. In the actual-query assertion of that theorem, take as unary weights the numerical status indicators of this option. These may depend on the orientation. The extra admissibility condition is orientation-only. Thus, after averaging over leaves, the successful mass tested by W_n differs from that tested by W_n^{(\varepsilon)} by at most the prescribed accuracy and a vanishing error.

For clarity, this last use does not require typicality separately on every leaf. At a typical orientation the product-testing error is uniform over the allowed bounded unary weights. Multiplying by any orientation flag only decreases its bound. After both leaves are averaged, the mass of exceptional orientations is bounded by the mixed orientation error in Lemma 11.7. An opposite-leaf-dependent choice of the flag cannot increase that unconditional error.

Apply Lemma 11.9 to each structured term. Again its unary weights are the status indicators times bounded global unary factors. The resulting expression is

up to a vanishing error at this fixed complexity. Here the measures inside the product are the empirical single-atom status measures at the given orientation. Every integral in parentheses is a finite linear combination of status-cylinder coordinates. The coefficients and conditional measures were stored in the compactification. Consequently (13.7) converges jointly with the successful cylinder mass to the analogous expression in the limit. The preceding errors are controlled in mean absolute value over Z.

It remains to compare that limiting structured expression with the integral of W G_Z. This is where the reference conclusion of Theorem 12.1 is also needed. Its error bound, uniform against products of bounded unary functions, passes to the limiting reference law first for cylinder-simple unary functions, since all the relevant finite test probabilities converge. It then holds for all bounded measurable unary functions on the signature spaces: approximate each one in L^1(m_{l,q}) by cylinder-simple functions, and telescope the product. At this fixed approximation accuracy the structured test has a fixed finite bound, so this passage costs a quantity tending to zero.

We may therefore use the unary functions h^\theta_{t_\ell,\upsilon_\ell} in the limiting reference comparison, for each \theta, and integrate it under the subprobability law \alpha_Z. Independence of the unary projections under \rho gives

This is exactly the limit of (13.7). Replacing W^{(\varepsilon)} by W in this last integral costs at most \kappa times the reference approximation accuracy. Combining the empirical and reference estimates and sending \varepsilon\to0 yields

There are countably many cylinder indicators. Equality on all of them determines the measures and proves the lemma.□

Proof. For a usable option, Lemmas 13.5 and 13.6 give \int G_{A,Z}G_{B,Z}\,d\rho=0 for almost every Z with J(Z)=1. Fubini’s theorem and independence of the unary projections express this integral as

All factors are nonnegative and both \kappa constants are positive. Hence the product inside is zero for almost every passed pair from the conditional laws. Averaging Z and taking the finite union over options proves the assertion.□

Proof. Apply finite-dimensional duality to the linear constraint map on \bigoplus_{i,j}V_{ij}. The coefficients of the four coupled equations are s_j,r_i, giving (14.5) separately on each edge. If they were all zero, the local projection onto (q,h_{A,i}+h_{B,j},\mathbf x_{A,i},\mathbf x_{B,j}) would be surjective by (14.2), forcing all other dual coefficients to vanish. Hence a nonzero obstruction uses some coupled equation. Conversely the constraint target lies in the image exactly when it annihilates every dual relation. The coupled targets are zero, so their evaluated contribution is the sum stated in the lemma.□

Proof. Suppose otherwise. Let E_s be the event that a witnessing relation has some s_j=1, and define E_r similarly. Interchanging the two iid units interchanges these events, so they have the same probability. Their union is the obstructable event. Therefore \PP(E_s)\ge .05.

Fix a witness with s_j=1. For each first-side endpoint i, rewrite its edge relation as

For any surviving label/flavor choices and any common feasible (l,q), this equality holds almost surely under the product of the two status distributions conditional on the same signature. Otherwise a violating pair of numerical statuses would have positive overlap and would be a generator violating the relation. The two bits in (14.6) are conditionally independent at a fixed signature. If two independent bits agree almost surely, both are constant almost surely with their common value: writing their success probabilities as a,b, the mismatch probability a(1-b)+(1-a)b is zero only for (a,b)=(0,0) or (1,1).

Compare all surviving first-side choices to one fixed generic surviving choice at (B,j). Its total conditional status mass is one on every signature space, and its generic flavor admits either q. It follows that, simultaneously over all tags, feasible bits, labels and flavors remaining at (A,i),

where \lambda_{A,i} is the basis combination specified by \mathbf c_{ij} and \alpha_{A,i}=1+\beta_{ij}. The coefficients are common to these choices. The offset is also common across them; one does not choose a new offset for every label or flavor.

There are very few possible offsets after the second-side array is fixed. If r_i=0, generic positivity of the role and basis at (B,j) forces \mathbf c'_{ij}=0 and \beta_{ij}=0 in (14.6). The offset is then either zero or q. If r_i=1, it is, up to a common multiple of q, the deterministic value of

For this fixed array and endpoint there is at most one possible deterministic expression (14.8), including its coefficients, even if the permitted exclusions vary. Indeed two candidate exclusion sets of size at most B_* have a common surviving generic label, since the label universe is larger than 2B_*. At that label every role/basis assignment has positive density conditional on the signature. Subtracting the two claimed deterministic expressions therefore forces their coefficient differences to be zero, and then their offset functions agree almost everywhere on every (l,q) space. The same generic label can be used at every tag and diagonal bit.

Thus, for a fixed second-side array, each choice of j supplies at most four offsets for each first-side endpoint: the two multiples of q, and the unique function (14.8) plus those two multiples, if that function exists. Across both choices of j there are at most 2\cdot4^2=32 pairs (f_1,f_2).

All events used here are measurable. There are finitely many types, status vectors, coefficients, and exclusion sets, and generator availability is a positivity test on the integral of jointly measurable densities. By Fubini, choose a fixed second-side array for which the first-side mass of E_s exceeds .04. One of the at most 32 pairs of offset functions then gives (14.7) on first-side mass at least \delta_0=.04/32, allowing its coefficients and exclusion sets to vary with the first-side array. This is much larger than 10^{-6}.

We now transfer these fixed signature functions to a prediction in the finite problem. This step is necessary because the definition of prediction asks for global functions of actual keys. For any \varepsilon>0, approximate each fixed binary function f_i by a binary cylinder function f_i^{(\varepsilon)}, with disagreement measure at most \varepsilon on each of the finitely many (l,q) reference spaces. Such approximation follows by approximating the measurable event where f_i=1 in measure by the algebra of finite cylinders. The total unary measure of every type is its reference measure, so replacing f_i increases every relation error in (14.7) by at most \varepsilon.

For fixed cylinder functions and a fixed choice of coefficient bits and exclusions, all these error probabilities are finite linear combinations of status-cylinder coordinates. Their maximum over the remaining unary types is continuous. Minimizing over the finitely many permitted coefficient/exclusion choices is also continuous, separately on each discrete coordinate format. The strict event that this minimum is below 2\varepsilon consequently has limiting probability at least \delta_0. Weak convergence implies that its prelimit probability exceeds \delta_0/2 for all sufficiently large indices. One may see this directly by approximating the indicator of an open strict-error event from below by continuous functions.

Choose decreasing \varepsilon_m\to0 and increasing prelimit indices at which the last mass bound holds. At index m use the two global functions obtained by evaluating f_i^{(\varepsilon_m)} on the actual global key signature. Keep the orientations in the strict-error event and choose one of their successful coefficient/exclusion records. The kept mass is at least \delta_0/2>10^{-6}, and the maximum relation error over all remaining unary types tends uniformly to zero. Conditional-on-q errors give the same conclusion for the unconditioned flavor tests. These are precisely the requirements of Definition 10.1. The no-prediction branch has only the first effective spaces and only negligible trimming, so this mass margin also gives a prediction before that trimming. This contradiction proves the lemma.□

Proof. The exact limiting prediction is

where bold \boldsymbol\lambda denotes coordinates in the effective basis. Substitute this into a dual relation (14.5). At a fixed signature the two generic status distributions have every pair of role/basis assignments available. Comparing their coefficients forces

Thus

Equality of functions here is exactly the almost-everywhere equality recorded in the prepared subsequential class.

If both e_i vanish, Lemma 10.2 supplies the exact identity p_i=T(\lambda_i,\mathrm{atom})+h_i on all atoms. Hence on each span p_i+h_i=\boldsymbol\lambda_i\cdot\mathbf x_i. At the local targets, the first coupled sum for a fixed j is

by the empty-status compatibility condition. The reciprocal coupled sums vanish in the same way. Local surjectivity therefore solves all constraints in this case.

Suppose that some e_i is nonzero. A nonzero solution of (14.12) is possible only when all nonzero e_i are equal, and then both weight vectors are the indicator of their support S. To check this without any assumption on the dimension of the function space, first consider a support with one index, say e_1\ne0,e_2=0. The off-diagonal equations force r_2=s_2=0, and the diagonal gives s_1=r_1=1 for a nonzero solution. If both e_i are nonzero, the diagonal equations give s_i=r_i. The off-diagonal equation s_2e_1=s_1e_2 either makes both weights zero, or makes both one and e_1=e_2. These cases exhaust the possibilities.

If the two nonzero classes are unequal, no dual obstruction exists. Otherwise let d be the common first bit on S. With s_i=r_i=\1_{i\in S}, (14.11) is symmetric in i,j. Its diagonal is zero. Since the function q is not zero on the family of reference spaces, this gives \gamma_{ij}=\gamma_{ji} and \gamma_{ii}=0. The sum of all four q-contributions to a target is therefore zero. The total role contribution is

Evaluate the basis terms in (14.10) at their local targets. The a-terms sum to |S|c+|S|c=0, because Proposition 10.5 fixed the same value c=\sum_i a(\lambda_i) in both units. The remaining terms are

By (10.8), this equals |S|d. Together with the role contribution it is zero. Thus every dual relation vanishes on the target, and Lemma 14.2 proves solvability. The argument used only surviving generic labels and the prediction on those labels, so additional exclusions of the indicated kind do not change it.□

Proof. Without prediction, the probability of an obstructable base pair is less than .1 by Lemma 14.3. This statement uses the unflagged iid base law. In the full conditional-law experiment, a passed injecting table exists on mass at least .99 by Lemma 13.4. Their intersection therefore has mass greater than .89. On it no nonzero dual pattern exists for any exclusions within the stated budget, so Lemma 14.2 solves the scalar system for every such table. No independence of the two events is being assumed.

With prediction, a passed compatible injecting table exists on positive mass in the same experiment. The exact prediction and all almost-sure unary properties continue to hold on that event, and Lemma 14.4 gives the assertion.□

Proof. Begin with the mandatory support exclusions and, in the predicted case, the stored exceptions. More generally, start with the initial exceptions allowed by the scalar-solvability hypothesis. Whenever deleting at most 100 additional labels at each endpoint can shrink any of the four edge spans, make such a deletion. Each span continues to project onto its full base space. Its dimension exceeds that base dimension by at most two, so there are at most eight dimension-reducing steps in total. At the end, every edge span is unchanged by deleting up to 100 further labels at each endpoint. There remain generic labels, since (6.5) makes the label universe much larger than all these bounded exclusions. On the no-prediction branch the total budget, including later fresh-label removals, is at most B_0+900<B_*. On a predicted branch it is at most the stored exceptions plus this quantity, still leaving many generic labels. Scalar solvability is retained by the scalar-solvability hypothesis. Fix one solution on these stabilized spans.

We prove a statement for one edge after any labels used on earlier edges have also been reserved. Write its stabilized span as V, its base space as B, and its projection as \operatorname{pr}_B. Let G_L be the generators avoiding the current reserved sets L. Their span is still V. Let H_L be the span of sums of one, two, or three members of G_L whose total base projection is zero and whose endpoint labels are mutually disjoint within that word. We claim

To prove the claim, take two generator lifts of the same b\in B. There is a third generic lift of b at labels avoiding both of them and L. Comparing each original lift to this third one gives an allowed two-generator kernel word. Hence all lifts of b have the same class modulo H_L. Call that class \ell(b). A generator above base zero is itself an allowed one-generator kernel word, so \ell(0)=0. Choose mutually label-disjoint generic lifts of b,c,b+c. Their sum is an allowed three-generator kernel word, and therefore \ell(b)+\ell(c)=\ell(b+c). The generators span V, so this additive lift identifies V/H_L with B: the induced projection is inverse to \ell. This proves (14.13), including the case of zero base projection.

For the desired vector in V, first choose a generic singleton lift of its base projection. Reserve its labels. The remaining discrepancy belongs to \ker\operatorname{pr}_B, whose dimension is at most two. On the remaining labels (14.13) still holds because stability has preserved V. If the kernel is zero no correction is needed. If it is one-dimensional, choose a nonzero short kernel word and use it if needed. If it is two-dimensional, choose a nonzero short word, reserve its at most three labels at each end, and apply (14.13) again. The new short words still span the full kernel, so one lies outside the first word’s direction. These two words form a basis and the discrepancy is the sum of an appropriate subset of them. This uses at most 1+3+3=7 generators. The initial lift is always retained, so the list is nonempty; reserving labels before each choice ensures disjointness even when two generators have the same numerical bit vector.

Carry out this procedure on the four edges in turn. Each endpoint is incident to only two lists and uses at most fourteen labels in total. All removals and auxiliary freshness comparisons in the procedure are within the 100-label stability allowance. The generators keep their certificates of positive overlap, proving the lemma.□

Proof. Work on the subsequence defining the common model in the hypothesis. If the conclusion failed, finiteness of the option collection would give (13.3) along this same subsequence. Apply Proposition 13.7 in this model.

By hypothesis, there is positive model mass of permitted pairs with a table whose flags pass and whose scalar solution survives the needed exclusions. Apply Lemma 14.6. This gives between one and seven matched generators per edge with fresh allowed labels. Their sum vectors obey (14.3) and (14.4); equivalently, the lists obey all scalar recipe equations. At each generator the unspecified tester bits were only aggregated. Expanding the positive overlap integral as a finite sum over the two full tester summaries yields at least one pair of summaries for which the overlap is still positive. Make that refinement independently at each position.

The scalar consistency argument in Section 7, in particular (7.3), now supplies a consistent numerical prescription of the required within-endpoint binary bits from these summaries and p bits. Together with the already passed table, these data define a usable numerical option. The only parameter filters added are precisely the unary statuses and the prescribed binary conditions in (13.1). At every matched position the refined status overlap is positive. This contradicts Proposition 13.7 on a positive-mass event.

No pointwise uniform lower bound for these individual positive integrals is needed. The options form a finite collection and every product has finitely many nonnegative factors. A positive-mass event on which some such product is positive gives positive expectation for at least one option. Its lower bound is a constant on the chosen subsequence, however small that constant may be. The preceding contradiction therefore proves the stated subsequential lower bound.

For this probability consequence, assume additionally that the original laws satisfy the hypotheses of Proposition 8.1. The successful densities are unnormalized with respect to the retained law, and Proposition 8.1 explicitly charges any law restriction of reciprocal mass 2^{o(N)}. A positive constant, or its product with such restriction costs, is 2^{-o(N)}. The resulting four-hole probability, including the permitted-pair predicate, has exponent at most k_{\max}+.03+o(1), whereas

Thus these overlaps are on the scale required for Theorem 5.4.□

Proof. Suppose that the assertion fails along an unbounded sequence of n. The laws and their randomized colour marks may vary with n; the palette is fixed. Refine by colour and discard the exponentially light colour classes as in Lemma 5.6. Peel each remaining conditional class, but retain the original mass of every leaf. Their mixture is a restriction of the original law with total mass 1-o(1) before the fixed preparation restrictions. Hence its endpoint marginals remain bounded by a fixed multiple of M\pi and its primal marginals by the same multiple of the original primal law. The conditioning of a small colour may change a leaf’s joint density bound; this is already included in its absolute density and image budgets. It never changes the mixed marginal constant used next.

Apply Proposition 10.5 to this pooled law, carrying its colour as a mark. In the predicted case this yields a retained law of original mass at least \delta_*, and an event of passed compatible injecting tables of conditional pair mass at least 1/64. Its scalar systems are soluble by Lemma 14.4, robustly under the fresh-label exclusions. In the no-prediction case the retained mass is also at least \delta_* and Lemma 14.5 supplies conditional pair mass greater than .89. In both cases the successful scalar-table event has mass at least c_* in two draws from the original law.

If the original colour probabilities are p_c, their equal-colour pair mass is

The equal-colour part of any subevent, including a prepared subevent, has no larger original mass. Subtracting it therefore leaves at least c_*-\eta_{\mathrm{col}}>0 of successful scalar-table pairs of different colours. Equivalently, if preparation retained mass \delta, its normalized equal-colour pair mass is at most \eta_{\mathrm{col}}/\delta^2. This subtraction takes place before any pigeonholing of a numerical table. Thus neither the number of tables nor the palette size enters the early choice of \eta_{\mathrm{col}}.

Use the permitted-pair indicator J_n(L_A,L_B)=\mathbf1_{\{\operatorname{col}(L_A) \ne\operatorname{col}(L_B)\}}. Store this bit in the common model. The preceding original-mass lower bound, together with the retained prediction and injection assertions of Lemma 13.4, gives positive limiting mass on J=1 satisfying the hypothesis of Proposition 14.7. That proposition yields a fixed option with positive subsequential overlap on different-colour pairs. The filtered form of Proposition 8.1 now gives probability at least 2^{-(k_{\max}+.03)N-o(N)} for a four-hole event on those same pairs. Because k_{\max}+.03<100g, this is larger than 2^{-100gN} for all sufficiently large indices, contradicting the chosen violating sequence.

The overlap constant is allowed to depend on the subsequential model. This causes no loss in the uniform eventual assertion: any sequence violating it has a further subsequence with one fixed positive constant, and the fixed exponential gap just used defeats that sequence.□

Proof. Before imposing x\cdot y=q in one component, the four channel evaluation vectors

are uniform on \F^{4h}. Conditional on their values, x,y are independent uniforms on affine subspaces of codimension 2h. The pairing between their translation spaces has rank at least N-4h. For a bilinear form of rank R, its sign average on an affine product is either zero or has absolute value 2^{-R}: average first in one variable, leaving at most a 2^{-R} fraction of the other variable. Thus every fixed evaluation tuple has diagonal probability \frac12+O(2^{-N+4h}). Conditioning on the diagonal changes its uniform law by O(2^{-N+4h}) in total variation. Deleting zero key vectors incurs an additional O(2^{-N}) error.

For independent uniform bits a,b, \E(-1)^{ab}=1/2. There are h such products for one frame and 2h independent products for the pair of frames in each of the g-1 components. Independence across components proves the two formulas.

Under \rawlaw^2, two independent channel frames have concatenation rank less than 2h with probability at most O_g(2^{2h-N}), by exposing their uniform injective columns. The domination \nu^2\le L^2 2^{\varepsilon_{\rm ch}N}\rawlaw^2 still makes this probability exponentially small, since \varepsilon_{\rm ch}<1/2. This proves the last assertion.□

Proof. Suppose the limiting mass is positive. Approximate f, on each of the finitely many tag/diagonal reference spaces, by binary cylinder functions. For a fixed approximation, the maximum prediction error over the surviving unary types is a continuous function of the finitely many stored status-cylinder coordinates. Minimizing over the finite allowed exclusion choices preserves continuity. The strict-error transfer in the proof of Lemma 14.3 therefore gives a subsequence and global key functions f_n for which the finite prediction error tends to zero on a set of pairs of mass at least some \delta>0. The functions are fixed before sampling these pairs. We use no supremum over functions chosen by a sampled orientation.

There is a fixed surviving generic label on positive pair mass: average over the finite label set and retain one of its positive terms. Fix also a tag, a feasible diagonal, and a feasible generic tester summary \tau. This summary has a fixed positive nominal probability and fixes the role a(\tau). Conditioning the vanishing error on it still leaves vanishing error. Absorb the term \alpha a(\tau) into the global binary test \phi_n(k). Write the two points in the relevant order as U,V, so that p_{B,j} evaluates the channel form of V on the primal key supplied by U. Set

For each fixed V, the one-endpoint assertion of Lemma 11.7 applies with that entire frame as external data. Its exceptional set depends on this prescribed test, and its bound is uniform in the external data. The raw mean is d_n(V)+o(1) by the single-key frame law. The marginal of the primal frame of U is at most L times its \rawlaw-marginal. Consequently, for every fixed t>0,

For example the variance proof bounds the left side, apart from the negligible reference error, by LC2^{-cn}/t^2. Choose t_n\downarrow0 slowly enough for the exceptional probability still to vanish. If D_n\le\epsilon_n\to0 on the successful pair set, its projection to the V-coordinate therefore yields

Any adaptive choice of the successful pair set is harmless here: the typicality exception was bounded on the independent product law before restricting it.

Take two independent frames V,W from \nu conditioned on G_n. The probability of channel rank failure is at most its unconditioned o(1) probability divided by \nu(G_n)^2, and hence still tends to zero. On a pair with full ranks, agreement of both channel signs with the same test gives

This contradicts (15.5), whose right side tends to 2^{-2h(g-1)}<1. This use of two successful frames is essential: it introduces no required lower bound on \delta besides positivity. Finally, (15.2) changes all bounded error or event probabilities by o(1), so deleting internal holes cannot create the asserted limiting prediction.□

Proof. Use the cover threshold p_0, even moment s, and rank-growth constants in Lemma 9.2 and the proof of Theorem 9.3. Explicitly, s is the largest power of two at most c_sN, where c_s=10^{-12}(1+r)^{-4}, so s\ge c_sN/2 for large n. Put \theta=10^{-4} and \Gamma=D+2r+10. If no cover of the specified size has unit mass at least p_0, expand the moment against independent uniform channel columns of the one point:

This is (9.6) with no reciprocal phase and no candidate value of \Delta_Z. The inequalities (9.4) and (9.5), followed by Markov’s inequality at threshold \theta, bound the raw channel exception by C_h2^{-\Gamma N}. The channel comparison in Lemma 5.2 is included in the fixed factor C_h. Paying L2^{\varepsilon_{\rm ch}N} once leaves an exponentially small point-law exception. Thus \left|\E_{A,Z}(-1)^{u_Z(\Delta_A)}\right|<.01 for large n. Take R to be the whole space; each value of the bit has probability greater than .495.

Otherwise retain the p_0 mass in a fixed cover and delete the negligible set whose individual primal spans meet that cover. The deletion uses the unchanged primal marginal. The lifting identity (9.7) gives offset records with at most 2^{.002N} possibilities and offset basis size 1\le t\le2r. At one fixed record, let Z_A be its companion tuple. Its unnormalized subprobability law satisfies

by (9.10). For that record let R(A,Z) require the channel transposes of Z to have full rank on the plus and minus offset lists. The transpose estimate in Lemma 5.3, multiplied by the fixed point marginal factor, gives

after increasing h. We may, and do, make this bound less than .005.

On the retained rank event the output tuple \Phi_{u_Z}(\omega_A) has point masses at most 2^{-tN+.01N}. To check this directly, condition on the point’s primal frame and freeze the bounded lists of transpose coefficients on the offsets. Each list has full rank. Ignoring the equations defining those coefficients, their prescribed images under the opposite channel maps cost t(N-\dim\cB) bits. The number of coefficient lists is fixed in n. The density loss from thinning and the ratio \dim\cB/N are absorbed into .01N. This is the singleton image calculation of (9.11) with no point-side companion tuple.

The phase is Z_A\cdot\Phi_{u_Z}(\omega_A), plus a function of the point alone at this fixed record. The Walsh bound Lemma 5.9 therefore bounds its unnormalized signed mass, including the rank filter, by

Summing over records gives at most 2^{-.488N}. Since \PP(R)> .995-o(1), the mass where R holds and the phase bit has either prescribed value exceeds .49. This proves the singleton assertion.

For the last assertion put

The two points are conditionally independent given A, with the identical separate rank filter, so the left side of (15.7) is

This argument asserts an averaged singleton estimate; it does not require a pointwise estimate for each unit. Internal holes have not yet been deleted.□

Proof. Suppose a violating sequence exists. Peel the A law once by Lemma 5.6(a); retain the actual leaf weights and the resulting first effective spaces. After making all restrictions on this law, we will apply part (b) once to restore the required normalized-leaf image bounds without adding pins. The margins between 3000g and D=4000g absorb thinning and fixed normalizations. Throughout, the mixed marginal bounds used in Sections 11 and 13 concern the primal frames.

Preparing the unit and the point pair. Make the following subsequential choice on the A law. If an empty prediction exists on mass at least 10^{-6}, retain it. Here empty means \alpha_1=\alpha_2=1 and the offsets are \gamma_1q,\gamma_2q with fixed bits \gamma_i, modulo errors tending to zero in the reference spaces. Lemma 10.2 exactifies it, after negligible deletion, to

In particular its proof eliminates the multiples of q, using the odd number of star atoms. Fix c=a(\lambda_{A,1})+a(\lambda_{A,2}) and the indicator of \Delta_A=0, losing a factor at most four. If no such empty prediction exists, retain the first law without prediction preparation. Only this specialized empty prediction is tested; arbitrary common predictions need not be excluded.

In the predicted branch with \Delta_A\ne0, apply Lemma 15.3. In the branch with \Delta_A=0, necessarily c=0. Indeed the identities (15.8) give (u_{A,1}+u_{A,2})U_{A,i}=T(\lambda_{A,i},\cdot)+a, since u_{A,i}U_{A,i}=0; if c=1, these profiles and \Delta_A=0 satisfy all hole equations for the unit A, a contradiction. Thus in either predicted branch the independent experiment has fixed positive mass on

In the nonzero case this mass exceeds .49^2 under the normalized retained A law. Before constructing either common model, apply Lemma 5.6(b) to the combined restriction made on A. More explicitly, let w_\lambda be the original first-leaf weights and let q_\lambda be the fraction retained in leaf \lambda by all the A-only restrictions just made. Their total mass q=\sum_\lambda w_\lambda q_\lambda is bounded below by a fixed positive constant. Discard the leaves with q_\lambda<2^{-\zeta N}. They have mass at most 2^{-\zeta N}/q=o(1) in the restricted law; every remaining normalized leaf has the image bound (5.11) and an absolute density 2^{O(N)} relative to \rawlaw^2. The pins and first effective spaces have not changed, and the actual remaining leaf weights are retained. This operation depends only on A, so the two points remain independent conditional on A. On the predicted branch the two-bit compatibility mass is still at least .49^2-o(1).

Now delete internal B holes, costing o(1) by (15.2), and take the single unpinned B leaf from Corollary 5.8. Apply the independent-law version of Lemma 9.5 to these two laws, with failure probability less than .01. On the predicted branch compatibility and injection therefore coexist on mass at least .49^2-.01-o(1)>.22, for large n. On the branch without prediction a passed injecting actual table has mass at least .99. These are subtractions of exceptional mass, and require no independence between the exceptional events and compatibility.

Separate flags for candidate tables. We record this mass in the permitted finite-table format. For each leaf pair enumerate all numerical candidate small tables T, as in Definition 13.1; there are finitely many, with a bound independent of n. A fixed T has separate admissibility flags F_{A,T}(A) and F_{B,T}(B) by Lemma 7.2. In the predicted branch define

The star denotes contraction in the numerical table T, as in (14.9). It is calculated from the entries of T, the recorded tensor coordinates of the C_{A,i} bases, and the bounded coordinate vectors of the marks \lambda_{A,i}. Thus, for a fixed leaf pair and T, H_{A,T} is a flag of A alone. Include the mark coordinates among the finite orientation metadata and replace F_{A,T} by F_{A,T}H_{A,T}. In the branch without prediction set H_{A,T}=1. Injection is a finite matrix-rank test on the candidate table and the leaf metadata.

Each pair counted by the ambient compatibility and injection estimate has at least one passed candidate: take T to be its actual small table. Therefore the union of these permitted candidate-table events has at least the mass just established. We store their entire finite flag vector in the common model. This argument does not impose equality of a candidate table with the actual cross entries between private directions; such an equality would be a joint condition. The actual table is used only to witness the existence of a passed candidate. Nor do we condition the two unit laws on the ambient phase event (15.9). They remain independent laws with the separate flags just described.

Solving the mixed scalar system. Construct the common model for these two different unit laws, retaining the ordered A–B type filter. The dual relations (14.5) become

because C_{B,j}=0. We first show that no relation with some r_i=1 can occur on positive model mass, for any of the permitted bounded exclusions. If it did, Fubini fixes an A array with a positive-mass set of such B arrays. Pigeonhole its finite coefficient and exclusion data and fix a surviving generic label on the A side. At a fixed common signature, the two status distributions are independent. The two expressions in (15.11) must agree almost surely, because a mismatching positive-density pair would be an available generator violating the relation. Two independent bits which agree almost surely are both deterministic. The generic A type has total status density one on every signature space, so its deterministic value gives a fixed common function on all surviving B types. Solving (15.11) for p_{B,j} gives

The strict-error cylinder transfer used in Lemma 15.2 applies, and that lemma rules this out. The finite number of possible dual and exclusion records implies that, almost surely, every remaining dual relation has r_1=r_2=0.

In the branch without an empty prediction, suppose obstructable pairs had probability at least .1. A nonzero weight now has some s_j=1. Generic positivity of the two possible B-role values in (15.11) forces \beta_{ij}=0. The same relation, for both i, is then

It holds on all surviving unary types, by comparison to a fixed generic B type of total density one. These are empty predictions. There are only two choices of j and four offset pairs (\gamma_{1j}q,\gamma_{2j}q); therefore one choice occurs on A mass at least .1/8. The marked profiles and exclusions may still vary with A, as allowed in Definition 10.1; their number is not a further pigeonhole cost. Cylinder transfer with strict error events, as in Lemma 14.3, loses at most a factor two in this mass and supplies a finite empty prediction of mass much larger than 10^{-6}. This is a contradiction. Thus obstructable mass is less than .1, whereas passed injecting tables have mass at least .99. Their intersection with nonobstructable pairs has mass greater than .89. On it Lemma 14.2 solves the scalar system for every such table and every allowed exclusion.

On the predicted branch, substitute (15.8) into (15.11). The full generic base projection forces

For s_j=0 all these coefficients are zero. Fix any passed injecting candidate table T, including the flag H_{A,T}=1. At its local targets the dual evaluation is

by (15.10) and \sum_i a(\lambda_{A,i})=c. This calculation uses the selected candidate’s starred contractions throughout; it does not require that candidate to equal the actual cross table of the sampled pair. Every dual relation vanishes on its target. By Lemma 14.2, the scalar system is soluble on the positive mass having a passed compatible injecting candidate. The reasoning uses only surviving generic labels and hence persists through the further bounded exclusions for fresh lists.

Positive overlap and collision. In either branch we now have the hypothesis of the mixed, filtered Proposition 14.7. Equivalently, Lemma 14.6 supplies at most seven generators per cross edge, with distinct labels at each endpoint and positive status overlap at every matched position. The scalar recipe and gradient realization produce a usable numerical option; the filtered zero-product conclusion of Proposition 13.7 cannot hold on this positive mass. Consequently some option has a positive subsequential expected unnormalized overlap. This positive constant need not be uniform over all possible limit models.

The collision criterion Proposition 8.1 therefore gives four cross holes between A and B with probability

All retained-law normalizations have fixed positive mass and are included in the o(1)N loss. In particular these four holes imply that A conflicts with B_1. Viewed in the original independent experiment, the latter has exactly the probability of a conflict with one point of law \nu. Since

this contradicts the assumed bound below 2^{-100gN} for all sufficiently large indices of the violating sequence. The asserted uniform eventual distribution test follows.□

Proof. The minimum exists by continuity. If p(x)=0<p'(x), the right derivative of entropy along (1-t)p+tp' is -\infty at zero; all terms on the support of p have finite derivative. This contradicts minimality. Differentiating now on the common feasible support gives

Subtracting the two entropies proves the first inequality. If p' is supported on S, then

Relative entropy is nonnegative: apply \log t\le t-1 with t=q(x)/p'(x) and sum on the positive support of p'. This proves the second inequality as well.□

Proof. The compact convex sets C=\operatorname{conv}\{v_r:r\in\mathcal R\} and B=\prod_{j=1}^d[0,c_j] are disjoint. Choose a closest pair z\in C,b\in B, and put u=z-b\ne0. For fixed z, the nearest point of B is its coordinatewise truncation, so b_j=\min(z_j,c_j), u\ge0, and u\cdot b=u\cdot c. For every v\in C, comparison with (1-t)z+tv at t=0 gives u\cdot(v-z)\ge0. Consequently

Take w=u/(u\cdot z). This proves both assertions using only minimization on compact subsets of a Euclidean space.□

Proof. The assertion is immediate for empty R. Otherwise introduce separate resources for each left vertex, right vertex, ordered pair, and colour, with capacities

respectively. An object (x,y,c) uses one unit of each of its four resources. Apply Lemma 16.2. Write the resulting prices as \ell_x,r_y,e_{xy},d_c; their capacity-weighted sum is less than one, and \ell_x+r_y+e_{xy}+d_c\ge1 on R. Take all resources of price at least 1/4. They cover R. Let S be the union of the high-price left and right vertex sets. In fact

The corresponding pair and colour inequalities are \pi^2(E)<4/Q_N and |C|<4/\eta_{\mathrm{col}}. This uses the capacity on the pair projection, so all colours of one pair share a single pair resource.□

Proof. Make a directed network from a source to a left copy of \Omega, then to a right copy, then to a sink. The source and sink arcs have capacities L\pi(x) and L\pi(y). The middle arc x\to y, present for (x,y)\in R, has capacity Q_N\pi(x)\pi(y). A flow of value one is exactly a feasible unit law, and a larger flow can be scaled to value one.

A maximum flow exists by compactness. Its value is less than one. In its residual network there is no source-to-sink path, since augmenting by the smallest residual capacity on such a path would increase the value. Let Z be the vertices reachable from the source. Every original arc leaving Z is saturated; every original arc entering Z carries zero flow. Summing flow conservation over Z therefore shows that its cut capacity is the maximum flow value, hence is less than one.

Let A be the left types outside Z, and B the right types inside Z. The cut inequality reads

Take S=A\cup B and take E to be the pair set in the last summand. This proves the cover and both bounds. For the point assertion, a law of total mass one on T bounded by L\pi exists exactly when L\pi(T)\ge1: necessity follows by summing, and sufficiency follows by normalizing \pi|_T.□

Proof. Start with the entire relevant graph as residual set. On a nonempty feasible region choose the entropy minimizer, breaking all choices deterministically. For coloured units the reference probability is \pi^2 times the uniform law on [q]. The projected pair cap gives density at most qQ_N against this reference. The minimum entropy is therefore in [0,\log(qQ_N)]. By Theorem 5.4(i), the average minimizer mass of a residual neighbourhood is at least \epsilon_N. Select a vertex of maximal neighbourhood mass. If it belongs to the independent set being contained, record it and delete its neighbours. Otherwise delete only that vertex. These operations preserve containment of the target independent set.

For the bipartite problem, choose separate entropy minimizers on the two residual sides, against \pi^2 and \pi. Their sum lies in [0,\log Q_N+\log L]. By Theorem 5.4(ii), some vertex on either side has opposite minimizer neighbourhood mass at least \epsilon_N. Choose deterministically a vertex of maximal such mass, including its side in the choice. If it belongs to the corresponding target set, record it and delete its neighbours on the opposite side; otherwise delete only the chosen vertex. The absence of edges between I and J preserves both containments.

In either procedure every step removes a vertex: a recorded vertex has a nonempty neighbourhood. Stop when feasibility fails (on either side in the bipartite case). Deleting vertices can only increase each minimum entropy. If a recording leaves the relevant feasible region nonempty, Lemma 16.1 increases its minimum by at least -\log(1-\epsilon_N)\ge\epsilon_N. Consequently the number of recordings is at most

The extra one permits a last recording that destroys feasibility.

After recording a vertex, its residual neighbourhood is empty forever. Since a selected vertex always has positive neighbourhood mass, it cannot be selected again. The set of recorded vertices, with side information in the bipartite case, thus determines the entire procedure: replay its deterministic choices, performing a recording exactly when the selected vertex is in that set, and otherwise deleting it. In particular it determines the terminal. The total number of available vertices has logarithm O(N^2). Bounding the number of fingerprints of length at most (16.5) by the corresponding power of one plus that number proves (16.4).□