Constant-factor hardness of uniform sparsest cut

1 Introduction

For a finite undirected graph G on [N], with nonnegative rational capacities c_{ij}=c_{ji} and c_{ii}=0, define

The denominator is the number of unordered pairs separated by the cut. Thus Equation (1) is the sparsest-cut objective with demand exactly one on every pair of distinct vertices. Capacities and thresholds are encoded in binary. A factor-C approximation must return a nonempty proper cut whose ratio is at most C\Phi(G).

The source decision problem is NP-complete [18, Main Theorem, Problem 11]. The reduction uses no unproved complexity hypothesis. It gives an explicit gap for the objective in Equation (1), including every nonempty proper cut, however small either side may be.

1.1 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 [20]. 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 [4, Section 6, Theorem 16].

Exact hardness and approximation hardness address different questions. Matula and Shahrokhi established NP-hardness of finding sparsest cuts [22]; Bonsma, Broersma, Patel, and Pyatkin proved NP-completeness for unweighted graphs with the cardinality-product denominator used here [8, 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^\eps} for every fixed \eps>0, where n is the SAT input length [2, Theorem 1.3]. Raghavendra and Steurer introduced the Small-Set Expansion hypothesis and its connection with Unique Games [24]. Raghavendra, Steurer, and Tulsiani established arbitrarily large constant-factor gaps for Balanced Separator from that hypothesis [25, 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 \cD 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_\cD(M), where q_\cD(M)>0 counts the demand pairs disconnected after deleting M. They proved every-constant-factor hardness under the Unique Games Conjecture [9, 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 [23, 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.1 is independent of this nonuniform consequence.

Khot and Vishnoi also developed the connection between Unique Games, cut hardness, and negative-type metrics [19]. Ordinary NP-hardness for nonuniform sparsest cut is known even with treewidth-two supply graphs, with a 17/16-\eps approximation threshold [15, Theorem 1.3]. The separation between the uniform and nonuniform hardness questions is discussed in [21, Section 1.2] and in the recent work of d’Orsi, Jones, Ruotolo, Vadhan, and Zhang on low-degree Abelian Cayley graphs [11].

Theorem 1.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 3CNF, 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.

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

Algebraic testing. A proof is a bit assignment on an explicitly constructed finite set of positions. A test samples a bounded list of positions and checks their answers. Section 2 constructs a linear-size list of evaluation vectors on which a quadratic form that is nonzero somewhere on the list vanishes only rarely. It uses the Garcia–Stichtenoth tower [13, 28]; the local algebra, dimension estimates, and finite computation needed here are supplied in that section. Section 3 uses this list to construct tests whose individual query probabilities are bounded by a fixed multiple of uniform measure. Its auxiliary parity-query law has exactly uniform marginals and strongly mixing pairs. It encodes Boolean tables by matrix minors and corrects a nearly passing oracle so that quadratic line identities hold at every base on a high-mass set of directions. Local proof testing belongs to the PCP framework developed by Arora and Safra and by Arora, Lund, Motwani, Sudan, and Szegedy, and subsequently recast through gap amplification by Dinur [5, 3, 10]. The correlated test laws and their soundness are proved here.

A predicate is a Boolean function of the entire proof assignment. A valuation assigns a bit to each actual predicate, so two sampled descriptions of the same function must receive the same answer. Calibration prescribes its mean under each specified predicate-sampling law, and order preservation asks that it usually respect pointwise inclusions of predicates. Section 4 proves that an approximately calibrated, approximately order-preserving valuation would decode a satisfying assignment.

Rare-event extraction. Section 5 studies a Boolean response to a conjunction of many independently sampled predicates. Its success probability may be very small. Conditioning on success and exposing a common prefix produces a density with nearly extremal entropy. Comparisons with the constant-one predicate bound the density from above in mean. An explicit clipping argument then forces it near two values, zero and a fixed positive constant. One threshold gives a single valuation satisfying all required calibrations and comparisons. The bounds depend on the fixed list of predicate types, not on their support sizes or on a smallest atom.

From cut variance to a rare successful event. A score is a bounded real function of boundedly many proof bits. A candidate cut is a measurable \{0,1\}-valued function of scores. A demand law measures the variance of this color, and comparison measures charge for disagreement between pairs of scores. Sections 6 and 7 construct these measures. The demand score is a sum of rare predicates with independent real amplitudes at several scales. Small resampling cost forces the cut color to retain a signal from at least one amplitude. Smoothed comparison paths preserve enough of this signal to produce the successful conjunction response required above. The conditional experiments ensure that this response depends on the predicate itself. Every error is proportional to the cut variance, so the argument applies to every positive demand mass.

Exact uniform demands. Section 8 rounds each score to a grid-valued truth table. A key consists of that table together with its ordered essential bit names. Equal functions have the same key. Box subdivision gives rational upper capacities and rational lower demand masses. Replicating keys converts these retained masses into vertex counts; heavy edges prevent a cut of small ratio from separating copies. Additional edges from the remaining keys charge for their possible contribution to separated demand. This produces exactly the denominator |S|(N-|S|) with polynomially many vertices and polynomial binary encodings.

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

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.

2 An explicit pencil of directions

The first ingredient is a short list of vectors on which every quadratic evaluation that is nonzero somewhere on the list has large support. Its length must be linear in the ambient dimension. We construct the list by evaluating functions in an additive tower, and give the local calculations and finite algorithm needed for its uniformity.

In Section 3, these vectors define rank-one directions for a random walk on a space of matrices. Its spectral estimate needs only quadratic evaluations that are nonzero somewhere on the list, exactly the hypothesis in (ii). The application takes d=O(\log(\text{input size}+1)), so the construction time is polynomial in the formula size.

The proof first describes the local branches of the tower and their integral lattices. Their determinant orders bound the conditions imposed on global functions with controlled poles. We then evaluate a sufficiently large space of these functions to obtain the quadratic zero bound, and finally give a finite algorithm with explicit precision and running-time bounds.

Fix a power of two r sufficiently large that, with D=r+1,

All finite fields used below have characteristic two. Write F=\F_q and let k be an algebraic closure of F. Define

where x_1 is transcendental. This is the Garcia–Stichtenoth tower [13]; the recurrence also appears in [28, Example 3.3]. The identities involving inverses are rational-function identities. In particular, the middle expression defines f at zero. We will prove that the tower through x_l is a field of degree N=r^{l-1} over k(x_1), and that the monomials

form a basis. For l=1 this is the one-element basis 1. The same equations and basis will then define the tower over F(x_1).

2.1 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 \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

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

2.2 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 2.2 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\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\F_r, the first right side is integral and the extension splits. An integral residue \beta\notin\F_r has f(\beta)\ne0, so no root of S(Y)=f(\beta) belongs to \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,

along the branch with zero residues. Suppose the first nonzero residue occurs at x_i, where i\geq2. It is an element \alpha\in\F_r^*, and

The numerator x_i^{r+1}-\alpha^2 is divisible by x_i-\alpha. Consequently, modulo integral series,

The equality uses S(x_i)=f(x_{i-1}), the last identity in Equation 3, and \alpha^2\in\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

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

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

2.3 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

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

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 \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 2.2.

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

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

At a good finite point a\notin\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\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

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

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.

2.4 A large space of global functions

In coefficient coordinates, let V_H consist of functions whose every coefficient is a linear combination of

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

At each of the r bad finite points and at infinity, its coefficient expansion belongs to t^{-H}k[[t]]^N. Let \cL_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

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 \cL_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 \cL of its F-rational coefficient vectors has

The algorithm below obtains this space by a finite ground-field matrix, not by searching for Frobenius-fixed vectors.

2.5 Evaluation and the quadratic zero bound

There are (q-r)N rational evaluation tuples above x_1\in F\setminus\F_r. To verify this count, if \beta\in F\setminus\F_r, then \beta^r+\beta\in\F_r^* and \beta^{r+1}\in\F_r^*, so f(\beta)\in\F_r^*. The map S:F\to\F_r is linear over \F_r with kernel \F_r, hence is onto. Each equation S(Y)=f(\beta) has exactly r distinct roots in F\setminus\F_r. Induction proves the count and describes all tuples. All functions in \cL 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 \cL_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,

and therefore

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

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 \cL: 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 \cL. 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 \cL, 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

Since N<rd for this choice of l, we have m=O_r(d). This proves the algebraic assertions of Lemma 2.1; it remains to justify the claimed algorithm and running time.

2.6 A finite algorithm and its precision bounds

The fixed fields F and \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.

Finite constant fields. At a splitting step, suppose the constant term of the shifted right side lies in a current finite field \F_Q containing F. If S(\beta) belongs to that field, then \beta^Q-\beta\in\F_r, because applying S gives zero. This difference is fixed by Q-Frobenius, so in characteristic two \beta^{Q^2}=\beta. Thus a quadratic extension suffices to solve the constant equation. It can be built without enumerating the field: the binary-linear map y\mapsto y^2+y on \F_Q has kernel \{0,1\} and image of codimension one. Linear algebra finds a vector b outside that image, and Y^2+Y+b is irreducible and defines the quadratic extension. The equation S(\beta)=b_0 is itself a binary linear system in that extension; all its other solutions differ by elements of \F_r.

At most one such quadratic extension is needed at each tower level. We may work in nested fields, one for each level, and finally express all constants in a common field of degree

over F. Simple-pole reversion introduces no new constants. Thus the use of k in the dimension calculation does not require an algorithm to enumerate an algebraic closure.

Elementary precision rules. Put M_0=N^2. Suppose a nonzero factor x_i-c has order in [-M_0,M_0] and is known modulo the current parameter to the power K, where K>M_0. Its relative error has order at least K-M_0. Multiplication, integer powers, and inversion preserve this lower bound on relative accuracy: for inversion use (a(1+u))^{-1}=a^{-1}(1+u)^{-1} with u of positive order. A product or quotient of at most a fixed number, depending on r, of these factors therefore has absolute accuracy at least K-C_rM_0, for a fixed constant C_r. The functions f, the indicated shifts \alpha^2/x_j, and their images under S are sums of such expressions; one may factor Y^{r-1}+1 over \F_r^* when computing f.

Subtraction preserves absolute accuracy even when all the known principal parts cancel. In a splitting step, the branch description already proves that f(x_i)-S(g) is integral. Computing its input factors through L+C_rM_0 therefore determines it through the required order L. After the constant equation has been solved, Equation 5 determines positive coefficients through L using only those right-side coefficients. Adding back g has the same finite accuracy bound.

In a simple-pole step, compute q_0=1/f(x_i), which has order one. Its inverse under composition through any order uses only its coefficients through that order and divides by its nonzero linear coefficient. Substitute w^r/(1+w^{r-1}) in this inverse to obtain Equation 6. If z(w) is known modulo w^B, its relative error has order at least B-r. An old Laurent series whose pole order in z is at most M_0 then changes, after substitution, only in orders at least B-r-rM_0. Indeed, for each retained term a_nz^n the relative error is at least B-r, and its order is at least -rM_0; sums preserve the resulting absolute bound. Thus B\geq L+r(M_0+1) suffices for output precision L. Old coefficients through \ceil{L/r}+M_0+2 suffice as well, since higher powers of z(w) cannot contribute below order L. Updating all previously constructed variables increases the number of operations, but not the exponent in these precision bounds.

Choose an integer a_r depending only on r so large that K_N=(2N)^{a_r} dominates M_0 and all fixed constants in the preceding rules, for every N\geq1. The rules are all covered by the single backward precision budget

This is an allocated upper budget; the algorithm may retain all coefficients up to that budget. It is uniform over levels, branches, and rational coefficient basis inputs.

The final integrality tests. Consider one rational coefficient basis element in V_H times one power-basis monomial. In a final branch its pole order, allowing also the infinity adjustment, is bounded by

The first term bounds a base pole of order at most H after total ramification at most N; the second bounds the monomial; the last is a harmless bound for the infinity multiplier. Such an input is a product of powers and inverses of the elementary factors already considered. Knowing each factor with relative error of order greater than P_0 makes the unknown remainder of the full input integral. A sufficiently large fixed multiple

as absolute factor precision therefore determines every negative coefficient, including after multiplication by t^D at infinity. Cancellation in a linear combination of these inputs can remove computed negative coefficients but cannot reveal an uncomputed one: each individual unknown remainder is already integral.

Use Equation 18 backwards from L_{\rm end}, and then perform the forward branch expansions at those precisions. The branch type and its prescribed shift are determined by the explicit residue and descending-shift rules above. For each basis input, record all negative coefficients in every branch, with the infinity multiplier included. Their vanishing is exactly the desired system defining \cL.

Size and running time. There are at most (r+1)N exceptional branches at any level. Since l=1+\log_r N, Equation 12 gives F_0=O_r(N^3) and H=O_r(N^4). The number of rational coefficient unknowns is N[1+(r+1)H]=O_r(N^5), and L_{\rm end}=O_r(N^6). Even retaining a full window of this latter length per branch gives only O_r(N^7) negative-coefficient equations over the finite constant fields. Expanding each coefficient in an F-basis of the common field in Equation 17 gives at most O_r(N^8) equations over F. Solving this explicit matrix computes \cL; Equation 15 proves that its dimension is at least N. The computation does not infer dimension by testing random functions.

Iterating Equation 18 for at most l-1 steps shows that every retained series length is at most

Elementary truncated addition, multiplication, inversion and composition, and coefficientwise reversion, use a number of field operations polynomial in the retained lengths. All branch counts, field representation sizes and matrix dimensions are polynomial in N; allowing every level and every basis input multiplies these bounds by polynomial factors. For N\geq2, \log((2N)^{O_r(l+1)})=O_r((\log N)^2)=O_r(N); the case N=1 is a fixed computation. Total bit complexity is consequently 2^{O_r(N)}. Enumerating the rational evaluation tuples, evaluating the functions, and selecting the independent columns require only additional polynomial time in N and the matrix sizes. Finally N<rd, so the entire construction takes 2^{O_r(d)} time. Together with the evaluation argument, this completes the proof of Lemma 2.1.

3 A bit-test system with mixing parity queries

Here clauses have three literal positions, with repetitions permitted. Repeat literals to pad a nonempty shorter clause; replace an empty clause by two opposing unit clauses on a fresh variable and then pad them. A formula with no clauses can be replaced by a single tautological clause. These operations preserve satisfiability and take linear time.

We first construct the finite tests from which the reduction will use predicates. A test law consists of a distribution of question lists and, for each sampled list together with its public sampling data, an acceptance predicate on the answers. Repeated questions are allowed and count toward the arity.

3.1 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 \F=\F_q of characteristic two and the pencil u_1,\ldots,u_m\in\F^d from Lemma 2.1. The field will be sufficiently large and the pencil parameter \lambda_0 sufficiently small. Set

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_{\F}G\leq b^2m=O(d).

Let \mathsf D be the law

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)=\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 [1, Lemma 2.3]. We prove the eigenvalue bound for this particular matrix walk directly.

Our field oracle will be a function P:G\to\F. Its binary encoding has positions

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\F, an independent uniform A\in G, an independent h\sim\mathsf D, and an independent uniform \sigma\in\F^*. Put

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

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 3.1 once the promised line-polynomial assignment is constructed.

3.2 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 [6]. 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=\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

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

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

For each of the 25 identity differences, group the residual terms from Lemma 3.4 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:

Let v(T) copy the off-diagonal part of T into bank one, w(T) copy \diag(T)-I into bank two, and u(T) copy \diag(T)^2-\diag(T) into bank one. Here \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

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.

3.3 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

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

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

2. 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. 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. 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\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 \cS, 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.

3.4 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 [7]. The modal interpolation and transverse-grid consistency argument in the point-filling step has precedents in polynomial self-testing [14, 27]. The next lemma proves the required correction statement for our restricted distribution of directions, with one common high-mass set of good directions.

3.5 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 3.5. Replacing P by P' increases any field-law failure probability by at most 2Q\delta, because each master query is uniform. Write

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 3.6, with the conservative degree bound six, gives the support lower bound

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

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

is also a subgroup. Indeed, for u,v\in V, the difference cocycle gives

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

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

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.1. These observations prove the size and sampler assertions and complete the proof of Theorem 3.1.

4 Primitive events and a valuation obstruction

Let \Omega=\{0,1\}^{\cS} be the cube of bit assignments for Theorem 3.1. A predicate is a Boolean function R:\Omega\to\{0,1\}. We identify predicates that are equal as functions, regardless of their sampled descriptions. We write R\subseteq R' when R(y)\leq R'(y) for every y\in\Omega.

A primitive type is a probability law P_s on predicates, together with a specified number p_s\in[0,1]. An ordered comparison is a coupling of two specified primitive laws supported on pairs R\subseteq R'. The type index is part of the sampling data, but is not part of the predicate to which a valuation is applied.

4.1 The primitive types

Use Theorem 3.1 with pair bound \lambda\leq10^{-6}. There are two basic literal types:

where i is uniform in \cS, (i,j) is uniform in \cS^2, and the target a\in\F_2 is an independent uniform bit. Both calibrations are 1/2.

We use three even-parity tuple experiments:

1. 1.

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

2. 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. 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\F_2^k. Add the type of the match event

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

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 3.1, 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\F_2^L uniformly and add the match-and-pass event

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 4.2. The finite sampling and arity properties follow from Theorem 3.1, since all products and target spaces have fixed size. We prove its unsatisfiable-instance assertion next.

4.2 A quantitative tag–dictator dichotomy

Suppose H satisfies Equation 37. For either the base or sum question space, write

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 |\E b|\leq2\zeta, and \E b^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 3.1. Hence, for \ell\ne r,

The first comparisons in Equation 38 give

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

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,

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

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

for each of the two basic literal types.

4.3 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

Extend the base tag sign arbitrarily to a sign b_i on all of \cS. The non-tag fraction is at most e_0, so |\E b_i|\leq h_0. If r_s=\Prob[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

If a sum question is not a tag of sign s, at least one of its two targets has sign different from s. Thus

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

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

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

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

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

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

Then \Prob[v(i,j)\ne u(i)w(j)]\leq R_0. Symmetry of v gives \Prob[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

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

Equations 44 and 47 upper-bound the same probability by 2D_0+3R_0. But direct substitution gives

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

4.4 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 \cS, 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

Thus the failure probability of this law is at most

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 3.1. In an unsatisfiable instance this contradicts that theorem. This completes the proof of Lemma 4.2.

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

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.

5 From rare conjunctions to a common valuation

We prove a general statement about primitive predicates. Its constants do not depend on the number of predicates or on the smallest probability of one of them. This uniformity will allow us to apply the statement to the systems in Section 4 as the input size grows.

Conditioning on successful repetitions and distributing the resulting relative-entropy cost among coordinates appears in the parallel-repetition proofs of Raz [26] and Holenstein [17, Section 4]. Here the entropy estimates feed a clipping and thresholding argument that produces one valuation of actual predicates, simultaneously satisfying the type calibrations and comparison laws. We prove this conclusion with estimates independent of atom probabilities.

Let \cX be a finite set, and identify a predicate on \cX with its function R\colon\cX\to\{0,1\}. Fix a finite set \cT of primitive types. Type s has a probability law P_s on predicates and a prescribed number p_s\in[0,1]. Fix weights \omega_s>0 with \sum_{s\in\cT}\omega_s=1. A sample from P_* first chooses s with probability \omega_s and then chooses R from P_s; we retain the type as part of the sample. Thus identical predicates can occur under different types. Auxiliary sampling presentations may likewise be retained, but all response functions below act on the actual predicates, not their presentations. Write

Assume that a designated type \top is concentrated on the constant-one predicate \mathbf 1 and has p_\top=1.

Fix also a finite list \cC of comparison laws. A comparison \Pi\in\cC couples two primitive predicates (R,R') with designated marginal laws P_{s(\Pi)} and P_{s'(\Pi)}, and satisfies R\le R' pointwise. The list contains, for every type s, the comparison from R\sim P_s to \mathbf 1. A Boolean valuation is a single function H of actual predicates. Its calibration and order requirements at tolerance \zeta>0 are

For an integer t\ge1, a type pattern \boldsymbol s=(s_1,\ldots,s_t) means independent draws R_i\sim P_{s_i}. Put

A lifted comparison chooses one coordinate from a prescribed law (R,R')\sim\Pi, and chooses the other t-1 predicates independently from specified primitive types, independently of (R,R'). It uses these same context predicates on both sides, giving a pair of conjunctions r\le r'. Bounds for all such type patterns and comparisons also hold when any of the context types are independently mixed with the weights \omega_s, simply by averaging.

For the primitive system of Section 4, choose the tolerance from Lemma 4.2. Lemma 5.1 then says that, on a NO instance, no common conjunction response can satisfy Equations 51–53 for those choices of t and \eps. The constants b_0,K_0,B_0 must be fixed before this choice; the next two sections produce precisely that interface from a putative sparse cut.

6 Scores, comparison measures, and an amplitude signal

A score is a real function on the cube of assignments to the bit positions of the test system. All scores below depend on a bounded number of positions. Identical functions are identified, even if their sampling presentations differ. A lookup h is a measurable function from scores to \{0,1\}; measurability means Borel measurability on each finite table of score values. A raw comparison form is a finite positive measure on pairs of scores, evaluated as

Its truth cost at an assignment x is \int|B(x)-B'(x)|\dd\mathfrak m(B,B').

We first construct the demand law and comparison measures, with bounded truth cost at a satisfying assignment. For a putative low-cost coloring, the resampling comparison supplies an amplitude signal. The remaining comparisons preserve enough of this signal to obtain the common conjunction response required by Lemma 5.1. Section 7 constructs that response and completes the proof of Theorem 6.1.

It suffices to prove the theorem for rational T_0\ge1, since one can replace a given real T_0 by a larger rational number. Choose positive rational mixture weights \omega_s for all primitive types, and write P_* for their mixture and p_*=\sum_s\omega_sp_s\in(0,1). A length-t conjunction from the independent mixture law has honest probability p=p_*^t. A fixed pattern of primitive types has honest probability equal to the product of their p_s’s. The ordered conjunction couplings change one coordinate by one of the prescribed primitive couplings and use independent, shared, fixed-type samples in all other coordinates. They give actual pointwise inclusions r\le r'.

6.1 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

All stage sizes will be chosen below. In each slot independently sample a primary presentation \cR_i of an iid conjunction r_i and an independent amplitude with law

The demand score and its law are

At a perfect witness x, each summand is symmetric, centered, and bounded by one, with variance s_j^2p/6. Consequently

For X=B^0(x), Cauchy–Schwarz gives

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

Throughout the soundness proof suppose, for a contradiction, that

In particular,

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 \cZ consists of the freeze sets and all complete primary variables in frozen slots. Let \cB add to \cZ the primary presentations of all unfrozen slots, but none of their amplitudes. Define, for i\in I_j,

Indices in such formulas are fixed after the freeze sets are specified. For any family b=(b_i) put

We must turn this amplitude signal into the response on actual conjunction predicates required by Lemma 5.1. 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.

6.2 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 5.1. Choose rational constants

These constants have no dependence on conjunction length. Apply Lemma 5.1 to b_0,K_0,B_0 and choose its length t and tolerance \eps>0. We can decrease \eps 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

Choose an integer

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.

6.3 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. 1.

   -\tau r\longrightarrow+\tau r for each of the V vertical laws;

2. 2.

   +\tau r\longrightarrow+\tau r' and -\tau r'\longrightarrow-\tau r for each ordered pair r\le r';

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

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

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.

6.4 Smoothing and the comparison measures

For \xi>0 use the probability density

It is even, continuously differentiable after extension by zero, and decreasing on [0,\xi]. Direct integration gives

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}\ind_z and \Theta_{\le j}=\sum_{\ell=0}^j\Theta_\ell. With partitions fixed, set

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

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

Mark a consistent cell in C_j if any of these conditions holds:

1. 1.

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

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

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

where the superscript fixes only coordinate (j,z) and all other noises are averaged. Translating the density and pairing b with -b gives

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

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

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

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

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

6.5 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. 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. 2.

   Choose an integer

   m_j\ge\frac{2T_0(2L2^J)}{\eta a_j\beta_jp_{\min}}.
3. 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. 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

The square bound follows by averaging raw comparisons and using |u-v|^2\le|u-v| for u,v\in[0,1]. In addition,

and each uniform-descriptor endpoint experiment satisfies

6.6 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

For each j, let E_j=\E[|\pi K_j-K_{j-1}|_1\mid\cB]. The pointwise inequality |K_{j-1}|_1\le|K_j|_1+ |\pi K_j-K_{j-1}|_1 gives U\le\E[|K_M|_1\mid\cB]+\sum_jE_j. Therefore

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

Summing and dropping -|K_0|_1 proves

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:

Define b_i^+ by replacing h_{j-1} with h_j, and put g_i=\E[b_i\mid\cZ,\cR_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

Since \alpha_j\le e\le1/2 and \|b^0\|_\Sigma\le\sqrt\nu, solving for b-b^0 gives

For the second bound, projection contraction in each forced experiment bounds s_j^2\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,

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

We now clip the fine component to obtain a bounded signal. Set A=\{U\le B_*,\ v\le B_*\}, which is \cB-measurable, and define \widetilde b_i=b_i^+\ind_A and \widetilde g_i=\E[\widetilde b_i\mid\cZ,\cR_i,a_i].

The conditional cap in Equation 79, even with its weaker upper bound one, and Markov’s inequality give

Projection contraction, Equation 94, and the triangle inequality now give

For every family q_i, Equation 76 implies

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

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

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

We fix this stage for the rest of the analytic argument.

7 Conditional kernels and ordered paths

Fix the good stage supplied by Equation 101. In this section abbreviate s=s_j, \alpha=\alpha_j, \beta=\beta_j, I=I_j, S=S_j, and J=J_{j-1}. All background experiments are through stage j only. We first identify the conditional laws needed to turn amplitude variation into a common response on predicates.

7.1 The deleted-slot background

Fix an exterior value \cZ=z. It fixes the freeze sets, the complete frozen variables, and the sets I,S. Let Y_i=(\cR_i,a_i) for i\in I, with common law P_Y=P_{\cR}\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

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

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

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(\dd B,\dd C). 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 \cR_i. The definition of b_i and the tower property give

Indeed \sigma(\cZ,\cR_i,a_i)\subseteq\cB\vee\sigma(a_i), and a_i is independent of \cB; averaging the subtracted \cB-conditional expectation therefore removes a_i. Forcing shared preserves the law of the background. The projected response is consequently

It is a version of every g_i, evaluated at the predicate represented by \cR_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

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.

7.2 Forcing a slot and rebuilding the fine state

Fix a mode m and an index i\in S. Let \cH_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 \cH_i-measurable. The event

has the exact conditional probability

The number of formal parent cells is deterministic; empty cells and colliding labels have not reduced J. Conditional on E_i,\cH_i, the path data have their original mode law and u is independent uniform.

Let \Gamma(\cH_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 \cH_i and satisfies

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

Then

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}\ind_{E_i}r_i^{\rm path}(z). The same calculation, now conditional on \cZ, gives

This uses the hit-match marking rule on each unmarked cell and the bound f_{m,z}^{\rm hit}\le1 elsewhere.

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

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

ordinary differentiation gives

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,

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 \E[|K_j|_1\mid\cZ]\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}(\cZ) such that

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

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

Let a' be an independent fresh amplitude. For any four real numbers of this form,

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 \cZ,r,a fixed. The absolute value of the averaged left difference is |g_{\cZ}(r,a)| by Equation 104; the width term averages to F_{\cZ}(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

Equations 113, 114, and 116 have constants 4,20,40 independent of all later scales. In their proof the oriented-path constant was ten.

7.4 Selecting an exterior and threshold

Draw a threshold \vartheta independently and uniformly from [\gamma/4,\gamma/2]. For each exterior (\cZ,\vartheta) define the common Boolean response on actual predicates

Equation 101 concerns a uniform index in I; Equation 104 makes its response exactly the common g_{\cZ}(r,a) under the independent iid conjunction and amplitude laws. On |g_{\cZ}(r,a)|\ge\gamma but F_{\cZ}(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,

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

Each final term has expectation at most 16\Delta\nu/\gamma. For real numbers u,u', the probability over this random threshold that \ind_{\{u>\vartheta\}}>\ind_{\{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,

Let e_{\rm tot}(\cZ,\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

Discard exteriors for which e_{\rm tot}>\eps v. The iid law is among the vertical laws, so Equation 118 bounds the integrated iid success on this discarded set by

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\eps v. An exterior in this set with v=0 has zero success by its iid upper bound. Moreover \E v\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

Otherwise its integrated success would be at most b_*p\nu/8. At this same exterior, every error summand is at most \eps v. Consequently every fixed type pattern and prescribed ordered law satisfy

This is exactly Lemma 5.1, with a single response depending only on the conjunction as a predicate. It produces the valuation forbidden by Lemma 4.2 in a NO instance. The contradiction proves the soundness assertion of Theorem 6.1.

7.5 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,\eps; 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.

8 Finite graphs with exactly uniform demands

We now convert Theorem 6.1 into the graph promised in Theorem 1.1. The conversion must retain cuts of arbitrarily small positive mass. In particular, replacing the demand by an additive approximation alone would be insufficient. We keep a multiplicative upper bound on the retained demand and attach every remaining vertex to that demand.

Fix an integer C'>C, and set

Apply Theorem 6.1 with this T_0. Write \mu for its demand law, and \cD for the sum of its raw comparison forms. Thus, for a perfect witness x, the total truth cost is at most 4, and

In a NO instance, every measurable binary lookup h with \nu=\Var_\mu(h)>0 satisfies \cD(h)>T_0\nu. All arities, numerical parameters, and total raw comparison weights below are constants depending on C only.

8.1 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

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

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

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,

For the second assertion use \widehat\mu(E)\ge l(E) and \mu(E)-l(E)\le1-L.

8.2 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 8.1 permits K of polynomial magnitude. Replace key i by a cluster of

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

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

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

8.3 Completeness

Suppose x is a perfect witness. For a common threshold \theta\in[-1/8,1/8], color key i by h_i=\ind_{\{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

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

because A_0\tau^2=625>22.

8.4 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

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

The tethers contribute exactly 2\kappa L_{\rm aux}.

We claim

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

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

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

This contradicts Theorem 6.1. Every nonempty proper cut in a NO instance therefore has ratio strictly greater than C'a.

8.5 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

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