Historical context and significance

Uniform Sparsest Cut asks for a partition that separates little capacity relative to the number of vertex pairs it separates. This normalization makes the problem sensitive to bottlenecks at every scale, including cuts with a small side. Its connection with multicommodity flow gives both a way to certify that a graph has no sparse cut and a route to approximation algorithms. Leighton and Rao developed this flow–cut approach and its logarithmic approximation guarantees (Leighton and Rao 1999). Arora, Rao, and Vazirani improved the approximation factor to \(O(\sqrt{\log N})\) using semidefinite programming; their treatment of the unweighted uniform objective appears in (Arora et al. 2009, sec. 6, Theorem 16).

Exact hardness and approximation hardness address different questions. Matula and Shahrokhi established NP-hardness of finding sparsest cuts (Matula and Shahrokhi 1990); Bonsma, Broersma, Patel, and Pyatkin proved NP-completeness for unweighted graphs with the cardinality-product denominator used here (Bonsma et al. 2012, Theorem 15). To rule out a constant-factor approximation, one must create a multiplicative separation between satisfiable and unsatisfiable instances, while preserving the uniform denominator.

Previous approximation lower bounds depend on the complexity assumption and on which pairs carry demand. Ambühl, Mastrolilli, and Svensson proved that a polynomial-time approximation scheme for Uniform Sparsest Cut would yield probabilistic SAT algorithms of time \(2^{n^\varepsilon}\) for every fixed \(\varepsilon>0\), where \(n\) is the SAT input length (Ambühl et al. 2011, Theorem 1.3). Raghavendra and Steurer introduced the Small-Set Expansion hypothesis and its connection with Unique Games (Raghavendra and Steurer 2010). Raghavendra, Steurer, and Tulsiani established arbitrarily large constant-factor gaps for Balanced Separator from that hypothesis (Raghavendra et al. 2012, full version, Theorem 3.5 and Corollary 3.6). Their balanced-cut statement measures set size by stationary volume. The standard recursive reduction then yields hardness of every constant factor for Uniform Sparsest Cut under polynomial-time oracle reductions, assuming the same hypothesis.¹

The nonuniform problem permits a selected set \(\mathcal D\) of distinct demand pairs. In the formulation of Chawla, Krauthgamer, Kumar, Rabani, and Sivakumar, a solution is an edge set \(M\) with total capacity \(c(M)\), and its ratio is \(c(M)/q_\mathcal D(M)\), where \(q_\mathcal D(M)>0\) counts the demand pairs disconnected after deleting \(M\). They proved every-constant-factor hardness under the Unique Games Conjecture (Chawla et al. 2006, Corollary 1.3 and p. 99). The independent Unique Games Theorem supplies the required game premise: its unweighted bipartite constraints can be given equal weights summing to one (OpenAI 2026, Theorem 1.1 and Corollary 8.3). The resulting nonuniform hardness concerns cutset-output search under polynomial-time Cook reductions. Only the selected pairs carry unit demand; they need not include all distinct vertex pairs. The direct reduction proving Theorem 1 is independent of this nonuniform consequence.

Khot and Vishnoi also developed the connection between Unique Games, cut hardness, and negative-type metrics (Khot and Vishnoi 2015). Ordinary NP-hardness for nonuniform sparsest cut is known even with treewidth-two supply graphs, with a \(17/16-\varepsilon\) approximation threshold (Gupta et al. 2013, Theorem 1.3). The separation between the uniform and nonuniform hardness questions is discussed in (Manurangsi and Trevisan 2018, sec. 1.2) and in the recent work of d’Orsi, Jones, Ruotolo, Vadhan, and Zhang on low-degree Abelian Cayley graphs (d’Orsi et al. 2025).

Theorem 1 establishes an unconditional approximation gap with unit demands. Its force comes from controlling all cut masses in a polynomial-size reduction. The proof starts with an explicit algebraic test system for \(3\)CNF, extracts a Boolean valuation from a rare successful event, and forces that event from any cut whose comparison cost is small relative to its demand variance.

Proof structure and main constructions

The reduction has four interfaces. A satisfying assignment supplies a low-cost cut; conversely, a cut with small cost relative to its separated demand will determine a satisfying assignment. The main difficulty in this converse is that the separated demand can be arbitrarily small. Errors must therefore be controlled relative to that demand, rather than by one fixed additive tolerance.

Conventions and parameter dependence

All probabilities refer to the explicitly described experiments. A predicate is a Boolean function of the entire proof-bit assignment; its sampling data may be retained when conditioning, but a response to the predicate depends only on that function. The same convention applies to scores. Thus two presentations of the same function cannot receive different cut colors.

For a probability law \(\mu\) and a Boolean function \(h\), \[\mathop{\mathrm{Var}}_\mu(h)=\mu(h=1)\mu(h=0) =\tfrac12\mathbb E_{B,B'\sim\mu}\abs{h(B)-h(B')},\] where the last two draws are independent. This identity explains the variance normalization used before the final graph is formed.

The approximation factor is fixed first. Thereafter every numerical constant, field size, arity, and number of repetitions is fixed independently of the input formula. Parameters chosen later may depend on earlier parameters only; the necessary order is specified in the proofs. Bounds written \(O(\cdot)\) have constants depending only on parameters already fixed at that point. The construction is polynomial in the formula size; no claim is made that its exponent is uniform in \(C\).

The two local extensions

For a formal Laurent series, its order is the least exponent with nonzero coefficient; the order of zero is \(+\infty\). An element of \(k((z))\) is called integral if it belongs to \(k[[z]]\).

Suppose first that the right side of an equation \(S(X)=b(z)\) becomes integral after subtracting \(S(g)\), for a specified \(g\in k((z))\). Put \(b_0=b-S(g)\in k[[z]]\). There are exactly \(r\) choices of a constant \(\beta\) satisfying \(\beta^r+\beta=b_0(0)\): the derivative of this polynomial is one, and its roots differ by the elements of \(\mathbb F_r\). For each choice, there is a unique positive-order series \(u\) with \(S(u)=b_0-S(\beta)\). Indeed, if \(b_0-S(\beta)=\sum_{n>0}b_nz^n\), then \[ u_n=b_n+\mathbf 1_{\{r\mid n\}}u_{n/r}^{r}\qquad(n>0) \tag{5}\] determines its coefficients successively. Thus the equation splits into \(r\) distinct roots \(g+\beta+u\) in \(k((z))\). Its local algebra is a product of \(r\) copies of \(k((z))\), with integral lattice \(k[[z]]^r\).

The second case is a simple pole. It is useful to establish the parameter and degree assertions without first assuming irreducibility.

Here and below the trace of an element of a finite algebra is the trace of its multiplication map, and its norm is the determinant of that map. For a separable field or product of separable fields, passing to a field containing all embeddings diagonalizes multiplication. Thus trace is the sum of the embedded values, and the trace matrix of a basis is the transpose of its evaluation matrix times that matrix. This also proves the discriminant identity used in Lemma 3.

All branches of the tower

At a pole of \(Y\), the difference \(f(Y)-Y\) is integral: from \(f(Y)=Y/(1+Y^{1-r})\), its order is at least zero. Start at infinity with the parameter \(t=1/x_1\). The first right side has a simple pole, and Lemma 3 produces a single branch in which \(x_2\) has a simple pole with parameter \(1/x_2\). Repeating the lemma gives a single branch at every level. Inductively, the polynomial defining \(x_{i+1}\) is irreducible over this completion of the preceding field, and hence over that field itself. This proves the degree and basis assertions following Equation 4. It also proves them over \(F(x_1)\), since an equation irreducible after extending constants to \(k\) was already irreducible over \(F\).

At a finite point \(x_1=a\), put \(t=x_1-a\). If \(a\in\mathbb F_r\setminus\{0\}\), then \(S(x_1)\) has a simple zero and \(x_1^{r+1}\) is a unit. Thus the first right side has a simple pole, and all subsequent steps are again simple-pole extensions. If \(a\notin\mathbb F_r\), the first right side is integral and the extension splits. An integral residue \(\beta\notin\mathbb F_r\) has \(f(\beta)\ne0\), so no root of \(S(Y)=f(\beta)\) belongs to \(\mathbb F_r\). Induction therefore gives only unshifted integral splittings at such a point.

It remains to describe every branch above zero. As long as the residues of \(x_1,x_2,\ldots\) are zero, all extensions split without a shift. Since \(f(Y)\) has order \(r\) at zero and \(S(Y)\) has order one there, \[\operatorname{ord}_t(x_j)=r^{j-1}\] along the branch with zero residues. Suppose the first nonzero residue occurs at \(x_i\), where \(i\geq2\). It is an element \(\alpha\in\mathbb F_r^*\), and \[\operatorname{ord}_t(x_i-\alpha) =\operatorname{ord}_t S(x_i)=r^{i-1}.\] The numerator \(x_i^{r+1}-\alpha^2\) is divisible by \(x_i-\alpha\). Consequently, modulo integral series, \[ f(x_i)\equiv\frac{\alpha^2}{S(x_i)} =S\left(\frac{\alpha^2}{x_{i-1}}\right). \tag{7}\] The equality uses \(S(x_i)=f(x_{i-1})\), the last identity in Equation 3, and \(\alpha^2\in\mathbb F_r\). Thus this step splits after the specified shift, and every resulting root satisfies \(x_{i+1}\equiv\alpha^2/x_{i-1}\) modulo integral series.

For any earlier small variable \(x_j\), \(j>1\), one has \[ \frac1{x_j}\equiv\frac1{S(x_j)}=S\left(\frac1{x_{j-1}}\right) \pmod{k[[t]]}. \tag{8}\] Indeed the difference of the first two expressions is \(x_j^{r-2}/(1+x_j^{r-1})\), which is integral. Since \(f(Y)\equiv Y\) at a pole, Equations 7 and 8 give successively \[x_{i+s}\equiv\frac{\alpha^2}{x_{i-s}}\pmod{k[[t]]}, \qquad 1\leq s\leq i-1,\] for as long as those variables occur in the tower. Each step in this list is a splitting step with the indicated shift. The last principal part is \(\alpha^2/x_1\), a simple pole. From then on every extension is the simple-pole extension of Lemma 3. This description includes branches for which the tower stops before the first nonzero residue, during the descending shifts, or after ramification.

At every step the split factors or the single ramified factor account for the full relative degree \(r\). Therefore, at each base place, the scalar extension of the degree-\(N\) tower to \(k((t))\) is exactly the product of the branch fields just constructed. No additional local factor is omitted.

Integral lattices and their determinants

Fix a base place with parameter \(t\), and put \(R=k[[t]]\). The product of its branch integral rings is a free \(R\)-module of rank \(N\), by the bases constructed above. Express it in coefficient coordinates relative to Equation 4, and denote the resulting lattice in \(k((t))^N\) by \(\Lambda\). If \(C\) is a basis matrix of this lattice, define its coefficient determinant order by \(\delta=\operatorname{ord}_t\det C\).

We use two elementary facts about this order. First, if a square matrix over \(R\) has nonzero determinant, invertible row and column operations reduce it to a diagonal matrix. To see this, choose an entry of least order and move it to the first position. It divides every entry in \(R\), so row and column subtractions clear its column and row. Continue in the remaining square matrix. The diagonal entries are units times powers of \(t\). It follows that the dimension over \(k\) of the cokernel equals the determinant order. Second, for a branch \(k((z))\) over \(k((t))\), multiplication by a unit has determinant a unit on \(k[[z]]\), whereas multiplication by \(z\) has cokernel \(k\) and hence determinant order one. Thus \[ \operatorname{ord}_t\operatorname{Norm}_{k((z))/k((t))}(z^a u)=a \qquad(a\in\mathbb Z,\ u\in k[[z]]^*). \tag{9}\] The equality for negative \(a\) follows by multiplicativity. The residue field of each branch is \(k\); this is why no residue-degree multiplier appears in Equation 9.

For completeness, if \(b_1,\ldots,b_n\) is a basis of a separable algebra over a field and \(c_1,\ldots,c_r\) is a relative basis for a separable algebra above it, their composed basis satisfies \[ \operatorname{disc}(b_i c_j) =\operatorname{disc}(b_i)^r \operatorname{Norm}\bigl(\operatorname{disc}(c_j)\bigr). \tag{10}\] Indeed, the evaluation map first applies \(r\) copies of the lower evaluation matrix and then, over each lower embedding, its relative evaluation matrix. Taking determinants and squaring gives the formula. For a product algebra choose the relative bases componentwise; the same factorization applies.

The discriminant of the power basis in Equation 4 is a nonzero constant. At every relative step the roots of the additive equation differ by nonzero elements of \(\mathbb F_r\), so its power-basis Vandermonde discriminant is a nonzero constant; Equation 10 preserves this property. For integral bases, a splitting step has relative discriminant one, using the idempotent basis of its product of rings. A simple-pole step has relative discriminant order \(2(r-1)\) by Lemma 3.

Suppose the current local algebra has degree \(n\), has \(B\) branches, and its integral discriminant has base order \(d_{\rm int}\). If \(R_0\) of those branches ramify at the next step, then \[\begin{align*} d_{\rm int,new}&=r d_{\rm int}+2(r-1)R_0,\\ B_{\rm new}&=rB-(r-1)R_0,\qquad n_{\rm new}=rn. \end{align*}\] Equation 9 justifies each contribution from a branch that may already be ramified over the base. Starting from \(d_{\rm int}=0\) and \(n=B=1\), these recurrences give \(d_{\rm int}=2(n-B)\) at every level. On changing from the power basis to an integral basis, the trace matrix changes to \(C^{\mathsf T}GC\), where \(G\) is the power-basis trace matrix. Since \(\det G\) is a unit, we obtain \[ \delta=N-B,\qquad 0\leq\delta\leq N. \tag{11}\] At a good finite point \(a\notin\mathbb F_r\) all variables are integral and all extensions split. The power basis is then itself an integral basis: its lattice is contained in the integral lattice, and both have determinant order zero.

We next give a bound that makes the lattice conditions finite. At every exceptional place, and in every partial branch, each nonzero \(x_i-c\), \(c\in\mathbb F_r\), has absolute order at most \(N^2\) in the current parameter. Before a later ramified extension, the zero-branch orders and the descending pole orders in the preceding subsection are at most \(N\); the order of \(x_i-c\) is zero unless its residue equals \(c\) or it has a pole. Subsequent ramification multiplies these orders by a total factor at most \(N\). This proves the bound for every such factor, including variables retained from an earlier level. Set \[ F_0=(l+1)rN^2,\qquad H=(2N-1)F_0+D. \tag{12}\] In every branch, \(t^{F_0}e_{\boldsymbol a}\) is integral: the pole order of the monomial is at most \((l-1)(r-1)N^2\), while \(t\) has positive integral order. Hence \(t^{F_0}R^N\subseteq\Lambda\).

Multiplication by an integral element acts on the integral lattice, so its trace belongs to \(R\). Each entry of \(G\) therefore has order at least \(-2F_0\). If \(y\) is integral, then \(\operatorname{tr}(y e_{\boldsymbol a})\) has order at least \(-F_0\); if \(t^D y\) is integral, the lower bound is \(-F_0-D\). The vector of these traces is \(G\) times the coefficient vector of \(y\). Since \(\det G\) has order zero, each cofactor has order at least \(-2F_0(N-1)\), and Cramer’s rule yields \[ \begin{aligned} t^{F_0}R^N&\subseteq\Lambda_a\subseteq t^{-H}R^N &&(a\in\mathbb F_r),\\ t^{F_0-D}R^N&\subseteq t^{-D}\Lambda_\infty \subseteq t^{-H}R^N. \end{aligned} \tag{13}\] All shifts here are powers of the base parameter, including the shift at infinity. In particular, membership in any target lattice inside \(t^{-H}R^N\) is determined by the coefficient jet with exponents from \(-H\) through \(F_0-1\). Changing the omitted tail adds an element of the target lattice. At infinity the smaller upper endpoint \(F_0-D-1\) would also suffice.

A large space of global functions

In coefficient coordinates, let \(V_H\) consist of functions whose every coefficient is a linear combination of \[1,x_1,\ldots,x_1^H, \qquad (x_1-a)^{-j}\quad(a\in\mathbb F_r, 1\leq j\leq H).\] These rational functions are independent: their principal parts at the distinct finite poles first determine all the negative-power coefficients, and the remaining polynomial determines the others. Consequently \[\dim_k V_H=N[1+(r+1)H].\] At each of the \(r\) bad finite points and at infinity, its coefficient expansion belongs to \(t^{-H}k[[t]]^N\). Let \(\mathcal L_k\) be the subspace of \(V_H\) that is integral at every finite place and becomes integral at infinity after multiplication by \(t^D\).

The finite-place quotient by \(\Lambda_a\) has dimension \(NH+\delta_a\): scale the inclusion into an integral matrix and apply the diagonalization argument preceding Equation 9. At infinity the target is \(t^{-D}\Lambda_\infty\), whose determinant order is \(\delta_\infty-ND\), because all \(N\) coefficient coordinates are scaled. The quotient dimension there is therefore \(NH+\delta_\infty-ND\). Expansion followed by these quotient maps gives one linear map from \(V_H\) to their direct sum. Its rank is at most the dimension of its target; no independent prescription of local jets is required. Equation 11 gives \[\begin{align*} \dim_k\mathcal L_k &\geq N[1+(r+1)H] -\left((r+1)NH+\sum_{a\in\mathbb F_r\cup\{\infty\}}\delta_a-ND\right) \\ &\geq N(D-r)=N. \tag{14}\end{align*}\] There are no conditions to impose elsewhere, since the rational coefficients and the power basis are integral at every other finite place. The space contains the constant function one.

This space is defined over \(F\). Indeed, coefficientwise \(q\)-Frobenius, fixing the formal variables \(x_i\), preserves the tower equations and permutes all branches above each exceptional place. It thus preserves the subspace \(\mathcal L_k\) in the fixed finite rational-coefficient basis of \(V_H\). Put a matrix whose rows form a basis of this subspace into reduced row echelon form. Applying Frobenius gives another reduced row echelon basis of the same subspace with the same pivots. Uniqueness of that form forces every entry to be fixed by Frobenius, hence to belong to \(F\). Thus the space \(\mathcal L\) of its \(F\)-rational coefficient vectors has \[ \dim_F\mathcal L=\dim_k\mathcal L_k\geq N. \tag{15}\] The algorithm below obtains this space by a finite ground-field matrix, not by searching for Frobenius-fixed vectors.

Evaluation and the quadratic zero bound

There are \((q-r)N\) rational evaluation tuples above \(x_1\in F\setminus\mathbb F_r\). To verify this count, if \(\beta\in F\setminus\mathbb F_r\), then \(\beta^r+\beta\in\mathbb F_r^*\) and \(\beta^{r+1}\in\mathbb F_r^*\), so \(f(\beta)\in\mathbb F_r^*\). The map \(S:F\to\mathbb F_r\) is linear over \(\mathbb F_r\) with kernel \(\mathbb F_r\), hence is onto. Each equation \(S(Y)=f(\beta)\) has exactly \(r\) distinct roots in \(F\setminus\mathbb F_r\). Induction proves the count and describes all tuples. All functions in \(\mathcal L\) are regular at these tuples, so evaluation is well defined.

Let \(a\) be a nonzero element of the span of products of two elements of \(\mathcal L_k\). It is integral at every finite place, and \(t^{2D}a\) is integral at infinity. Its field norm to \(k(x_1)\) is nonzero. At every finite place its local multiplication matrix is integral, so the norm has no finite poles and is a polynomial in \(x_1\). At infinity, \[0\leq\operatorname{ord}_t\operatorname{Norm}(t^{2D}a) =2DN+\operatorname{ord}_t\operatorname{Norm}(a),\] and therefore \[ \deg\operatorname{Norm}(a)\leq2DN. \tag{16}\] At a good base value \(b\), the local algebra is a product of \(N\) copies of \(k((x_1-b))\). The local norm is the product of the integral branch values \(a_1,\ldots,a_N\), and \[\operatorname{ord}_{x_1-b}\operatorname{Norm}(a) =\sum_{j=1}^N\operatorname{ord}_{x_1-b}(a_j).\] Each zero evaluation contributes at least one to this sum. In particular, several zero branches above the same \(b\) are counted with their full multiplicity. Equation 16 bounds the total number of zero evaluation positions by \(2DN\).

Evaluation on these positions is injective on \(\mathcal L\): if a nonzero function vanished everywhere, its product with the constant one would contradict \(2DN<(q-r)N\), which follows from Equation 2. Choose \(l\) least such that \(N=r^{l-1}\geq d\), and choose \(d\) independent functions in \(\mathcal L\). Their \(d\) by \((q-r)N\) evaluation matrix has rank \(d\). Choose \(d\) independent columns and left-multiply by the inverse of their square matrix. The new functions still belong to \(\mathcal L\), and their evaluation vectors include all standard basis vectors.

Call the resulting columns \(u_1,\ldots,u_m\). If a homogeneous quadratic \(Q\) is nonzero on this list, applying \(Q\) to the \(d\) functions gives a nonzero element of the product span. The preceding zero bound and Equation 2 give \[\#\{j:Q(u_j)=0\}\leq2DN\leq\lambda_0(q-r)N=\lambda_0m.\] Since \(N<rd\) for this choice of \(l\), we have \(m=O_r(d)\). This proves the algebraic assertions of Lemma 2; it remains to justify the claimed algorithm and running time.

A finite algorithm and its precision bounds

The fixed fields \(F\) and \(\mathbb F_r\) can be constructed once and for all. For example, the roots of \(Z^{2^s}-Z\) form the field of \(2^s\) elements, and a representation by a binary basis and an irreducible polynomial can be fixed by a finite search when \(s\) is fixed. Only the extension degrees below grow with \(d\); they will be constructed by linear algebra. Field arithmetic in a binary basis has polynomial bit complexity in the basis dimension.

The matrix walk and the masked parity law

Pad the variable set to addresses in \(\{0,1\}^d\), with \(d\geq1\) and \(d=O(\log(\text{input size}+1))\). Dummy addresses impose no clauses. Choose the fixed square field \(\mathbb F=\mathbb F_q\) of characteristic two and the pencil \(u_1,\ldots,u_m\in\mathbb F^d\) from Lemma 2. The field will be sufficiently large and the pencil parameter \(\lambda_0\) sufficiently small. Set \[G_0=\mathop{\mathrm{span}}_{\mathbb F}\{u_j u_j^{\mathsf T}:1\leq j\leq m\}, \qquad G=\operatorname{Mat}_{b\times b}(G_0).\] We regard \(G\) as a space of \((bd)\times(bd)\) matrices with \(d\times d\) blocks. We may take \(b=101\); the allocation of its blocks is described below. Since the pencil contains the standard basis, \(G_0\) contains every diagonal matrix. Also \(\dim_{\mathbb F}G\leq b^2m=O(d)\).

Let \(\mathsf D\) be the law \[ h=(c\otimes u_j)(e\otimes u_j)^{\mathsf T}, \qquad c,e\ \text{uniform in }\mathbb F^b,\quad j\ \text{uniform in }[m], \tag{21}\] with the three choices independent. This law is invariant under multiplication by a nonzero scalar, and under simultaneous permutations of block rows and block columns. It may have an atom at zero. Write \(\mathsf T f(A)=\mathbb E_{h\sim\mathsf D}f(A+h)\), and give \(G\) uniform measure \(\mu\).

The internal-edge estimate below is the usual centered-indicator spectral calculation; see Alon and Chung (Alon and Chung 1988, Lemma 2.3). We prove the eigenvalue bound for this particular matrix walk directly.

Our field oracle will be a function \(P:G\to\mathbb F\). Its binary encoding has positions \[\mathcal S=G\times\mathbb F^*,\qquad y_{(A,\sigma)}=\ell(\sigma P(A)).\] The vector of all \(q-1\) masks determines \(P(A)\) uniquely by the same nondegenerate pairing. Any field query below is implemented by querying all these masks and rejecting unless they are the encoding of a field element.

Choose a uniformly ordered tuple of four distinct times \(t_1,t_2,t_3,t_4\in\mathbb F\), an independent uniform \(A\in G\), an independent \(h\sim\mathsf D\), and an independent uniform \(\sigma\in\mathbb F^*\). Put \[ s_i=(A+t_i h,\sigma\alpha_i),\qquad \alpha_i=\left(\prod_{j\ne i}(t_i-t_j)\right)^{-1}. \tag{23}\] This law is exchangeable and each marginal is uniform. If the restriction of \(P\) to every sampled line is a polynomial of degree at most two, Lagrange interpolation gives \(\sum_i\alpha_iP(A+t_i h)=0\); applying \(\ell(\sigma\,\cdot)\) gives the required binary parity identity.

Choose the field and pencil so that \[ \lambda_1<10^{-6},\qquad \max\{\lambda_1,2/(q-3)\}\leq\lambda,\qquad \frac6{q-1}\leq\frac1{16}. \tag{24}\] These are fixed choices. On two independent copies of the bit space, the pair operator is the tensor square. Decomposing each factor into constants and mean-zero functions shows that its nonconstant norm is at most the same bound. This proves the final assertion of Theorem 4 once the promised line-polynomial assignment is constructed.

Boolean tables and polynomial slack

Evaluation codes formed from spans of matrix minors were studied by Beelen, Ghorpade, and Høholdt as affine Grassmann codes (Beelen et al. 2010). Here we use principal minors to extend Boolean tables, and products of two minors to retain quadratic restrictions on the chosen rank-one lines.

Let \(T\) be the principal matrix on the first three blocks, and put \(n=3d\). For \(I\subseteq[n]\), define \(p_I(T)=\det T_{I,I}\), including \(p_\varnothing=1\). On a Boolean diagonal \(T=\mathop{\mathrm{diag}}(z)\) these are the monomials \(\prod_{i\in I}z_i\). Every table on \(\{0,1\}^n\) has a unique expansion in these monomials: at the indicator of a set \(J\), its value is \(\sum_{I\subseteq J}a_I\), which determines the coefficients successively by increasing \(|J|\). We extend a Boolean table to matrices by replacing its monomials by the corresponding principal minors.

For each \(a=(a_1,a_2,a_3)\in\{0,1\}^3\), let \(E_a(T)\) be the public extension of the following table on triples of addresses. It equals one if the input contains a clause on that ordered triple whose falsifying answer pattern is \(a\), and zero otherwise. Multiple clauses and repeated variables cause no change to this definition.

There is one assignment field \(X\), required to depend only on the first diagonal block. For \(i=1,2,3\), let \(\pi_i\) simultaneously swap block one with block \(i\) in rows and columns, with \(\pi_1\) the identity, and write \(X_i(A)=X(\pi_i A)\). For each \(a\) define \(M_{a,i}=X_i\) when \(a_i=1\) and \(M_{a,i}=1-X_i\) when \(a_i=0\). Introduce gate fields \(Y_a,Z_a\). On Boolean diagonal \(T\) we want \[ X^2-X=0,\qquad Y_a-E_aM_{a,1}=0,\qquad Z_a-M_{a,2}M_{a,3}=0,\qquad Y_aZ_a=0. \tag{25}\] There are \(25\) identities. In a satisfying assignment, extend the assignment table to \(X\) using the first block. Extend the Boolean tables \(E_aM_{a,1}\) and \(M_{a,2}M_{a,3}\) to \(Y_a,Z_a\) using \(T\). Every left side of Equation 25 is then a linear combination of products \(p_Ip_J\), and vanishes on all Boolean diagonals. For the last identity, simultaneous nonzero values would exhibit the forbidden pattern of a clause.

We need to enforce these identities at uniform matrix arguments. The following explicit reduction supplies their slack.

Reserve two disjoint tag banks, each consisting of three new blocks. Let \(b_r(i)\) be the copy of address index \(i\) in bank \(r\in\{1,2\}\). For an arbitrary minor \(M(T)=\det T_{R,C}\), define \[\mathsf E^{(r)}_{ij}M(A) =\det A_{(R,b_r(i)),(C,b_r(j))},\] where the new row and column are appended to their respective lists. For the empty minor this is just the appended entry. If \(V\) is supported in the principal bank \(r\), the extended submatrix contains exactly one entry of that bank, its appended corner. Its corner cofactor is \(M\). Consequently, with \(\Delta_VL(A)=L(A+V)-L(A)\), \[ \Delta_V(\mathsf E^{(r)}_{ij}M) =V_{b_r(i),b_r(j)}M. \tag{29}\]

For each of the \(25\) identity differences, group the residual terms from Lemma 7 by the three forms in Equation 26. Construct three fields \(L_1,L_2,L_3\) as follows, summing with the same coefficients as the residuals: \[\begin{array}{c|c} \text{residual term}&\text{term placed in the field}\\ \hline cT_{ij}MN&c(\mathsf E^{(1)}_{ij}M)N\quad\text{in }L_1\\ cT_{ij}(T_{ii}-1)MN& c(\mathsf E^{(1)}_{ij}M)(\mathsf E^{(2)}_{ii}N) \quad\text{in }L_2\\ c(T_{ii}^2-T_{ii})MN& c(\mathsf E^{(1)}_{ii}M)N\quad\text{in }L_3. \end{array}\] Let \(v(T)\) copy the off-diagonal part of \(T\) into bank one, \(w(T)\) copy \(\mathop{\mathrm{diag}}(T)-I\) into bank two, and \(u(T)\) copy \(\mathop{\mathrm{diag}}(T)^2-\mathop{\mathrm{diag}}(T)\) into bank one. Here \(\mathop{\mathrm{diag}}(T)\) means the diagonal matrix retaining the diagonal entries of \(T\). These shifts belong to \(G\): copying a full block preserves membership in \(G_0\), and removing or replacing diagonal entries is allowed because every diagonal matrix belongs to \(G_0\). All these shifts leave \(T\) unchanged. Equation 29 therefore proves the identity \[ F(A)=\Delta_{v(T)}L_1(A) +\Delta_{v(T)}\Delta_{w(T)}L_2(A) +\Delta_{u(T)}L_3(A) \tag{30}\] for the honest difference \(F\). In addition, \(L_1,L_3\) are affine under all translations in bank one, and \(L_2\) is separately affine under translations in each bank. Indeed its first extended factor depends affinely on bank one and not on bank two, and its second factor has the reverse properties. Cross entries between a tag bank and the address indices do not change under principal-bank translations.

One oracle, a fixed list of tests, and completeness

The one assignment field, sixteen gate fields, and seventy-five slack fields are \(92\) fields altogether. Give each its own selector index, using one index in each of \(92\) fresh blocks. Together with the three address and six tag blocks, this uses \(101\) blocks. Every honest field constructed above is a linear combination of products of two arbitrary minors using address and tag indices only. For a field \(F\) with selector index \(s_F\), replace the first minor in each of its terms \(cMN\) by the minor with appended row and column \(s_F\). Sum all such packed terms over the \(92\) fields to obtain \(P\). If \(v_F\) is the unit diagonal matrix at \(s_F\), the corner-cofactor calculation gives \[ \Delta_{v_F}P=F. \tag{31}\] Terms belonging to another field omit \(s_F\) completely, so they make no contribution to this difference. The shift \(v_F\) belongs to \(G\).

Every minor of \(A+th\), with \(h\) as in Equation 21, is affine in \(t\). To see this, expand the determinant by multilinearity in columns. Terms using two perturbed columns vanish because those columns are proportional. Thus each packed product has line degree at most two, as does \(P\).

For an arbitrary oracle \(P\), use Equation 31 as the definition of all proof fields. The ordinary laws are:

1. The line law samples uniform \(A\) and \(h\sim\mathsf D\), queries \(P(A+th)\) for all \(t\in\mathbb F\), and checks degree at most two.

2. Each of the \(25\) laws checks Equation 30 at uniform \(A\), with its own three designated slack fields and the corresponding difference from Equation 25.

3. The assignment invariance law samples a uniform translation \(v\in G\) whose first diagonal block is zero, and checks \(X(A+v)=X(A)\) at uniform \(A\).

4. For each slack field and each bank in which it is required to be affine, let \(B_r\) be the subspace of \(G\) supported in that principal bank. Test \[ \Delta_w\Delta_vL(A)=0 \quad(v,w\text{ independent uniform in }B_r), \qquad \Delta_{av}L(A)=a\Delta_vL(A) \quad(v\text{ uniform in }B_r) \tag{32}\] at uniform \(A\), with a separate law for each fixed scalar \(a\in\mathbb F\).

Every displayed field value is evaluated through its selector difference and all masks. Queries are made even when a coefficient vanishes, keeping each law’s list length fixed.

All master-oracle query points have uniform marginals on \(G\). Translations and block swaps are bijections. The maps \(A\mapsto A+v(T(A))\), and the analogous tag shears, are bijections because they leave their source \(T\) fixed; subtraction of the same shift is their inverse. Their compositions with selectors have the same property. Bank-test parameters are independent of the uniform base. A fixed mask at a uniform base is at most \(q-1\) times uniform on \(\mathcal S\), so we may use \(B=q-1\).

The honest construction above satisfies every law identically and has line degree at most two. It therefore proves perfect completeness, including the auxiliary parity identity. The witness-dependent fields are used only to prove completeness; all public test laws are specified without knowing a satisfying assignment.

Deterministic correction of almost quadratic lines

The remaining issue is constant soundness. It is not enough for the identities to hold at most matrices, since the Boolean diagonals may be sparse. We first obtain exact line identities by correcting a small set. This is a local-to-global correction problem in the self-testing framework of Blum, Luby, and Rubinfeld (Blum et al. 1993). The modal interpolation and transverse-grid consistency argument in the point-filling step has precedents in polynomial self-testing (Gemmell et al. 1991; Rubinfeld and Sudan 1996). The next lemma proves the required correction statement for our restricted distribution of directions, with one common high-mass set of good directions.

Support gaps and exact bank affinity

Suppose now that every ordinary binary test law fails with probability at most \(\eta\). Decode the full mask vector to \(P(A)\) wherever it is valid, and choose \(P(A)\) arbitrarily otherwise. Acceptance of a binary test certifies both valid encodings at all its queried points and its field relation. Thus every decoded field law also fails with probability at most \(\eta\).

Let \(Q\) be a fixed upper bound on the number of master-field queries in a law, counting repetitions; for example \(Q=q+32\) suffices for the displayed list. Put \(\delta=\sqrt\eta\) and apply Lemma 8. Replacing \(P\) by \(P'\) increases any field-law failure probability by at most \(2Q\delta\), because each master query is uniform. Write \[ \tau=\eta+2Q\delta. \tag{34}\] Intersect the pullbacks of \(H\) under the three block permutations \(\pi_1,\pi_2,\pi_3\). Their common scalar-invariant direction set has missing mass at most \(K_{\rm sw}\delta\), with \(K_{\rm sw}=3\). Every fixed translate of every corrected proof field, and of every \(X_i\), has line degree at most two on this common set. Lemma 9, with the conservative degree bound six, gives the support lower bound \[ \kappa=1-K_{\rm sw}\delta-\frac6{q-1}-\lambda_1 \tag{35}\] for any nonzero discrepancy to which that degree bound applies.

First consider a fixed parameter in the assignment invariance test. Its discrepancy has degree at most two. If it is not identically zero, it fails on at least a \(\kappa\) fraction of bases. Hence at least a \(1-\tau/\kappa\) fraction of the tested translations preserve \(X\) identically. Those translations form an additive subgroup. A subgroup of a finite additive group with density greater than one half is the whole group, since otherwise one of its disjoint cosets has the same size. Thus the assignment invariance is exact provided \(\tau/\kappa<1/2\).

For a bank \(B_r\) and slack field \(L\), fix \(v\) and let \[W_v=\{w\in B_r: \Delta_vL(A+w)=\Delta_vL(A)\text{ for every }A\}.\] This is the translation stabilizer of the function \(\Delta_vL\), hence a subgroup. Each fixed \((v,w)\) discrepancy has line degree at most two. The fraction of pairs for which it is not identically zero is at most \(\tau/\kappa\). If \(\tau/\kappa<1/16\), Markov’s inequality leaves more than three quarters of \(v\) for which more than three quarters of \(w\) are valid. For these \(v\), \(W_v=B_r\). The set \[V=\{v\in B_r:\Delta_vL\text{ is invariant under all }B_r \text{ translations}\}\] is also a subgroup. Indeed, for \(u,v\in V\), the difference cocycle gives \[\Delta_{u+v}L(A) =\Delta_uL(A+v)+\Delta_vL(A) =\Delta_uL(A)+\Delta_vL(A),\] and \(\Delta_{-v}L(A)=-\Delta_vL(A-v)=-\Delta_vL(A)\). Thus \(V=B_r\), and the map \(v\mapsto\Delta_vL(A)\) is additive for every \(A\).

For each fixed scalar \(a\), the map \(v\mapsto(\Delta_{av}L(A)-a\Delta_vL(A))_{A\in G}\) is now additive. Its kernel has density at least \(1-\tau/\kappa>1/2\) by that scalar’s test and the support gap, and so equals \(B_r\). This proves exact \(\mathbb F\)-affinity in each required bank. There are only \(q\) scalar laws, with \(q\) fixed. The argument has exactified whole translation laws before introducing a basis of any bank.

We may now expand the shifts in Equation 30. For bases \((e_i)\) and \((f_j)\) of the two banks, exact separate affinity gives \[ \Delta_{v(T)}\Delta_{w(T)}L(A) =\sum_{i,j}v_i(T)w_j(T)\Delta_{e_i}\Delta_{f_j}L(A). \tag{36}\] Each coefficient function on the right is a fixed combination of translates of a selector difference of \(P'\), so has line degree at most two. The coordinates of \(v(T)\) and \(w(T)\) have degree at most one on an \(A\)-line. The corresponding coordinates of \(u(T)\) have degree at most two. The one-bank expansions have the same form with one fixed difference. Thus every slack term has line degree at most four. The main field products have degree at most four, and every public principal minor has degree at most one. The number of coefficients in Equation 36 does not affect the degree of their sum; every coefficient identity is already exact.

Every full identity discrepancy therefore has degree at most four on the common good directions and fails on at most a \(\tau\) fraction of bases. If \(\tau<\kappa\), the support gap forces it to vanish identically. On Boolean diagonal \(T\), the shifts \(v(T)\) and \(u(T)\) are zero. Both single differences and the mixed difference with \(v(T)=0\) therefore vanish, regardless of \(w(T)\), and Equation 25 holds exactly. Every triple of Boolean addresses is available because \(G_0\) contains all diagonal matrices. Exact invariance makes \(X\) a well-defined function of its first block alone. The Booleanity identity assigns a bit to each Boolean address, and the gate identities exclude every falsifying clause pattern: if all three assigned bits matched a forbidden pattern, then \(E_a=M_{a,1} =M_{a,2}=M_{a,3}=1\), forcing \(Y_a=Z_a=1\) and contradicting \(Y_aZ_a=0\). This is a satisfying assignment to the input formula.

All required smallness conditions follow from a single fixed choice. With Equation 24 in force, put \[d_0=\min\left\{\frac{\gamma}{16}, \frac1{16K_{\rm sw}},\frac1{128(1+2Q)}\right\}, \qquad 0<\eta\leq d_0^2.\] Then Equation 33 holds, \(\kappa\geq1-1/16-1/16-\lambda_1>1/2\), and \(\tau\leq(1+2Q)\sqrt\eta\leq1/128\). In particular \(\tau/\kappa<1/16\) and \(\tau<\kappa\). No bound contains \(d\) or \(|G|\). An unsatisfiable formula must therefore have a law failing with probability greater than this \(\eta\).

Finally, the space \(G\) has size \(q^{O(d)}=2^{O(d)}\), and all test samplers enumerate fixed products of this space, fixed finite fields, and the \(O(d)\)-length pencil. Public table interpolation uses at most \(2^{3d}\) addresses and elementary linear algebra. Every arithmetic operation has polynomial bit complexity; seed probabilities are rational products of the reciprocals of these polynomial-size spaces. Query arity, number of laws, and all mask counts are constants. The pencil construction itself takes \(2^{O(d)}\) time by Lemma 2. These observations prove the size and sampler assertions and complete the proof of Theorem 4.

The primitive types

Use Theorem 4 with pair bound \(\lambda\leq10^{-6}\). There are two basic literal types: \[L_i^a(y)=\mathbf 1_{\{y_i=a\}}, \qquad L_{i,j}^a(y)=\mathbf 1_{\{y_i+y_j=a\}},\] where \(i\) is uniform in \(\mathcal S\), \((i,j)\) is uniform in \(\mathcal S^2\), and the target \(a\in\mathbb F_2\) is an independent uniform bit. Both calibrations are \(1/2\).

We use three even-parity tuple experiments:

1. Four base expressions \(y_{i_1},\ldots,y_{i_4}\), with \((i_1,\ldots,i_4)\) from the auxiliary law of Theorem 4.

2. Four sum expressions \(y_{i_1}+y_{j_1},\ldots,y_{i_4}+y_{j_4}\), using two independent copies of that auxiliary law.

3. The three expressions \(y_i,y_j,y_i+y_j\), for independent uniform \(i,j\).

For each experiment of length \(k\in\{3,4\}\), independently sample a uniform even-parity target vector \(a\in\mathbb F_2^k\). Add the type of the match event \[M(y)=\mathbf 1_{\{(\text{the }k\text{ expressions at }y)=a\}}\] and the type of its complement \(\overline M=1-M\). Their calibrations are \(2^{-(k-1)}\) and \(1-2^{-(k-1)}\). For each occurrence, add the comparisons \[ M\subseteq L^{a_\ell}, \qquad L^{1-a_\ell}\subseteq\overline M \tag{38}\] with the questions and targets sampled in that experiment. Their literal marginals are the basic base or sum type, since each target coordinate is uniform and independent of the questions. In the perfect assignment all three response tuples have even parity, so exactly one of the \(2^{k-1}\) targets matches.

For each ordinary law in Theorem 4, let its arity be \(L\) and let \(T_e\) be its acceptance predicate for public seed \(e\), with questions \(i_1,\ldots,i_L\). Independently choose \(a\in\mathbb F_2^L\) uniformly and add the match-and-pass event \[ R_{e,a}(y)=T_e(a)\prod_{\ell=1}^L L_{i_\ell}^{a_\ell}(y), \qquad p_s=2^{-L}. \tag{39}\] It has the stated calibration in the perfect assignment, which passes every seeded test. Compare it to each containing literal \(L_{i_\ell}^{a_\ell}\), and include the induced literal marginal as a type of calibration \(1/2\). These additional question marginals are at most the fixed factor \(B\) times uniform. If the seeded test rejects \(a\), Equation 39 is the constant-zero predicate.

Finally include the two constant types and, for every type \(P_s\), the comparison \((R,1)\) with \(R\sim P_s\). This specifies all data in Lemma 11. The finite sampling and arity properties follow from Theorem 4, since all products and target spaces have fixed size. We prove its unsatisfiable-instance assertion next.

A quantitative tag–dictator dichotomy

Suppose \(H\) satisfies Equation 37. For either the base or sum question space, write \[B(q,a)=2H(L_q^a)-1\in\{-1,1\},\qquad b(q)=\frac{B(q,0)+B(q,1)}2.\] A question is a tag when its two signs agree, in which case \(b(q)=\pm1\); otherwise it is a dictator, with \(b(q)=0\). Let \(\delta\) be the tag fraction. Literal calibration gives \(|\mathbb Eb|\leq2\zeta\), and \(\mathbb Eb^2=\delta\).

Consider its four-occurrence experiment and a uniform even target vector, and put \(B_\ell=B(q_\ell,a_\ell)\). Distinct target bits are independent. The question pair operator has norm at most \(\lambda\), also for sums by the tensor assertion of Theorem 4. Hence, for \(\ell\ne r\), \[ \mathbb EB_\ell B_r =\mathbb Eb(q_\ell)b(q_r) \leq4\zeta^2+\lambda\delta. \tag{40}\] The first comparisons in Equation 38 give \[\mathbb P[B_1=\cdots=B_4=1]\geq\frac18-5\zeta.\] For the second comparisons, the event \(H(\overline M)=0\) has probability at least \(1/8-\zeta\), and outside the four comparison failures all opposite literals have value zero. Complementing all four target bits preserves the uniform even-target law. Therefore \[\mathbb P[B_1=\cdots=B_4=-1]\geq\frac18-5\zeta.\] The squared sum of four signs is \(16\) on these two constant-sign vectors, \(4\) when their product is negative, and zero otherwise. Combining this identity with Equation 40 gives, for \(\zeta\leq1\), \[ \mathbb P[B_1B_2B_3B_4=-1]\leq 3\lambda\delta+40\zeta+12\zeta^2 \leq3\lambda\delta+52\zeta. \tag{41}\]

When some but not all questions are tags, the product of the four signs contains the product of a nonempty proper subset of the target signs. Under uniform even targets that product is an unbiased sign. Thus negative product has conditional probability one half. On the other hand, the probability that the first question is a tag and the second is not is at least \(\delta(1-\delta)-\lambda\delta\), by the pair-operator bound applied to the tag indicator. Consequently \[\delta(1-\delta)\leq7\lambda\delta+104\zeta.\] For \(\lambda\leq1/28\), if \(\delta\leq1/2\) this implies \(\delta\leq416\zeta\), and if \(\delta>1/2\) it implies \(1-\delta\leq7\lambda+208\zeta\). We have proved \[ \delta\leq416\zeta \quad\text{or}\quad 1-\delta\leq7\lambda+208\zeta \tag{42}\] for each of the two basic literal types.

The tag regime is impossible

We give explicit error bounds for this step. Assume \(\lambda\leq10^{-6}\) and \(\zeta\leq10^{-8}\), and suppose the base literal type is in the second regime of Equation 42. Put \[e_0=7\lambda+208\zeta,\qquad h_0=e_0+2\zeta,\qquad D_0=3e_0+6\zeta.\] Extend the base tag sign arbitrarily to a sign \(b_i\) on all of \(\mathcal S\). The non-tag fraction is at most \(e_0\), so \(|\mathbb Eb_i|\leq h_0\). If \(r_s=\mathbb P[b_i=s]\) for \(s=\pm1\), then \(|r_s-1/2|\leq h_0/2\) and \(r_s^2\leq1/4+h_0\).

In the triple experiment, match calibration and its three containing-literal comparisons give an all-positive literal-sign vector with probability at least \(1/4-4\zeta\) under even targets. Complement calibration and the opposite-literal comparisons give an all-negative vector with the same lower bound under the complemented, now odd, target law. Outside the event that one of the two base questions is not a tag, of probability at most \(2e_0\), these occurrences require \(b_i=b_j=1\) and \(b_i=b_j=-1\), respectively. The sum target is a uniform bit under both target laws, independent of \(i,j\). Subtracting these lower bounds from the respective masses \(r_s^2\) yields \[ \mathbb P_{i,j,a}\bigl[b_i=b_j=s,\ B((i,j),a)\ne s\bigr] \leq h_0+4\zeta+2e_0=D_0, \qquad s=\pm1. \tag{43}\] If a sum question is not a tag of sign \(s\), at least one of its two targets has sign different from \(s\). Thus \[\mathbb P_{i,j}[b_i=b_j=s,\ (i,j)\text{ is not a tag of sign }s] \leq2D_0.\] Since \(r_+^2+r_-^2\geq1/2\), the sum tag fraction is at least \(1/2-4D_0>416\zeta\). Its dichotomy in Equation 42 therefore also gives non-tag fraction at most \(e_0\).

Let \(v(i,j)\) be the sum tag sign, extended to the remaining pairs by a fixed sign. We take a symmetric extension: the literal predicates for \((i,j)\) and \((j,i)\) are equal, so the actual tag statuses and tag signs are already symmetric. In particular \[ \mathbb P[b_i=b_j=s,\ v(i,j)\ne s]\leq2D_0. \tag{44}\] For two independent auxiliary four-tuples \(\boldsymbol i\) and \(\boldsymbol j\), Equation 41 and the at-most \(4e_0\) chance of a non-tag sum question imply \[ \mathbb P\left[\prod_{\ell=1}^4v(i_\ell,j_\ell)=-1\right] \leq E_4:=3\lambda+52\zeta+4e_0. \tag{45}\] Exchangeability permits swapping \(j_1\) and \(j_2\) without changing this bound. Where both fourfold products are positive, cancellation of their last two factors gives \[v(i_1,j_1)v(i_2,j_2) =v(i_1,j_2)v(i_2,j_1).\] Thus this rectangle identity fails with probability at most \(2E_4\) when \((i_1,i_2)\) and \((j_1,j_2)\) are independent copies of the auxiliary pair marginal.

We next replace both pair marginals by independent uniform draws. For fixed \(i,i'\), set \(f(j)=v(i,j)v(i',j)\). The pair-operator bound gives \[\abs{\mathbb E_{\rm pair}f(j)f(j')-(\mathbb Ef)^2} \leq\lambda\mathop{\mathrm{Var}}(f)\leq\lambda.\] This changes the expectation of the rectangle sign by at most \(\lambda\). After replacing the \(j\) pair, apply the same calculation to the \(i\) pair with \(j,j'\) fixed. The rectangle sign has therefore changed in expectation by at most \(2\lambda\). Its failure probability for four independent uniform indices is at most \[ R_0:=2E_4+\lambda. \tag{46}\]

Average over an independent reference pair \((i_0,j_0)\) and fix one for which the rectangle failure probability over \(i,j\) is at most \(R_0\). Define \[u(i)=v(i,j_0),\qquad w(j)=v(i_0,j)v(i_0,j_0).\] Then \(\mathbb P[v(i,j)\ne u(i)w(j)]\leq R_0\). Symmetry of \(v\) gives \(\mathbb P[u(i)w(j)\ne u(j)w(i)]\leq2R_0\). Equivalently, the signs \(a(i)=u(i)w(i)\) at two independent indices disagree with probability at most \(2R_0\). Choose the majority sign \(c\) of \(a\). If its minority mass is \(m\leq1/2\), the disagreement probability is \(2m(1-m)\geq m\), so \(m\leq2R_0\). Therefore \(w(i)=cu(i)\) outside a set of mass at most \(2R_0\), and \[ \mathbb P[v(i,j)\ne c\,u(i)u(j)]\leq3R_0. \tag{47}\]

Take the base-sign class \(s=-c\). Since \(h_0<1/2\), it has mass \(r_s\geq1/4\). On two independent draws from this class, the probability that \(u(i)u(j)=1\) is at least one half: if the conditional positive mass of \(u\) is \(a\), this probability is \(a^2+(1-a)^2\geq1/2\). Consequently \[\mathbb P[b_i=b_j=s,\ c\,u(i)u(j)\ne s]\geq r_s^2/2\geq1/32.\] Equations 44 and 47 upper-bound the same probability by \(2D_0+3R_0\). But direct substitution gives \[2D_0+3R_0=231\lambda+6564\zeta<1/32\] under the stipulated bounds. The other inequalities used above, \(h_0<1/2\) and \(1/2-4D_0>416\zeta\), follow from the same bounds. This contradiction excludes the base-tag regime. We conclude \[ \mathbb P_i[i\text{ is not a dictator}]\leq416\zeta. \tag{48}\]

Decoding the ordinary tests

At each dictator question \(i\), assign the unique bit \(y_i\) whose literal has \(H(L_i^{y_i})=1\); assign arbitrary bits to the other questions. This is one assignment on \(\mathcal S\), because \(H\) is a function of the actual predicates. For an ordinary law of arity \(L\), its probability of querying any non-dictator is at most \(416LB\zeta\) by Equation 48 and the marginal bound. Its \(L\) containing-literal comparisons fail with total probability at most \(L\zeta\) in the seed-and-target experiment. The constant-zero type has \(H(0)=0\), since \(\zeta<1\).

Outside these two bad events, if \(H(R_{e,a})=1\) in Equation 39, all targets agree with the assigned bits and \(T_e(a)=1\). Conversely, an independent uniform target equals the assigned response vector with probability exactly \(2^{-L}\), even with repeated questions. It follows that \[2^{-L}-\zeta \leq \mathbb EH(R_{e,a}) \leq 2^{-L}\mathbb P_e[T_e(y_{i_1},\ldots,y_{i_L})=1] +(416LB+L)\zeta.\] Thus the failure probability of this law is at most \[2^L(1+L+416LB)\zeta.\] There are only finitely many ordinary laws. Choose the fixed \(\zeta\leq10^{-8}\) small enough that this expression is at most \(\eta/2\) for each of them, where \(\eta\) is the soundness constant of Theorem 4. In an unsatisfiable instance this contradicts that theorem. This completes the proof of Lemma 11.

For the next section, fix any positive mixture weights \((\omega_s)_s\) with \(\sum_s\omega_s=1\), for example equal weights, and let \(P_*=\sum_s\omega_sP_s\), retaining the type as sampling data. Put \[ p_*=\sum_s\omega_sp_s. \tag{49}\] The two constant types imply \(0<p_*<1\). All these quantities are fixed independently of the instance size. Equal predicates in different types remain the same argument of a valuation; only their sampling probabilities differ.

Demand and random half-freezing

Let \(M\) be a positive integer. Stage \(j\) contains \(n_j\) slots, where \(n_j\) is even. Choose a positive rational coefficient satisfying \[ \frac1{\sqrt{pMn_j}}\le s_j\le\frac2{\sqrt{pMn_j}},\qquad s_j\le1. \tag{76}\] All stage sizes will be chosen below. In each slot independently sample a primary presentation \(\mathcal R_i\) of an iid conjunction \(r_i\) and an independent amplitude with law \[\lambda=\tfrac12\delta_0+\tfrac12\operatorname{Unif}[-1,1].\] The demand score and its law are \[B^0=\sum_{j=1}^M s_j\sum_{i\text{ in stage }j}a_i r_i, \qquad \mu=\operatorname{Law}(B^0).\] At a perfect witness \(x\), each summand is symmetric, centered, and bounded by one, with variance \(s_j^2p/6\). Consequently \[\frac16\le\mathop{\mathrm{Var}}(B^0(x))\le\frac23,\qquad \mathbb EB^0(x)^4 \le\sum_{j,i}\mathbb E(s_ja_ir_i(x))^2+3\mathop{\mathrm{Var}}(B^0(x))^2<4.\] For \(X=B^0(x)\), Cauchy–Schwarz gives \[\mathbb P(|X|\ge1/4) \ge\frac{(\mathbb EX^2-1/16)^2}{\mathbb EX^4} \ge\frac{25}{9216}.\] Symmetry splits this probability equally between the two required tails.

Set \(\rho=1/(2048T_0^2)\). Include the form with weight \(16T_0\) that compares \(B^0\) with \(B^{0,\rho}\), obtained by independently resampling each complete primary slot with probability \(\rho\). Its truth cost is at most \[16T_0\sqrt{2\rho\mathop{\mathrm{Var}}(B^0(x))} \le16T_0\sqrt{4\rho/3}=1/\sqrt6<1.\] Throughout the soundness proof suppose, for a contradiction, that \[ 0<\nu=\mathop{\mathrm{Var}}(h(B^0)),\qquad \mathcal D(h)\le T_0\nu. \tag{77}\] In particular, \[ \mathbb E|h(B^0)-h(B^{0,\rho})|\le\nu/16. \tag{78}\]

Independently choose a uniform half of the slots in each stage to freeze. Let \(F_j\) be that half, \(I_j\) its complement, and \(F=\bigcup_jF_j\). The information \(\mathcal Z\) consists of the freeze sets and all complete primary variables in frozen slots. Let \(\mathcal B\) add to \(\mathcal Z\) the primary presentations of all unfrozen slots, but none of their amplitudes. Define, for \(i\in I_j\), \[s_jb_i^0=\mathbb E[h(B^0)\mid\mathcal B,a_i]-\mathbb E[h(B^0)\mid\mathcal B], \qquad g_i^0=\mathbb E[b_i^0\mid\mathcal Z,\mathcal R_i,a_i].\] Indices in such formulas are fixed after the freeze sets are specified. For any family \(b=(b_i)\) put \[\|b\|_\Sigma^2=\mathbb E\sum_j s_j^2\sum_{i\in I_j}|b_i|^2.\]

We must turn this amplitude signal into the response on actual conjunction predicates required by Lemma 12. We will first construct a real response, bound its size under each type pattern, and control its decrease when \(r\) is replaced by a containing predicate \(r'\). Three kinds of comparison path provide these estimates. Paths between opposite contributions of one conjunction bound the response under each pattern; paths using \(r\le r'\) control its order; paths through the random-amplitude contribution carry the signal to that response. The comparison measures sample their path orientations independently of the lookup. A common orientation extracted from the lookup will enter only the analysis. The estimates must retain errors proportional to \(\nu\) throughout, so that thresholding the response can meet the rare-event criterion even when the cut variance is arbitrarily small.

The order of the constants

We first fix the signal-loss tolerance \(e\), the clipping bound \(B_*\), and the signal threshold \(\gamma\), together with the resulting inputs \(b_0,K_0,B_0\) to Lemma 12. Choose rational constants \[ \begin{gathered} c_1=c/4,\quad 0<e\le c/160000,\quad B_*\ge\max(1,3200(T_0+1)/c),\quad K_*=32(T_0+2),\\ 0<\gamma\le c_1/(16K_*),\quad b_*=c_1/(128B_*^2),\quad b_0=b_*/[8(T_0+1)],\quad K_0=16/\gamma,\quad B_0=B_*. \end{gathered} \tag{82}\] These constants have no dependence on conjunction length. Apply Lemma 12 to \(b_0,K_0,B_0\) and choose its length \(t\) and tolerance \(\varepsilon>0\). We can decrease \(\varepsilon\) to make it rational. From now on \(p=p_*^t\) is fixed. Let \(V\) be the number of fixed type patterns together with the iid conjunction law, and let \(Q\) be the number of required ordered conjunction couplings, counting the changed coordinate. Our path menu below has \(L=V+2Q+2\) entries. Set \(A_t=16V+80Q\), and choose rational \(\Delta>0\) so small that \[ \Delta\le b_*p\gamma/160,\qquad \left(\frac{16p}{\gamma\varepsilon}+1\right) \frac{A_t\Delta}{\gamma}\le b_*p/4. \tag{83}\] Choose an integer \[ M\ge\frac{32B_*K_*(T_0+3)}{c_1\Delta}. \tag{84}\] The remaining parameters are chosen sequentially in Subsection 6.5. This order will be justified by estimates whose constants are independent of the later stage sizes.

Paths, replacements, and formal cells

Start with the one-cell partition \(C_0\) of the assignment cube. At stage \(j\), given the preceding partition \(C_{j-1}\), use these path laws \(D^-\longrightarrow D^+\) for a sign function \(\tau\) constant on its cells:

1. \(-\tau r\longrightarrow+\tau r\) for each of the \(V\) vertical laws;

2. \(+\tau r\longrightarrow+\tau r'\) and \(-\tau r'\longrightarrow-\tau r\) for each ordered pair \(r\le r'\);

3. \(-\tau r\longrightarrow ar\) and \(ar\longrightarrow+\tau r\), where \(r\) is iid and \(a\sim\lambda\) is fresh.

Every endpoint has absolute value at most one, and every coordinate of \(\tau(D^+-D^-)\) is nonnegative. All predicates and any amplitude in a path are fresh samples from its specified law.

Independently in each unfrozen slot of stage \(j\), retain the primary summand with probability \(1-\alpha_j\); call this choice shared. Otherwise draw a uniform menu entry, its fresh path data, a uniform descriptor \(\tau\in\{-1,+1\}^{J_{j-1}}\), a uniform time \(u\in[0,1]\), and a fair sign \(\chi\in\{-1,+1\}\). Replace that slot by \[s_j\chi[(1-u)D^-+uD^+].\] Here \(J_{j-1}\) is the number of formal cells at the preceding level. The score after all replacements through stage \(j\) is \(B^j\); future slots and frozen slots still have their primary summands.

Construct \(C_j\) by refining \(C_{j-1}\) with all queried positions in the current unfrozen primary presentations, including those in replaced slots, and all queried positions in the current fresh paths. Use fixed orders and pad each list to a deterministic length with coordinates whose value is identically zero. Retain all formal binary cells, including inconsistent and empty ones. Thus \(J_j\) is a deterministic constant once the sizes through stage \(j\) are fixed. A descriptor defines the indicated sign function on actual cells; values on empty cells do not matter. This construction inspects neither amplitudes, times, nor signs when forming the partition after its question lists are known. Frozen and future query lists do not enter \(C_j\).

The whole experiment first draws primary samples and freeze sets, then performs these independent stage trials given the preceding partitions. Trials use no lookup and no analytic reference signs. Although a reference sign defined below can depend on future primary summands, it never enters the generative history.

At truth, conditional on frozen variables and earlier actual trials, the current summand differences are independent and centered. Their second moments are at most \(4s_j^2\alpha_j\). Thus \[ \mathbb E|B^j(x)-B^{j-1}(x)| \le\delta_j:=4\sqrt{\alpha_j/(pM)}. \tag{85}\] For each \(j\), let \(S_j\) be the first \(m_j\) indices of \(I_j\) in their fixed order. Delete their current summands from \(B^j\) to obtain \(B_\circ^j\), and delete only slot \(i\) to obtain \(B^j_{\neg i}\). Conditional on the other summands and preceding history, these deleted bases do not use the variables in the deleted slots. The single-slot deletion will provide the background for varying that slot’s predicate. Deleting all of \(S_j\) will let us choose one orientation, from the remaining score and preceding partitions, for every tested slot.

Smoothing and the comparison measures

For \(\xi>0\) use the probability density \[f_\xi(a)=\frac{15}{16\xi}(1-a^2/\xi^2)^2\mathbf 1_{[-\xi,\xi]}(a).\] It is even, continuously differentiable after extension by zero, and decreasing on \([0,\xi]\). Direct integration gives \[ \int|f_\xi'|=\frac{15}{8\xi},\qquad \int_0^\xi 2b[-f_\xi'(b)]\,\mathrm db=1. \tag{86}\] For every \(z\in C_\ell\), let \(\theta_{\ell,z}\) have this density with scale \(\xi_\ell\), independently. Put \(\Theta_\ell=\sum_{z\in C_\ell}\theta_{\ell,z}\mathbf 1_z\) and \(\Theta_{\le j}=\sum_{\ell=0}^j\Theta_\ell\). With partitions fixed, set \[h_j(B)=\mathbb E_\theta h(B+\Theta_{\le j}),\qquad K_{j,z}(B)=\left.\frac{\partial}{\partial a} h_j(B+a\mathbf 1_z)\right|_{a=0}.\] Translation of the last density proves continuous differentiability in all cell shifts, even for merely measurable \(h\). Indeed the translated density is continuously differentiable in \(L^1\), and \(h\) is bounded. Derivatives on empty cells vanish. Write \(K_j=K_j(B^j)\) and \(|K_j|_1=\sum_z|K_{j,z}|\). The map \(\pi\) sums fine coordinates on each parent cell. Define the common reference descriptor \[ \sigma^j=\operatorname{sign}K_{j-1}(B_\circ^j), \tag{87}\] with ties positive and using only partitions through level \(j-1\). It is common to every tested index in \(S_j\).

For each mode and formal descriptor, a match in a slot means replacement with that mode and descriptor and \(\chi=+1\). Its probability is \[\beta_j=\frac{\alpha_j}{2L2^{J_{j-1}}}.\] Mark a consistent cell in \(C_j\) if any of these conditions holds:

1. For some mode and descriptor, the match fraction in \(S_j\) exceeds \(2\beta_j\).

2. For some vertical mode and descriptor, the fraction in \(S_j\) of matches whose path predicate is one at the cell exceeds \(2\beta_jp_{\rm law}\).

3. The fraction in \(I_j\) that is shared and has primary predicate one at the cell exceeds \(2p\).

The first condition, if it occurs, marks every consistent cell. All these rules use actual query values and trial data, and do not use \(h\). Every descriptor is checked, so on an unmarked cell the empirical bounds also hold for the lookup-dependent descriptor \(\sigma^j\). They will bound match-weighted gradient sums without assuming that the fine gradient is independent of the match indicators. A separate comparison form below will charge for gradient mass on the marked cells. At a fixed perfect witness, condition on frozen data and earlier actual trials. Indicators in each count are independent over current slots. Plain matches have mean \(\beta_j\), vertical hit matches have mean \(\beta_jp_{\rm law}\), and shared hits have mean at most \(p\). For \(m\) independent indicators of mean \(b>0\), Chebyshev’s inequality bounds the probability that their average exceeds \(2b\) by \(1/(mb)\). A zero mean gives a zero count almost surely. If \(p_{\min}\) is the minimum positive vertical honest probability (including \(p\)), a union bound gives \[ \mathbb P(x\text{ lies in a marked cell}) \le\frac{2L2^{J_{j-1}}}{m_j\beta_jp_{\min}}+\frac2{n_jp}. \tag{88}\]

We now specify every additional raw form. All expectations below include the indicated score experiment; numerical noises are shared whenever their levels appear in both arguments.

For any set \(A\) of level-\(j\) cells, define \[N_j(B;A)=\mathbb E\sum_{z\in A}\int_0^{\xi_j}[-f_{\xi_j}'(b)] \big|h(B+\Theta_{\le j}^{z,+b}) -h(B+\Theta_{\le j}^{z,-b})\big|\,\mathrm db,\] where the superscript fixes only coordinate \((j,z)\) and all other noises are averaged. Translating the density and pairing \(b\) with \(-b\) gives \[K_{j,z}(B)=\int_0^{\xi_j}[-f_{\xi_j}'(b)] \mathbb E_{\rm other\ noises} [h(B+\Theta_{\le j}^{z,+b})-h(B+\Theta_{\le j}^{z,-b})]\,\mathrm db.\] Thus \(N_j\) dominates the expected variation on its tested cells. Its truth cost is at most the probability that the witness cell is in \(A\): all other coordinates contribute zero, and the contributing integral is one by Equation 86. Include \(N_M(B^M;C_M)\) with weight one and \(N_j(B^j;\text{marked cells})\) with weight \(T_0/a_j\), where \(a_j=\min(p,\Delta\beta_j)\).

For \(A=B^{j-1}\) or \(A=B_\circ^j\), include with weight \(T_0M\) the form \[P_j(A)=\mathbb E\sum_{z\in C_{j-1}} \int_{-\xi_{j-1}}^{\xi_{j-1}}|f_{\xi_{j-1}}'(b)| \big|h(B^j+\Theta_{<j}^{z,b}+\Theta_j) -h(A+\Theta_{<j}^{z,b})\big|\,\mathrm db.\] Here the fixed coordinate is \((j-1,z)\) and all other preceding noises have their usual law. Differentiating with respect to this preceding coordinate shifts all its children equally in the first term; its derivative is \((\pi K_j)_z\). The second derivative is \(K_{j-1,z}(A)\). Taking absolute values under the common integral proves \[\mathbb E|\pi K_j-K_{j-1}(A)|_1\le P_j(A).\] With \(\Lambda_{j-1}=15J_{j-1}/(8\xi_{j-1})\), its unweighted truth cost is at most \(\Lambda_{j-1}(\delta_j+\xi_j)\) for the first choice of \(A\), and \(\Lambda_{j-1}(m_js_j+\xi_j)\) for the second.

Include also the following ordinary coupled raw differences:

1. Compare \(B^0\) to \(B^j+\Theta_{<j}\), with weight \(T_0M/e\).

2. For uniform \(i\in I_j\) forced shared, compare \(B^j+\Theta_{\le j}\) to \(B^j+\Theta_{<j}\), with weight \(T_0/(e\,p\,s_j^2)\).

3. For each mode and each of its two endpoints, force uniform \(i\in S_j\) into that mode with independent uniform descriptor and \(\chi=+1\). Rebuild \(C_j\) using its fresh path data. For \(B=B^j_{\neg i}+s_jD^\pm\), compare \(B+\Theta_{\le j}\) to \(B+\Theta_{<j}\), with weight \(T_0/(s_j\Delta2^{-J_{j-1}})\).

The forced trial has its prescribed conditional law given earlier stages, and all other trials retain their ordinary laws. The primary presentation remains in the query list. The two last types of form have unweighted truth cost at most \(\xi_j\). The first has cost at most \(\sum_{k\le j}\delta_k+\sum_{\ell<j}\xi_\ell\).

All coefficients in these measures are nonnegative. Their laws use uniform descriptors; the lookup-dependent descriptor \(\sigma^j\) in Equation 87 occurs only in the analysis.

A sequential rational funding schedule

The schedule makes all comparison truth costs simultaneously small while retaining the variance-relative estimates needed below. Every choice uses only parameters already fixed.

Put \(\eta=1/[100M(L+1)]\) and \(d_{\rm cap}=\eta e/(4T_0M^2)\). Choose positive rational \(\xi_0\le d_{\rm cap}\). At stage \(j\), the numbers \(J=J_{j-1}\) and \(\Lambda=\Lambda_{j-1}\) are already known. Choose the following parameters in this order:

1. Choose rational \(0<\alpha_j\le\min(1/2,e)\) so small that \[\delta_j\le\min(d_{\rm cap},\eta/(2T_0M\Lambda)).\] Squaring the right-hand bound supplies a rational sufficient condition. Set \(\beta_j=\alpha_j/(2L2^J)\) and \(a_j=\min(p,\Delta\beta_j)\).

2. Choose an integer \[m_j\ge\frac{2T_0(2L2^J)}{\eta a_j\beta_jp_{\min}}.\]

3. Choose an even integer \[n_j\ge\max\left(2m_j,4k,\frac4{pM},\frac{4T_0}{\eta a_jp}, \frac{16T_0^2M\Lambda^2m_j^2}{\eta^2p}\right),\] and rational \(s_j\) satisfying Equation 76. Such a rational can be found between the two endpoints by rational interval refinement; the bound \(n_j\ge4/(pM)\) ensures \(s_j\le1\).

4. Choose rational \(\xi_j>0\) with \[\xi_j\le\min\left(d_{\rm cap},\frac\eta{2T_0M\Lambda}, \frac{\eta e p s_j^2}{T_0}, \frac{\eta s_j\Delta2^{-J}}{T_0}\right).\]

The marked form costs at most \(\eta\) by Equation 88: its two terms cost at most \(\eta/2\) each after multiplication by \(T_0/a_j\). Each projected-gradient form costs at most \(\eta\); for deletion use \(m_js_j\le\eta/(2T_0M\Lambda)\), which follows from the last lower bound on \(n_j\). Each forced form costs at most \(\eta\). The cumulative demand comparison costs at most \((T_0M/e)2Md_{\rm cap}=\eta/2\). There are \(5+2L\) tunable forms per stage, so their total truth cost is less than \(M(5+2L)\eta<1\). Together with resampling and final variation this is less than three, and in particular at most four. All earlier truth-cost estimates are uniform over the later primary backgrounds, so subsequent parameter choices preserve the allocated bounds.

The consequences of Equation 77 are \[ \begin{gathered} \mathbb E|K_M|_1\le T_0\nu,\qquad \mathbb E\sum_{z\text{ marked}}|K_{j,z}|\le a_j\nu,\\ \mathbb E|\pi K_j-K_{j-1}|_1\le\nu/M,\qquad \mathbb E|\pi K_j-K_{j-1}(B_\circ^j)|_1\le\nu/M,\\ \mathbb E|h(B^0)-h_{j-1}(B^j)|^2\le e\nu/M. \end{gathered} \tag{89}\] The square bound follows by averaging raw comparisons and using \(|u-v|^2\le|u-v|\) for \(u,v\in[0,1]\). In addition, \[ \mathbb E^{i\ {\rm uniform\ shared}} |h_j(B^j)-h_{j-1}(B^j)|\le e p s_j^2\nu, \tag{90}\] and each uniform-descriptor endpoint experiment satisfies \[ \mathbb E|h_j(B)-h_{j-1}(B)|\le s_j\Delta2^{-J_{j-1}}\nu. \tag{91}\]

Orientation and clipping

The comparison measures and all numerical parameters are now fixed. It remains to locate a stage at which a common amplitude signal survives the accumulated approximation and clipping errors.

Put \[U=\max_{0\le j\le M}\mathbb E[|K_j|_1\mid\mathcal B],\qquad v=\mathbb E[U\mid\mathcal Z].\] For each \(j\), let \(E_j=\mathbb E[|\pi K_j-K_{j-1}|_1\mid\mathcal B]\). The pointwise inequality \(|K_{j-1}|_1\le|K_j|_1+ |\pi K_j-K_{j-1}|_1\) gives \(U\le\mathbb E[|K_M|_1\mid\mathcal B]+\sum_jE_j\). Therefore \[ \mathbb EU=\mathbb Ev\le(T_0+1)\nu. \tag{92}\] Define \(d_{j,z}=|K_{j,z}|-\sigma^j_{\operatorname{par}(z)}K_{j,z}\ge0\). For vectors \(a,b\) and \(\sigma=\operatorname{sign}b\), \(|a|_1-\sigma\cdot a\le2|a-b|_1\). Applying this with \(a=\pi K_j\), \(b=K_{j-1}(B_\circ^j)\), and then the across-stage comparison, gives \[\sum_zd_{j,z}\le |K_j|_1-|K_{j-1}|_1 +|\pi K_j-K_{j-1}|_1 +2|\pi K_j-K_{j-1}(B_\circ^j)|_1.\] Summing and dropping \(-|K_0|_1\) proves \[ \sum_j\mathbb E\sum_zd_{j,z}\le(T_0+3)\nu. \tag{93}\] Call \(j\) good when its expected defect is at most \(\Delta\nu\).

Transferring the amplitude signal requires both smoothing levels. A current predicate \(r_i\) can split a cell of \(C_{j-1}\), so smoothing along the preceding cells need not permit differentiation in its direction. Fine smoothing \(h_j\) does: \(r_i\) is constant on every cell of \(C_j\). Its smoothing law, however, retains the current query partition and can depend on the predicate’s presentation. The coarse smoothing \(h_{j-1}\) omits that partition, while its score still contains the contribution of \(r_i\). Section 7 will use this omission to express the coarse amplitude projection through a common deleted-slot background, depending on the current presentation only through the actual predicate. We therefore preserve the coarse component as the source of the response and use the fine component for derivative estimates.

For \(i\in I_j\), define \(b_i\) as the centered amplitude component of \(h_{j-1}(B^j)\) divided by \(s_j\) under the experiment forcing \(i\) shared: \[s_jb_i=\mathbb E^{i,\rm sh}[h_{j-1}(B^j)\mid\mathcal B,a_i] -\mathbb E^{i,\rm sh}[h_{j-1}(B^j)\mid\mathcal B].\] Define \(b_i^+\) by replacing \(h_{j-1}\) with \(h_j\), and put \(g_i=\mathbb E[b_i\mid\mathcal Z,\mathcal R_i,a_i]\). Forcing shared does not alter the primary or freeze law. On replacement the score and partition ignore the primary amplitude \(a_i\). Thus the corresponding amplitude projection under the ordinary law is exactly \((1-\alpha_j)s_jb_i\). Conditional Bessel inequalities, applied at each stage to the last line of Equation 89, give \[\|((1-\alpha_j)b_i-b_i^0)_i\|_\Sigma^2\le e\nu.\] Since \(\alpha_j\le e\le1/2\) and \(\|b^0\|_\Sigma\le\sqrt\nu\), solving for \(b-b^0\) gives \[ \|b-b^0\|_\Sigma\le4\sqrt{e\nu},\qquad \|b^+-b\|_\Sigma\le\sqrt{2e\nu}. \tag{94}\] For the second bound, projection contraction in each forced experiment bounds \(s_j^2\mathbb E|b_i^+-b_i|^2\) by the expected squared difference of the two smoothed values. Sum over \(i\), use Equation 90, and use \(|I_j|s_j^2\le2/(pM)\).

Fine differentiation along the primary amplitude gives, for every \(a\), \[ |b_i^+(a)|\le\frac4{1-\alpha_j} \mathbb E\left[\mathbf 1_{\{i\ {\rm shared}\}} \sum_z|K_{j,z}|r_i(z)\,\middle|\,\mathcal B\right]\le8U. \tag{95}\] To check the first inequality, bound the centered amplitude value by the integral of absolute derivatives over the whole interval \([-1,1]\). The derivative of \(h_j\) along \(a\) is \(s_j\sum_zK_{j,z}r_i(z)\). The partition is fixed along this amplitude path. Lebesgue measure on \([-1,1]\) is bounded by \(4\lambda\), giving the factor four; conditioning a trial to be shared gives \(1/(1-\alpha_j)\). Average Equation 95 over \(I_j\). On unmarked cells the shared-hit fraction is at most \(2p\), and on marked cells at most one. Equations 89 and 92 imply \[ \mathbb E\operatorname{avg}_{i\in I_j}|b_i^+| \le16p(T_0+1)\nu+8p\nu\le K_*p\nu. \tag{96}\]

We now clip the fine component to obtain a bounded signal. Set \(A=\{U\le B_*,\ v\le B_*\}\), which is \(\mathcal B\)-measurable, and define \(\widetilde b_i=b_i^+\mathbf 1_A\) and \(\widetilde g_i=\mathbb E[\widetilde b_i\mid\mathcal Z,\mathcal R_i,a_i]\).

The conditional cap in Equation 79, even with its weaker upper bound one, and Markov’s inequality give \[\|b^0\mathbf 1_{A^c}\|_\Sigma^2 \le\mathbb P(A^c)\le2(T_0+1)\nu/B_*.\] Projection contraction, Equation 94, and the triangle inequality now give \[\begin{align*} \|\widetilde g-g^0\|_\Sigma &\le[6\sqrt e+\sqrt{2(T_0+1)/B_*}]\sqrt\nu, \tag{97}\\ \|\widetilde g-g\|_\Sigma &\le[10\sqrt e+\sqrt{2(T_0+1)/B_*}]\sqrt\nu. \tag{98}\end{align*}\] For every family \(q_i\), Equation 76 implies \[ \frac p2\|q\|_\Sigma^2 \le\operatorname{avg}_j\mathbb E\operatorname{avg}_{i\in I_j}|q_i|^2 \le2p\|q\|_\Sigma^2. \tag{99}\] The first bracket above is at most \(\sqrt c/25\) and the second at most \(\sqrt c/20\) by Equation 82. Using the amplitude signal and Equation 99, we obtain \[ \operatorname{avg}_j\mathbb E\operatorname{avg}_{i\in I_j} |\widetilde g_i|^2\ge c_1p\nu,\qquad \operatorname{avg}_j\mathbb E\operatorname{avg}_{i\in I_j} |\widetilde g_i-g_i|^2\le\tfrac1{10}c_1p\nu. \tag{100}\] Also \(|\widetilde g_i|\le8B_*\), its averaged first moment is at most \(K_*p\nu\) at each stage by Equation 96, and it vanishes when \(v>B_*\).

At most \((T_0+3)/\Delta\) stages are bad. Each contributes at most \(8B_*K_*p\nu\) to the unaveraged second moment of \(\widetilde g\). Equation 84 bounds their average contribution by \(c_1p\nu/4\). On \(|g_i|<\gamma\), the elementary inequality \[|\widetilde g_i|^2\le2\gamma|\widetilde g_i| +|\widetilde g_i-g_i|^2\] holds, as follows by expanding the last square and using \(|g_i|<\gamma\). Its average is at most \((1/8+1/10)c_1p\nu\). Thus at least \(c_1p\nu/2\) of the average second moment remains on good stages with \(|g_i|\ge\gamma\) and \(v\le B_*\). The bound \(|\widetilde g_i|^2\le64B_*^2\) proves that some good stage \(j\) satisfies \[ \mathbb P_{\mathcal Z,\,i\ {\rm uniform\ in}\ I_j,\,\mathcal R_i,a_i} (|g_i|\ge\gamma,\ v\le B_*)\ge b_*p\nu. \tag{101}\] We fix this stage for the rest of the analytic argument.

The deleted-slot background

Fix an exterior value \(\mathcal Z=z\). It fixes the freeze sets, the complete frozen variables, and the sets \(I,S\). Let \(Y_i=(\mathcal R_i,a_i)\) for \(i\in I\), with common law \(P_Y=P_{\mathcal R}\otimes\lambda\). Let \(X\) contain all unfrozen primary samples and actual trial variables at stages before \(j\), all future primary samples, and the fixed frozen contributions. It determines the preceding partition sequence \(C^-=C_{\le j-1}\) and the score \(B_{\rm out}\) contributed by slots outside \(I\) after earlier stages. It includes no analytic reference gradients or signs as inputs. Actual previous trials used only their preceding query partitions to interpret independent descriptors, so \(X\) is independent of the current unfrozen primary samples conditional on \(z\).

For a preceding partition sequence \(C\), write the current trial kernel as \[ q_C=(1-\alpha)\delta_{\rm shared} +\frac\alpha L\sum_{m=1}^L P_m(\,\mathrm dE)\operatorname{Unif}(\{-1,+1\}^{J})(\,\mathrm d\tau) \operatorname{Unif}[0,1](\,\mathrm du) \operatorname{Unif}\{-1,+1\}(\,\mathrm d\chi), \tag{102}\] where \(P_m\) is the fresh data law of mode \(m\), including its fresh amplitude if required. The descriptor in this formula is interpreted on \(C_{j-1}\). If \(T_i\) denotes the current trial, the exact conditional factorization is \[ P_z(\,\mathrm dX,\,\mathrm dY,\,\mathrm dT) =q_z(\,\mathrm dX)\prod_{i\in I} [P_Y(\,\mathrm dY_i)q_{C^-(X)}(\,\mathrm dT_i)]. \tag{103}\] This conditional-on-\(X\) product is the independence statement we use. After mixing over \(X\), no mutual independence of interpreted trials is needed.

Let \(V_C(Y_i,T_i)\) be the current slot summand, including its factor \(s\). Then \[B^j_{\neg i}=B_{\rm out}+\sum_{k\in I\setminus\{i\}}V_{C^-}(Y_k,T_k), \qquad B_\circ^j=B_{\rm out}+\sum_{k\in I\setminus S}V_{C^-}(Y_k,T_k).\] For every \(i\in I\), the pair \((B^j_{\neg i},C^-)\) uses none of \(Y_i\). Equation 103 shows that its conditional law given \(z\) is independent of the entire primary presentation and amplitude in that slot. This law is also the same for every \(i\in I\): permutations of these slots preserve the product law and send one deleted sum to another. Denote the common law by \(\kappa_z(\,\mathrm dB,\,\mathrm dC)\). The actual fine partition \(C_j\) is not a coordinate of this kernel.

Write \(\phi_C(B)\) for lookup smoothed through the preceding partition sequence \(C\). In the experiment forcing \(i\) shared, put \(F_i=\phi_{C^-}(B^j_{\neg i}+sa_ir_i)\), where \(r_i\) is the predicate represented by \(\mathcal R_i\). The definition of \(b_i\) and the tower property give \[s g_i=\mathbb E^{i,\mathrm{sh}}[F_i\mid\mathcal Z,\mathcal R_i,a_i] -\mathbb E^{i,\mathrm{sh}}[F_i\mid\mathcal Z,\mathcal R_i].\] Indeed \(\sigma(\mathcal Z,\mathcal R_i,a_i)\subseteq\mathcal B\vee\sigma(a_i)\), and \(a_i\) is independent of \(\mathcal B\); averaging the subtracted \(\mathcal B\)-conditional expectation therefore removes \(a_i\). Forcing shared preserves the law of the background. The projected response is consequently \[ s\,g_z(r,a)=\int\left[ \phi_C(B+sar)-\int\phi_C(B+sa'r)\,\mathrm d\lambda(a') \right]\,\mathrm d\kappa_z(B,C). \tag{104}\] It is a version of every \(g_i\), evaluated at the predicate represented by \(\mathcal R_i\) and at \(a_i\). It depends on the actual predicate \(r\), not its presentation. In particular \(g_z(0,a)=0\). An unused queried position in a zero-predicate presentation can change \(C_j\), but it cannot change Equation 104, which uses only the preceding partitions. Independent sampled predicates may have overlapping bit names; independence here concerns samples and does not require disjoint supports on the assignment cube.

For \(i\in S\), extend this background by \(\sigma=\operatorname{sign}K_{j-1}(B_\circ^j)\). The triple \((B^j_{\neg i},C^-,\sigma)\) still uses none of \(Y_i\) and is unaffected by changing \(T_i\). Its conditional law is common to all \(i\in S\), by permutations within \(S\); call it \(\kappa_z^S\). Its \((B,C)\) marginal is precisely \(\kappa_z\). This extended independence is asserted only for \(i\in S\). The sign can be correlated with the remaining background, and indices outside \(S\) can enter its definition.

Define the coarse width on any actual predicate \(r\) by \[ F_z(r)=\int\frac{\phi_C(B+s\sigma r)-\phi_C(B-s\sigma r)}s \,\mathrm d\kappa_z^S(B,C,\sigma). \tag{105}\] Fresh \(r\) is independent of this background. Averaging over uniform \(i\in S\) in the ordinary experiment is another description of this integral. Because its two amplitude terms ignore \(\sigma\), the same extended kernel also represents Equation 104. This supplies one common background for all three values at \(ar,-\sigma r,+\sigma r\).

Figure 1 records the two conditional laws and their common marginal.

Forcing a slot and rebuilding the fine state

Fix a mode \(m\) and an index \(i\in S\). Let \(\mathcal H_i\) contain \(z\), \(X\), every current primary pair \(Y_k\), and all current trials \(T_k\) except \(T_i\). In particular it retains \(Y_i\), whose original question list still enters the fine partition when its summand is replaced. The preceding partitions, \(B_\circ^j\), and \(\sigma\) are \(\mathcal H_i\)-measurable. The event \[E_i=\{T_i\text{ is replacement in mode }m, \ \tau_i=\sigma,\ \chi_i=+1\}\] has the exact conditional probability \[ \mathbb P(E_i\mid\mathcal H_i)=\frac\alpha{2L2^J}=\beta. \tag{106}\] The number of formal parent cells is deterministic; empty cells and colliding labels have not reduced \(J\). Conditional on \(E_i,\mathcal H_i\), the path data have their original mode law and \(u\) is independent uniform.

Let \(\Gamma(\mathcal H_i,T_i)\) construct the entire stage-\(j\) state, including the score and the fine partition rebuilt from all unchanged primary question lists and the trial’s new path question list. For every nonnegative measurable full-state function \(Q_0\), the forced experiment preserves the ordinary marginal law of \(\mathcal H_i\) and satisfies \[ \mathbb E_{\rm forced}[Q_0(\Gamma)\mid\mathcal H_i] =\mathbb E_{\rm actual} [Q_0(\Gamma)\mathbf 1_{E_i}/\beta\mid\mathcal H_i]. \tag{107}\] This is just conditional expectation under the event in Equation 106; it applies because the event constrains only the mode, descriptor, and sign. It also holds for integrable signed functions by subtraction. One may include independent numerical noises in \(\Gamma\), or integrate them in \(h_j\) first.

In particular the identity permits \(Q_0\) to depend on the new \(C_j\), its fine gradient, marks, and all current questions. There is no conditioning on \(C_j\) in Equation 106: that partition is an output of \(\Gamma\). Deleting the whole subbatch in \(B_\circ^j\) ensures that the reference sign stays fixed as \(T_i\) is redrawn. It is essential here that we do not retain the old trial’s fine partition after replacing its path data.

Apply Equation 107 for each \(i\in S\), then average. On the resulting single actual state there is one common \(C_j\), one \(K_j\), and one \(\sigma\). Put \[d_z=|K_{j,z}|-\sigma_{\operatorname{par}(z)}K_{j,z},\qquad f_m=\operatorname{avg}_{i\in S}\mathbf 1_{E_i}.\] Then \[ \operatorname{avg}_{i\in S}\mathbb E_{\rm forced}\sum_zd_z =\mathbb E_{\rm actual}\sum_zd_z\frac{f_m}\beta \le2\mathbb E\sum_zd_z+\frac2\beta\mathbb E\sum_{z\text{ marked}}|K_{j,z}| \le4\Delta\nu. \tag{108}\] Indeed all descriptor counts are tested, so the count for the realized \(\sigma\) is among them. On an unmarked cell \(f_m\le2\beta\); everywhere \(f_m\le1\) and \(0\le d_z\le2|K_{j,z}|\). This is a pointwise empirical inequality. It does not presume any independence of a gradient and its match indicators. Goodness and the marked-gradient budget pay for its last two terms. In particular the unmarked defect is not multiplied by the reciprocal match probability.

For a vertical mode, retain the hit in the empirical fraction: \(f_{m,z}^{\rm hit}=\operatorname{avg}_{i\in S}\mathbf 1_{E_i}r_i^{\rm path}(z)\). The same calculation, now conditional on \(\mathcal Z\), gives \[ \operatorname{avg}_{i\in S}\mathbb E_{\rm forced} \left[\sum_z|K_{j,z}|r_i^{\rm path}(z)\,\middle|\,\mathcal Z\right] \le2p_{\rm law}\mathbb E[|K_j|_1\mid\mathcal Z] +\beta^{-1}\mathbb E\left[\sum_{z\text{ marked}}|K_{j,z}|\, \middle|\,\mathcal Z\right]. \tag{109}\] This uses the hit-match marking rule on each unmarked cell and the bound \(f_{m,z}^{\rm hit}\le1\) elsewhere.

Endpoint conversion and path inequalities

In the forced experiment use \(\tau=\sigma\) and \(\chi=+1\). Compared with an independent uniform descriptor, this adaptive choice is dominated by the factor \(2^J\): conditional on the remaining variables, the latter gives that descriptor probability \(2^{-J}\). The fine state is rebuilt in both experiments by the same rule. Thus Equation 91 implies, for either endpoint, \[ \operatorname{avg}_{i\in S}\mathbb E_{\rm forced} \frac{|h_j(B^j_{\neg i}+sD^\pm) -h_{j-1}(B^j_{\neg i}+sD^\pm)|}{s} \le\Delta\nu. \tag{110}\] The background and the sign use none of the forced slot’s fresh path data. This domination therefore changes only the descriptor choice.

For fixed path questions, mode, descriptor, and amplitude data, the rebuilt fine partition is fixed as \(u\) varies. Along \[B(u)=B^j_{\neg i}+s[(1-u)D^-+uD^+]\] ordinary differentiation gives \[ \frac1s\frac{\,\mathrm d}{\,\mathrm du}h_j(B(u)) =\sum_zK_{j,z}(B(u))(D^+(z)-D^-(z)). \tag{111}\] Each slope is \(\sigma_{\operatorname{par}(z)}w_z\) with \(0\le w_z\le2\). Its negative part is bounded, conservatively, by \(2\sum_zd_z(B(u))\): if \(\sigma K\ge0\) the coordinate contributes no negative part, whereas if \(\sigma K<0\), then \(-w_z\sigma K\le2(-\sigma K)\le2d_z\). Integrating in \(u\) and using Equation 107 identifies the uniform-time law with the actual gradient law in Equation 108. Converting the two endpoints with Equation 110 proves, for every mode, \[ \operatorname{avg}_{i\in S}\mathbb E_{\rm forced} \left(\frac{h_{j-1}(B^j_{\neg i}+sD^-) -h_{j-1}(B^j_{\neg i}+sD^+)}s\right)_+ \le10\Delta\nu. \tag{112}\] Here eight units pay for fine negative variation and two for the endpoints. The estimates are uniform in the number of slots, cells, and descriptors.

For a vertical mode, the absolute slope in Equation 111 is at most \(2\sum_z|K_{j,z}|r(z)\). Equation 109, together with \(\mathbb E[|K_j|_1\mid\mathcal Z]\le v\), bounds its conditional expected integral by \(4p_{\rm law}v\) plus a nonnegative error whose expectation is at most \(2\Delta\nu\). The two conditional endpoint errors add at most \(2\Delta\nu\) in expectation. Conditional Jensen’s inequality and Equation 105 therefore give a nonnegative function \(e_{\rm law}(\mathcal Z)\) such that \[ \mathbb E_{r\sim P_{\rm law}}|F_{\mathcal Z}(r)| \le4p_{\rm law}v+e_{\rm law}(\mathcal Z),\qquad \mathbb Ee_{\rm law}\le4\Delta\nu. \tag{113}\] This statement also covers zero-probability laws: their expected unmarked contribution is zero and no division by their honest probability has been used.

For an ordered coupling \((r,r')\), write the difference of coarse widths as the sum of the difference of their upper endpoints and the reversed difference of their lower endpoints. The two corresponding menu entries are \(+\sigma r\to+\sigma r'\) and \(-\sigma r'\to-\sigma r\). The positive part of a sum is at most the sum of positive parts. Applying conditional Jensen and Equation 112 twice yields \[ \mathbb E_{\mathcal Z,r,r'}(F_{\mathcal Z}(r)-F_{\mathcal Z}(r'))_+\le20\Delta\nu. \tag{114}\] The same background kernel is used for both endpoints because fresh comparison data are drawn independently after the background.

For the amplitude comparison, use the common extended kernel described after Equation 105. At one realization abbreviate \[H_a=\phi_C(B+sar),\qquad H_-=\phi_C(B-s\sigma r),\qquad H_+=\phi_C(B+s\sigma r).\] Let \(a'\) be an independent fresh amplitude. For any four real numbers of this form, \[ |H_a-H_{a'}|\le H_+-H_- +\sum_{b\in(a,a')} [(H_--H_b)_++(H_b-H_+)_+]. \tag{115}\] The sum counts both amplitudes, including when \(a=a'\). Indeed write \(H_a-H_{a'}=(H_a-H_+)+(H_+-H_-)+(H_--H_{a'})\) and bound the first and last terms by their positive parts. Adding the other two nonnegative terms gives the right side of Equation 115. Repeating with \(a,a'\) exchanged bounds the opposite signed difference by the same expression, proving the absolute-value bound without any ordering assumption on \(H_-,H_+\).

Divide Equation 115 by \(s\) and average over the background and \(a'\) with \(\mathcal Z,r,a\) fixed. The absolute value of the averaged left difference is \(|g_{\mathcal Z}(r,a)|\) by Equation 104; the width term averages to \(F_{\mathcal Z}(r)\). The four positive-part errors are supplied by the two amplitude modes, once for \(a\) and once for \(a'\). Integrating the iid predicate and amplitude laws and applying Equation 112 four times proves \[ \mathbb E_{\mathcal Z,r,a}(|g_{\mathcal Z}(r,a)|-F_{\mathcal Z}(r))_+\le40\Delta\nu. \tag{116}\] Equations 113, 114, and 116 have constants \(4,20,40\) independent of all later scales. In their proof the oriented-path constant was ten.

Selecting an exterior and threshold

Draw a threshold \(\vartheta\) independently and uniformly from \([\gamma/4,\gamma/2]\). For each exterior \((\mathcal Z,\vartheta)\) define the common Boolean response on actual predicates \[W(r)=\mathbf 1_{\{F_{\mathcal Z}(r)>\vartheta\}}.\] Equation 101 concerns a uniform index in \(I\); Equation 104 makes its response exactly the common \(g_{\mathcal Z}(r,a)\) under the independent iid conjunction and amplitude laws. On \(|g_{\mathcal Z}(r,a)|\ge\gamma\) but \(F_{\mathcal Z}(r)\le\gamma/2\), the positive part in Equation 116 is at least \(\gamma/2\). Consequently the lost mass is at most \(80\Delta\nu/\gamma\). By Equation 83, \[ \mathbb E_{\mathcal Z,\vartheta} [\mathbf 1_{\{v\le B_*\}}\mathbb P_{P_*^t}(W=1)] \ge b_*p\nu/2. \tag{117}\] Indeed \(F>\gamma/2\) ensures success for every possible threshold, and the event no longer depends on the auxiliary amplitude.

For every vertical law and each fixed exterior, Equation 113 and \(\vartheta\ge\gamma/4\) give \[ \mathbb P_{\rm law}(W=1) \le \frac{16}{\gamma}p_{\rm law}v +\frac4\gamma e_{\rm law}(\mathcal Z). \tag{118}\] Each final term has expectation at most \(16\Delta\nu/\gamma\). For real numbers \(u,u'\), the probability over this random threshold that \(\mathbf 1_{\{u>\vartheta\}}>\mathbf 1_{\{u'>\vartheta\}}\) is at most \(4(u-u')_+/\gamma\), since the relevant threshold interval has length at most \((u-u')_+\). Thus Equation 114 gives, for each ordered law, \[ \mathbb E_{\mathcal Z,\vartheta}\mathbb P(W(r)>W(r')\mid\mathcal Z,\vartheta) \le80\Delta\nu/\gamma. \tag{119}\]

Let \(e_{\rm tot}(\mathcal Z,\vartheta)\) be the sum of all \(V\) upper-error terms in Equation 118 and all \(Q\) conditional violation probabilities in Equation 119. It is nonnegative and \[ \mathbb Ee_{\rm tot}\le A_t\Delta\nu/\gamma. \tag{120}\] Discard exteriors for which \(e_{\rm tot}>\varepsilon v\). The iid law is among the vertical laws, so Equation 118 bounds the integrated iid success on this discarded set by \[\left(\frac{16p}{\gamma\varepsilon}+1\right)\mathbb Ee_{\rm tot} \le b_*p\nu/4.\] This estimate is relative to \(\nu\) and remains valid for arbitrarily small positive cut variance. Equations 117 and 120 leave at least \(b_*p\nu/4\) integrated success on exteriors satisfying \(v\le B_*\) and \(e_{\rm tot}\le\varepsilon v\). An exterior in this set with \(v=0\) has zero success by its iid upper bound. Moreover \(\mathbb Ev\le(T_0+1)\nu\) by Equation 92. Since \(b_0(T_0+1)=b_*/8\), there must be a remaining exterior with \(v>0\) and \[\mathbb P_{P_*^t}(W=1)\ge b_0vp.\] Otherwise its integrated success would be at most \(b_*p\nu/8\). At this same exterior, every error summand is at most \(\varepsilon v\). Consequently every fixed type pattern and prescribed ordered law satisfy \[\mathbb P_{\rm pat}(W=1)\le v(K_0p_{\rm pat}+\varepsilon),\qquad \mathbb P(W(r)>W(r'))\le\varepsilon v, \qquad 0<v\le B_0.\] This is exactly Lemma 12, with a single response depending only on the conjunction as a predicate. It produces the valuation forbidden by Lemma 11 in a NO instance. The contradiction proves the soundness assertion of Theorem 13.

The interface for finite compilation

We record the effective structure of the construction, including its dependence on input size. The primitive test samplers use fixed mixtures of uniform choices from polynomial-size finite sets. They therefore have polynomially enumerable discrete sample spaces with rational probabilities of polynomial bit length and inverse-polynomial lower bounds on positive seed probabilities. For fixed \(T_0\), all choices in Equation 82, the conjunction length, the path menu, \(\Delta\), \(M\), and then the sequential stage parameters are constants. The upper bounds on the required integers and the numerical precision can be arbitrarily large functions of \(T_0\); none depends on the instance size.

The parameter order can now be read without circular dependencies: \(T_0\) fixes the resampling and signal constants; these fix \(e,B_*,\gamma,b_0,K_0,B_0\); the rare-event lemma fixes \(t,\varepsilon\); then \(\Delta\) fixes \(M\); finally each stage fixes \(\alpha_j,m_j,n_j,s_j,\xi_j\) in that order. The path constants above do not grow when any later scale is made smaller or any stage size larger.

Canonical keys and rational integration

Let \(b\) be the number of bit names in the test system. After fixing all parameters of the score construction, unroll each complete demand or comparison experiment, including both endpoints. Count all primitive query occurrences: retained, frozen, and future primary lists, resampled copies, fresh and forced path lists, and all lists defining formal partitions. Counting repetitions gives an effectively computable bound \(Q_*=Q_*(C)\) on the number of distinct queried bit names in any experiment. Descriptors, cell indicators, translations, and numerical noises introduce no names beyond those lists. The finite sampler templates and their sample counts are fixed by \(C\), so \(Q_*\) is independent of input size. Choose \(k=Q_*+1\); here \(k\) is solely the key-enumeration bound. Choose a bounded rational interval containing the ranges of all score functions in these experiments, and a fixed finite rational grid in that interval. Rounding means nearest-grid-point rounding with a fixed rule at ties. A key is a grid-valued function on the bit cube, specified by its ordered list of essential bit names and its truth table. Equal functions have the same key; sampling presentations are not part of a key. Enumerate all such keys of arity at most \(k\). If the grid has \(g\) values, there are at most \[\sum_{j=0}^k\binom bj g^{2^j}\] keys. This is polynomial in the original instance size.

Write \(R(B)\) for entrywise rounding of a score. If the entrywise error is at most \(\delta\) and the total raw comparison weight is \(W_0\), then for each truth assignment \[\abs{R(B)(x)-R(\widetilde B)(x)} \le \abs{B(x)-\widetilde B(x)}+2\delta.\] Take the fixed grid fine enough that \(2\delta W_0\le1\) and \(\delta<1/16\). The total rounded truth cost is then at most \(5\), and the two demand tails remain strictly outside \([-1/8,1/8]\).

Every coloring of the keys extends to a measurable lookup on the scores: apply \(R\) and then the coloring. The range can be truncated outside the interval used by the experiments and the function defined arbitrarily on any unused scores. Measurability follows because each rounded table is specified by finitely many polynomial inequalities in the numerical parameters of each experiment. Consequently the soundness assertion of Theorem 13 applies to every key coloring.

Here and below, \(\mu_i\) denotes the pushforward demand mass of key \(i\). For an unordered pair of distinct keys, let \(c^0_{ij}\) be its total raw comparison weight, adding both possible orderings. Self-comparisons contribute zero. Thus \[ \mathcal D(h)=\sum_{i<j}c^0_{ij}\abs{h_i-h_j}. \tag{122}\] The numbers \(c^0_{ij}\) and \(\mu_i\) need not be rational. The next observation gives the particular approximations we require without exact real integration.

Normalize the retained demand by \(\widehat\mu_i=l_i/L\). From Equations (124) we have, for every key and every set \(E\) of keys, \[ \widehat\mu_i\le2\mu_i,\qquad \widehat\mu(E)\ge\mu(E)-10^{-6}. \tag{125}\] For the second assertion use \(\widehat\mu(E)\ge l(E)\) and \(\mu(E)-l(E)\le1-L\).

Replication and auxiliary vertices

Let \(m\) be the number of keys, and choose an integer \(K\) at least \(4\kappa m\) and at least the reciprocal of the smallest positive \(\widehat\mu_i\). Lemma 16 permits \(K\) of polynomial magnitude. Replace key \(i\) by a cluster of \[n_i=\begin{cases} \lceil K\widehat\mu_i\rceil,&\widehat\mu_i>0,\\ 1,&\widehat\mu_i=0 \end{cases}\] vertices, designating one representative. Put \(N=\sum_i n_i\) and \(w_i=n_i/N\). Since \(K\le N\le K+m\), we obtain \[ \frac12\widehat\mu_i\le w_i\le2\widehat\mu_i \quad(\widehat\mu_i>0),\qquad \alpha:=\sum_{\widehat\mu_i=0}w_i\le\frac1{4\kappa}. \tag{126}\] For the upper bound use \(K\widehat\mu_i\ge1\); for the lower bound use \(K\ge m\). Every key has a positive number of copies.

Place capacity \(c_{ij}\) between representatives \(i,j\). Join every other vertex in cluster \(i\) to its representative by an edge of capacity \(2\kappa\). Finally, if \(\widehat\mu_i=0\) and \(\widehat\mu_j>0\), add capacity \[2\kappa w_i\widehat\mu_j\] between their representatives. These last edges are the tethers. Add capacities when edges coincide, and set all diagonal capacities to zero. Give every unordered pair of distinct vertices demand exactly one. The output threshold is the positive rational number \[ a=\frac{A_0}{N^2}. \tag{127}\]

Completeness

Suppose \(x\) is a perfect witness. For a common threshold \(\theta\in[-1/8,1/8]\), color key \(i\) by \(h_i=\mathbf 1_{\{i(x)>\theta\}}\), and give its copies the same color. The tails in Equation (121), their preservation by rounding, and Equations (125)–(126) show that both sides of every such cut have counting mass at least \[\tfrac12(10^{-4}-10^{-6})\ge\tau,\qquad \tau:=10^{-4}/4.\] Thus all these cuts are proper and nonempty.

Take \(\theta\) uniformly in that interval. For any two real values \(u,v\), the probability that the threshold separates them is at most \(4\abs{u-v}\). The expected raw rounded comparison capacity is consequently at most \(4\cdot5=20\). The excess in Equation (123) contributes at most \(1\), and the total tether capacity is \(2\kappa\alpha\le1/2\). No coherence edge crosses. In particular, the expected cut capacity is at most \(22\), so some threshold cut has capacity at most \(22\). If its counting mass is \(z\), then \(z,1-z\ge\tau\) and \[\frac{\operatorname{cap}(S,V\setminus S)}{|S|(N-|S|)} \le\frac{22}{N^2\tau^2} <\frac{A_0}{N^2}=a,\] because \(A_0\tau^2=625>22\).

Soundness

Suppose the formula is unsatisfiable and a nonempty proper cut has ratio at most \(C'a\). Let \(z=|S|/N\) and let \(T\) be its capacity. Then \[ T\le\kappa z(1-z)\le\kappa/4. \tag{128}\] A split cluster would cut an edge of capacity \(2\kappa\), so every cluster is monochromatic. The cut therefore determines a binary coloring \(h_i\) of the keys and hence a measurable lookup on scores. Set \[\nu=\mathop{\mathrm{Var}}_\mu(h),\qquad L_{\rm aux}=\sum_{\widehat\mu_i=0}w_i \sum_j\widehat\mu_j\abs{h_i-h_j}.\] The tethers contribute exactly \(2\kappa L_{\rm aux}\).

We claim \[ z(1-z)\le36\nu+L_{\rm aux}. \tag{129}\] To prove this, draw a key with distribution \(w\). Retain it if its \(\widehat\mu\) mass is positive, and otherwise replace it by an independent \(\widehat\mu\) draw. The color changes with probability \(L_{\rm aux}\). The replacement distribution is \[\rho_j=\mathbf 1_{\{\widehat\mu_j>0\}}w_j+\alpha\widehat\mu_j \le3\widehat\mu_j\le6\mu_j.\] Apply this coupling independently to two \(w\) draws. Their original disagreement probability is \(2z(1-z)\); their replacement disagreement probability is at most \(36\cdot2\nu\) by the product domination \(\rho\otimes\rho\le36\mu\otimes\mu\). A union bound for the two possible color changes proves Equation (129).

Combining the claim with Equation (128) and the tether lower bound gives \[T\le36\kappa\nu+\kappa L_{\rm aux} \le36\kappa\nu+T/2, \qquad\text{hence}\qquad T\le72\kappa\nu.\] Moreover \(\nu>0\): otherwise these inequalities give \(T=0\), then \(L_{\rm aux}=0\), and Equation (129) gives \(z(1-z)=0\), contrary to the cut being proper and nonempty. By Equations (122)–(123), \[\mathcal D(h)\le T\le72\kappa\nu<T_0\nu.\] This contradicts Theorem 13. Every nonempty proper cut in a NO instance therefore has ratio strictly greater than \(C'a\).

Complexity and conclusion

Every enumeration above is polynomial in the original formula size; its exponent may depend on \(C\). The rational compilation has polynomial bit complexity, the replication creates polynomially many vertices, and all capacities and the threshold have polynomial binary encodings. The construction does not inspect a satisfying assignment or a candidate cut. It is therefore a polynomial-time reduction with \[\text{YES}:\ \Phi(G)\le a, \qquad \text{NO}:\ \Phi(G)>C'a.\] A factor-\(C\) approximation outputs a cut of ratio at most \(Ca<C'a\) in the YES case, whereas every cut has ratio greater than \(C'a\) in the NO case. Testing the output ratio against the rational number \(C'a\) decides the original satisfiability instance. This proves Theorem 1.