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 elements 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 functional 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. 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. If \(\rho(x)=0<\rho'(x)\) at a feasible support point, the entropy along \((1-t)\rho+t\rho'\) has right derivative \(-\infty\) at zero from the newly occupied points. At all points where \(\rho>0\), its derivative is finite. This contradicts minimality, proving the support assertion.

We can therefore differentiate toward any feasible \(\rho'\) using only points where \(\rho>0\). The right derivative at the minimizer is nonnegative, giving \[\sum_x(\rho'(x)-\rho(x))\log\frac{\rho(x)}{q(x)}\ge0,\] where the constant derivative term cancels because both measures have total mass one. The exact identity \[\mathsf D(\rho'\Vert q)-\mathsf D(\rho\Vert q) =\mathsf D(\rho'\Vert\rho) +\sum_x(\rho'(x)-\rho(x))\log\frac{\rho(x)}{q(x)}\] proves the second assertion. Finally, if \(\rho'\) is supported on \(S\), comparison with the normalized restriction \(\rho(\cdot\mid S)\) gives \[\mathsf D(\rho'\Vert\rho) =\mathsf D(\rho'\Vert\rho(\cdot\mid S))-\log\rho(S) \ge-\log\rho(S).\] For completeness, nonnegativity of relative entropy follows from \(\log t\le t-1\), applied with \(t=q(x)/\rho'(x)\) and summed over the positive support of \(\rho'\). ◻

Proof. Construct a directed network with source \(s\), a left copy and a right copy of \(\Omega_n\), and sink \(t\). Give the edge from \(s\) to left \(x\) capacity \(M\mu(x)\), the edge from right \(y\) to \(t\) capacity \(M\mu(y)\), and the edge from left \(x\) to right \(y\) capacity \(2^{DN}\mu(x)\mu(y)\) whenever \((x,y)\in R\). A flow of value one is precisely a law satisfying the three caps. A flow of larger value could be scaled down to value one, so the maximum value is less than one.

The feasible flows form a compact polytope, hence the flow value has a maximizer \(f\). In its residual network, include a forward edge whenever its capacity exceeds its flow and a reverse edge whenever its flow is positive. There is no residual path from \(s\) to \(t\): augmenting by the smallest positive residual capacity on such a path would increase the value. Let \(Z\) be the vertices reachable from \(s\). Every forward edge across \(Z\) to its complement is saturated, and every forward edge in the opposite direction has zero flow, since otherwise its reverse residual edge would leave \(Z\). Summing flow conservation over \(Z\) shows that the capacity of this cut equals the value of \(f\), hence is less than one.

Let \(L_0\) be the raw types whose left copies are outside \(Z\), and let \(R_0\) be those whose right copies are in \(Z\). The cut-capacity inequality is \[M\mu(L_0)+M\mu(R_0) +2^{DN}\mu^2\bigl(R\cap((\Omega_n\setminus L_0) \times(\Omega_n\setminus R_0))\bigr)<1.\] Take \(S=L_0\cup R_0\) and take \(E_0\) to be the pair set in the last summand. Its measure and that of \(S\) have the asserted bounds. A pair in \(R\) with neither endpoint in \(S\) necessarily belongs to \(E_0\). ◻

Proof. Entropy-controlled fingerprints. Make a finite conflict graph whose vertices are raw units; two units are adjacent when they give all four cross holes. There are no loops, since a repeated unit would require a hole from a raw vertex to itself. Put \(\varepsilon_N=2^{-100gN}\).

For an independent set \(I\) of raw units, start with all units as a residual set \(R\). If there is a feasible law satisfying [eq:raw-law-caps] on \(R\), choose its relative-entropy minimizer with respect to \(\mu^2\). Such a minimizer exists because the feasible laws form a compact convex polytope and relative entropy is continuous on the finite probability simplex. Fix deterministic choices throughout. The average, under this law \(\rho\), of \(\rho(N_R(v))\) is the conflict probability of two independent \(\rho\)-units, so is at least \(\varepsilon_N\). Choose a unit \(v\in R\) maximizing this neighborhood mass. If \(v\in I\), record \(v\) and delete its entire neighborhood \(N_R(v)\). If \(v\notin I\), delete \(v\) alone. Both operations preserve \(I\subseteq R\). Each removes at least one unit, so the procedure terminates at a residual set with no feasible law.

When a recording leaves a feasible residual, 7 shows that the new minimum entropy exceeds the old one by at least \(-\log(1-\varepsilon_N)\). Other deletions cannot decrease the minimum. Every feasible law has entropy in \([0,DN\log2]\), since its density is at most \(2^{DN}\). Allowing one final recording that leaves no feasible residual, the fingerprint has length at most \[ L_N=1+\left\lceil \frac{DN\log2}{-\log(1-\varepsilon_N)} \right\rceil =O(1+DN\,2^{100gN}). \tag{18}\]

The fingerprint determines the terminal set. Indeed, after a unit is recorded its residual neighborhood is empty, and remains empty as residual sets shrink. A feasible law always has a unit with strictly positive neighborhood mass, so a recorded unit is never selected again. Given the set of recorded units, replay the deterministic procedure, recording a selected unit exactly when it is in that set. All other selected units are deleted. This reproduces every step and the terminal set.

By [eq:raw-space-size], the logarithm of the number of raw units is \(O(N^2)\). The number of possible fingerprints, and hence terminal sets, is at most \((|\Omega_n|^2+1)^{L_N}\). Its logarithm is \[ O(N^3\,2^{100gN})=o(m), \tag{19}\] since \(m=2^{1000gN}\).

Terminal exceptions in the sample. For each terminal set fix sets \(S,E_0\) supplied by 8. Let \(k=\lceil m/200\rceil\). The probability that at least \(k\) sampled positions have raw type in \(S\) is at most \[\binom mk\mu(S)^k \le \left(\frac{em}{kM}\right)^k \le (200e/M)^k =\exp(-\Omega(m)).\] A fixed collection of \(k\) disjoint ordered pairs of distinct sampled positions consists of independent \(\mu^2\)-draws. It lies entirely in \(E_0\) with probability at most \(2^{-kDN}\). There are at most \(m^{2k}\) such collections, so the probability that one exists is at most \[ m^{2k}2^{-kDN} =2^{(2C_0g-D)Nk} =2^{-2C_0gNk}. \tag{20}\] Union over the \(\exp(o(m))\) terminal sets using [eq:container-count]. Outside a set of probability \(\exp(-\Omega(m))\), every terminal set has fewer than \(m/200\) exceptional positions and fewer than \(m/200\) disjoint position pairs in its pair exception. The strict bounds follow from \(k-1<m/200\).

Suppose on this event that \(G\) has a touching matching of size at least \(m/100\). Orient its edges arbitrarily, and let \(I\) be the set of raw unit types thereby realized. This is independent in the conflict graph: four cross holes would mean that the two endpoint sets have no edge between them in \(G\). Different sampled matching edges may have the same raw type; no injectivity of this assignment is needed. Run the container procedure for this set \(I\). Every occurrence of a matching-edge type lies in its terminal set, and hence is covered by \(S\) or \(E_0\). Because the matching uses disjoint sampled positions, fewer than \(m/200\) of its edges can meet the positions in \(S\). The rest give disjoint ordered position pairs in \(E_0\), of which there are also fewer than \(m/200\). Their sum is less than \(m/100\), a contradiction.

Finally, \(\alpha(G)\le2\) holds deterministically by 4. ◻

Proof. Consider a complete-minor model with \(b\) branch sets. Let \(s\) of them be singletons and \(e\) have two vertices. Each two-vertex branch is an edge. The singleton vertices form a clique, so pairing them gives \(\lfloor s/2\rfloor\) more edges. All these edges together form one touching matching: their vertex sets are disjoint, and adjacency of the original branches guarantees every required contact. Writing \(c=\mathop{\mathrm{cm}}(G)\), we obtain \[c\ge e+\lfloor s/2\rfloor,\qquad s\le2(c-e)+1.\] Every remaining branch has at least three vertices, whence \[m\ge s+2e+3(b-s-e)=3b-2s-e.\] Combining the inequalities gives \[3b\le m+2s+e\le m+4c-3e+2\le m+4c+2.\] Maximize over all complete-minor models. For the final assertion, every color class has at most two vertices when \(\alpha(G)\le2\), so \(\chi(G)\ge m/2\). Combine this with \(c<m/100\) and \(26m/75+2/3<m/2\) when \(m\ge5\). ◻

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 plus columns are linearly independent with probability at least \(1-2^{p-N}\): each nonzero coefficient dependence has probability \(2^{-N}\). Given their linear 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. The raw law is invariant under \(L\) on each \(V_e^+\) and \(L^{-\mathsf T}\) on \(V_e^-\), independently at vertices and components. For (a), 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 12. 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.

For (b), the restricted Gram of primal tuples is fixed by \(E\). By 11, 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 (b).

For (c), we prove the image cap, 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 (a). 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. ◻

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 \(\mu^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 5, 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 \(\mu^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{28}\] 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}\mu^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.

For (c), first apply this trimming to any preceding small-cost restrictions. Split each retained old leaf by the further coefficient choices, scalar metadata, and exact images. There are at most \(2^{O(n)}2^{u_0N}\) parts. Discard every part having relative mass less than \(2^{-(u_0+1)N}\) in its old leaf. The total discarded fraction is at most \[2^{O(n)-N}=2^{-\Omega(N)}\] once \(M_0\) is large enough for the fixed metadata coefficient. The normalized law \(Q\) on each retained part consequently has the absolute density bound \[ Q\le2^{D'N}\mu^2,\qquad D'=D+K_1+u_0+5. \tag{29}\] The harmless slack covers the preceding trimming and normalizations. There are initially at most \(K_1+u_0\) pinned dimensions on this part.

Repeat the first procedure, keeping those old and deliberately added pins fixed. Only new directions are counted in its rank comparison. To justify this point, let \(c_1,\ldots,c_u\) be cumulative new lifts independent modulo the stored pin space. They are linearly independent in the full nominal space. The refined event is contained in their prescribed image event, whether or not the old pin event is also imposed. Using the unconditioned reference measure in [eq:second-peeling-start], \[Q(\text{refined event}) \le 2^{D'N} \mu^2\{\operatorname{image}(c_j)\text{ has its prescribed value for all }j\} \le2^{D'N-(1-\epsilon)uN}.\] No reference measure conditioned on the rare old-pin event is used. For each selected current part the tuple is fixed, so adaptive selection of the next violating tuple does not require an additional union bound.

The lower mass bound is again \(2^{-\zeta N-(1-\zeta)uN}\). Thus \(u<4(D'+1)/\zeta\), a conservative consequence of the analogue of [eq:peeling-rank-comparison]. Together with the initial \(K_1+u_0\) pins this is less than the chosen \(K\) in [eq:law-budgets]. The same leaf-mass calculation gives a \(2^{O(N)}\mu^2\) bound with a common early-parameter constant. The second procedure discards at most \(2^{-\zeta N}\) relative mass per part; summing with the actual part weights gives the same total bound. It restores [eq:leaf-minentropy] relative to all old and new pins. Part (b) can then be applied once more to yield [eq:final-leaf-minentropy] after subsequent restrictions.

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. 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. We first construct the label summands at a selector degree where the pairing rank has stabilized. We then show that any discrepancy at a higher degree would contradict the rank bounds.

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 that are base-linear and have 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{32}\] 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 (32) means that the image of \(V_j\) is all of \(Q\), and that a vector of \(V_j\) pairing to zero with \(V_j\) 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 (31) 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\). We have therefore obtained the required label blocks and all moments through selector degree \(2j\).

It remains to recover the higher-degree moments. Extend the right side of (31) to the full row and column indexing. Its rank is at most \(\sum_s\dim Q_s\le R_*\). By 17 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 17 and (30). 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 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{38}\] 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 selected rays as an element of \(S_{i,e}^{\pm}\). Any nonzero such vector would have a sparse representation on selected labels and is forbidden by 19. 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 (41), 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 (40). 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 21. This argument specifies the bits; their occurrence in parameter tests will be supplied by 47. 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 (40) 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.

The construction has three steps. We first solve a relaxed linear problem, allowing an arbitrary bilinear correction on the unfrozen quotients. We then bound the rank of that correction, and finally factor it through the available channel coordinates.

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.

Proof. Vanishing prediction classes give \(\alpha_i=1\) and \(f_i\simeq\gamma_iq\) for a fixed \(\gamma_i\in\mathbb F_2\). At any fixed tag, label and parameter point, the raw key law is the single-key reference up to an exponentially small injectivity error, by 13. The individual marginal density bound, which is a fixed constant at this stage, transfers the reference disagreement of \(f_i\) and \(\gamma_iq\) to an average \(o(1)\) parameter error on the marked population. There are only finitely many endpoint, tag and label choices. Markov’s inequality therefore allows deletion of \(o(1)\) unit mass so that this error tends to zero uniformly on the remaining units and choices. Combining it with [eq:prediction] gives, at every nonexceptional label, \[p_i(x)+T(\lambda_i,x)+a(x)+\gamma_iq(x)=0\] with parameter error tending to zero in the generic flavor.

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

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

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

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 13 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. 16 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 14, 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 marginal is at most \(L\mu\) for a fixed \(L\). 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{82}\] 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{83}\] 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{84}\] 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.

We will compare \(g\) matrices of cross coefficients, each of rank at most \(2s_1\), whose sum is an identity matrix of size \(2gs_1+1\). To construct them, place the common predictor on one array of synthetic keys. Shared-only parity will determine the sum, while its restrictions to small pure-flavor slices will give the individual rank bounds.

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 36 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 \(\mu\) concentrates at its global reference probability. The endpoint marginal bound \(L\mu\), 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{85}\]

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. 36 and the marginal bound \(L\mu\) 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 of 34. If no prediction exists along any subsequence, retain the first-peeling law. Apply 30 to the unconditional pair event, using the first pins and the final budget \(K\) as an upper bound. The failure tolerance here and in the remaining cases is a fixed numerical constant chosen before \(h\). With a sufficiently small failure tolerance it gives injection probability greater than \(.99\). The actual small table is admissible, so this proves (i). Negligible later deletions cannot create a prediction on a mass bounded above \(10^{-6}\) by a fixed positive amount: transfer its uniformly valid marks and functions to the original law and multiply its mass by the retained proportion. This is the form of the no-prediction conclusion used subsequently.

Otherwise make the prediction and the finite initial pigeonholing described after 33. If both prediction classes vanish, perform the \(o(1)\) deletion in 35 now. Thus all later refinements start with the exact identity in that case. For the moment test attainability of [eq:phase-compatibility] on the actual table.

Proof. The bounds in 12 put the probability, divided by \(2^{-ab}\), between \((1-2^{a-N})(1-2^{a+b-N})\) and \(1\). This gives the stated relative error uniformly even when \(a,b\) grow subject to \(a+b\le N/2\). Multiplication over the independent groups gives the remaining assertions. ◻

Proof. By 13, 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. 16 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 40 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. 16 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 descriptions of the same unordered slot pairing. 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 40. 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{88}\] 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 (87) with a constant independent of the partition and its positive weight bound. ◻

Proof of 39. 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)>L+1\), the empirical histogram has entropy greater than \(L\) with probability \(1-o(1)\), uniformly over those orientations. The nominal independence event of 43 can be imposed simultaneously at a further \(o(1)\) loss, also uniformly over orientations.

There are at most \((\ell+1)^r\) empirical types. The standard method-of-types estimate (Cover and Thomas 2006, Theorems 11.1.1 and 11.1.4) gives, for a type \(v\), \[\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 (87) for each cell sequence of a type, and then pay (86). We obtain \[\begin{align*} &(1-o(1))\pi\{D_2(H_O\Vert w)>L+1\}\\ &\hspace{1cm}\le 2^{C_LM_0n+(c_2-L)\ell+r\log_2(\ell+1)}. \tag{90}\end{align*}\] Choose \(L>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\pi}D_2(H_O\Vert w)\le C_H \tag{91}\] 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 (91) 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 (91) 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 (89) 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{92}\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 (91) 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. 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, 41 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\mu}\bigl(\mathbb E_zF_n(z,K(O,z))\bigr) \le C_1 2^{-c_1'n}. \tag{94}\] 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 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\mu}h_o(D_2).\] Fix a small constant \(\eta>0\). By (94), uniformly in \(D_2\), \(\mathbb P_\mu\{\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 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 marginal cap in (93) 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 40 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 orientation. Hence the set of paired orientations with a good first endpoint but a bad oversampling second endpoint has \(\mu^2\)-mass \(2^{-\Omega(n^2)}\). Multiplying by the 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 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. Its 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 21 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 (93) 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. 16 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 (95). 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 13. The first conclusion therefore follows from the one-endpoint part of 45, 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 21, 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 law because \(E\) has no \(Z\) rows or columns. 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 48, \[\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{98}\] 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 (98). This proves the transformation claim with \(J\) fixed independently of the cell mass.

Integrate that claim over the starting raw 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 bad conditional sign-bias event on that set 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 21. Union over them, and over the bounded numerical position and summary choices. The resulting event is still exponentially small, also after the marginal inflation in (93).

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 (97), 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 (113), also for refinements. The final indicator assertion follows from the absolute-value bound before the indicator is applied. ◻

Proof. We construct the test lists by successive finite stages. On predicted branches begin with the two global predictor bits. For every numerical option, positive integer truncation height, and successively improving fixed accuracy, request the cells of a partition provided by 58 as tuple tests. For every tuple cylinder already obtained and successively improving accuracy, request all unary indicator factors needed in 51. Include their unary pullbacks and the finite Boolean operations needed to record them. Enumerate these requests and fulfill finitely many at each stage, so that every request is eventually included. The resulting countable lists are closed under the required 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. Regularity in 51 is performed on key spaces, so its new unary factors remain global key functions. Nominal input phases handled in that theorem are not added to the lists.

In \(\theta_n\), 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. 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.

Besides the two conditional laws already specified, retain in \(Z_n\) 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, 45 says that the sum of its empirical status masses differs in probability from its reference mass by a quantity tending to zero. The mixed marginal assumption is the one needed here; no assertion is made about every individually normalized leaf. 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 (114). Versions jointly measurable in \((\theta,\xi)\) are obtained by taking the limits of their conditional density averages on increasing finite cylinder partitions.

For a generic role/basis assignment, apply 49 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, so the chosen \(C_i\) may vary with the orientation. 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 42, 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 with the same law at every \(n\), so this remains true after averaging \(Z\) and dropping flags. 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 39 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 usability, tends to zero because it is bounded above by (111). Choose a global partition with projection error at most \(\varepsilon\) in 58. 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 usability indicator. 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 58 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 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. There are only finitely many options. ◻

Proof. The displayed expression is jointly measurable and nonnegative, by 59. We prove equality against every tuple cylinder indicator \(W\).

At a fixed accuracy \(\varepsilon\), apply 51 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 45. An opposite-leaf-dependent choice of the flag cannot increase that unconditional error.

Apply 47 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{116}\] 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 (116) 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 51 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 (116). 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\). 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 (122) 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 (119), 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{123}\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 (123) 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{124}\] 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 (123). 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{125}\] For this fixed array and endpoint there is at most one possible deterministic expression (125), 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 (125) 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 (124) 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 (124) 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 33. 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 (122). 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{127}\\ s_jf_i+r_if_j&=\gamma_{ij}q. \tag{128}\end{align*}\] Thus \[ s_je_i=r_ie_j\qquad(i,j\in\{1,2\}). \tag{129}\] Equality of functions here is exactly the almost-everywhere equality recorded in the prepared subsequential class.

If both \(e_i\) vanish, 35 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 (129) 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}\), (128) 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 (127) at their local targets. The \(a\)-terms sum to \(|S|c+|S|c=0\), because 34 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 (80), this equals \(|S|d\). Together with the role contribution it is zero. Thus every dual relation vanishes on the target, and 64 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 65. 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 59. Their intersection therefore has mass greater than \(.89\). On it no nonzero dual pattern exists for any exclusions within the stated budget, so 64 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 66 gives the assertion. ◻

Proof. Begin with the mandatory support exclusions and, in the predicted case, the stored exceptions. 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 (34) 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 67. 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 \(\pi\). 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\pi. \tag{130}\]

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 (130), 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\pi\), whose dimension is at most two. On the remaining labels (130) 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 (130) 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. If the conclusion failed, finiteness of the option collection would give (112) along the sequence in question. Construct the common model of 59 and apply 62.

By 67, there is positive model mass of a table with both flags passed and with a scalar solution surviving the needed exclusions. Apply 68. This gives between one and seven matched generators per edge with fresh allowed labels. Their sum vectors obey (120) and (121); 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 6, in particular (41), 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 (110). At every matched position the refined status overlap is positive. The full-density identification in 61, combined with the independent unary projections of the limiting reference law, expresses the limiting full-query overlap as \(\kappa_A\kappa_B\) times the integral of the product of these matched overlaps against the two flagged orientation laws. Thus this usable option contradicts 62 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.

Finally the successful densities are unnormalized with respect to the retained law, and 26 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 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 6. ◻

Proof. Suppose the conclusion fails for some \(p\). Along a subsequence there are deterministic sets \(W_n\), requests \(\mathfrak r\), and a fixed \(c>0\) for which the displayed bad event has probability at least \(c n^{-p}\). By a finite subdivision, fix the numerical format and request along this subsequence. Restrict the unit law to this bad event and normalize it. The additional density factor is at most \(c^{-1}n^p\). Since \(N=M_0n\) with \(M_0\) fixed, its logarithm is \(O(\log n)=o(n)=o(N)\). The restricted mixed law therefore still satisfies the hypotheses of [lem:typicality,thm:weak-product], and the uniform profile estimates in 49.

We give the measure-identification argument for this restricted law. It uses no density bound on its individually normalized old leaves. On each single-key space choose countably many common bit tests, and on the tuple-key space choose countably many bit tests containing \(\mathbf 1_{W_n}\). Include the unary factors in weak product approximations to every tuple cylinder at accuracies tending to zero, their unary pullbacks, and the resulting finite Boolean combinations. This countable collection is obtained by successive closure. At every fixed stage its complexity is bounded independently of \(n\).

Pass to a subsequence on which the reference signature laws, the bounded coefficients in these approximations, and the laws of all empirical unary status arrays converge. The arrays have coordinates in \([0,1]\), indexed by finite cylinders and the finite status choices; hence this is ordinary compactness on a countable product of compact spaces. Write \(\Xi_j\) for the single-key signature space at position \(j\), and \(\rho\) for the tuple-test reference law. By 42, the unary projections of \(\rho\) are independent with the respective laws on \(\Xi_j\). The limiting \(W\)-coordinate is a bit, and \(\rho(W)\ge\delta\).

Let \(\theta\) denote a limiting orientation status array. Its unfiltered unary measure equals the single-key reference measure on every cylinder, by 45. The requested unary base-status measure therefore has a density \(h_j^\theta\) relative to that reference measure. Versions can be chosen measurably by conditional averages on the increasing finite cylinder partitions. The simultaneous positive-fraction estimates on all fixed positive-reference-mass cylinders give \[ \beta\le h_j^\theta\le1 \quad\text{almost everywhere, for almost every }\theta. \tag{135}\] Indeed these inequalities hold on the generating cylinder algebra and hence on its generated sigma-algebra by measure domination. All requests are feasible in the restricted law, so their limiting coordinate formats and summary assignments are feasible as well.

Also pass to a limit of the unnormalized accepted tuple measures on the tuple-test cylinders. Denote it by \(\tau\). We claim that \[ \frac{d\tau}{d\rho} =\kappa_{\mathfrak r}\, \mathbb E_\theta\prod_{j=1}^{s}h_j^\theta(\xi_j), \qquad s\le s_{\max}. \tag{136}\] Here \(\xi_j\) is the unary projection of the tuple signature. This is the one-law version of the density identification in 61; the details needed here are as follows.

Fix a tuple cylinder and an accuracy \(\epsilon>0\). By 51, its prelimit indicator can be replaced on actual successful queries by a bounded finite sum of products of global unary key functions, with error at most \(\epsilon\) outside a vanishing set of orientations. This comparison allows the requested unary status indicators as orientation-dependent unary weights. For each structured product, 47 gives its successful integral as \(\kappa_{\mathfrak r}\) times the product of its separate unary status integrals, with vanishing error. Averaging over the restricted law preserves these errors: the relevant estimates use the mixed density and marginal bounds already checked.

The unary integrals and finite numerical metadata are coordinates of the status arrays. Their finite products and averages therefore pass to the limit. Independence of the unary projections of \(\rho\) identifies the result with the structured test against the right side of (136). The reference part of 51 bounds the error of the same replacement against arbitrary products of unary functions bounded by one. Passing this assertion first for cylinder-simple functions and then by \(L^1\) approximation permits the functions \(h_j^\theta\) themselves. After averaging \(\theta\), the discrepancy on the chosen cylinder is bounded by a constant multiple of \(\epsilon\). Send \(\epsilon\) to zero. A countable generating algebra of cylinders proves (136).

In particular, the limiting mean of \(Q_{\omega,\mathfrak r}(W_n)\) is \[\tau(W) =\kappa_{\mathfrak r} \int_W \mathbb E_\theta\prod_{j=1}^{s}h_j^\theta(\xi_j)\,d\rho \ge\kappa_{\min}\beta^{s_{\max}}\delta.\] But each restricted orientation had hit mass smaller than \(c_{\mathrm{hit}}(\delta)\), contradicting (133). This proves (134). ◻

Proof. Every such density is dominated by the corresponding unfiltered query density. Since \(\int d\,d\nu\le1\), its superlevel set \(\{d>T\}\) has reference measure at most \(1/T\). The uniform small-set conclusion of 39 therefore makes the integral on this set uniformly small as \(T\) increases. Choose a fixed \(T\) so large that \(\int_{\{d>T\}}d\,d\nu<b_0/4\) for every density in question and all sufficiently large \(n\). Put \[t=b_0/4,\qquad \delta_0=b_0/(2T).\] The region \(t\le d\le T\) carries integral at least \(b_0/2\), so its reference measure is at least \(\delta_0\).

Take an \(L^1(\nu)\) \(\epsilon\)-net for the entire family of orientation-filtered densities, as supplied by 39. If \(f_j\) approximates \(d\), set \(W_j=\{f_j\ge t/2\}\). At most \(2\epsilon/t\) of the region \(d\ge t\) lies outside \(W_j\). Consequently \(\nu(W_j)\ge\delta_0/2\) when \(\epsilon\le\delta_0t/4\). On \(W_j\cap\{d<t/4\}\) one has \(\lvert f_j-d\rvert\ge t/4\), so that set has measure at most \(4\epsilon/t\). The sets \(W_j\) for all net representatives form the required family. ◻

Proof. Write \(\pi_n\) for the prepared leaf distribution and \(\sigma_\ell\) for the conditional orientation law on a leaf. Two leaves are initially independent. The preparation supplies a set \(\mathcal C_n\) of compatible leaf pairs with \[(\pi_n\otimes\pi_n)(\mathcal C_n)\ge c_0N^{-4}\] for some fixed \(c_0>0\). For every pair in this set, choose an injecting compatible small table whose two separate admissibility filters have orientation masses at least \(a_0>0\). All choices are from finite numerical table and coordinate formats; the constants \(c_0,a_0\) do not depend on \(n\).

Choose one generic atom for each cross edge, at a common fixed tag, with diagonal bit \(q=1\). At each endpoint choose two distinct allowed labels. Use role zero on the first unit and role one on the second. Feasible summaries exist: on the first side take all ordinary-block tester bits zero and the shared tester bit one; on the second side take one allowed ordinary-block tester bit one, all the other such bits zero, and the shared tester bit zero. Prescribe the basis values at endpoint \(i\), facing endpoint \(z\), to be \[T(x_{iz},\cdot)|_{C_i} =(a+(u_zU_i)^*)|_{C_i}.\] Here the star denotes the contraction computed with the chosen table. By (131), \[(p_i+a)(x_{iz}) =T(\lambda_i,x_{iz}) =a(\lambda_i)+(u_zU_i)^*(\lambda_i).\] Summing over the two endpoints \(i\) gives \(c+u_z(\Delta_A)=0\), by the pinned compatibility. The same calculation applies with the two units interchanged. Thus the coupled conditions in (40) hold, as do its diagonal and role conditions. Choose the binary prescriptions given by 24. These are base queries: the recorded old marks and prescribed basis values already determine the \(p_i\)-values, so no additional \(p_i\)-filter is imposed. By 25, equal accepted keys therefore satisfy the hypotheses of 26.

At all but an exponentially small proportion of orientations, [lem:binary-mixing,lem:unary-positivity] give a fixed positive lower bound for the total successful mass of every feasible numerical base request. There are finitely many requests. Markov’s inequality over conditional leaf probabilities shows that, outside an exponentially small set of second-side leaves, every admissibility filter of mass at least \(a_0\) retains total successful query mass at least a fixed \(b_0>0\). For example, first make the conditional fraction of exceptional orientations at most \(a_0/2\); the fixed success lower bound times \(a_0/2\) then gives \(b_0\). Removing these leaves loses \(o(N^{-4})\) leaf-pair mass even before compatibility is imposed.

Apply 72 on each remaining B-leaf and each numerical base format. Fix its uniform constants \(t,\delta_0\), and put \[\delta=\delta_0/2,\qquad c_{\mathrm{hit}}=c_{\mathrm{hit}}(\delta),\qquad A_0=(a_0/2)c_{\mathrm{hit}}>0.\] Use uniform per-leaf small-set control to choose \(\eta>0\) such that every reference set of measure at most \(\eta\) has A-query mass less than \(A_0/2\), for all sufficiently large \(n\). This applies also to a filtered query, which is dominated by the unfiltered one. Now fix a net accuracy satisfying \[\epsilon\le \min\{\delta_0t/4,\eta t/4\}.\] For each B-leaf and numerical base format, take the family of sets \(W_{\ell_B,r,j}\) supplied at this accuracy, and let \(L\) be a uniform bound on its cardinality. The constants through \(L\) are independent of \(n\), although the sets themselves may vary with \(n\) and the B-leaf. Each family was formed over all orientation-only filters. For a compatible pair, its filtered B-density \(d_B\) has mass at least \(b_0\), so choose a member \(W\) satisfying (137) for that density. Although the table and filter may depend on \(\ell_A\), that dependence only selects a member of the already fixed B-leaf family.

We now quantify the first-side exceptional pairs. Let \(C\) bound the number of numerical request and shape choices. Discard family members of reference measure below \(\delta\); the selected member is not discarded. Let \(e_n\) denote the supremum bad probability in (134), over the remaining sets and all relevant requests. For a fixed B-leaf every such set is deterministic for an independent A-orientation. A union bound and then independence of the original leaves give \[ \mathbb E_{\ell_A,\ell_B} \mathbb P_{\omega_A\mid\ell_A} \bigl(\text{some relevant }W_{\ell_B,r,j} \text{ fails its feasible hit bound}\bigr) \le CL e_n . \tag{138}\] Hence the leaf pairs on which the inner probability exceeds \(a_0/2\) have mass at most \(2CL e_n/a_0=o(N^{-4})\), by 70. On any other compatible pair, at least \(a_0/2\) of the A-orientations pass the admissibility filter and all relevant hit bounds. For its selected \(W\) and unnormalized density \(d_A\), this gives \[ \int_W d_A\,d\nu\ge A_0. \tag{139}\]

Together with the exceptional B-leaves, the discarded leaf pairs consume \(o(N^{-4})\) mass.

On a remaining compatible pair let \(H=\{k\in W:d_B(k)<t/4\}\). Then \(\nu(H)\le\eta\), and (139) yields \[\int d_A d_B\,d\nu \ge \frac t4\left(\int_Wd_A\,d\nu-\int_Hd_A\,d\nu\right) \ge \frac{tA_0}{8}.\] There remain at least \((c_0/2)N^{-4}\) compatible pairs for large \(n\). Consequently \[ \mathbb E_{\ell_A,\ell_B}\int d_A d_B\,d\nu \ge \frac{c_0tA_0}{16}N^{-4}. \tag{140}\] Tables and numerical requests may be chosen separately for each leaf pair, as allowed in 26; alternatively one may sum over their finitely many options. This proves the overlap criterion. ◻

Proof of 6. Fix the construction constants and, for every sufficiently large \(n\), fix mixers satisfying 21, before choosing a unit law. Suppose there is no common sufficiently-large-\(n\) bound as asserted. Then along an increasing sequence of \(n\)’s there are admissible unit laws \(\sigma_n\) whose probability of four cross holes is smaller than \(2^{-100gN}\). Apply [lem:peeling,prop:status-preparation], taking subsequences where needed. All retained laws have relative mass \(2^{-o(N)}\), and their final leaves satisfy the required image bounds.

Every alternative with positive limiting mass of injecting compatible tables gives the overlap criterion by 69. The remaining inverse-polynomial alternative gives it by 73. In both cases 26, including the cost of returning to the original laws, gives four-hole probability at least \[2^{-(k_{\max}+.03)N-o(N)}.\] But \[100g-k_{\max}-.03 =100g-56(g-1)-.03 =44g+55.97>0.\] The displayed lower bound is therefore larger than \(2^{-100gN}\) for large \(n\), a contradiction. Since a failure of uniformity over admissible laws produced precisely such a sequence, the resulting sufficiently-large-\(n\) statement is uniform over those laws. ◻

Proof of 1. Apply 9 to 6. For every sufficiently large admissible \(n\), there is a graph on \(m=2^{C_0gN}\) sampled positions with independence number at most two and with \(\mathop{\mathrm{cm}}(G)<m/100\). Since all constants, including \(M_0\), are fixed and \(N=M_0n\) tends to infinity, these orders are arbitrarily large. ◻