Proof. Take the constructed examples in Theorem 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 \[-[x,z]=-[x_\perp,z]\ge\sqrt{1+q},\] with equality at \(z=y\). This proves (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 \[S_i^{\mathsf T}S_i=I+t_i^{\mathsf T}t_i, \qquad \|S_i\|_{\mathrm{op}}\le\cosh R.\] 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 (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 \[q_{ij}=\frac{|u_i-u_j|}{2},\qquad a_{ij}=\min\{r_i,r_j,-\log q_{ij}\},\] with \(-\log0=+\infty\), and set \(a_{ii}=r_i\). The exact identity \[ \cosh d_{\mathbb H}(z_i,z_j) =\cosh(r_i-r_j)+2\sinh r_i\sinh r_j\,q_{ij}^2 \tag{5}\] implies \[ \left|d_{\mathbb H}(z_i,z_j)-(r_i+r_j-2a_{ij})\right|\le4. \tag{6}\] 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 \[D=\max\{|r_i-r_j|,\ r_i+r_j+2\log q_{ij}\} =r_i+r_j-2a_{ij},\] the two terms in (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 \[ a_{ij}\le A_{ij} \le a_{ij}+\log\bigl(\max\{1,\ell-1\}\bigr),\qquad A_{ij}\le\min(r_i,r_j). \tag{7}\] 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 (6)–(7) prove (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 \[ d_T(p,q)=\max_{e\in\{a,b\},\ f\in\{c,d\}} \{d_T(e,f)-d_T(e,p)-d_T(f,q)\}. \tag{9}\] 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 \[ d(X,P_\theta)=\max\{d(A,X)-\theta d(A,B),\, d(B,X)-(1-\theta)d(A,B)\}. \tag{10}\] 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 6 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 (10), each corresponding difference is therefore at most \(2K'\). Thus \[d_{T'}(p',\widetilde p)\le2K',\qquad d_{T'}(q',\widetilde q)\le2K'.\] Together with the \(K'\) distance error for the pair \(\widehat p,\widehat q\), this gives \[|d_{\mathbb H}(\widehat p,\widehat q) -d_{T'}(\widetilde p,\widetilde q)|\le5K'.\] 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 (9) therefore changes by at most \(6K'\), and hence \[|d_T(p,q)-d_{T'}(\widetilde p,\widetilde q)|\le6K'.\] 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 6 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 \[R=\frac{D+1+K(\ell)}2,\qquad U_{i,s}=\{x\in K_s:d_T(x,H_{i,s})\le R\}.\] 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 7 gives \[ d_{\mathbb H}(z_i,z_j)\le 2R+11K(\ell+2)=:R_*. \tag{11}\] For any nonempty bag, fix one of these lifts. It has distance at most \(R_*\) from every flat in the bag. By 5, 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 (11) proves the uniform bag assertion. The final assertion follows from 5 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 [mt:property-colour] 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 [mt:property-hole]. 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 [mt:property-hole]. 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 \[\frac m4<W'\le 2k+\frac{k}{Q}\frac{am}{10} \le\frac{11}{5}k.\] 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 [mt:property-colour]. ◻

Proof. Let \(r\) be the vertex bag from 10, let \(z\) be the edge bag from 11, 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 \[A_- =\{v\in A:y\notin S_v\},\qquad \mathcal E_+=\{e:z\in S_e,\ x\notin S_e\}.\] 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 2.

If the bag weight at \(x\) were less than \(cm/2\), then \(\sum_{e\in\mathcal E_+}w_e>cm/2\). By 9, \(\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 [mt:property-point]. 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 \[ D^{-1/2}=c^{-1/2}\sum_{k=0}^{\infty} \frac{\binom{2k}{k}}{4^k}A^k. \tag{15}\] 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 94, 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 \(\mathop{\mathrm{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 (16) 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 \[\int_{x\ne1}(1+x)\,d\nu(x)=\theta-2r \le1-\theta\le\delta.\] 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 \[\lim_j\frac{\|B_j^2-I\|_{\mathrm F}^2}{v_j} =\int(1-x^2)^2\,d\nu(x)\le2\delta.\] 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 \[d_i=\sum_jB_{ij}^2, \qquad r_i=d_i^2-\sum_j B_{ij}^4\ge0.\] The diagonal entries of \(B^2-I\) show that \(\sum_i(d_i-1)^2\le\varepsilon v\). Nonnegativity also gives \[\begin{align*} \sum_i r_i &=\sum_{j\ne k}\sum_iB_{ij}^2B_{ik}^2\\ &\le\sum_{j\ne k}\left(\sum_iB_{ij}B_{ik}\right)^2 \le\varepsilon v. \end{align*}\] 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 \[a_i\ge\frac{\sum_jB_{ij}^4}{d_i} =d_i-r_i/d_i, \qquad d_i-a_i\le\frac{\tau^2}{1-\tau}.\] Because \(\tau\le1/8\), it follows that \[a_i\ge\frac{1-2\tau}{1-\tau}\ge\frac67, \qquad d_i-a_i\le\frac87\tau^2, \qquad |\sqrt{a_i}-1|\le\tau.\] 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 \[ \sum_{i\in S}d_i \le |S|+\sqrt{|S|\varepsilon v}. \tag{20}\] 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 \[\left(2+\frac76(2+\sqrt2\tau)\right)\tau^2v \le5\tau^2v.\] 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 (20), 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 \[P_j=\begin{pmatrix}A_j&C_j\\ C_j^{\mathsf T}&D_j\end{pmatrix}.\] 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\), \[\|C_jE_{\mathrm{lo}}\|_{\mathrm F}^2 \le(2+\varepsilon)\mathop{\mathrm{Tr}}A_j.\] On the other spectral subspace, \(\|C_jE_{\mathrm{hi}}\|_{\mathrm F}^2\le K^2 \mathop{\mathrm{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 14. Use the constant \(c=c(a)>0\) from 11; explicitly we may take \[ \begin{aligned} K(a)&=\left\lceil\frac5a\right\rceil \left(\left\lceil\log_2\frac5a\right\rceil+1\right), &c(a)&=\frac1{40K(a)},\\ \delta_0(a)&=\min\left\{\frac1{3\cdot8^4},\frac{c(a)}{12}, \frac13\left(\frac{c(a)}{2340}\right)^4\right\}, &\beta_0(a)&=\frac{\delta_0(a)}{10},\\ m_0(a)&=\left\lceil\max\left\{\frac2a, \frac{10}{\delta_0(a)},2\right\} \right\rceil. \end{aligned} \tag{22}\] Fix \(a,\beta,m,G\) as in the theorem with these choices, and put \[ q=\lceil\beta m\rceil, \qquad\delta=5(\beta+1/m), \qquad\tau=(3\delta)^{1/4}. \tag{23}\] These choices imply \[ \delta\le\delta_0, \qquad\tau\le\frac18, \qquad\tau\le\frac{c}{2340}, \qquad\frac qm\le\frac{\delta}{5}\le\frac c{60}, \qquad am\ge2. \tag{24}\]

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\), \[ \mathop{\mathrm{rank}}M_s\le v/2+1. \tag{25}\] 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; 15 shows that deleting at most one coordinate makes each positive definite. Work with \(s\ge2\), and apply 8 to their positive spans. For every hole between two labels the blocks are orthogonal, so their tree subtrees intersect. By 10, 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 \[ d_s\ge(m-5q)(s-1), \qquad \liminf_{s\to\infty}\frac{d_s}{v}\ge1-\delta. \tag{26}\] 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 15, 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 \[ A_s=I-B_s, \qquad B_s\ge0\ \text{entrywise}, \qquad (B_s)_{uu}=0\ \text{as a whole diagonal block}. \tag{27}\] The bag bound from [mt:finite-tree,mt:flat-normalization] 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 16 gives \[\limsup_{s\to\infty}\frac{\|B_s^2-I\|_{\mathrm F}^2}{v} \le2\delta.\] 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 17 to obtain a coordinate matching with \(p_s^0\) pairs and adjacency matrix \(W_s\). Then \[ \begin{split} \liminf_s\frac{p_s^0}{v} &\ge\frac12-\frac\delta2-\frac52\tau^2,\\ \|B_s-W_s\|_{\mathrm F}^2&\le8\tau^2v, \qquad |(B_s)_{ij}-1|\le\tau \quad\text{on retained pairs}. \end{split} \tag{28}\] 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 \[ w_e=\lim_s k_e(s)/s, \qquad \sum_{e\ni u}w_e\le1, \qquad \sum_e w_e\le m/2. \tag{29}\] 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 (29) therefore gives \[ \sum_{e:\,\text{group has a negative eigenvalue}}w_e \le2k<m/10. \tag{30}\] 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 \[\begin{pmatrix}I&-C\\-C^{\mathsf T}&I\end{pmatrix}, \qquad C\ \text{entrywise strictly positive}.\] The graph of negative entries is connected. If the group is singular, delete one whole matching pair. By 15 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 (28), (30) and \(\tau\le1/8\), the total candidate weight satisfies \[ \sum_{e\text{ candidate}}w_e \ge m\left(\frac25-\frac\delta2-\frac52\tau^2\right) >\frac{3m}{10}. \tag{31}\]

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 [eq:hole-equations].

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}\): \[u_j(U_ix_{ik})=a(x_{ik})+T(x_{ij},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 \[\sum_{\{i,j\}}\bigl(a(x_{ij})+a(x_{ji})\bigr)=1+1+1=1,\] a contradiction. ◻

Proof. Write \(\Phi=B^{\mathsf T}:V\to W^*\) and \(\Phi'=(B')^{\mathsf T}: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 22, 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^{\mathsf T}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}(\mathop{\mathrm{im}}[P,X])\), of dimension \(N-d-h\). For a nonzero coefficient vector \(c\in\mathbb F_2^{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^{\mathsf T}\), the allowed \(Y\)-columns in \(\ker P^{\mathsf T}\), 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 \(\mathop{\mathrm{GL}}(\mathbb F_2^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 \(\mathbb F_2^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 [eq:channel-transpose-failure]. To compare their joint marginal with completely independent columns, condition on \(G=X^{\mathsf T}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 \(\mathbb F_2^{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 \[2^{-(N-2(d+h))t_-}.\] 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^{|\mathcal E|}\), and the resulting bound is \[4^{|\mathcal E|}\,2^{-t_+N-(N-2(d+h))t_-}.\] 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 [eq:reference-image-cap] 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{\Cref{eq:channel-allowed}})\), a random variable in the random subsets. Channel injectivity makes the \(q_h\) nonzero values in each component and sign distinct. Consequently \[\mathbb E_A Z_f=p^{k_h}.\] 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{\Cref{eq:channel-allowed}})\) similarly has expectation \(p^{k_h}\nu_f(T)\).

We establish simultaneous concentration of these fractions by the bounded-differences method (Azuma 1967; McDiarmid 1989), with the needed exponential-moment estimate included below. By 23(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 \[c_N=C_h2^{-N+d},\] 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 \[S_N=C_{g,h}2^{-N+2d}.\] 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 \[\Pr_A(|Z-\mathbb E_AZ|>u)\le2\exp(-2u^2/S_N).\] 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 [eq:channel-translate]. 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 \[\mathbb E_AZ_{f,v}^{+,e} \le p^{k_h}\bigl(C_h2^{-N+d}+q_hp\bigr).\] 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 \[Z_f=p^{k_h}(1+O(\epsilon_N/p^{k_h}))>0\] uniformly, and the relative error tends to zero exponentially. The pointwise density of \(\pi\) with respect to \({\mathsf P_0}\) is the survival indicator divided by \(Z_f\). Consequently \[\frac{d\pi^2}{d{\mathsf P_0}^2} \le4p^{-2k_h}\le2^{\varepsilon_{\rm ch}N}\] 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 [eq:channel-transpose-failure] 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 \[C_h2^{-N+d}+q_h2^{-\rho N} +O(\epsilon_N/p^{k_h})\le2^{-\rho N/2}\] 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, [eq:reference-image-cap] bounds the probability of their zero images by \(2^{-(1-\epsilon)2DN}\) under \({\mathsf P_0}^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, \[\mathop{\mathrm{rank}}(\lambda_{i,e})=\mathop{\mathrm{rank}}(\xi_e) \le\dim(\mathop{\mathrm{im}}P_{1,e}\cap\mathop{\mathrm{im}}P_{2,e}).\] 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 \[\#\{\text{unequal pairs}\} =\frac12\left(g^2-\sum_vc_v^2\right) \ge\frac12\left(g^2-\frac g2\sum_vc_v\right) =\frac{g^2}{4}>2D,\] 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 19, 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 [eq:E-moments], \[\mathop{\mathrm{Tr}}(P_{i,e}\lambda_{i,e}Q_{i,e}^{\mathsf T}) =\langle P_{i,e}^{\mathsf T}Q_{i,e},\lambda_{i,e}\rangle =\eta(\lambda_{i,e}).\] For \(e=\{l,l'\}\), it follows that \[\eta(w_{1,l})+\eta(w_{2,l}) =\eta(w_{1,l'})+\eta(w_{2,l'}).\] 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 \({\mathsf P_0}^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 [eq:leaf-minentropy] 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 \[2^{-\zeta N-(1-\zeta)uN}.\] The cumulative directions are independent after taking a basis, so the absolute density cap and [eq:reference-image-cap] give the upper bound \[2^{DN-(1-\epsilon)uN}.\] Comparing the bounds yields \[ (\zeta-\epsilon)u<D+\zeta. \tag{74}\] 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, \[\sigma_\lambda\le 2^{(D+K_1+1)N}{\mathsf P_0}^2.\] 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 \[q^{-1}\sum_{\lambda:q_\lambda<2^{-\zeta N}} w_\lambda q_\lambda \le 2^{-\zeta N+o(N)}.\] On every other leaf, division by \(q_\lambda\) multiplies probabilities by at most \(2^{\zeta N}\). For \(t\ge1\), \[2^{\zeta N}2^{-(1-\zeta)tN} \le2^{-(1-2\zeta)tN}.\] 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}{\mathsf P_0}^2\), which is below \(2^{DN}{\mathsf P_0}^2\). The intersection exception and the residual mass in 27(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 27(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 [eq:hole-equations]. 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, [eq:reference-image-cap] and [eq:thinning-density] bound its probability by \[L^2 2^{\varepsilon_{\rm ch}N-(1-\epsilon)tN}.\] 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\mathbb F_2^d\), \[(HH^{\mathsf T})_{xx'}=\sum_y(-1)^{(x+x')\cdot y} =\begin{cases}2^d,&x=x',\\0,&x\ne x'.\end{cases}\] 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 \[|a^{\mathsf T}Hb|\le2^{d/2}\|a\|_2\|b\|_2,\qquad \|a\|_2^2\le p_1\sum_x\alpha(x)\le p_1,\] 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_{\mathop{\mathrm{rank}}C},0)\); the tensor matrix then has rank \(N\mathop{\mathrm{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 \(i\)th unit vector. The third is the sum of the point matrices at zero, at the \(i\)th and \(j\)th 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 \[ r_j=r_{j+1}=r_{j+2}. \tag{77}\] 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 (77) 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\), \[B(s_a f,g)=B(f,s_a g)=0,\] 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 \[B(M_aM_b[f],[g])=\Lambda(s_as_bfg).\] 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 \(\mathbb F_2\) have a simultaneous eigenspace splitting \[Q=\bigoplus_{s\in L}Q_s, \qquad M_a|_{Q_s}=s_a I.\] 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 \(\mathop{\mathrm{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 (76) 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 \[B(z_i e_s,z_i e_s) =\Lambda(z_i e_s^2) =B(e_s,z_i e_s),\] which is \((Z_s)_{ii}=(Z_s)_{0i}\). The interpolation degrees are within \(j\).

Extend the right side of (76) to the full row and column indexing. Its rank is at most \(\sum_s\dim Q_s\le R_*\). By 31 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 31 and (75). 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^{\mathsf T}\), 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^{\mathsf T}\). The projection \(ZL\) fixes \(x\) on the left and, by symmetry, on the right; hence \(ZHZ^{\mathsf T}=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)^{|\mathcal E|}\) such rank tuples. Therefore the number of profiles under consideration satisfies \[ \#\{x\in\mathcal X:\textstyle\sum_e\mathop{\mathrm{rank}}x_e\le K\}\le2^{An} \tag{83}\] 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^{\mathsf T}\), with \(r_e=\mathop{\mathrm{rank}}x_e\). For a tag-\(l\) atom the contribution from a single indexed matrix uses the forward forms \(Z_e^{\mathsf T}L v\) when \(l\in f\), and the reverse forms \(v^{\mathsf T}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 \[m_0=4J(g-1)K.\] 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^{\mathsf T}L\) and \(LZ_f\) imposes at most \(r_er_f\) compatibility bits, namely their common \(Z_e^{\mathsf T}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 \[2^{2JK^2+(s_0+1)m_0}\,2^{-(s_0+1)n}.\] 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 [item:mixer-unary]. 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 [item:mixer-binary], 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 \[A_{s,s'}=\sum_{a=1}^b(s_a+s'_a)M_a,\] which is uniform because \(s\ne s'\). The reverse gives \(A_{s,s'}^{\mathsf T}\), 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|\mathcal E|^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\mathcal B)=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 33. 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 (86), the self-pairing requirements hold because \(T(v,v)=a(v)\). Mutual consistency is \[p_z(v_{zi})+p_{z'}(v_{z'i}) =a(v_{iz})+a(v_{iz'}).\] 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 (85). 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 35. This argument specifies the bits; their occurrence in parameter tests will be supplied by 61. 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 (85) 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.

Proof. First note where thinning enters the hypotheses. By 24, with \(\varepsilon_{\rm ch}=10|\mathcal E|2^h\rho\), the projected unit laws satisfy \[\sigma_O\le 2^{3000gN}\pi^{\otimes2} \le 2^{(3000g+\varepsilon_{\rm ch})N} {\mathsf P_0}^{\otimes2}.\] 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 \({\mathsf P_0}\); 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.

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 \[C(a,u)+C'(a',u')=0\] has \(a=a'\), by its constant coordinate. Its \(Z\)-part is \[a(z_0+z_0')+L_Zu+L'_Zu'=0.\] 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 23 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(\mathop{\mathrm{rank}}A+\mathop{\mathrm{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. 30 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 26, 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 \[T_0=\{t:\eta_S(w_t^{(i)})=1\}, \qquad |T_0|\le4D/g,\] 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}_*{\mathsf P_0}\) 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 \[a(\lambda_i)+b_t(\lambda_i)+\alpha_i =\chi_*(w^{(i)})+\eta_S(w_t^{(i)})+\alpha_i=1\] on the retained \(t\)’s. Hence [eq:prediction] gives \[ f_i(l,q,\operatorname{key}(x))+q =p_i(x)+T^1(\lambda_i,x) \tag{128}\] with uniform \(o(1)\) parameter error.

The right side of [eq:pure-prediction] is a sum of at most \[ s_1=(g-1)(h+2JK_1) \tag{129}\] 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 \[ \frac{g-1}{2}(g-4D/g)r_0>2s_1+1 \tag{130}\] 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\mathbb F_2^{m_1}\) and \[q_*=\sum_{j=1}^{m_1}\xi_j\upsilon_j.\] 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 \[\langle \text{plus}(1,\xi,\upsilon),\text{minus}(1,\xi',\upsilon')\rangle =\sum_j\xi_j\upsilon'_j.\] 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 \(\mathcal X\). Summing [eq:prediction] therefore gives \[\sum_l f_i(l,q,\operatorname{key}_l)=0\] 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 48 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}_*{\mathsf P_0}\), 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, \[ \sum_l f_i(l,q_*,\operatorname{key}_l)=0 \quad\text{at every synthetic point}. \tag{131}\]

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 [eq:synthetic-tester-room] 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 [eq:pure-prediction] 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

the array of values of the common function \(f_i+q_*\) on this specified slice admits such an affine-product representation.

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. 48 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 [eq:synthetic-parity] 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 \[F_l(\xi,\upsilon) =f_i(l,q_*,\operatorname{key}_l)+q_*.\] For each tag define its Boolean cross-coefficient matrix by \[C_l[j,k]=F_l(e_j,e_k)+F_l(e_j,0) +F_l(0,e_k)+F_l(0,0).\] 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 \(\mathop{\mathrm{rank}}C_l\le2s_1\). On the other hand [eq:synthetic-parity], together with odd \(g\), gives \(\sum_lF_l=q_*\) and hence \[\sum_l C_l=I_{m_1}.\] Rank subadditivity would imply \(m_1\le\sum_l\mathop{\mathrm{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 45 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 47. All subsequent restrictions then preserve the exact identities [eq:exact-prediction].

Suppose \(\Delta=0\). By 49, \(\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 [eq:phase-compatibility] is zero. With two equal active statuses it is also zero, because \(2d=0\) over \(\mathbb F_2\). 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 [eq:exact-prediction] 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 43 to the pooled marked law. It retains at least the early fraction \(\delta_{\mathrm{ph}}\), and gives either full mixing or the identity \[F(A,B)=u_{B,\{1,2\}}(\Delta_A)=0 \quad\text{for every two retained units }A,B,\] together with exponentially small singleton character means. For clarity, write the four phase bits as \[X_j=u_{B,j}(\Delta_A),\qquad Y_i=u_{A,i}(\Delta_B),\qquad i,j\in\{1,2\}.\] 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 \[\frac{1-15(.005)}{16}>\frac1{32}.\] Each condition in [eq:phase-compatibility] 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 \[\begin{align*} \mathbb P\{X_1=X_2=Y_1=Y_2=c\} &=\frac14\left(1+(-1)^c\mathbb E(-1)^X +(-1)^c\mathbb E(-1)^Y+\mathbb E(-1)^{X+Y}\right)\\ &=\frac14+o(1)>\frac1{32}. \end{align*}\] 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 44.

Apply the unconditional form of 45 to this retained law, with failure below \(1/128\). The probability of a compatible injecting actual table is then at least \[\frac1{32}-\frac1{128}-o(1)>\frac1{64}.\] 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 \[\sum_{\lambda:q_\lambda<2^{-\zeta N}} w_\lambda q_\lambda\le 2^{-\zeta N}.\] On each remaining leaf, division by \(q_\lambda\) weakens [eq:leaf-minentropy] to \[2^{\zeta N}2^{-(1-\zeta)tN} \le 2^{-(1-2\zeta)tN}\qquad(t\ge1),\] as required. Its joint density gains at most \(2^{\zeta N}\) and remains \(2^{O(N)}{\mathsf P_0}^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 [eq:preparation-early-margins]. 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 [eq:thinning-density]. 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 \[\sum_\gamma p_\gamma^2\le \eta_{\mathrm{col}}\sum_\gamma p_\gamma=\eta_{\mathrm{col}}.\] 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 23, 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. 30 bounds this character by a constant times \(\lVert F\rVert_\infty\lVert G\rVert_\infty2^{-N/2}\). There are only boundedly many characters. Applying the same expansion with \(F=G=1\) controls the normalization, while 53 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. 30 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 53. In the nonnegative numerator, drop injectivity and the within-draw conditions, and expand only the cross-draw conditions. It remains to bound \[2^{O(\ell)}\sum_{\chi} \lvert \mathbb E_{\omega_n^{\otimes\ell}} \chi\prod_{j=1}^{\ell}\mathbf 1_{A_j}\rvert,\] 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 \[ \lvert \mathbb E\chi\prod_j\mathbf 1_{A_j}\rvert \le 2^{-tN/2}\prod_{j\notin I\cup J}w_j \le 2^{-tN/2}w_{\min}^{-2t}\prod_jw_j, \tag{136}\] 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 \[\sum_{t\ge1} 2^{Ck^2\ell t-tN/2+2t\log_2(1/w_{\min})}.\] 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 (135) 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 56 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 \[\frac{\ell!}{\prod_C(\ell v_C)!}\prod_Cw_C^{\ell v_C} \le 2^{-\ell D_2(v\Vert w)}.\] 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 (135) for each cell sequence of a type, and then pay (138). We obtain \[\begin{align*} &(1-o(1))\nu_L\{D_2(H_O\Vert w)>T+1\}\\ &\hspace{1cm}\le 2^{C_LM_0n+(c_2-T)\ell+r\log_2(\ell+1)}. \tag{139}\end{align*}\] 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 \[ \limsup_{n\to\infty}\mathbb E_{O\sim\nu_L}D_2(H_O\Vert w)\le C_H \tag{140}\] 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_{\mathcal P}(K)\) denote the cell of \(\mathcal P\) 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 \[\mathbb ED_2(p_{O,V}\Vert w) =\mathbb ED_2(H_O\Vert w)+I(C_{\mathcal P}(K);V\mid O) \le\mathbb ED_2(H_O\Vert w)+F.\] Indeed, split each logarithm \(\log_2(p_{O,V}(C)/w_C)\) through \(H_O(C)\). The first term averages to \(I(C_{\mathcal P}(K);V\mid O)\); the second averages to \(\mathbb ED_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 (140) 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 \[D_2((p,1-p)\Vert(\delta,1-\delta)) \ge p\log_2(1/\delta)-1.\] Taking expectations and limits in (140) 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 \(\mathcal P\), write \(\Pi_{\mathcal P}d\) for its conditional-average density relative to \(\omega_n\). If some filtered density \(d\) satisfies \(\lVert d-\Pi_{\mathcal P}d\rVert_1>\varepsilon\), split every cell by the set where \(d-\Pi_{\mathcal P}d\) is positive. On the refined partition the filtered cell masses differ in \(\ell^1\) by more than \(\varepsilon\) 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 \(\varepsilon\).

For any refinement, the relative entropy chain rule and (137) give \[\begin{align*} &\mathbb ED_2(p_{\mathrm{child}}\Vert w_{\mathrm{child}}) -\mathbb ED_2(p_{\mathrm{parent}}\Vert w_{\mathrm{parent}})\\ &\quad\ge \frac12 \left(\mathbb E\lVert p_{\mathrm{child}}- \operatorname{split}_{w}(p_{\mathrm{parent}})\rVert_1\right)^2. \tag{141}\end{align*}\] 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 \(\varepsilon/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 (140) 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 [eq:histogram-refinement-gain] telescopes. That identity forces the final entropy to be at least \(d\varepsilon^2/8\), a contradiction for large fixed \(d\).

Apply the preceding argument with \(\varepsilon/2\). On a partition of bounded size \(r_0'\) that approximates every family member, quantize each cell mass downwards in increments \(\varepsilon/(2r_0')\). The \(L^1\) error in the piecewise-constant density is the sum of the cell-mass errors, at most \(\varepsilon/2\). There are at most \((1+2r_0'/\varepsilon)^{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(\mathcal K_n)d\) on \(\mathcal K_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 (142). 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, 54 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 \[ \mathop{\mathrm{Var}}_{O\sim{\mathsf P_0}}\bigl(\mathbb E_zF_n(z,K(O,z))\bigr) \le C_1 2^{-c_1'n}. \tag{143}\] 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 \[h_o(D_2)=\mathbb E_{z_1}F_n(z_1,K_1(o,z_1),D_2),\qquad \bar h(D_2)=\mathbb E_{o\sim{\mathsf P_0}}h_o(D_2).\] Fix a small constant \(\eta>0\). By (143), uniformly in \(D_2\), \(\mathbb P_{{\mathsf P_0}^{\mathrm{pr}}}\{\lvert h_o(D_2)-\bar h(D_2)\rvert>\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 \[B_o=\{D_2:\lvert h_o(D_2)-\bar h(D_2)\rvert>\eta\}\] is at most \(2^{-c n}\) for some \(c>0\). The projected marginal cap in (142) 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 \[\eta-O(2^{-n+O(\ell')})\ge\eta/2.\] 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 53 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 \[2^{C_2(\ell')^2}\mathbb P(D_2\in B_o)^{\ell'} \le2^{C_2(\ell')^2-cn\ell'}.\] 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 \(({\mathsf P_0}^{\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, \[\lvert \mathbb E_{z_2}h_o(D_2)-\mathbb E_{z_2}\bar h(D_2)\rvert\le3\eta.\] 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<\varepsilon\) 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 35 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\mathcal B+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 (142) 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. 30 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 (144). 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 \[\lvert \mathbb E_x(-1)^{Q(x)}\rvert^2 =\mathbb E_h(-1)^{Q(h)+Q(0)}\mathbf 1_{\{B(h,\cdot)=0\}},\] 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 23. The first conclusion therefore follows from the one-endpoint part of 59, also after conditioning on a feasible summary.

Fix a nonzero profile \(x\in\mathcal X\) of total component rank at most \(K\), and consider the sign \[s_x(z)=(-1)^{T(x,\operatorname{atom}(z))}.\] By the first property of 35, 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 \[\gamma=2^{-K^2-3},\qquad b_*=2^{-J+2s_0}<\gamma.\] The strict inequality follows from the chosen lower bound on \(J\).

Apply a uniform \(G\in\mathop{\mathrm{GL}}_n(\mathbb F_2)\) 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 \({\mathsf P_0}^{\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'=\mathbb P(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 \[m_j=\mathbb E(s_j\mid\mathcal F_{j-1}),\qquad D_j=s_j-m_j.\] 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 62, \[\lvert m_j\rvert\le b_*\] pointwise, including after the non-\(Z\) inputs are fixed. The \(D_j\) are martingale differences with second moments at most one, so \(\lVert u^{-1}\sum_jD_j\rVert_2\le u^{-1/2}\). On the other hand every selected sign has conditional mean greater than \(\gamma\) on \(E_0\). Consequently \[ (\gamma-b_*)\delta' \le \lvert \mathbb E\mathbf 1_{E_0}\,u^{-1}\sum_jD_j\rvert \le\sqrt{\delta'/u}. \tag{147}\] 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 (147). 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 35. 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 (142). 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 \[\mathbb P(\text{assignment}\mid E_0,\text{summary}) \ge2^{-d_i}\bigl(1-(2^{d_i}-1)\gamma\bigr) \ge(7/8)2^{-d_i}.\] 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 (146), 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. We may truncate net representatives to \([0,R]\). Since \(\lVert f-g\rVert_2^2\le R\lVert f-g\rVert_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)\) \[C_A=\mathbb E_L\sum_{a=1}^m f_{L,a}\otimes f_{L,a},\qquad C_B=\mathbb E_{L'}\sum_{b=1}^m g_{L',b}\otimes g_{L',b}.\] Here \((f\otimes f)v=f\langle f,v\rangle\). 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, \[|e(x)| \le\lambda^{-1}\mathbb E_L\sum_a |f_{L,a}(x)|\, |\langle f_{L,a},e\rangle| \le T/\lambda\le T/\delta.\] Quantize these finitely many bounded eigenfunctions with a common finite partition. Its conditional expectation \(P\) can be made to satisfy \(\lVert (1-P)e\rVert_2\le\varepsilon\) for every one of them. With \(Q=1-P\), the spectral decomposition gives \[\lVert Q C_A Q\rVert_{\mathrm{op}} \le\delta+T\varepsilon^2.\] 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 \[\begin{align*} \mathbb E_{L,L'}\sum_{a,b} \bigl|\langle f_{L,a},g_{L',b}\rangle- \langle P'f_{L,a},P'g_{L',b}\rangle\bigr|^2 &=\mathop{\mathrm{Tr}}(Q'C_AQ'C_B)\\ &\le(\delta+T\varepsilon^2)T. \end{align*}\] 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 (162), 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 \(\mathcal K_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 72. For every tuple cylinder test and successively improving accuracy, include all unary indicator factors needed in 65; 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 65 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, 59 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 (163). Versions jointly measurable in \((\theta,\xi)\) are obtained by taking the limits of their conditional density averages on increasing finite cylinder partitions, as in 95. 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 63 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 55, 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 57 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, \[0\le\eta(Z)(\Upsilon)-\eta_R(Z)(\Upsilon)\le\varepsilon_R \quad\text{almost surely}.\] 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 (160). Choose a global partition with projection error at most \(\varepsilon\) in 72. For that finite partition the inner product of the projected densities is \[\sum_{C:\,\nu_n(C)>0} \frac{\eta_{A,R,n}(C)\eta_{B,R,n}(C)}{\nu_n(C)}.\] 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 72 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 \[\mathbb E_Z J(Z)U_\omega(Z) \int \frac{d\eta_{A,R}}{d\rho} \frac{d\eta_{B,R}}{d\rho}\,d\rho=0.\] 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 73. We prove equality against every tuple cylinder indicator \(W\).

At a fixed accuracy \(\varepsilon\), apply 65 to its prelimit global key test \(W_n\). On the reference key space its structured approximation has the form \[W_n^{(\varepsilon)}(k) =\sum_{a=1}^{m_\varepsilon} c_{a,n} \prod_{\ell}\phi_{a,\ell,n}(k_\ell),\] 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 59. An opposite-leaf-dependent choice of the flag cannot increase that unconditional error.

Apply 61 to each structured term. Again its unary weights are the status indicators times bounded global unary factors. The resulting expression is \[ \kappa\int\sum_a c_{a,n} \prod_\ell\left( \int\phi_{a,\ell,n}\,d\eta^{\theta_n}_{t_\ell,\upsilon_\ell,n} \right)d\alpha_{Z_n}(\theta_n), \tag{165}\] 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 (165) 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 65 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 \[\begin{align*} \int W^{(\varepsilon)}(u)G_Z(u)\,d\rho(u) &=\kappa\int\sum_a c_a \prod_\ell\left( \int\phi_{a,\ell}(\xi) h^\theta_{t_\ell,\upsilon_\ell}(\xi)\,dm_{l_\ell,q_\ell}(\xi) \right)d\alpha_Z(\theta). \end{align*}\] This is exactly the limit of (165). 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 \[\mathbb E_Z\left|\eta(Z)(W)-\int W G_Z\,d\rho\right|=0.\] There are countably many cylinder indicators. Equality on all of them determines the measures and proves the lemma. ◻

Proof. For a usable option, [lem:limit-zero-product,lem:limit-density] 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 \[\kappa_A\kappa_B \int\!\int \prod_\ell\left( \int h^{\theta_A}_{t_{A,\ell},\upsilon_{A,\ell}}(\xi) h^{\theta_B}_{t_{B,\ell},\upsilon_{B,\ell}}(\xi) \,dm_{l_\ell,q_\ell}(\xi)\right) \,d\alpha_{A,Z}(\theta_A)\,d\alpha_{B,Z}(\theta_B).\] 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 (171) 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 (168), 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 \(\mathbb P(E_s)\ge .05\).

Fix a witness with \(s_j=1\). For each first-side endpoint \(i\), rewrite its edge relation as \[\begin{align*} p_{A,i}+\mathbf c_{ij}\cdot\mathbf x_{A,i} +(1+\beta_{ij})h_{A,i} ={}&r_i p_{B,j}+\mathbf c'_{ij}\cdot\mathbf x_{B,j} +(r_i+\beta_{ij})h_{B,j}+\gamma_{ij}q. \tag{172}\end{align*}\] 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 (172) 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)\), \[ p_{A,i}=T(\lambda_{A,i},\mathrm{atom})+\alpha_{A,i}h_{A,i} +f_i(l,q,\xi), \tag{173}\] 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 (172). 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 \[ p_{B,j}+\mathbf c'\cdot\mathbf x_{B,j}+\alpha' h_{B,j}. \tag{174}\] For this fixed array and endpoint there is at most one possible deterministic expression (174), 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 (174) 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 (173) 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 (173) 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 46. 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 \[p_{A,i}=\boldsymbol\lambda_{A,i}\cdot\mathbf x_{A,i} +\alpha_i h_{A,i}+f_i, \qquad p_{B,j}=\boldsymbol\lambda_{B,j}\cdot\mathbf x_{B,j} +\alpha_j h_{B,j}+f_j,\] where bold \(\boldsymbol\lambda\) denotes coordinates in the effective basis. Substitute this into a dual relation (171). At a fixed signature the two generic status distributions have every pair of role/basis assignments available. Comparing their coefficients forces \[\begin{align*} \mathbf c_{ij}&=s_j\boldsymbol\lambda_{A,i},& \mathbf c'_{ij}&=r_i\boldsymbol\lambda_{B,j},& \beta_{ij}&=s_jd_i=r_id_j, \tag{176}\\ s_jf_i+r_if_j&=\gamma_{ij}q. \tag{177}\end{align*}\] Thus \[ s_je_i=r_ie_j\qquad(i,j\in\{1,2\}). \tag{178}\] Equality of functions here is exactly the almost-everywhere equality recorded in the prepared subsequential class.

If both \(e_i\) vanish, 47 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 \[\sum_i a(\lambda_{A,i})+ \mathsf u_{B,j}(\Delta_A) =c+\mathsf u_{B,j}(\Delta_A)=0\] 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 (178) 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=\mathbf 1_{i\in S}\), (177) 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 \[\sum_{i,j}\beta_{ij}=|S|d\quad\text{in }\mathbb F_2.\]

Evaluate the basis terms in (176) at their local targets. The \(a\)-terms sum to \(|S|c+|S|c=0\), because 50 fixed the same value \(c=\sum_i a(\lambda_i)\) in both units. The remaining terms are \[\sum_{j\in S}\mathsf u_{B,j}(\Delta_A) +\sum_{i\in S}\mathsf u_{A,i}(\Delta_B).\] By (132), this equals \(|S|d\). Together with the role contribution it is zero. Thus every dual relation vanishes on the target, and 78 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 79. 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 73. Their intersection therefore has mass greater than \(.89\). On it no nonzero dual pattern exists for any exclusions within the stated budget, so 78 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 80 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 (79) 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 \[ H_L=\ker\operatorname{pr}_B. \tag{179}\]

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 (179), 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 (179) 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 (179) 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 (161) along this same subsequence. Apply 76 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 82. This gives between one and seven matched generators per edge with fresh allowed labels. Their sum vectors obey (169) and (170); 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 7, in particular (86), 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 (159). At every matched position the refined status overlap is positive. This contradicts 76 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 40. The successful densities are unnormalized with respect to the retained law, and 40 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 \[100g-(k_{\max}+.03)=44g+55.97>0.\] Thus these overlaps are on the scale required for 25. ◻

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 27. 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 50 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 80, robustly under the fresh-label exclusions. In the no-prediction case the retained mass is also at least \(\delta_*\) and 81 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 \[\sum_c p_c^2\le (\max_c p_c)\sum_c p_c \le\eta_{\mathrm{col}}.\] 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 73, gives positive limiting mass on \(J=1\) satisfying the hypothesis of 83. That proposition yields a fixed option with positive subsequential overlap on different-colour pairs. The filtered form of 40 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 \[(Y_v^{\mathsf T}x,Y_w^{\mathsf T}x,X_v^{\mathsf T}y,X_w^{\mathsf T}y)\] are uniform on \(\mathbb F_2^{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\), \(\mathbb 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 \({\mathsf P_0}^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}{\mathsf P_0}^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 79 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 \[\begin{split} D_n(U,V)&=\mathbb P_z\{u_V(K_U(z))\ne\phi_n(K_U(z)) \mid \tau\},\\ d_n(V)&=\mathbb P_{k\sim\Omega_{l,q,n}} \{u_V(k)\ne\phi_n(k)\}. \end{split}\] For each fixed \(V\), the one-endpoint assertion of 59 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 \({\mathsf P_0}\)-marginal. Consequently, for every fixed \(t>0\), \[\mathbb P_{U,V\sim\nu}\{|D_n(U,V)-d_n(V)|>t\}=o(1).\] 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 \[G_n=\{v:d_n(v)\le\epsilon_n+t_n\},\qquad \nu(G_n)\ge\delta-o(1).\] 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 \[\mathbb E_{\Omega_{l,q,n}}\chi_V\chi_W \ge 1-4(\epsilon_n+t_n).\] This contradicts (184), 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, (181) 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 42 and the proof of 43. 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: \[\mathbb E_{\rm iid\ channels} \left|\mathbb E_A(-1)^{u_Z(\Delta_A)}\right|^s \le \mathbb E_{A_1,\ldots,A_s} 2^{-h\mathop{\mathrm{rank}}(\Delta_{A_1}+\cdots+\Delta_{A_s})} \le 4^s p_0^{q_0s/2}+2^{-hq_0s/4}.\] This is (112) with no reciprocal phase and no candidate value of \(\Delta_Z\). The inequalities (110) and (111), followed by Markov’s inequality at threshold \(\theta\), bound the raw channel exception by \(C_h2^{-\Gamma N}\). The channel comparison in 23 is included in the fixed factor \(C_h\). Paying \(L2^{\varepsilon_{\rm ch}N}\) once leaves an exponentially small point-law exception. Thus \(\left|\mathbb 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 (113) 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 \[p_{\max}(Z_A)\le2^{-tN+.01N}\] by (116). 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 24, multiplied by the fixed point marginal factor, gives \[\mathbb P\{R(A,Z)\text{ fails}\} \le L\,O(r)2^{2r-h}+o(1)<.01\] 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\mathcal B)\) bits. The number of coefficient lists is fixed in \(n\). The density loss from thinning and the ratio \(\dim\mathcal B/N\) are absorbed into \(.01N\). This is the singleton image calculation of (117) 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 30 therefore bounds its unnormalized signed mass, including the rank filter, by \[2^{tN/2} \left(2^{-tN+.01N}2^{-tN+.01N}\right)^{1/2} =2^{(-t/2+.01)N}.\] Summing over records gives at most \(2^{-.488N}\). Since \(\mathbb P(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 \[f(A)=\mathbb P_{Z\sim\nu}\{u_Z(\Delta_A)=c, R(A,Z)\mid A\}.\] The two points are conditionally independent given \(A\), with the identical separate rank filter, so the left side of (186) is \[\mathbb E_A f(A)^2\ \ge\ (\mathbb E_A f(A))^2\ >\ .49^2.\] 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 27(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 [sec:histograms,sec:common-limit] concern the primal frames.

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 \[\sum_x(p'(x)-p(x))\log\frac{p(x)}{q(x)}\ge0.\] Subtracting the two entropies proves the first inequality. If \(p'\) is supported on \(S\), then \[\mathsf D(p'\Vert p) =\mathsf D(p'\Vert p(\cdot\mid S))-\log p(S).\] 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 \[u\cdot v\ge u\cdot z =u\cdot c+\|u\|^2>u\cdot c\ge0.\] 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 \[M\pi(x),\quad M\pi(y),\quad Q_N\pi(x)\pi(y),\quad \eta_{\mathrm{col}},\] respectively. An object \((x,y,c)\) uses one unit of each of its four resources. Apply 90. 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 \[\pi(S)\le4\sum_x\pi(x)(\ell_x+r_x)<4/M<8/M.\] 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 \[L\pi(A)+L\pi(B) +Q_N\pi^2\bigl(R\cap((\Omega\setminus A) \times(\Omega\setminus B))\bigr)<1.\] 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 25(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 25(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, 89 increases its minimum by at least \(-\log(1-\epsilon_N)\ge\epsilon_N\). Consequently the number of recordings is at most \[ 1+\left\lceil \frac{\max\{\log(qQ_N),\log Q_N+\log L\}} {\epsilon_N}\right\rceil =O(N2^{100gN}). \tag{196}\] 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 (196) by the corresponding power of one plus that number proves (195). ◻