# Constant-factor hardness of uniform sparsest cut

*An expository proof, written to be readable with high-school mathematics.*

---

## 0. The paper in one sentence

Take the graph-partitioning problem where every pair of vertices carries one
unit of demand, and you want to cut as little capacity as possible per unit
of separated demand. This is **Uniform Sparsest Cut**. The paper proves:
for every fixed constant $C>1$, approximating it within a factor $C$ is
**NP-hard**. There is no polynomial-time factor-$C$ algorithm unless
P = NP.

The method is a *reduction*: a polynomial-time machine that turns any
Boolean formula into a graph, built so that

- a **satisfiable** formula yields a graph with a cut of ratio $a$;
- an **unsatisfiable** formula yields a graph where *every* cut has ratio
  bigger than $Ca$.

A gap by a factor $>C$ means a factor-$C$ approximation, which must always
output a cut within $C$ of the true optimum, would have to output a cut with
ratio $\le Ca$ on satisfiable instances and would be forced above $Ca$ on
unsatisfiable ones. Just compare the returned ratio with the rational
number $Ca$: this decides satisfiability. So a factor-$C$ approximator
solves an NP-hard problem, which would collapse P and NP.

The rest of the paper is the construction.

---

## 1. The problem, precisely

### 1.1 Cuts and their ratio

Let $G$ be a finite undirected graph on the vertex set
$[N]=\{1,2,\dots,N\}$. Give each unordered pair of distinct vertices a
nonnegative rational **capacity** $c_{ij}=c_{ji}\ge 0$, with $c_{ii}=0$.
A **cut** is a partition of the vertices into two nonempty parts $S$ and
$V\setminus S$. Its **capacity** is the total capacity of the edges
crossing it:

$$\operatorname{cap}(S)=\sum_{i\in S,\ j\notin S} c_{ij}.$$

The **denominator** we divide by is the number of unordered pairs of
distinct vertices that the cut *separates*:

$$|S|\,(N-|S|).$$

This is exactly the number of pairs with one vertex in $S$ and one
outside. The **sparsest-cut ratio** of $G$ under uniform demand is

$$\Phi(G)=\min_{\varnothing\ne S\subsetneq [N]}
\frac{\operatorname{cap}(S)}{|S|\,(N-|S|)}. \tag{1}$$

### 1.2 Why this exact denominator

The denominator $|S|(N-|S|)$ encodes **unit demand between every pair of
distinct vertices**: the cut "serves" $|S|(N-|S|)$ demands and pays
$\operatorname{cap}(S)$ in capacity. Dividing, we get the average capacity
per separated pair. This normalization is what makes the problem sensitive
to bottlenecks at every scale, including cuts where one side is tiny. A
lone vertex cut has denominator $1\cdot(N-1)=N-1$; a balanced cut has
denominator about $N^2/4$. A cut with a huge numerator but an even huger
denominator can still be the sparsest. The uniform objective refuses to
let the big side win by being big.

### 1.3 What "factor-$C$ approximation" means

A **factor-$C$ approximation algorithm** must, on every input $G$ with
$N\ge 2$, output a nonempty proper cut $S$ with

$$\frac{\operatorname{cap}(S)}{|S|\,(N-|S|)} \le C\,\Phi(G).$$

It may be worse than optimal by at most the factor $C$, but not more.
Capacities are given in binary; the algorithm is allowed to run in time
polynomial in the input length, with the exponent permitted to depend on
$C$.

### 1.4 The main theorem

**Theorem (main).** *For every fixed real constant $C>1$ there is a
polynomial-time reduction from 3CNF satisfiability to finite undirected
graphs with nonnegative rational capacities and exactly unit demands,
together with a positive rational threshold $a$, such that*

$$\text{formula satisfiable}\ \Longrightarrow\ \Phi(G)\le a,$$
$$\text{formula unsatisfiable}\ \Longrightarrow\ \Phi(G)>Ca.$$

*The graph size and the binary lengths of all output numbers are polynomial
in the formula size, with constants and exponents allowed to depend on $C$.
In particular, approximating Uniform Sparsest Cut within any fixed factor
$C>1$ is NP-hard.*

The source decision problem is NP-complete (Karp's original list, Problem
11). The reduction uses **no unproved complexity hypothesis** — no Unique
Games Conjecture, no Small-Set Expansion hypothesis. It produces an
explicit multiplicative gap for the objective (1), valid for *every*
nonempty proper cut, however lopsided.

---

## 2. Context: what was known, and what is new

Sparsest Cut sits at the meeting point of graph partitioning and
multicommodity flow. The denominator's sensitivity to bottlenecks makes it
the wrong objective to approximate by local tricks, but it is exactly the
objective tamed by flow-cut duality.

### 2.1 Approximation algorithms

**Leighton and Rao (1999).** The multicommodity-flow/edge-embedding
approach yields an $O(\log N)$-factor approximation for the uniform and
more general sparsest-cut objectives. This launched a long line of work.

**Arora, Rao, and Vazirani (2009).** Semidefinite programming and the
geometry of negative-type metrics improved the factor to
$O(\sqrt{\log N})$. Their paper treats the unweighted uniform objective
explicitly (Section 6, Theorem 16).

So we *do* have algorithms. The question is whether the logarithm can be
removed, i.e. whether a constant factor is possible. This paper says no.

### 2.2 Exact hardness

**Matula and Shahrokhi (1990)** established NP-hardness of finding the
sparsest cut exactly.

**Bonsma, Broersma, Patel, and Pyatkin (2012)** proved NP-completeness for
*unweighted* graphs with the cardinality-product denominator used here
(their Theorem 15).

But exact NP-hardness leaves a gap: it permits a constant-factor
approximator to slip through. To rule one out, we must manufacture a
**multiplicative separation** — satisfiable versus unsatisfiable differing
by more than any fixed constant — while preserving the uniform denominator.

### 2.3 Previous approximation lower bounds (conditional)

**Ambuhl, Mastrolilli, and Svensson (2011)** proved that a polynomial-time
approximation scheme for Uniform Sparsest Cut would give probabilistic
SAT algorithms of time $2^{n^{\varepsilon}}$ for every fixed
$\varepsilon$; so a PTAS would contradict standard hardness assumptions
and would also be an algorithmic breakthrough. This is a lower bound on how
small the factor can be, under an assumption about SAT algorithms.

**Raghavendra and Steurer (2010)** introduced the Small-Set Expansion
hypothesis and tied it to Unique Games. **Raghavendra, Steurer, and
Tulsiani (2012)** proved arbitrarily large constant-factor gaps for
Balanced Separator from that hypothesis (their full-version Theorems 3.5
and 3.6). Their balanced-cut statement measures set size by stationary
volume.

**The nonuniform problem.** If we allow a chosen set $\mathcal D$ of demand
pairs instead of all pairs, the problem is easier to crack:
**Chawla, Krauthgamer, Kumar, Rabani, and Sivakumar (2006)** proved
every-constant-factor hardness for the *nonuniform* objective under the
Unique Games Conjecture. A sparsest cut there means an edge set $M$ with
capacity $c(M)$; its ratio is $c(M)/q_{\mathcal D}(M)$, where
$q_{\mathcal D}(M)>0$ counts demand pairs disconnected by deleting $M$.
**Khot and Vishnoi (2015)** further developed the link between Unique
Games, cut hardness, and negative-type metrics. Ordinary NP-hardness for
nonuniform sparsest cut is known even on treewidth-two supply graphs, with
a $17/16-\varepsilon$ threshold (**Gupta, Talwar, Witmer 2013**).

The recent **OpenAI Unique Games Theorem (2026)** supplies the game premise
behind the conditional nonuniform results: its unweighted bipartite
constraints may be given equal weights summing to one (its Theorem 1.1 and
Corollary 8.3). That nonuniform hardness concerns *cutset-output search*
under polynomial-time Cook reductions; only the selected pairs carry unit
demand. It does **not** settle the uniform question.

**The gap between uniform and nonuniform.** This separation is discussed by
Manurangsi and Trevisan (2018, Section 1.2) and by d'Orsi, Jones, Ruotolo,
Vadhan, and Zhang (2025) on low-degree Abelian Cayley graphs.

### 2.4 What this paper does

Theorem 1 establishes an **unconditional** approximation gap with **unit**
demand on **all** pairs. Its force is that it controls *all* cut masses in
a polynomial-size reduction — including cuts with an arbitrarily small
side. The proof starts with an explicit algebraic test system for 3CNF,
extracts a single Boolean valuation from a rare successful event, and
forces that event from any cut whose comparison cost is small relative to
its demand variance.

---

## 3. The proof, as a map

The reduction is best understood as a pipeline of four **interfaces**. Each
interface turns data of one kind into data of the next, and each is
separately organized in the sections below.

### 3.1 The four interfaces

1. **Algebraic testing (Sections 4–5).** A "proof" is a bit assignment on
   an explicitly constructed finite set of positions. A "test" samples a
   bounded list of positions and checks a relation among the answers. The
   tests are designed so that (a) satisfiable formulas admit perfect
   proofs, and (b) unsatisfiable formulas have no proof passing more than
   $1-\eta$ of the tests, for a *constant* $\eta>0$.

2. **Valuation obstruction (Section 6).** From many Boolean tests we distill
   a single **valuation**: a bit attached to each actual predicate, so two
   sampled descriptions of the same function must receive the same answer.
   An approximately calibrated, approximately order-preserving valuation
   decodes a satisfying assignment; and conversely, on unsatisfiable
   formulas no such valuation exists.

3. **Rare-event extraction (Section 7).** A Boolean response to a
   conjunction of many independently sampled predicates, whose success
   probability may be astronomically small, still forces a single valuation
   through an entropy argument. This is where the "arbitrarily small cut
   mass" difficulty is handled: all errors are proportional to the cut
   variance, never to a fixed additive tolerance.

4. **Scores to a finite graph (Sections 8–10).** A **cut** becomes a
   measurable lookup on real-valued **scores**. A demand law measures the
   variance of the cut's color; comparison measures charge for disagreement
   between scores. Small comparison cost forces a successful rare event,
   contradicting the valuation obstruction on unsatisfiable inputs.
   Finally the analytic score laws are rounded and compiled into a genuine
   finite graph with exactly uniform demand.

### 3.2 The proof structure in detail

**Algebraic testing.** Section 4 builds a short list of vectors on which a
quadratic polynomial that is nonzero somewhere on the list vanishes only
rarely (at most a fixed fraction $\lambda_0$ of positions). It uses the
Garcia–Stichtenoth tower of function fields and a finite, explicit
computation over a small finite field. Section 5 uses this list to build
tests whose individual query probabilities are within a fixed multiple of
uniform, with an auxiliary four-point parity law that has exactly uniform
marginals and *strongly mixing* pairs. It encodes Boolean tables by matrix
minors, corrects a nearly passing oracle so that quadratic line identities
hold on a high-mass set of directions, and proves constant soundness.

**Valuation obstruction.** A *predicate* is a Boolean function of the
entire proof assignment. A *valuation* assigns a bit to each actual
predicate. *Calibration* prescribes its mean under each predicate-sampling
law; *order preservation* asks it usually to respect pointwise inclusions.
Section 6 proves that good calibration and order force a satisfying
assignment, via a quantitative "tag versus dictator" dichotomy.

**Rare-event extraction.** Section 7 studies a Boolean response $W$ to a
conjunction $r=\bigwedge_{i=1}^t R_i$ of $t$ independently sampled
predicates. Even if success is rare, conditioning on success and exposing
a common prefix produces a conditional density with nearly extremal
entropy. Comparisons with the constant-one predicate bound the density
above in mean. A clipping argument forces it near two values, $0$ and a
fixed positive constant $A$, and one threshold produces a single valuation
satisfying every required calibration and comparison. Crucially, the bounds
depend only on the fixed list of predicate types, not on support sizes or
on a smallest atom.

**Cut to rare event.** Section 8 defines **scores**: bounded real functions
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; comparison measures charge for disagreement between scores. The
demand score is a sum of rare predicates with independent real amplitudes
at several scales, so that a small resampling cost forces the cut color to
retain a signal from at least one amplitude. Sections 8–9 then build
smoothed comparison paths preserving enough signal to produce the
conjunction response; the conditional experiments ensure the response
depends on the *predicate*, not its presentation.

**Exact uniform demands.** Section 10 rounds each score to a grid-valued
truth table, calling the table plus its essential bit names a **key**. Box
subdivision gives rational upper capacities and rational lower demand
masses; replication of keys turns retained masses into vertex counts;
heavy edges prevent a small-ratio cut from splitting a cluster; and
tether edges from the remaining keys charge for their possible contribution
to separated demand. The result is exactly the denominator $|S|(N-|S|)$
with polynomially many vertices and polynomial binary encodings.

### 3.3 The parameter order (no circular reasoning)

The approximation factor is fixed first and never varies. Afterwards every
numerical constant, field size, arity, and number of repetitions is fixed
*independently of the input formula*. Parameters chosen later may depend on
earlier ones only. The concrete order in the score construction is:

$$T_0 \to (\text{resampling, signal constants}) \to e,B_*,\gamma,b_0,K_0,B_0 \to t,\varepsilon \to \Delta \to M \to (\alpha_j,m_j,n_j,s_j,\xi_j)_j.$$

Section 9 spells out the dependencies. Bounds written $O(\cdot)$ carry
constants depending only on parameters already fixed at that point. The
construction is polynomial in the formula size; the paper makes *no* claim
that its exponent is uniform in $C$.

### 3.4 Conventions

**Functions, not presentations.** 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. Two presentations of the same function cannot receive different
cut colors. The same convention applies to scores.

**Variance.** For a probability law $\mu$ on a space and a Boolean function
$h$,

$$\operatorname{Var}_\mu(h)=\mu(h=1)\,\mu(h=0)=\tfrac12\,\mathbb E_{B,B'\sim\mu}\,|h(B)-h(B')|, \tag{2}$$

the last with $B,B'$ independent draws from $\mu$. This identity is the
bridge between "the cut disagrees on a pair" and "the cut has positive
variance." Every error in Sections 7–9 is bounded by a multiple of this
variance, not by an additive tolerance. That is what lets the argument
survive a cut of arbitrarily small positive mass.

**Measure and integral conventions.** A raw comparison form in Section 8 is
a finite positive measure on pairs of scores; its evaluation on a lookup
$h$ is $\mathcal D(h)=\int |h(B)-h(B')|\,d\mathfrak m(B,B')$, and its truth
cost at assignment $x$ is $\int |B(x)-B'(x)|\,d\mathfrak m(B,B')$. The total
raw comparison weight is a constant independent of input size.

---
## 4. The pencil: a list on which quadratics vanish rarely

Everything starts with one list of vectors, surprisingly short, on which
any quadratic polynomial that is *not everywhere zero* is zero at only a
small fraction of points. This is the only place the proof touches deep
algebra, and the algebra is entirely explicit.

### 4.1 The statement

**Lemma (Quadratic evaluation pencil).** *For every $0<\lambda_0<1$ and
every sufficiently large power of two $r$, let $q=r^2$. There is a
deterministic algorithm which, given an integer $d\ge 1$, outputs a list*

$$u_1,\dots,u_m\in\mathbb F_q^d$$

*with:*

**(i)** $m=O(d)$, and the list contains every standard basis vector of
$\mathbb F_q^d$;

**(ii)** *if a homogeneous quadratic polynomial $Q$ in $d$ variables does
not vanish at every point of the list, then*
$$\#\{j:Q(u_j)=0\}\le\lambda_0\,m.$$

*The running time is $2^{O(d)}$ bit operations; the constants in both
bounds may depend on $r$, which is fixed independently of $d$.*

Think of it as a **pencil of measurements**: a small, structured set of
points such that a quadratic cannot hide by being zero at most of them. In
Section 5 the list supplies rank-one steps of a random walk on a matrix
space; the eigenvalue estimate on that walk needs precisely "a quadratic
nonzero somewhere on the list vanishes rarely". The application takes
$d=O(\log(\text{input size}+1))$, so $2^{O(d)}$ time is polynomial in the
formula size.

The list is built from an explicit tower of function fields (the
Garcia–Stichtenoth tower). The proof has four stages: (1) the two local
shapes of the tower at a place; (2) all branches above every base place;
(3) an integral-lattice discriminant count; (4) a big space of global
functions, a norm-degree bound, and an explicit finite matrix.

### 4.2 The tower

Fix a power of two $r$ so large that, with $D=r+1$,
$$\frac{2D}{r^2-r}\le\lambda_0. \tag{3}$$
All finite fields below have characteristic two. Put $F=\mathbb F_q$,
$q=r^2$, and let $k$ be an algebraic closure of $F$. Define

$$S(Y)=Y^r+Y,\qquad
f(Y)=\frac{Y^{r+1}}{Y^r+Y}=\frac{Y^r}{Y^{r-1}+1}=\frac{1}{S(1/Y)},
\qquad S(x_{i+1})=f(x_i), \tag{4}$$

where $x_1$ is transcendental. The identities are rational-function
identities, and 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)$, with basis the monomials

$$e_{\!\boldsymbol a}=x_2^{a_2}\cdots x_l^{a_l},\qquad 0\le a_i<r. \tag{5}$$

For $l=1$ this is the one-element basis $1$. Then the same equations and
basis define the tower over $F(x_1)$.

Order of a Laurent series means the least exponent with nonzero
coefficient (order of zero is $+\infty$); an element of $k((z))$ is
*integral* if it lies in $k[[z]]$.

### 4.3 The two local extension shapes

Suppose an equation $S(X)=b(z)$ becomes integral after subtracting $S(g)$,
for a fixed $g\in k((z))$. Put $b_0=b-S(g)\in k[[z]]$. The polynomial
$\beta^r+\beta=b_0(0)$ has derivative one, so it has exactly $r$ roots,
differing by elements of $\mathbb F_r$; call one $\beta$. For each choice
there is a unique positive-order $u$ with $S(u)=b_0-S(\beta)$. If
$b_0-S(\beta)=\sum_{n>0}b_n z^n$, then

$$u_n=b_n+\mathbf 1_{\{r\mid n\}}\,u_{n/r}^r\qquad(n>0) \tag{6}$$

determines coefficients successively. So the equation **splits into $r$
distinct roots** $g+\beta+u$ in $k((z))$. The local algebra is $r$ copies
of $k((z))$, with integral lattice $k[[z]]^r$.

The other shape is a simple pole, and it accounts for ramification:

**Lemma (simple-pole extension).** *Let $b\in k((z))$ have order $-1$. Then
$X^r+X-b$ is irreducible over $k((z))$, its extension is a Laurent series
field $k((w))$ with $w=1/X$, $z$ has order $r$ in $w$, and the integral
lattice has $k[[z]]$-basis $1,w,\dots,w^{r-1}$ with discriminant of
$z$-order $2(r-1)$.*

*Proof.* $q_0(z)=1/b(z)$ has order one and a compositional inverse $\psi$.
In a new series field $k((w))$, set

$$z=\psi\!\left(\frac{w^r}{1+w^{r-1}}\right). \tag{7}$$

Substitution is injective $k((z))\to k((w))$, and $z=cw^r+\cdots$ with
$c\ne0$, while $X=1/w$ satisfies $X^r+X=b(z)$. The monomials $w^jz^n$,
$0\le j<r$, $n\ge0$, have distinct leading orders $j+rn$ exhausting all
nonnegative integers, so successively subtracting the lowest remaining
coefficient converges formally and gives

$$k[[w]]=\bigoplus_{j=0}^{r-1}w^j\,k[[z]].$$

The sum is direct (leading orders fall in distinct residue classes mod
$r$), so $[k((w)):k((z))]=r$ and $k((w))=k((z))(X)$, proving
irreducibility; separability follows from $S'(X)=1$. The displayed free
module is closed under multiplication, so its elements are integral over
$k[[z]]$; conversely a negative-$w$-order element cannot satisfy a monic
polynomial over $k[[z]]$ (its highest power would be the unique
smallest-order term). Hence $k[[w]]$ is the integral closure. The
embeddings send $X\mapsto X+c$, $c\in\mathbb F_r$, hence
$w\mapsto w_c=1/(X+c)$; for $c\ne c'$,
$w_c-w_{c'}=(c'-c)/((X+c)(X+c'))$ has $w$-order two, i.e. extended
$z$-order $2/r$. The evaluation matrix of $1,w,\dots,w^{r-1}$ is
Vandermonde; its determinant squared is the trace-pairing determinant,
of order $2\binom r2(2/r)=2(r-1)$. $\square$

**Trace and norm convention.** The trace of an element of a finite algebra
is the trace of its multiplication map, the norm its determinant. Over a
separable field or product of them, diagonalizing multiplication shows
trace is the sum of embedded values and the trace matrix of a basis is the
evaluation matrix times its transpose. This also gives the discriminant
identity used above.

### 4.4 All branches of the tower

**At infinity** (parameter $t=1/x_1$): $f(Y)-Y$ is integral, since
$f(Y)=Y/(1+Y^{1-r})$. The first right side has a simple pole, so the
simple-pole lemma gives a single branch with $x_2$ a simple pole of
parameter $1/x_2$. Repeating gives a single branch at every level.
By induction the defining polynomials are irreducible over the
completion, hence over the field, proving degree and basis over
$k(x_1)$, hence over $F(x_1)$ (an equation irreducible after extending
constants was already irreducible).

**At a finite $a$** with $t=x_1-a$: if $a\in\mathbb F_r\setminus\{0\}$,
$S(x_1)$ has a simple zero and $x_1^{r+1}$ is a unit, so the first right
side has a simple pole, and every subsequent step is again a simple-pole
extension. If $a\notin\mathbb F_r$, the first right side is integral and
the extension splits; an integral residue $\beta\notin\mathbb F_r$ has
$f(\beta)\ne0$, so no root of $S(Y)=f(\beta)$ is in $\mathbb F_r$, and
induction gives only unshifted integral splittings.

**Above zero** ($t=x_1$): while residues of $x_1,x_2,\dots$ are zero, all
extensions split without a shift. Since $f(Y)$ has order $r$ at zero and
$S(Y)$ order one,
$$\operatorname{ord}_t(x_j)=r^{j-1}$$
along the zero-residue branch. If the first nonzero residue is at $x_i$
($i\ge2$), it is $\alpha\in\mathbb F_r^\ast$ and
$\operatorname{ord}_t(x_i-\alpha)=\operatorname{ord}_t S(x_i)=r^{i-1}$.
Because $x_i^{r+1}-\alpha^2$ is divisible by $x_i-\alpha$, modulo integral
series

$$f(x_i)\equiv\frac{\alpha^2}{S(x_i)}=S\!\left(\frac{\alpha^2}{x_{i-1}}\right), \tag{8}$$

using $S(x_i)=f(x_{i-1})$ and $\alpha^2\in\mathbb F_r$. This step splits
after the shift $\alpha^2/x_{i-1}$, and every root satisfies
$x_{i+1}\equiv\alpha^2/x_{i-1}$ modulo integral series. For any earlier
small variable ($j>1$),
$$\frac1{x_j}\equiv\frac1{S(x_j)}=S\!\left(\frac1{x_{j-1}}\right)\pmod{k[[t]]}, \tag{9}$$
since the difference of the first two expressions is
$x_j^{r-2}/(1+x_j^{r-1})$, integral. Since $f(Y)\equiv Y$ at a pole, (8)
and (9) give, successively,
$$x_{i+s}\equiv\frac{\alpha^2}{x_{i-s}}\pmod{k[[t]]},\qquad 1\le s\le i-1,$$
each step a splitting with the stated shift; the last principal part
$\alpha^2/x_1$ is a simple pole, after which every extension is the
simple-pole extension. This covers branches where the tower stops early,
during descending shifts, or after ramification.

At every step the split factors or the single ramified factor account for
the full relative degree $r$, so 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 local factor is omitted.

### 4.5 Integral lattices and the discriminant count

Fix a base place with parameter $t$, $R=k[[t]]$. The product of branch
integral rings is a free $R$-module of rank $N$. In coefficient coordinates
relative to (5), call the resulting lattice $\Lambda\subset k((t))^N$, and
for a basis matrix $C$ set the **determinant order**
$\delta=\operatorname{ord}_t\det C$.

Two elementary facts. First, a square matrix over $R$ with nonzero
determinant reduces, by invertible row and column operations, to a diagonal
of units times powers of $t$ (choose a least-order entry, clear its row and
column); the $\dim_k$ of the cokernel equals the determinant order. Second,
for a branch $k((z))$ over $k((t))$, multiplication by a unit has unit
determinant on $k[[z]]$, while multiplication by $z$ has cokernel $k$ and
determinant order one, so

$$\operatorname{ord}_t\operatorname{Norm}_{k((z))/k((t))}(z^a u)=a
\qquad(a\in\mathbb Z,\ u\in k[[z]]^\ast). \tag{10}$$

The equality for negative $a$ is by multiplicativity; each branch residue
field is $k$, so no residue-degree multiplier appears.

For a relative extension with basis $(c_j)$ over a basis $(b_i)$ of a
separable algebra, the composed basis satisfies the discriminant tower
formula
$$\operatorname{disc}(b_ic_j)=\operatorname{disc}(b_i)^r\,
\operatorname{Norm}\bigl(\operatorname{disc}(c_j)\bigr), \tag{11}$$
because the evaluation map applies $r$ copies of the lower matrix then,
over each lower embedding, its relative matrix. The power basis (5) has
discriminant a nonzero constant: every relative step's additive roots
differ by nonzero elements of $\mathbb F_r$, so its Vandermonde
discriminant is a nonzero constant, and (11) preserves this.

Bookkeeping. Suppose the current local algebra has degree $n$, $B$
branches, integral discriminant base-order $d_{\mathrm{int}}$, and $R_0$ of
the branches ramify at the next step. Then
$$d_{\mathrm{int}}^{\mathrm{new}}=r\,d_{\mathrm{int}}+2(r-1)R_0,\qquad
B^{\mathrm{new}}=rB-(r-1)R_0,\qquad n^{\mathrm{new}}=rn.$$
Starting from $d_{\mathrm{int}}=0$, $n=B=1$, induction gives
$d_{\mathrm{int}}=2(n-B)$ at every level. Passing from the power basis to
an integral basis changes the trace matrix to $C^{\mathsf T}GC$ with $G$
the power-basis trace matrix; $\det G$ is a unit, so

$$\delta=N-B,\qquad 0\le\delta\le N. \tag{12}$$

At a good finite point $a\notin\mathbb F_r$ all variables are integral and
all extensions split, so the power basis is already an integral basis
(contained in the integral lattice with both determinant orders zero).

For a finite computation we need a bound on how negative orders go. At
every exceptional place, in every partial branch, each nonzero $x_i-c$,
$c\in\mathbb F_r$, has absolute order at most $N^2$ in the current
parameter: before a later ramified extension the zero-branch and
descending-pole orders are at most $N$, and the order of $x_i-c$ is zero
unless its residue equals $c$ or it has a pole; subsequent ramification
multiplies by a factor at most $N$. Set

$$F_0=(l+1)rN^2,\qquad H=(2N-1)F_0+D. \tag{13}$$

In every branch $t^{F_0}e_{\boldsymbol a}$ is integral (the monomial's pole
order is at most $(l-1)(r-1)N^2$), so $t^{F_0}R^N\subseteq\Lambda$.
Multiplication by an integral element preserves the integral lattice, so
its trace is in $R$; each entry of $G$ has order at least $-2F_0$. If $y$
is integral, $\operatorname{tr}(y\,e_{\boldsymbol a})$ has order at least
$-F_0$; if $t^Dy$ is integral, at least $-F_0-D$. Since $\det G$ has order
zero, each cofactor has order at least $-2F_0(N-1)$, and Cramer's rule
gives the **lattice sandwich**

$$t^{F_0}R^N\subseteq\Lambda_a\subseteq t^{-H}R^N\quad(a\in\mathbb F_r),$$
$$t^{F_0-D}R^N\subseteq t^{-D}\Lambda_\infty\subseteq t^{-H}R^N. \tag{14}$$

All shifts are powers of the base parameter, including at infinity.
Membership in any target lattice inside $t^{-H}R^N$ is therefore determined
by the coefficient jet of exponents from $-H$ through $F_0-1$; changing the
omitted tail adds an element of the target lattice.

### 4.6 A large space of global functions

In coefficient coordinates, let $V_H$ consist of functions whose every
coefficient is a linear combination of
$$1,x_1,\dots,x_1^H,\qquad (x_1-a)^{-j}\quad(a\in\mathbb F_r,\ 1\le j\le H).$$
These are independent (principal parts at distinct finite poles first
determine all negative-power coefficients, then the polynomial the rest),
so

$$\dim_k V_H=N\,[1+(r+1)H].$$

At each of the $r$ bad finite points and at infinity its coefficient
expansion lies in $t^{-H}k[[t]]^N$. Let $\mathcal L_k$ be the subspace of
$V_H$ integral at every finite place and integral at infinity after
multiplying by $t^D$.

The finite-place quotient by $\Lambda_a$ has dimension $NH+\delta_a$
(scale the inclusion to an integral matrix and diagonalize); at infinity
the target $t^{-D}\Lambda_\infty$ has determinant order
$\delta_\infty-ND$, so its quotient has dimension $NH+\delta_\infty-ND$.
Expansion followed by these quotient maps is one linear map from $V_H$ to
the direct sum; its rank is at most the target dimension. Using (12),

$$\dim_k\mathcal L_k\ge N[1+(r+1)H]-\Big((r+1)NH+\sum_{a\in\mathbb F_r\cup\{\infty\}}\delta_a-ND\Big)\ge N(D-r)=N. \tag{15}$$

No conditions are imposed at other places (all integrals there), and the
space contains the constant function $1$.

**Descent to the ground field.** Coefficientwise $q$-Frobenius, fixing the
formal variables $x_i$, preserves the tower equations and permutes the
branches above each exceptional place, so it preserves $\mathcal L_k$ in
the fixed rational-coefficient basis of $V_H$. Putting a basis matrix in
reduced row echelon form and applying Frobenius gives the same reduced form
with the same pivots; uniqueness forces every entry to be Frobenius-fixed,
hence in $F$. So the space $\mathcal L$ of $F$-rational coefficient
vectors has

$$\dim_F\mathcal L=\dim_k\mathcal L_k\ge N. \tag{16}$$

The algorithm below obtains $\mathcal L$ from an explicit finite
ground-field matrix, not by searching for Frobenius-fixed vectors.

### 4.7 Evaluation and the quadratic zero bound

There are $(q-r)N$ rational evaluation tuples above $x_1\in F\setminus
\mathbb F_r$: if $\beta\in F\setminus\mathbb F_r$ then
$\beta^r+\beta\in\mathbb F_r^\ast$ and $\beta^{r+1}\in\mathbb F_r^\ast$,
so $f(\beta)\in\mathbb F_r^\ast$; the map $S:F\to\mathbb F_r$ is
$\mathbb F_r$-linear with kernel $\mathbb F_r$, hence onto; each
$S(Y)=f(\beta)$ has exactly $r$ distinct roots in $F\setminus\mathbb F_r$,
and induction completes the count. All functions of $\mathcal L$ are
regular there, so evaluation is well defined.

**Norm degree bound.** Let $a\ne0$ lie in the span of products of two
elements of $\mathcal L_k$. It is integral at every finite place and
$t^{2D}a$ is integral at infinity, and its field norm to $k(x_1)$ is
nonzero. At each finite place the local multiplication matrix is integral,
so the norm has no finite poles and is a polynomial in $x_1$; at infinity,

$$0\le\operatorname{ord}_t\operatorname{Norm}(t^{2D}a)
=2DN+\operatorname{ord}_t\operatorname{Norm}(a),$$
so
$$\deg\operatorname{Norm}(a)\le 2DN. \tag{17}$$

At a good base value $b$ the local algebra is $N$ copies of
$k((x_1-b))$; the local norm is the product of the $N$ integral branch
values, and
$$\operatorname{ord}_{x_1-b}\operatorname{Norm}(a)
=\sum_{j=1}^N\operatorname{ord}_{x_1-b}(a_j).$$
Each zero evaluation contributes at least one, several zero branches above
the same $b$ counted with full multiplicity. So (17) bounds the total number
of zero evaluation positions by $2DN$.

**Injectivity and selection.** Evaluation on these positions is injective on
$\mathcal L$: a nonzero function vanishing everywhere, multiplied by the
constant $1$, would give $\deg\operatorname{Norm}\ge(q-r)N>2DN$, from
Equation (3). Choose $l$ least with $N=r^{l-1}\ge d$ and pick $d$
independent functions in $\mathcal L$. Their $d\times(q-r)N$ evaluation
matrix has rank $d$; choosing $d$ independent columns and left-multiplying
by the inverse square matrix gives $d$ new functions of $\mathcal L$ whose
evaluation vectors include all standard basis vectors. Call the resulting
$m$ columns $u_1,\dots,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 zero bound and (3) then give

$$\#\{j:Q(u_j)=0\}\le2DN\le\lambda_0(q-r)N=\lambda_0 m. \tag{18}$$

Since $N<rd$ for this $l$, $m=O_r(d)$. This is the algebraic content of the
pencil lemma; it remains to justify the algorithm and its running time.

### 4.8 A finite algorithm and its precision

**Small constant fields.** $F=\mathbb F_q$ and $\mathbb F_r$ can be fixed
once and for all. For a splitting step, if the constant term of the shifted
right side lies in a current finite field $\mathbb F_Q\supseteq F$ and
$S(\beta)\in\mathbb F_Q$, then $\beta^Q-\beta\in\mathbb F_r$ (apply $S$);
that difference is $Q$-Frobenius-fixed, so in characteristic two
$\beta^{Q^2}=\beta$ and a *quadratic* extension suffices. It is built
without enumerating the field: $y\mapsto y^2+y$ on $\mathbb F_Q$ has kernel
$\{0,1\}$ and image of codimension one, so linear algebra finds $b$ outside
the image and $Y^2+Y+b$ is irreducible; the equation $S(\beta)=b_0$ is a
binary linear system in that extension, all solutions differing by
elements of $\mathbb F_r$. At most one quadratic extension per tower level
is needed; expressing all constants in a common field of degree
$$E=2^{l-1}\le N \tag{19}$$
over $F$ avoids enumerating an algebraic closure.

**Precision.** Put $M_0=N^2$. A nonzero $x_i-c$ of order in $[-M_0,M_0]$
known modulo the current parameter to the power $K>M_0$ has relative error
of order at least $K-M_0$; multiplication, integer powers, and inversion
preserve this (inversion: $(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 such factors has absolute accuracy at least $K-C_rM_0$.
Subtraction preserves absolute accuracy even when known principal parts
cancel; in a splitting step the branch description already proves
$f(x_i)-S(g)$ integral, so computing its input factors through
$L+C_rM_0$ determines it through order $L$, and (6) determines positive
coefficients through $L$ from right-side coefficients. In a simple-pole
step compute $q_0=1/f(x_i)$ (order one), invert under composition through
the needed order, substitute $w^r/(1+w^{r-1})$ to obtain (7); if $z(w)$ is
known mod $w^B$ its relative error has order at least $B-r$, and an old
Laurent series of pole order at most $M_0$ changes only in orders at least
$B-r-rM_0$; so $B\ge L+r(M_0+1)$ suffices for output precision $L$, with
old coefficients through $\lceil L/r\rceil+M_0+2$ enough. Choose $a_r$
depending only on $r$ so that $K_N=(2N)^{a_r}$ dominates $M_0$ and all fixed
constants. The rules are covered by the single backward precision budget

$$L_{i-1}=K_N\,(L_i+K_N+H+D). \tag{20}$$

**Final integrality tests.** A rational coefficient basis element of $V_H$
times a power-basis monomial has, in a final branch (including the infinity
adjustment), pole order bounded by
$$P_0=HN+(r-1)(l-1)N^2+DN. \tag{21}$$
Knowing each elementary factor with relative error of order greater than
$P_0$ makes the unknown remainder integral; a large fixed multiple
$$L_{\mathrm{end}}=C_r'(H+D+l+1)N^2 \tag{22}$$
as absolute factor precision determines every negative coefficient,
including after the $t^D$ multiplier at infinity. Cancellation in a linear
combination cannot reveal an uncomputed negative coefficient because each
individual unknown remainder is already integral.

Use (20) backward from $L_{\mathrm{end}}$, then run the forward branch
expansions at those precisions. The branch type and its shift are fixed by
the explicit residue and descending-shift rules. Record, for each basis
input, all negative coefficients in every branch (with the infinity
multiplier included); their vanishing is exactly the linear system defining
$\mathcal L$.

**Size.** There are at most $(r+1)N$ exceptional branches at each level;
$l=1+\log_r N$, so (13) gives $F_0=O_r(N^3)$, $H=O_r(N^4)$. The number of
rational coefficient unknowns is $N[1+(r+1)H]=O_r(N^5)$, and
$L_{\mathrm{end}}=O_r(N^6)$; keeping a full window of this length per branch
gives only $O_r(N^7)$ negative-coefficient equations over the finite
constant fields, and expanding each in an $F$-basis of the common field in
(19) gives at most $O_r(N^8)$ equations over $F$. Solving this explicit
matrix computes $\mathcal L$; (16) proves its dimension is at least $N$.
The computation never infers dimension by testing random functions.

Iterating (20) yields every retained series length at most
$(2N)^{O_r(l+1)}$; truncated addition, multiplication, inversion, and
composition use a number of field operations polynomial in these lengths.
For $N\ge2$, $\log((2N)^{O_r(l+1)})=O_r((\log N)^2)=O_r(N)$, and $N=1$ is a
fixed computation, so total bit complexity is $2^{O_r(N)}$. Enumerating the
evaluation tuples and selecting independent columns adds polynomial time.
Since $N<rd$, the whole construction takes $2^{O_r(d)}$ time, completing the
proof of the pencil lemma.

---
## 5. The bit-test system

We now build the actual tests. A **proof** is a bit assignment on an
explicitly constructed finite set of positions. A **test law** is a
distribution over 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.

Standard preprocessing puts every 3CNF formula into a convenient shape:
clauses have three literal positions with repetitions permitted; repeat
literals to pad a shorter clause; replace an empty clause by two opposing
unit clauses on a fresh variable and pad; replace a formula with no clauses
by a single tautological clause. These preserve satisfiability and cost
linear time.

### 5.1 The statement

**Theorem (bit-test system).** *For every fixed $\lambda>0$ there are
constants $\eta>0$, $B<\infty$, and a fixed finite list of bounded-arity
test laws with the following properties. From a Boolean 3CNF formula one
constructs, in polynomial time, a finite uniform space $\mathcal S$ of bit
positions and these test laws.*

**(i)** *Every individual question marginal is at most $B$ times uniform
measure on $\mathcal S$. All samplers are polynomially enumerable finite
weighted lists with rational probabilities; every positive seed probability
is at least inverse-polynomial in the input size.*

**(ii)** *If the formula is satisfiable, some assignment $y:\mathcal S\to
\mathbb F_2$ is accepted by every test in every support.*

**(iii)** *If the formula is unsatisfiable, every assignment fails one of
the test laws with probability greater than $\eta$.*

**(iv)** *There is an exchangeable law of $(s_1,s_2,s_3,s_4)\in\mathcal S^4$
with uniform marginals, whose pair operator (conditional expectation of any
coordinate given any other, on mean-zero $L^2(\mathcal S)$) has norm at most
$\lambda$, and whose support satisfies*
$$y_{s_1}+y_{s_2}+y_{s_3}+y_{s_4}=0\quad\text{in }\mathbb F_2$$
*for the assignment in (ii).*

*All constants, including the degrees of the polynomial size and time
bounds, depend only on $\lambda$. Two independent copies of the law in
(iv), paired coordinatewise, have the same pair-operator bound on
$\mathcal S^2$ and give the corresponding parity identity for the
expressions $y_i+y_j$.*

The finiteness of the test list and the constant soundness $\eta$ are the
whole difficulty. The construction runs in four layers: a spectral bound
for a random walk on a matrix space; a masked four-point parity law; a
principal-minor encoding of Boolean tables; and a self-correction argument
that turns almost-quadratic lines into exactly quadratic lines on
almost every line.

### 5.2 The matrix walk

Pad the variable set to addresses in $\{0,1\}^d$ with $d\ge1$ and
$d=O(\log(\text{input size}+1))$; dummy addresses impose no clauses. Fix the
square field $\mathbb F=\mathbb F_q$ of characteristic two and the pencil
$u_1,\dots,u_m\in\mathbb F^d$ of Lemma 4.1; the field is chosen large and
the pencil parameter $\lambda_0$ small. Set

$$G_0=\operatorname{Span}_{\mathbb F}\{u_ju_j^{\mathsf T}:1\le j\le m\},
\qquad G=\operatorname{Mat}_{b\times b}(G_0),$$

regarded as $(bd)\times(bd)$ matrices with $d\times d$ blocks; we may take
$b=101$, with block allocation described shortly. The pencil contains every
standard basis vector, so $G_0$ contains every diagonal matrix, and
$\dim_{\mathbb F}G\le b^2 m=O(d)$.

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

**Lemma (matrix walk).** *On mean-zero $L^2(G)$, $\mathsf T$ has norm at most
$\lambda_1=\lambda_0+q^{-1}$. In particular, for every nonempty
$D\subseteq G$,*
$$\frac{\langle \mathbf 1_D,\mathsf T\mathbf 1_D\rangle}{\mu(D)}
\le\mu(D)+\lambda_1. \tag{24}$$

*Proof.* Fix a nonzero $\mathbb F_2$-linear functional $\ell:\mathbb F\to
\mathbb F_2$. Every additive character of $G$ is $A\mapsto
(-1)^{\ell(L(A))}$ for an $\mathbb F$-linear functional $L:G\to\mathbb F$,
because $(a,x)\mapsto\ell(ax)$ is nondegenerate ($a\ne0$ admits $x$ with
$\ell(ax)=1$), and counting over a basis gives all characters. For such an
$L$, (23) gives $L(h)=c^{\mathsf T}M_j e$ with every entry of $M_j$ a
homogeneous quadratic form in $u_j$. If $L\ne0$ some entry is nonzero on
the list (take $c,e$ coordinate vectors to see the directions span $G$),
and that entry vanishes on at most $\lambda_0 m$ indices by the pencil.
For $M_j\ne0$, averaging the character first over $c$ gives zero unless
$M_je=0$, so the full average is $q^{-\operatorname{rank}M_j}\le q^{-1}$;
the remaining indices contribute at most one. Orthogonality of additive
characters diagonalizes $\mathsf T$, proving the norm bound, and applying
it to $\mathbf 1_D-\mu(D)$ proves (24). $\square$

### 5.3 The masked four-point parity law

The field oracle is a function $P:G\to\mathbb F$, encoded on positions
$$\mathcal S=G\times\mathbb F^\ast,\qquad y_{(A,\sigma)}=\ell(\sigma P(A)).$$
The vector of all $q-1$ masks determines $P(A)$ uniquely, so any field
query is a batch of mask queries that must decode to a field element.

Choose four distinct times $t_1,t_2,t_3,t_4\in\mathbb F$, an independent
uniform $A\in G$, an independent $h\sim\mathsf D$, and an independent
uniform $\sigma\in\mathbb F^\ast$. Put

$$s_i=(A+t_ih,\ \sigma\alpha_i),\qquad
\alpha_i=\Big(\prod_{j\ne i}(t_i-t_j)\Big)^{-1}. \tag{25}$$

This law is exchangeable with uniform marginals. If $P$ restricted to every
sampled line is a polynomial of degree at most two, Lagrange interpolation
gives $\sum_i\alpha_iP(A+t_ih)=0$; applying $\ell(\sigma\,\cdot)$ gives the
binary parity identity $y_{s_1}+\cdots+y_{s_4}=0$ of Theorem 5.1(iv).

**Lemma (masked pair-mixing).** *Every pair-operator of (25) has mean-zero
norm at most $\max\{\lambda_1,\,2/(q-3)\}$.*

*Proof.* By exchangeability it suffices to treat the first two times, call
them $a,b$, with the others $c,d$. For every fixed $(a,b,c,d,h)$ and every
$(x,\mathsf m)\in G\times\mathbb F^\ast$,
$$\Pr[(A+ah,\sigma\alpha_a)=(x,\mathsf m)\mid a,b,c,d,h]
=\tfrac{1}{|G|(q-1)}.$$
Conditioning on the complete first position preserves the joint time and
direction law, and the second position is
$(x+(b-a)h,\ \mathsf m\,\alpha_b/\alpha_a)$. For every time tuple
$(b-a)h\sim\mathsf D$, independent of the mask multiplier, so the pair
operator is the tensor product of $\mathsf T$ and the averaged mask
permutation. For fixed distinct $a,b,c$, put $k=(b-c)/(a-c)$; direct
cancellation in characteristic two gives
$\alpha_a/\alpha_b=k\,(b-d)/(a-d)$, and the fractional-linear map on the
right is one-to-one on the projective line, sending the excluded projective
arguments $a,b,c,\infty$ to $\infty,0,k^2,k$; so for allowed $d$ the ratio
is uniform on $\mathbb F^\ast\setminus\{k,k^2\}$ (with $k\notin\{0,1\}$,
these are distinct), and the inverse ratio likewise omits exactly two
nonzero values. On mean-zero functions of the uniform mask the sum of all
$q-1$ multiplicative permutations is zero, so the average with two
permutations removed has norm at most $2/(q-3)$; averaging over $a,b,c$
preserves this. The spatially centered and mask-only mean-zero subspaces
are invariant, the former has norm at most $\lambda_1$, the latter the just
proved bound, and they exhaust the orthogonal complement of the constants.
$\square$

Choose the field and pencil so that

$$\lambda_1<10^{-6},\qquad
\max\{\lambda_1,2/(q-3)\}\le\lambda,\qquad
\frac{6}{q-1}\le\frac{1}{16}. \tag{26}$$

On two independent copies the pair operator is the tensor square; splitting
each factor into constants and mean-zero functions preserves the bound,
giving the final assertion of Theorem 5.1 once the line-polynomial
assignment is built.

### 5.4 Boolean tables and polynomial slack

Let $T$ be the principal matrix on the first three blocks, $n=3d$. For
$I\subseteq[n]$ define $p_I(T)=\det T_{I,I}$, with $p_\varnothing=1$. On a
Boolean diagonal $T=\operatorname{diag}(z)$ these are the monomials
$\prod_{i\in I}z_i$, and every table on $\{0,1\}^n$ has a unique expansion in
them (at the indicator of a set $J$ the value is $\sum_{I\subseteq J}a_I$,
determining $a_I$ by increasing $|J|$). Extend a Boolean table to matrices
by replacing monomials by principal minors.

For $a=(a_1,a_2,a_3)\in\{0,1\}^3$, let $E_a(T)$ be the public extension of
the table that is one if the input contains a clause on the ordered triple
whose falsifying answer pattern is $a$, zero otherwise (multiple clauses
and repeated variables change nothing). 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
($\pi_1$ the identity), and set $X_i(A)=X(\pi_iA)$. For each $a$ put
$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 a Boolean diagonal we want

$$X^2-X=0,\quad Y_a-E_aM_{a,1}=0,\quad Z_a-M_{a,2}M_{a,3}=0,\quad Y_aZ_a=0. \tag{27}$$

There are $25$ identities. In a satisfying assignment, extend the
assignment table to $X$ using the first block, and the Boolean tables
$E_aM_{a,1}$ and $M_{a,2}M_{a,3}$ to $Y_a,Z_a$ using $T$. Each left side of
(27) is a linear combination of products $p_Ip_J$ vanishing on all Boolean
diagonals; for the last, simultaneous nonzero values would exhibit the
forbidden clause pattern.

The following reduction supplies the *slack* that makes (27) testable at
uniform matrix arguments.

**Lemma (minor-product slack).** *A linear combination of products
$p_I(T)p_J(T)$ that vanishes on all Boolean diagonal matrices is a sum of
terms of the form*
$$cMN\,T_{ij},\qquad cMN\,T_{ij}(T_{ii}-1),\qquad cMN\,(T_{ii}^2-T_{ii}),
\tag{28}$$
*where $i\ne j$ in the first two, $c\in\mathbb F$, and $M,N$ are arbitrary
square minors, possibly empty.*

*Proof.* For $i\in K$ write the row-$i$ expansion
$p_K=T_{ii}p_{K\setminus\{i\}}+\sum_{j\ne i}T_{ij}C^K_{ij}$, where
$C^K_{ij}$ is the signed cofactor when $j\in K$, zero otherwise; every
nonzero cofactor is a scalar sign times an arbitrary minor. If
$i\in J\setminus I$, expanding $p_J$ and $p_{I\cup\{i\}}$ along row $i$
cancels the diagonal terms and gives
$$p_Ip_J-p_{I\cup\{i\}}p_{J\setminus\{i\}}
=\sum_{j\ne i}T_{ij}\big(p_I C^J_{ij}-C^{I\cup\{i\}}_{ij}p_{J\setminus\{i\}}\big).$$
If $i\in I\cap J$, first expand $p_J-p_{J\setminus\{i\}}$ and then the
$p_I$ multiplying $T_{ii}-1$, giving
$$p_Ip_J-p_Ip_{J\setminus\{i\}}
=(T_{ii}^2-T_{ii})\,p_{I\setminus\{i\}}p_{J\setminus\{i\}}
+\sum_{j\ne i}T_{ij}p_IC^J_{ij}
+\sum_{j\ne i}T_{ij}(T_{ii}-1)C^I_{ij}p_{J\setminus\{i\}}.$$
Each residual term is of a form in (28). Starting from $(I,J)$, pick an
element of the second set and apply one of these two identities; the second
set loses that element and the union is unchanged, so after exactly $|J|$
steps the remaining product is $p_{I\cup J}$. Telescoping reduces every
product to this canonical principal minor plus permitted residuals.
Applying the reduction to the given combination leaves $\sum_U b_Up_U$ plus
residuals. All residuals vanish on Boolean diagonals; at the indicator
diagonal of a set $S$ we get $\sum_{U\subseteq S}b_U=0$, and induction on
$|S|$, beginning with the empty set, gives every $b_S=0$. $\square$

### 5.5 Tag banks and the selector construction

Reserve two disjoint tag banks, each of three new blocks. Let $b_r(i)$ be
the copy of address index $i$ in bank $r\in\{1,2\}$. For a minor
$M(T)=\det T_{R,C}$ define the extended minor
$$\mathsf E^{(r)}_{ij}M(A)=\det A_{(R,b_r(i)),\,(C,b_r(j))},$$
appending the new row and column to their lists (for the empty minor this is
just the appended entry). If $V$ is supported in principal bank $r$, the
extended submatrix has exactly one entry of that bank, its appended corner,
with corner cofactor $M$; writing $\Delta_VL(A)=L(A+V)-L(A)$,

$$\Delta_V(\mathsf E^{(r)}_{ij}M)=V_{b_r(i),b_r(j)}\,M. \tag{29}$$

For each of the $25$ identity differences, group the residual terms of
Lemma 5.4 by the three forms of (28) and construct three fields $L_1,L_2,L_3$
by summing with the same coefficients:

$$
\begin{array}{c|c}
\text{residual term} & \text{placed in the field}\\ \hline
c\,T_{ij}MN & c(\mathsf E^{(1)}_{ij}M)N \text{ in }L_1\\
c\,T_{ij}(T_{ii}-1)MN & c(\mathsf E^{(1)}_{ij}M)(\mathsf E^{(2)}_{ii}N)
\text{ in }L_2\\
c\,(T_{ii}^2-T_{ii})MN & c(\mathsf E^{(1)}_{ii}M)N \text{ in }L_3
\end{array}
$$

Let $v(T)$ copy the off-diagonal part of $T$ into bank one, $w(T)$ copy
$\operatorname{diag}(T)-I$ into bank two, and $u(T)$ copy
$\operatorname{diag}(T)^2-\operatorname{diag}(T)$ into bank one. These
shifts lie in $G$ (copying a full block preserves $G_0$, and every diagonal
matrix is in $G_0$) and leave $T$ unchanged, so (29) gives the identity

$$F(A)=\Delta_{v(T)}L_1(A)+\Delta_{v(T)}\Delta_{w(T)}L_2(A)
+\Delta_{u(T)}L_3(A) \tag{30}$$

for the honest difference $F$. Moreover $L_1,L_3$ are affine under all
translations in bank one, and $L_2$ is separately affine under translations
in each bank (its first extended factor depends affinely on bank one only,
its second on bank two only; cross entries to address indices do not change
under principal-bank translations).

The one assignment field, sixteen gate fields, and seventy-five slack
fields make $92$ fields. Give each its own selector index in a fresh block;
with the three address and six tag blocks, this uses $101$ blocks. Every
honest field 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 term $cMN$ by the minor with appended
row and column $s_F$, and sum all packed terms over the $92$ fields to get
$P$. If $v_F$ is the unit diagonal matrix at $s_F$, the corner-cofactor
calculation gives

$$\Delta_{v_F}P=F. \tag{31}$$

Terms of other fields omit $s_F$, so they contribute nothing; and
$v_F\in G$.

Every minor of $A+th$, with $h$ as in (23), is affine in $t$: expand the
determinant by multilinearity in columns; terms using two perturbed columns
vanish because those columns are proportional. Hence each packed product,
and $P$, has line degree at most two.

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

1. **Line law:** sample uniform $A$ and $h\sim\mathsf D$, query $P(A+th)$
   for all $t\in\mathbb F$, check degree at most two.
2. **Identity laws (25):** check (30)'s analogue of (27) at uniform $A$,
   with the three designated slack fields and the corresponding difference.
3. **Assignment invariance:** sample a uniform translation $v\in G$ whose
   first diagonal block is zero, check $X(A+v)=X(A)$ at uniform $A$.
4. **Bank laws:** for each slack field and each bank in which it must be
   affine, with $B_r$ the subspace supported in bank $r$, check
   $$\Delta_w\Delta_vL(A)=0\ (v,w\text{ iid uniform in }B_r),\qquad
   \Delta_{av}L(A)=a\Delta_vL(A)\ (v\text{ uniform in }B_r)$$
   at uniform $A$, one law per fixed scalar $a\in\mathbb F$.

Every displayed value is evaluated through its selector difference and all
masks; queries are made even at vanishing coefficients, keeping each list
length fixed. All query points have uniform marginals ($G$ carries uniform
measure; translations and block swaps are bijections; the tag shears
$A\mapsto A+v(T(A))$ are bijections because they fix their source $T$, with
inverse the subtraction of the same shift). A fixed mask at a uniform base
is at most $q-1$ times uniform on $\mathcal S$, so $B=q-1$ works.

The honest construction satisfies every law identically with line degree at
most two, proving perfect completeness, including the auxiliary parity
identity. Witness-dependent fields appear only in completeness; all public
laws are fixed without knowing a satisfying assignment.

### 5.6 Deterministic correction of almost-quadratic lines

Constant soundness needs more than "identities hold at most matrices",
since the Boolean diagonals may be sparse; we first force *exact* line
identities by correcting a small set. This is a local-to-global
self-correction problem.

**Lemma (quadratic correction).** *Put $\gamma=10^{-3}$. Suppose the line
law of $P:G\to\mathbb F$ fails with probability at most $\delta^2$, where*
$$2\delta+\lambda_1<\gamma/2,\qquad
1-4\gamma-4\delta-\tfrac{2}{q-1}>\delta+\lambda_1,\qquad
27\gamma+5\delta<1. \tag{32}$$
*Then there is a scalar-invariant set $H$ of directions of $\mathsf D$-mass
at least $1-\delta$ and a function $P'$ differing from $P$ on at most
$2\delta$ of $G$ such that $t\mapsto P'(A+th)$ has degree at most two for
every $A$ and $h\in H$.*

*Proof.* Let $H$ consist of directions whose fraction of failing bases is
at most $\delta$; mark those points whose fraction of failing directions
exceeds $\delta$, giving $D_0$ with $\mu(D_0)\le\delta$, and $\mathsf
D(H)\ge1-\delta$ by Markov. Both notions are scalar-invariant. Enlarge
$D_0$ by adding an outside point $x$ whenever
$\Pr_h[x+h\in D]\ge\gamma$. If the seed $D_0$ has $k\ge1$ points, the first
time the set reaches size $2k$ it has internal directed edge mass at least
$k\gamma/|G|$ (each added source contributed that at its addition, and those
edges stay internal), and dividing by the density gives at least
$\gamma/2$, contradicting (24) and $2\delta+\lambda_1<\gamma/2$; if $k=0$
no point can be added. So the final $D$ has density at most $2\delta$, and
every outside point has entry probability $<\gamma$ into $D$; call these
outside points clean.

Fix $h\in H$ and four distinct times $t_i$. Let $J$ be the set of bases
with four clean positions but $\sum_i\alpha_iP(A+t_ih)\ne0$; then
$\mu(J)\le\delta$ since each such base gives a failing $h$-line. For
$A\in J$ put $z_i=A+t_ih$ and sample independent $k\sim\mathsf D$, uniform
$a\in\mathbb F^\ast$. Since $z_i\notin D_0$, each
$s\mapsto P(z_i+sk)$ is quadratic except on an event of probability at most
$4\delta$; off that event the four-position discrepancy is a degree-two
polynomial in $s$, nonzero at zero, so zero for at most two choices of
$a\in\mathbb F^\ast$. Separately each $z_i+ak$ is missing with probability
at most $\gamma$ (since $ak\sim\mathsf D$). A union bound gives
$$\Pr_{k,a}[A+ak\in J]\ge1-4\delta-4\gamma-\tfrac{2}{q-1}.$$
The step $ak\sim\mathsf D$ (including at zero), so a nonempty $J$ would
contradict (24) and (32). Hence every four-position relation on clean
positions is exact.

Now fill the missing points one at a time, maintaining that every assigned
point has entry probability at most $\gamma$ into the current missing set
and that every $H$-direction four-position relation on assigned points is
exact. If the missing set is nonempty, (24) supplies $x$ in it with entry
probability at most $\gamma$; removing $x$ only decreases entry
probabilities.

Fix three distinct nonzero times $a_1,a_2,a_3$ and interpolation
coefficients $\ell_1,\ell_2,\ell_3$ for evaluation at zero. A direction $k$
*predicts* $\sum_i\ell_iP'(x+a_ik)$ if its three positions are already
assigned, else gives a fixed default. For independent $h,k$, require the
six axis points $x+a_ih,x+a_jk$ and nine grid points $x+a_ih+a_jk$ to be
assigned. The six axis failures cost at most $6\gamma$; after an assigned
first-axis point is exposed, the independent second direction reaches the
missing set with probability at most $\gamma$, so the nine grid failures
cost at most $9\gamma$; requiring $h,k\in H$ costs at most $2\delta$. On
the resulting event, interpolating the grid by rows then columns shows the
two predictions agree, because all relations used involve already assigned
points. The full prediction distribution has collision probability at least
$1-15\gamma-2\delta$, hence largest atom at least that; choose one modal
value $m_x$ once. A random prediction equals $m_x$ and uses an assigned
triple except with probability at most $18\gamma+2\delta$; at an old
assigned center the analogous prediction reproduces its value except with
probability at most $3\gamma+\delta$.

Consider any fixed relation newly enabled by assigning $x$. A zero
direction gives an automatic constant-line identity; otherwise its four
positions are distinct and only one is $x$. For a fresh transverse
direction $k$, simultaneous correct interpolation from old triples at its
four centers fails with probability at most
$(18\gamma+2\delta)+3(3\gamma+\delta)=27\gamma+5\delta<1$, so some such
$k$ exists. Each of the three translated copies lies entirely in the old
assigned set and is zero; interpolating those three identities back
recovers the old values and the selected $m_x$, so the original relation is
zero. Repeated positions cause no problem (same value); a position equal to
the still-missing center was excluded by the old-assignment event. The modal
value is fixed before the relation is considered, so different transverse
directions give relations for the same value with no union bound over
relations or peeling steps. This proves the induction. At the end all
four-position relations hold in every direction in $H$; interpolating at
three distinct parameters and then at a fourth gives the asserted line
degree, and only the original enlarged set of density at most $2\delta$ was
changed. $\square$

### 5.7 Support gaps and exact bank affinity

**Lemma (line support gap).** *Suppose a scalar-invariant direction set has
$\mathsf D$-mass at least $1-\rho$, and $F:G\to\mathbb F$ has degree at most
$D<q-1$ on every line in those directions. Then either $F=0$ identically or*
$$\mu(\operatorname{supp}F)\ge1-\rho-\frac{D}{q-1}-\lambda_1. \tag{33}$$
*Proof.* From a support point $x$, sample $h\sim\mathsf D$ and independent
uniform $a\in\mathbb F^\ast$. On a good direction the nonzero line
polynomial has at most $D$ roots among those scalars, so $x+ah$ is in the
support with probability at least $1-\rho-D/(q-1)$; the law of $ah$ is the
original direction law. Average over support points and apply (24). $\square$

Suppose every ordinary binary law fails with probability at most $\eta$.
Decode the mask vector to $P(A)$ wherever valid and choose arbitrary values
elsewhere; acceptance of a binary test certifies valid encodings and its
field relation, so every decoded field law also fails with probability at
most $\eta$. Let $Q$ be a fixed upper bound on master-field queries per law
($Q=q+32$ suffices). Put $\delta=\sqrt\eta$ and apply Lemma 5.6; replacing
$P$ by $P'$ raises each field-law failure by at most $2Q\delta$, since each
master query is uniform. Write

$$\tau=\eta+2Q\delta. \tag{34}$$

Intersecting the pullbacks of $H$ under $\pi_1,\pi_2,\pi_3$ gives a common
scalar-invariant direction set of missing mass at most $K_{\mathrm{sw}}
\delta$, $K_{\mathrm{sw}}=3$. Every fixed translate of every corrected field
and of every $X_i$ has line degree at most two on this set, and with the
conservative degree bound six, (33) gives the support lower bound

$$\kappa=1-K_{\mathrm{sw}}\delta-\frac{6}{q-1}-\lambda_1 \tag{35}$$

for any nonzero discrepancy to which that bound applies.

**Exact invariance.** A fixed-parameter assignment-invariance discrepancy has
degree at most two; if nonzero it fails on at least a $\kappa$ fraction of
bases, so at least $1-\tau/\kappa$ tested translations preserve $X$
identically. These translations form an additive subgroup; a subgroup of a
finite additive group of density greater than one half is the whole group
(else one disjoint coset has the same size). So assignment invariance is
exact provided $\tau/\kappa<1/2$.

**Exact bank affinity.** For a bank $B_r$ and slack field $L$, fix $v$ and
let $W_v=\{w\in B_r:\Delta_vL(A+w)=\Delta_vL(A)\ \forall A\}$ be the
translation stabilizer of $\Delta_vL$, a subgroup. Each fixed $(v,w)$
discrepancy has line degree at most two, and the fraction of pairs for which
it is not identically zero is at most $\tau/\kappa$. If $\tau/\kappa<1/16$,
Markov leaves more than three quarters of $v$ for which more than three
quarters of $w$ are valid, forcing $W_v=B_r$. The set
$V=\{v\in B_r:\Delta_vL\text{ invariant under all }B_r\text{ translations}\}$
is a subgroup: for $u,v\in V$ the difference cocycle gives
$\Delta_{u+v}L(A)=\Delta_uL(A+v)+\Delta_vL(A)=\Delta_uL(A)+\Delta_vL(A)$
and $\Delta_{-v}L(A)=-\Delta_vL(A)$, so $V=B_r$ and $v\mapsto\Delta_vL(A)$
is additive for every $A$. For each scalar $a$, the map
$v\mapsto(\Delta_{av}L(A)-a\Delta_vL(A))_A$ is now additive; its kernel has
density at least $1-\tau/\kappa>1/2$ by that scalar's test and the support
gap, hence is $B_r$, proving exact $\mathbb F$-affinity in each required
bank. There are only $q$ scalar laws, with $q$ fixed.

**Assembly.** Expanding the shifts in (30), exact separate affinity yields
$$\Delta_{v(T)}\Delta_{w(T)}L(A)=\sum_{i,j}v_i(T)w_j(T)\Delta_{e_i}\Delta_{f_j}L(A)$$
for bases $(e_i),(f_j)$ of the two banks. Each coefficient function is a
fixed combination of translates of a selector difference of $P'$, of line
degree at most two; the coordinates of $v(T),w(T)$ have degree at most one,
of $u(T)$ at most two; and the one-bank expansions have the same form. So
every slack term, the main field products, and every public principal minor
give full identity discrepancies of line degree at most four. Such a
discrepancy fails on at most a $\tau$ fraction of bases; if $\tau<\kappa$,
the support gap forces it to vanish identically. On a Boolean diagonal the
shifts $v(T),u(T)$ are zero, so both single differences and the mixed
difference vanish regardless of $w(T)$, and (27) holds exactly.

Every triple of Boolean addresses is available ($G_0$ contains all diagonal
matrices). Exact invariance makes $X$ a function of its first block alone.
The Booleanity identity assigns a bit to each Boolean address; 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.

**Closing constants.** With (26) in force, put
$$d_0=\min\Big\{\frac{\gamma}{16},\ \frac{1}{16K_{\mathrm{sw}}},\
\frac{1}{128(1+2Q)}\Big\},\qquad 0<\eta\le d_0^2.$$
Then (32) holds, $\kappa\ge1-1/16-1/16-\lambda_1>1/2$, and
$\tau\le(1+2Q)\sqrt\eta\le1/128$, giving $\tau/\kappa<1/16$ and
$\tau<\kappa$. No bound involves $d$ or $|G|$, so an unsatisfiable formula
must have a law failing with probability greater than this $\eta$.

**Size and samplers.** $|G|=q^{O(d)}=2^{O(d)}$, and all 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; all arithmetic has polynomial bit complexity, and
seed probabilities are rational products of reciprocals of polynomial-size
spaces. Query arity, number of laws, and all mask counts are constants. The
pencil itself runs in $2^{O(d)}$ time. These prove Theorem 5.1.

---
## 6. Primitive events and the valuation obstruction

The bit-test system speaks of assignments. We now package its output so a
*cut* can interact with it. The bridge is a **valuation**: a single bit for
each *predicate* (Boolean function of the whole proof assignment), with the
rule that two sampled descriptions of the same function must get the same
bit. We show that a good valuation decodes a satisfying assignment, and
that on unsatisfiable formulas no good valuation can exist.

Throughout, $\Omega=\{0,1\}^{\mathcal S}$ is the cube of bit assignments
of the bit-test system. A **predicate** is a Boolean function
$R:\Omega\to\{0,1\}$. We identify predicates that are equal as functions,
regardless of their sampled descriptions, and write $R\subseteq R'$ when
$R(y)\le R'(y)$ for every $y\in\Omega$.

A **primitive type** is a probability law $P_s$ on predicates together with
a 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 sampling data; it is not part of the predicate the valuation sees.

**Definition.** A Boolean valuation $H$ on the actual predicates is
*$\zeta$-calibrated and ordered* if, for every primitive type and every
specified comparison,

$$\big|\mathbb E_{R\sim P_s}H(R)-p_s\big|\le\zeta,\qquad
\Pr\big[H(R)>H(R')\big]\le\zeta. \tag{36}$$

### 6.1 The statement

**Lemma (event obstruction).** *There is a fixed finite family of primitive
types $(P_s,p_s)$ and ordered comparisons, and a fixed $\zeta>0$,
constructible in polynomial time from the input formula, such that:*

**(i)** *each predicate depends on boundedly many bit positions, and all
samplers are polynomially enumerable finite rational laws with
inverse-polynomial positive seed probabilities;*

**(ii)** *constant-one and constant-zero types are included, with
calibrations one and zero; every comparison marginal is a primitive type;
and every type has a comparison to the constant-one type;*

**(iii)** *in a satisfiable instance, evaluation at the perfect assignment
$y^\ast$ satisfies $\mathbb E_{P_s}R(y^\ast)=p_s$ for every type;*

**(iv)** *in an unsatisfiable instance, no Boolean valuation is
$\zeta$-calibrated and ordered.*

*The numbers $p_s$, the number of types and comparisons, and $\zeta$ are
independent of the input size.*

### 6.2 The primitive types

Use Theorem 5.1 with pair bound $\lambda\le10^{-6}$. Two **basic literal**
types:

$$L_i^a(y)=\mathbf 1_{\{y_i=a\}},\qquad
L_{i,j}^a(y)=\mathbf 1_{\{y_i+y_j=a\}},$$

where $i$ is uniform in $\mathcal S$, $(i,j)$ uniform in $\mathcal S^2$, and
the target $a\in\mathbb F_2$ an independent uniform bit; both calibrations
are $1/2$.

Three **even-parity tuple experiments**:

1. four base expressions $y_{i_1},\dots,y_{i_4}$, the tuple from the
   auxiliary law of Theorem 5.1(iv);
2. four sum expressions $y_{i_1}+y_{j_1},\dots$ using two independent copies
   of that law;
3. the three expressions $y_i,y_j,y_i+y_j$ for independent uniform $i,j$.

For each experiment of length $k\in\{3,4\}$, sample a uniform even-parity
target $a\in\mathbb F_2^k$ and add the type of the match event
$$M(y)=\mathbf 1_{\{(\text{the }k\text{ expressions at }y)=a\}}$$
and of its complement $\overline M=1-M$, with calibrations $2^{-(k-1)}$ and
$1-2^{-(k-1)}$. For each occurrence add the comparisons
$$M\subseteq L^{a_\ell},\qquad L^{1-a_\ell}\subseteq\overline M \tag{37}$$
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 of Theorem 5.1, let its arity be $L$ and $T_e$ its
acceptance predicate for public seed $e$ with questions $i_1,\dots,i_L$.
Sample uniform $a\in\mathbb F_2^L$ and add the **match-and-pass** event
$$R_{e,a}(y)=T_e(a)\prod_{\ell=1}^L L_{i_\ell}^{a_\ell}(y),\qquad
p_s=2^{-L}. \tag{38}$$
It has the stated calibration at 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 question marginals are at most the fixed factor $B$
times uniform. If the seeded test rejects $a$, (38) is constant zero.

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 6.1;
finite sampling and arity follow from Theorem 5.1. The
unsatisfiable-instance assertion is proved next.

### 6.3 A quantitative tag--dictator dichotomy

Suppose $H$ satisfies (36). For either the base or sum question space write
$$B(q,a)=2H(L_q^a)-1\in\{-1,1\},\qquad
b(q)=\tfrac12\,(B(q,0)+B(q,1)).$$
A question is a **tag** when its two signs agree ($b(q)=\pm1$), otherwise a
**dictator** ($b(q)=0$). Let $\delta$ be the tag fraction. Literal
calibration gives $|\mathbb E b|\le2\zeta$ and $\mathbb E b^2=\delta$.

Consider the four-occurrence experiment with a uniform even target and put
$B_\ell=B(q_\ell,a_\ell)$; distinct target bits are independent, and the
question pair operator has norm at most $\lambda$ (also for sums, by the
tensor assertion of Theorem 5.1). Hence for $\ell\ne r$,

$$\mathbb E B_\ell B_r=\mathbb E\,b(q_\ell)b(q_r)\le4\zeta^2+\lambda\delta. \tag{39}$$

The first comparisons in (37) give $\Pr[B_1=\cdots=B_4=1]\ge 1/8-5\zeta$.
For the second comparisons, $\Pr[H(\overline M)=0]\ge1/8-\zeta$, and
outside the four comparison failures all opposite literals are zero;
complementing all four target bits preserves the uniform even-target law,
so $\Pr[B_1=\cdots=B_4=-1]\ge1/8-5\zeta$. The squared sum of four signs is
$16$ on these two constant-sign vectors, $4$ when their product is negative,
$0$ otherwise; combining with (39) gives, for $\zeta\le1$,

$$\Pr[B_1B_2B_3B_4=-1]\le3\lambda\delta+40\zeta+12\zeta^2
\le3\lambda\delta+52\zeta. \tag{40}$$

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, which
under uniform even targets is an unbiased sign; so negative product has
conditional probability one half. Meanwhile 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. Hence
$$\delta(1-\delta)\le7\lambda\delta+104\zeta.$$
For $\lambda\le1/28$: if $\delta\le1/2$ this gives $\delta\le416\zeta$, and
if $\delta>1/2$ it gives $1-\delta\le7\lambda+208\zeta$. So

$$
\delta\le416\zeta\quad\text{or}\quad 1-\delta\le7\lambda+208\zeta \tag{41}
$$
for each of the two basic literal types.

### 6.4 The tag regime is impossible

Assume $\lambda\le10^{-6}$, $\zeta\le10^{-8}$, and the base literal type in
the second regime of (41). Put
$$e_0=7\lambda+208\zeta,\quad h_0=e_0+2\zeta,\quad D_0=3e_0+6\zeta.$$
Extend the base tag sign to a sign $b_i$ on all of $\mathcal S$. The
non-tag fraction is at most $e_0$, so $|\mathbb E b_i|\le h_0$; if
$r_s=\Pr[b_i=s]$, then $|r_s-1/2|\le h_0/2$ and $r_s^2\le1/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 a base question is not a tag (probability at most $2e_0$), these
require $b_i=b_j=1$ and $b_i=b_j=-1$, respectively. The sum target is a
uniform bit under both laws, independent of $i,j$. Subtracting these lower
bounds from the respective masses $r_s^2$ yields
$$\Pr_{i,j,a}\big[b_i=b_j=s,\ B((i,j),a)\ne s\big]\le h_0+4\zeta+2e_0=D_0,
\qquad s=\pm1. \tag{42}$$
If a sum question is not a tag of sign $s$, at least one of its two targets
has sign different from $s$; so
$\Pr_{i,j}[b_i=b_j=s,\ (i,j)\text{ not a tag of sign }s]\le2D_0$. Since
$r_+^2+r_-^2\ge1/2$, the sum tag fraction is at least $1/2-4D_0>416\zeta$,
so by (41) its non-tag fraction is also at most $e_0$.

Let $v(i,j)$ be the sum tag sign, extended sympathetically (the literal
predicates for $(i,j)$ and $(j,i)$ are equal, so tag statuses and signs are
already symmetric). Then
$$\Pr[b_i=b_j=s,\ v(i,j)\ne s]\le2D_0. \tag{43}$$
For two independent auxiliary four-tuples $\boldsymbol i,\boldsymbol j$,
(40) and the at-most-$4e_0$ chance of a non-tag sum question give
$$\Pr\Big[\prod_{\ell=1}^4 v(i_\ell,j_\ell)=-1\Big]\le E_4:=3\lambda+52\zeta+4e_0. \tag{44}$$
Exchangeability permits swapping $j_1$ and $j_2$; where both fourfold
products are positive, canceling their last two factors gives the rectangle
identity $v(i_1,j_1)v(i_2,j_2)=v(i_1,j_2)v(i_2,j_1)$, which thus fails with
probability at most $2E_4$.

Replace both pair marginals by independent uniform draws. For fixed $i,i'$
put $f(j)=v(i,j)v(i',j)$; the pair-operator bound gives
$|\mathbb E_{\mathrm{pair}}f(j)f(j')-(\mathbb E f)^2|\le\lambda
\operatorname{Var}(f)\le\lambda$, changing the rectangle sign's expectation
by at most $\lambda$; after replacing the $j$ pair, apply the same to the
$i$ pair. The rectangle sign has changed in expectation by at most
$2\lambda$, and its failure probability for four independent uniform
indices is at most
$$R_0:=2E_4+\lambda. \tag{45}$$

Average over an independent reference pair $(i_0,j_0)$ and fix one for
which the rectangle failure probability over $i,j$ is at most $R_0$. Define
$u(i)=v(i,j_0)$, $w(j)=v(i_0,j)v(i_0,j_0)$. Then
$\Pr[v(i,j)\ne u(i)w(j)]\le R_0$, and symmetry of $v$ gives
$\Pr[u(i)w(j)\ne u(j)w(i)]\le2R_0$; equivalently the signs $a(i)=u(i)w(i)$
at two independent indices disagree with probability at most $2R_0$. With
$c$ the majority sign of $a$ and minority mass $m\le1/2$ (the disagreement
probability is $2m(1-m)\ge m$), $m\le2R_0$, so $w(i)=cu(i)$ outside a set of
mass at most $2R_0$, and
$$\Pr[v(i,j)\ne c\,u(i)u(j)]\le3R_0. \tag{46}$$

Take the base-sign class $s=-c$; since $h_0<1/2$ it has mass
$r_s\ge1/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$, it is $a^2+(1-a)^2\ge1/2$). Hence
$$\Pr[b_i=b_j=s,\ c\,u(i)u(j)\ne s]\ge r_s^2/2\ge1/32.$$
But (43) and (46) upper-bound the same probability by $2D_0+3R_0$, and
direct substitution gives
$$2D_0+3R_0=231\lambda+6564\zeta<1/32$$
under the stipulated bounds ($h_0<1/2$ and $1/2-4D_0>416\zeta$ follow from
the same bounds). Contradiction: the base-tag regime is excluded, so

$$\Pr_i[i\text{ is not a dictator}]\le416\zeta. \tag{47}$$

### 6.5 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 elsewhere. This is one assignment on
$\mathcal S$, because $H$ is a function of actual predicates. For an ordinary
law of arity $L$, its probability of querying any non-dictator is at most
$416LB\zeta$ by (47) and the marginal bound, and its $L$ containing-literal
comparisons fail with total probability at most $L\zeta$. The constant-zero
type has $H(0)=0$, since $\zeta<1$.

Outside these two bad events, if $H(R_{e,a})=1$ in (38) then 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). Thus
$$2^{-L}-\zeta\le\mathbb E H(R_{e,a})
\le2^{-L}\Pr_e[T_e(y_{i_1},\dots,y_{i_L})=1]+(416LB+L)\zeta.$$
So this law fails with probability at most $2^L(1+L+416LB)\zeta$. There are
only finitely many ordinary laws; choose the fixed $\zeta\le10^{-8}$ small
enough that this is at most $\eta/2$ for each, with $\eta$ the soundness
constant of Theorem 5.1. On an unsatisfiable instance this contradicts
Theorem 5.1, completing Lemma 6.1.

For the next section fix positive mixture weights $(\omega_s)_s$ with
$\sum_s\omega_s=1$ (e.g. equal weights) and let $P_\ast=\sum_s\omega_sP_s$,
retaining the type as sampling data. Put

$$p_\ast=\sum_s\omega_s p_s. \tag{48}$$

The two constant types give $0<p_\ast<1$. All these quantities are fixed
independently of instance size. Equal predicates in different types remain
the same argument of a valuation; only their sampling probabilities differ.

---
## 7. From a rare conjunction to one valuation

This section is the technical heart of "arbitrarily small cut mass". We
have a Boolean response $W$ to a conjunction $r=R_1\wedge\cdots\wedge R_t$
of many independently sampled predicates, whose success probability may be
astronomically small. We prove that a good response, with errors measured
*relative to* its own success scale $v$, still forces a single valuation
satisfying (36). The key advantage is uniformity: the bounds do not involve
the number of predicates or any atom's probability.

The method is an entropy argument. Conditioning on success gives a
probability law with a controlled amount of relative entropy; a chain-rule
and convexity analysis exposes a *common* conditional density; counting with
the type-pattern bounds concentrates the law near a single type mixture;
two clipping steps pinch the density near $0$ and a fixed value $A$; one
threshold then produces the valuation. (The parallel-repetition
entropy-distribution technique is due to Raz and Holenstein; the clipping and
thresholding here are adapted to produce one valuation of *actual
predicates*.)

### 7.1 The statement

Let $\mathcal X$ be a finite set and identify a predicate on $\mathcal X$
with its function $R:\mathcal X\to\{0,1\}$. Fix a finite set $\mathcal T$ of
primitive types; type $s$ has a probability law $P_s$ on predicates and a
number $p_s\in[0,1]$. Fix weights $\omega_s>0$ with $\sum_s\omega_s=1$. A
sample from $P_\ast$ first picks $s$ with probability $\omega_s$ and then
$R\sim P_s$, retaining the type as part of the sample; identical predicates
may appear under different types. Write
$$p_\ast=\sum_s\omega_s p_s,\qquad 0<p_\ast<1.$$
Assume a designated type $\top$ is concentrated on the constant-one
predicate $\mathbf 1$ and has $p_\top=1$.

Fix a finite list $\mathcal C$ of comparison laws: a comparison $\Pi$ couples
two primitive predicates $(R,R')$ with designated marginals $P_{s(\Pi)},
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
$$\big|\mathbb E_{P_s}H(R)-p_s\big|<\zeta\ (s\in\mathcal T),\qquad
\Pr_{\Pi}\big(H(R)>H(R')\big)<\zeta\ (\Pi\in\mathcal C). \tag{49}$$

For an integer $t\ge1$, a **type pattern** $\boldsymbol s=(s_1,\dots,s_t)$
means independent draws $R_i\sim P_{s_i}$. Put
$$r=\bigwedge_{i=1}^t R_i,\qquad p_{\boldsymbol s}=\prod_{i=1}^t p_{s_i}.$$
A **lifted comparison** chooses one coordinate from a prescribed $(R,R')\sim
\Pi$ and the other $t-1$ predicates independently from specified types,
independently of $(R,R')$, and uses the same context on both sides, giving
$r\le r'$. Bounds for all type patterns and comparisons also hold when
context types are mixed with the weights $\omega_s$, by averaging.

**Lemma (rare-event criterion).** *Fix the type data, positive constants
$b_0,K_0,B_0$, and a tolerance $\zeta>0$. There is $t_0$ such that for every
$t\ge t_0$ there is $\varepsilon_0(t)>0$ with the following property. Set
$p=p_\ast^t$ and $0<\varepsilon\le\varepsilon_0(t)$. Suppose $0<v\le B_0$
and $W$ is a Boolean function of the actual conjunction predicate satisfying*

$$\Pr_{P_\ast^t}(W(r)=1)\ge b_0\,v\,p, \tag{50}$$
$$\Pr_{\boldsymbol s}(W(r)=1)\le v\big(K_0p_{\boldsymbol s}+\varepsilon\big)
\quad\text{for every type pattern }\boldsymbol s, \tag{51}$$
$$\Pr\big(W(r)>W(r')\big)\le\varepsilon\,v
\quad\text{for every lifted comparison.} \tag{52}$$

*Then a single Boolean valuation $H$ satisfies (49). The choices of $t_0,
\varepsilon_0(t)$ depend only on $b_0,K_0,B_0,\zeta$, the finite type and
comparison lists, and $(\omega_s,p_s)$, uniformly in $\mathcal X$, the
primitive supports, their atom probabilities, and the couplings. Types with
$p_s=0$ are allowed.*

*Proof.* Let all logarithms be natural, $0\log0=0$. Write
$$Z=\Pr_{P_\ast^t}\Big(W\big(\textstyle\bigwedge_{i=1}^tR(Y_i)\big)=1\Big),
\qquad
Q=P_\ast^t\big(\,\cdot\;|\;W\big(\textstyle\bigwedge R(Y_i)\big)=1\big),$$
where $Y_i$ is the marked primitive sample. Equation (50) gives $Z>0$, and
$Q$ is exchangeable (permuting coordinates preserves the product law and the
conjunction). For $0\le k\le t$ let $Q_k$ be the first-$k$ marginal and
$I_k=\operatorname{KL}(Q_k\Vert P_\ast^k)$, $I_0=0$. The chain rule
$I_k-I_{k-1}=\mathbb E_{Q_{k-1}}\operatorname{KL}(Q(Y_k\in\cdot\,|\,Y_{<k})
\Vert P_\ast)$ and convexity of $x\log x$ show the increments are
nondecreasing, and exchangeability gives
$$I_j\le\frac jtI_t,\qquad I_{j+1}-I_j\ge\frac{I_j}{j}\quad(1\le j<t). \tag{53}$$
Since $Q$ has density $1/Z$ on success,
$$I_t=\log(1/Z)\le\log(1/v)+tL-\log b_0,\qquad L=\log(1/p_\ast)>0. \tag{54}$$

Take $t\ge4$, $j=\lfloor t/2\rfloor$, $m=t-j$, and replace the last $m$
predicates successively by $\mathbf 1$. If $W$ changes from one to zero, at
least one comparison to $\mathbf 1$ fails; averaging (52) over the context
and union-bounding,
$$\delta:=Q\Big(W\big(\textstyle\bigwedge_{i=1}^jR(Y_i)\big)=0\Big)
\le\frac{m\varepsilon v}{Z}\le\frac{t\varepsilon}{b_0p}.$$
Averaging (51) over the first $j$ types gives
$P_\ast^j(W(\bigwedge_{i\le j}R(Y_i))=1)\le v(K_0e^{-jL}+\varepsilon)$.
Coarsening the relative entropy to this binary event (with probabilities
$q=1-\delta$ under $Q_j$ and $a$ under $P_\ast^j$) and using convexity on the
event and its complement,
$$I_j\ge q\log\frac qa+(1-q)\log\frac{1-q}{1-a}\ge q\log(1/a)-\log2,$$
hence with $a_v=\log(1/v)$,
$$I_j\ge(1-\delta)\big(a_v+jL-\log(K_0+\varepsilon e^{jL})\big)-\log2. \tag{55}$$

Impose the smallness
$$\frac{t^2\varepsilon}{p}\le c_0,\qquad c_0=\min\{b_0/8,\,1\}, \tag{56}$$
which gives $\delta\le1/(8t)$, $\delta jL\le L/16$, $1-\delta-j/t\ge3/8$,
$\varepsilon e^{jL}\le1$. Combining (53)–(55) gives $(1-\delta-j/t)a_v\le
\delta jL+(1-\delta)\log(K_0+\varepsilon e^{jL})+\log2-(j/t)\log b_0$.
Define constants (independent of $t$ and all supports)
$$R_0=\tfrac L{16}+\log(K_0+1)+\log2+\tfrac12|\log b_0|,\quad
A_v=\tfrac83R_0,\quad c_v=e^{-A_v},\quad c_z=b_0c_v.$$
The last inequality gives $a_v\le A_v$, hence
$$v\ge c_v,\qquad Z\ge c_zp. \tag{57}$$
(If $c_v>B_0$ the hypotheses are inconsistent and there is nothing to prove.)
The separate hypothesis $v\le B_0$ likewise gives
$$I_j\ge jL-C_I,\qquad
C_I=\tfrac L{16}+\log(K_0+1)+\log2+\max\{\log B_0,0\}. \tag{58}$$

**A common conditional density.** For a full ordered prefix
$D=(Y_1,\dots,Y_j)$, write $R_D=\bigwedge_{i\le j}R(Y_i)$ and set
$$Z_D=\mathbb E_{P_\ast^m}W\big(R_D\wedge\textstyle\bigwedge_{i\le m}R(Y_i)\big),\quad
U_D(R)=\mathbb E_{P_\ast^{m-1}}W\big(R_D\wedge R\wedge\textstyle\bigwedge_{i\le m-1}R(Y_i)\big).$$
The density of the $Q$-prefix relative to $P_\ast^j$ is $Z_D/Z$, so $Z_D>0$
for $Q$-a.e. prefix, and on those prefixes set
$$f_D(R)=U_D(R)/Z_D. \tag{59}$$
Then $f_D(R(Y))$ is the conditional next-coordinate density, so
$0\le f_D\le1/Z_D$, $\int f_D\,dP_\ast=1$. Crucially (59) defines its value
from the *predicate alone*, even with several presentations or across types.
The chain rule plus (53), (58) give
$$\mathbb E_D\int f_D\log f_D\,dP_\ast\ge L-C_I/j. \tag{60}$$

Put $\pi_s=\omega_sp_s/p_\ast$, $u=\varepsilon/(b_0p)$, $\mu_s(D)=
\omega_s\mathbb E_{P_s}f_D(R)$. For every full type sequence $\boldsymbol s$,
(50)–(51) give
$$Q(\text{types}=\boldsymbol s)\le\frac{K_0}{b_0}\prod_{i\le t}\pi_{s_i}
+u\prod_{i\le t}\omega_{s_i}. \tag{61}$$
Let $F_s$ be $s$'s empirical frequency among the $m$ suffix coordinates.
Under $\pi^{\otimes t}$, $\mathbb E|F_s-\pi_s|\le1/(2\sqrt m)$; since
$|F_s-\pi_s|\le1$, applying (61) to this nonnegative function yields
$\mathbb E_Q|F_s-\pi_s|\le R_t$ with
$$R_t=\frac{K_0}{2b_0\sqrt m}+u. \tag{62}$$
Fixing the whole ordered prefix still leaves an exchangeable suffix whose
reference law is a product, so $\mathbb E_Q(F_s|D)=\mu_s(D)$, and
conditional Jensen gives
$$\mathbb E_D|\mu_s(D)-\pi_s|\le R_t. \tag{63}$$
With $A=1/p_\ast$, $H_{\max}=1/\omega_\top$, this gives
$$0\le f_D(\mathbf 1)\le H_{\max},\qquad
\mathbb E_D|f_D(\mathbf 1)-A|\le R_t/\omega_\top. \tag{64}$$
($\mu_\top(D)=\omega_\top f_D(\mathbf 1)$, $\pi_\top=A\omega_\top$,
$p_\ast\ge\omega_\top$, so $H_{\max}\ge A>1$.)

**Cancellation of the prefix likelihood.** For a comparison $(R,R')\sim\Pi$,
convexity of the positive part and a shared suffix in $U_D(R),U_D(R')$ give
$$\mathbb E_D\mathbb E_\Pi\big(f_D(R)-f_D(R')\big)_+
=\frac1Z\mathbb E_{D\sim P_\ast^j}\Big[\mathbf 1_{Z_D>0}\,
\mathbb E_\Pi\big(U_D(R)-U_D(R')\big)_+\Big]\le\frac{\varepsilon v}{Z}\le u,
\tag{65}$$
the last step averaging (52) over one tested coordinate and $t-1$ shared
context coordinates, the density denominator $Z_D$ having canceled. Averaging
the comparisons to $\mathbf 1$ over the first marginal type also gives
$$\mathbb E_D\int\big(f_D-f_D(\mathbf 1)\big)_+\,dP_\ast\le u. \tag{66}$$

**Two clippings, retaining rare-prefix entropy.** Set
$g_D=\min\{f_D,f_D(\mathbf 1)\}$, $\widehat f_D=\min\{g_D,A\}$. The
first-moment losses are
$$\mathbb E_D\int(f_D-g_D)\,dP_\ast\le u,\qquad
\mathbb E_D\int(g_D-\widehat f_D)\,dP_\ast\le\mathbb E_D(f_D(\mathbf 1)-A)_+
\le R_t/\omega_\top, \tag{67}$$
so $0\le1-\mathbb E_D\int\widehat f_D\,dP_\ast\le u+R_t/\omega_\top$.
Take $t$ large enough that $\beta=p^2\le e^{-1}$ and consider
$\mathcal B_\beta=\{0<Z_D<\beta\}$. Since $f_D\le1/Z_D$ and
$\int f_D=1$, $\int\varphi(f_D)_+\,dP_\ast\le\log(1/Z_D)$ (here
$\varphi(x)=x\log x$), while $\varphi(g_D)\ge-1/e$; using the prefix density
$Z_D/Z$ bounds the *signed* entropy loss over $\mathcal B_\beta$ by
$$\frac1Z\mathbb E_{P_\ast^j}[\mathbf 1_{\mathcal B_\beta}Z_D\log(1/Z_D)]
+\frac1eQ_j(\mathcal B_\beta)\le
T_t:=\frac p{c_z}\Big(2tL+\frac1e\Big). \tag{68}$$
On the complement $f_D\le1/\beta$; though $\varphi'(x)=1+\log x$ is
unbounded below at zero, it is bounded above there by $M_\beta=1+\log(1/\beta)
=1+2tL$, so integrating gives $\varphi(x)-\varphi(y)\le M_\beta(x-y)$ for
$0\le y\le x\le1/\beta$, and (66) bounds the complementary entropy loss by
$M_\beta u$. In the second clipping only values in $[A,H_{\max}]$ change,
where $\varphi'\le M_H:=1+\log H_{\max}$, so that loss is at most
$M_H R_t/\omega_\top$. Combining with (60),
$$\mathbb E_D\int\varphi(\widehat f_D)\,dP_\ast\ge
L-\tfrac{C_I}{j}-T_t-M_\beta u-M_HR_t/\omega_\top.$$
Since $\log A=L$ and the mean mass of $\widehat f_D$ is at most one, the
nonnegative endpoint defect satisfies
$$0\le\mathbb E_D\int\widehat f_D\log\frac A{\widehat f_D}\,dP_\ast\le
\tfrac{C_I}{j}+T_t+M_\beta u+M_HR_t/\omega_\top. \tag{69}$$

**Thresholding.** For $0\le x\le A$,
$$\operatorname{dist}(x,\{0,A\})\le2x\log(A/x) \tag{70}$$
($x\le A/2$: $2\log(A/x)>1$; $A/2\le x\le A$: set $z=x/A$ and use
$-\log z\ge1-z$, $2z\ge1$; $x=0$ by continuity). Define the single valuation
$$H_D(R)=\mathbf 1_{\{f_D(R)>A/2\}}.$$
For every $x\ge0$ (including $x>A$ and the tie $x=A/2$),
$|x-A\mathbf 1_{x>A/2}|=\operatorname{dist}(x,\{0,A\})$, since distance to a
set is $1$-Lipschitz. Applying this to $f_D$ and $\widehat f_D$ and using
(67), (69), (70) gives
$$\rho_t:=\mathbb E_D\int|f_D-AH_D|\,dP_\ast
\le\tfrac{2C_I}{j}+2T_t+(1+2M_\beta)u+(1+2M_H)\tfrac{R_t}{\omega_\top}
\le C\Big(t^{-1/2}+tp+(1+t)\tfrac{\varepsilon}{p}\Big) \tag{71}$$
with $C$ depending only on $p_\ast,\omega_\top,b_0,K_0,B_0$. This has no
dependence on any atom; arbitrarily small $Z_D$ are handled by (68), not
excluded.

**One prefix for all requirements.** Let $\rho_s(D)=\mathbb
E_{P_s}|f_D-AH_D|$; positive weights give $\mathbb E_D\rho_s(D)\le
\rho_t/\omega_s$, while $\mu_s(D)=\omega_s\mathbb E_{P_s}f_D$ and
$\pi_s=A\omega_sp_s$. The triangle inequality and (63) give
$$\mathbb E_D\big|\mathbb E_{P_s}H_D-p_s\big|\le\frac{\rho_t+R_t}{A\omega_s}.
\tag{72}$$
For a comparison $\Pi$ with marginals $P_s,P_{s'}$, the pointwise inequality
$A\mathbf 1_{H_D(R)>H_D(R')}\le|AH_D(R)-f_D(R)|+(f_D(R)-f_D(R'))_+
+|f_D(R')-AH_D(R')|$ and (65) give
$$\mathbb E_D\Pr_\Pi\big(H_D(R)>H_D(R')\big)\le
\frac{\rho_t/\omega_s+\rho_t/\omega_{s'}+u}{A}. \tag{73}$$
Only the two marginal laws enter the absolute-error bounds — no density of
$\Pi$ relative to a product is needed, and no $p_s$ is inverted, so $p_s=0$
is included.

Summing all calibration errors (72) and comparison errors (73) over the
fixed finite lists gives a nonnegative quantity $\Theta(D)$ with a bound
whose right side is a fixed finite sum of terms from (71)–(73). Since
$0<p_\ast<1$, $t^{-1/2}+tp_\ast^t\to0$; choose $t_0$ so large that for every
$t\ge t_0$ the bound is $<\zeta/2$, and also $p_\ast^{2t}\le e^{-1}$. For
each such $t$ choose $\varepsilon_0(t)>0$ satisfying (56) and making all
remaining $\varepsilon/p$ terms contribute $<\zeta/2$; shrinking if needed
makes the total strictly less than $\zeta$. Some positive-$Q_j$ prefix then
has $\Theta(D)<\zeta$; every individual error is nonnegative, so that single
$H=H_D$ satisfies all of (49). Its dependence only on actual predicates
follows from (59). $\square$

For the primitive system of Section 6, choose the tolerance from Lemma 6.1.
Lemma 7.1 then says that on a NO instance no common conjunction response can
satisfy (50)–(52) for those choices of $t$ and $\varepsilon$. The constants
$b_0,K_0,B_0$ must be fixed before this choice; the next two sections produce
exactly that interface from a putative sparse cut.

---
## 8. Scores, comparison measures, and the amplitude signal

A **score** is a real function of the proof-bit assignment, depending 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\}$ (Borel on each finite table of score
values). A **raw comparison form** is a finite positive measure
$\mathfrak m$ on pairs of scores, with

$$\mathcal D(h)=\int|h(B)-h(B')|\,d\mathfrak m(B,B'),\qquad
\text{truth cost at }x=\int|B(x)-B'(x)|\,d\mathfrak m(B,B'). \tag{74}$$

The task of this section: build, from the primitive system of Section 6, a
demand law and a sum $\mathcal D$ of comparison forms, so that at a
satisfying assignment the total truth cost is small, while in a NO instance
*every* positive-variance lookup incurs a large comparison cost relative to
its variance. The small-but-positive variance is exactly the arbitrarily
small cut mass; every error is measured in units of that variance.

### 8.1 The analytic score gap

**Theorem (score gap).** *For each fixed $T_0\ge1$, the primitive system of
Section 6 admits a demand law $\mu$ of scores and a finite sum $\mathcal D$
of raw comparison forms with: all arities, score bounds, numerical
dimensions, and total comparison weight bounded by constants independent of
input size; laws and weights depending on no lookup; at a perfect witness
$x$,*
$$\int|B(x)-B'(x)|\,d\mathfrak m\le4,\qquad
\mu\{B:B(x)\ge1/4\},\ \mu\{B:B(x)\le-1/4\}\ge10^{-4}; \tag{75}$$
*and in a NO instance every binary measurable lookup with
$\nu=\operatorname{Var}_\mu(h)>0$ satisfies $\mathcal D(h)>T_0\nu$.
Conditional on the discrete sampling data, the numerical laws and score
entries belong to fixed finite families of rational-coefficient polynomials
on rational boxes, atoms represented as separate cases.*

The proof spans Sections 8–9. Section 8 builds the demand and the
resampling comparison, shows that a low-cost cut retains a *signal* from at
least one amplitude, and sets up smoothing. Section 9 turns the signal into
the common conjunction response required by Lemma 7.1.

It suffices to prove the theorem for rational $T_0\ge1$ (replace any real
$T_0$ by a larger rational). Choose positive rational mixture weights
$\omega_s$ and put $P_\ast$, $p_\ast=\sum\omega_sp_s\in(0,1)$. A length-$t$
conjunction from the independent mixture law has honest probability
$p=p_\ast^t$; a fixed type pattern has probability $\prod p_{s_i}$.
Ordered conjunction couplings change one coordinate by a primitive coupling
and use independent shared fixed-type samples in the others, giving actual
pointwise inclusions $r\le r'$.

### 8.2 Demand and random half-freezing

Let $M$ be a positive integer. Stage $j$ has $n_j$ slots, $n_j$ even. Choose
rational coefficients

$$\frac1{\sqrt{pMn_j}}\le s_j\le\frac2{\sqrt{pMn_j}},\qquad s_j\le1. \tag{76}$$

In each slot independently sample a primary presentation $\mathcal R_i$ of
an iid conjunction $r_i$ and an independent amplitude
$$\lambda=\tfrac12\delta_0+\tfrac12\operatorname{Unif}[-1,1].$$
Define the demand score and its law
$$B^0=\sum_{j=1}^M s_j\sum_{i\in\text{stage }j}a_ir_i,\qquad
\mu=\operatorname{Law}(B^0).$$

At a perfect witness $x$, each summand is symmetric, centered, bounded by
one, with variance $s_j^2p/6$, so
$$\frac16\le\operatorname{Var}(B^0(x))\le\frac23,\qquad
\mathbb E\,B^0(x)^4<4.$$
For $X=B^0(x)$, Cauchy–Schwarz gives
$\Pr(|X|\ge1/4)\ge(\mathbb E X^2-1/16)^2/\mathbb E X^4\ge25/9216$, and
symmetry splits this equally between the two tails, giving (75)'s demand
tails.

Set $\rho=1/(2048T_0^2)$ and include, with weight $16T_0$, the form
comparing $B^0$ to $B^{0,\rho}$ obtained by independently resampling each
complete primary slot with probability $\rho$. Its truth cost is at most
$$16T_0\sqrt{2\rho\operatorname{Var}(B^0(x))}\le16T_0\sqrt{4\rho/3}
=1/\sqrt6<1. \tag{77}$$

Suppose, for contradiction, that a lookup achieves
$$0<\nu=\operatorname{Var}(h(B^0)),\qquad \mathcal D(h)\le T_0\nu. \tag{78}$$
Then in particular
$$\mathbb E|h(B^0)-h(B^{0,\rho})|\le\nu/16. \tag{79}$$

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

**Lemma (amplitude signal).** *Choose $k=\lceil\rho^{-1}\rceil$ and require
$n_j\ge4k$. With $c=4^{-(k+2)}$, (79) implies*
$$\|b^0\|_\Sigma^2\le\nu,\quad
\sum_j s_j^2\sum_{i\in I_j}\mathbb E[|b_i^0|^2|\mathcal B]\le\tfrac14,\quad
\|g^0\|_\Sigma^2\ge c\nu. \tag{80}$$
*The constants $k,c$ depend only on $T_0$.*

*Proof.* For one slot, the *erasure observation* $O$ is $\ast$ when $a=0$
and $(\mathcal R,a)$ otherwise. For square-integrable $\psi(O)$, writing
$c_\ast=\psi(\ast)$, $\psi_1(\mathcal R,u)$ for its non-erased value, and
$m=\mathbb E\psi_1$,
$$\operatorname{Var}(\mathbb E[\psi(O)|\mathcal R])
=\tfrac14\operatorname{Var}(\mathbb E_u\psi_1)\le\tfrac14
\operatorname{Var}(\psi_1),\quad
\operatorname{Var}(\psi(O))=\tfrac12\operatorname{Var}(\psi_1)
+\tfrac14(c_\ast-m)^2,$$
so the conditional expectation from centered functions of $O$ to functions
of $\mathcal R$ has norm at most $2^{-1/2}$. The centered
$f=h(B^0)-\mathbb E h(B^0)$ is a function of the independent erasures
(a zero amplitude contributes nothing). Using the Hoeffding /
Efron–Stein orthogonal decomposition into active sets $S\ne\varnothing$,
$f_S=\prod_{i\in S}(I-P_i)\prod_{i\notin S}P_if$ (with $P_i$ averaging
observation $i$), the components are orthogonal and separately centered;
conditional expectation onto all primary presentations preserves this
centering, so images of different active sets stay orthogonal, and applying
the one-slot bound in each active coordinate gives
$$\|\mathbb E[f|(\mathcal R_i)_i]\|_2^2\le\sum_{S\ne\varnothing}2^{-|S|}
\|f_S\|_2^2\le\nu/2. \tag{81}$$

Refine on complete primary slots. With $\mathsf P_i$ averaging the whole
slot and $\mathsf R_i$ averaging its amplitude alone, the operators
$\mathsf C_i=\mathsf P_i$, $\mathsf D_i=\mathsf R_i-\mathsf P_i$,
$\mathsf A_i=I-\mathsf R_i$ are orthogonal projections onto constants,
centered primary functions, and functions with conditional amplitude mean
zero. They commute across slots. Write
$f_\eta=\prod_i\eta_if$, $\eta_i\in\{\mathsf C_i,\mathsf D_i,\mathsf A_i\}$,
and $S(\eta)=\{i:\eta_i\ne\mathsf C_i\}$, $A(\eta)=\{i:\eta_i=\mathsf A_i\}$.
Equation (81) says the squared mass with $A(\eta)\ne\varnothing$ is at least
$\nu/2$. Slot resampling acts on $f_\eta$ by $(1-\rho)^{|S(\eta)|}$, so
$$\mathbb E(h(B^0)-h(B^{0,\rho}))^2=2\sum_\eta
[1-(1-\rho)^{|S(\eta)|}]\|f_\eta\|_2^2.$$
Binary differences have equal absolute and squared values; for
$|S(\eta)|>k$ twice the bracket is at least one, so (79) bounds these
components' mass by $\nu/16$, and
$$\sum_{A(\eta)\ne\varnothing,\ |S(\eta)|\le k}\|f_\eta\|_2^2\ge3\nu/8. \tag{82}$$

Given $\mathcal B$ the unfrozen amplitudes are independent; the $s_jb_i^0$
are orthogonal projections of $h(B^0)-\mathbb E[h(B^0)|\mathcal B]$ onto
their centered amplitude spaces, and Bessel bounds their conditional squared
norms by $\operatorname{Var}(h(B^0)|\mathcal B)\le1/4$; averaging with total
variance gives the first two assertions. The tower property and amplitude
independence give
$$s_jg_i^0=\mathbb E[h(B^0)|\mathcal Z,\mathcal R_i,a_i]
-\mathbb E[h(B^0)|\mathcal Z,\mathcal R_i],$$
i.e. the projection $\mathsf A_i\prod_{\ell\notin F\cup\{i\}}\mathsf P_\ell
f$. Averaging the observed frozen values and using orthogonality,
$$\|g^0\|_\Sigma^2=\sum_\eta\|f_\eta\|_2^2\sum_{i\in A(\eta)}
\Pr_F(i\notin F,\ S(\eta)\setminus\{i\}\subseteq F).$$
For a component of (82), distinguish $i\in A(\eta)$ in stage $j$, put
$d=|S(\eta)|\le k$, and let $q_\ell$ count its active slots in stage $\ell$.
The capture probability is
$$\tfrac12\frac{(n_j/2)_{q_j-1}}{(n_j-1)_{q_j-1}}
\prod_{\ell\ne j}\frac{(n_\ell/2)_{q_\ell}}{(n_\ell)_{q_\ell}},$$
each of whose $d-1$ ratio factors is at least $1/4$ (numerator at least
$n_\ell/2-k+1\ge n_\ell/4$, denominator at most $n_\ell$), so the probability
is at least $\tfrac12 4^{-(d-1)}\ge4^{-k}$; keeping the distinguished
contribution and using (82) gives the claimed $c\nu$. $\square$

### 8.3 The order of the constants

We now fix the signal-loss tolerance, clipping bound, and threshold, and the
resulting inputs to Lemma 7.1. Choose rational
$$
c_1=\tfrac c4,\quad 0<e\le\tfrac c{160000},\quad
B_\ast\ge\max\!\Big(1,\tfrac{3200(T_0+1)}c\Big),\quad K_\ast=32(T_0+2),
$$
$$
0<\gamma\le\tfrac{c_1}{16K_\ast},\quad
b_\ast=\tfrac{c_1}{128B_\ast^2},\quad
b_0=\tfrac{b_\ast}{8(T_0+1)},\quad K_0=\tfrac{16}\gamma,\quad B_0=B_\ast.
\tag{83}
$$
These do not depend on the conjunction length. Apply Lemma 7.1 to
$b_0,K_0,B_0$ and choose its $t$ and rational $\varepsilon>0$. From now on
$p=p_\ast^t$ is fixed. Let $V$ be the number of fixed type patterns together
with the iid conjunction law, $Q$ the number of required ordered conjunction
couplings (counting the changed coordinate). The path menu below has
$L=V+2Q+2$ entries. Set $A_t=16V+80Q$ and choose rational $\Delta>0$ with
$$\Delta\le\frac{b_\ast p\gamma}{160},\qquad
\Big(\frac{16p}{\gamma\varepsilon}+1\Big)\frac{A_t\Delta}{\gamma}
\le\frac{b_\ast p}{4}, \tag{84}$$
and an integer
$$M\ge\frac{32B_\ast K_\ast(T_0+3)}{c_1\Delta}. \tag{85}$$
The remaining parameters are chosen sequentially in Section 8.5; the order
is justified by estimates whose constants do not depend on the later sizes.

### 8.4 Paths, replacements, formal cells

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

1. $-\tau r\to+\tau r$ for each of the $V$ vertical laws;
2. $+\tau r\to+\tau r'$ and $-\tau r'\to-\tau r$ for each ordered
   $r\le r'$;
3. $-\tau r\to ar$ and $ar\to+\tau r$, $r$ iid and $a\sim\lambda$ fresh.

Each endpoint is bounded by one and every coordinate of $\tau(D^+-D^-)$ is
nonnegative; all predicates and amplitudes are fresh from their laws.

Independently in each unfrozen slot of stage $j$, retain the primary summand
with probability $1-\alpha_j$ (**shared**); otherwise draw a uniform menu
entry, 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$, and replace the slot by
$$s_j\chi\big[(1-u)D^-+uD^+\big].$$
$J_{j-1}$ is the number of formal cells at level $j-1$. The score after all
replacements through stage $j$ is $B^j$. Construct $C_j$ by refining
$C_{j-1}$ with all queried positions in current unfrozen primary
presentations (including replaced slots) and current fresh paths, padded to
a deterministic length with identically zero coordinates; keep all formal
binary cells (consistent, inconsistent, empty). Thus $J_j$ is deterministic
given the sizes. A descriptor defines the indicated sign on actual cells;
values on empty cells do not matter. This construction inspects neither
amplitudes, times, nor signs when forming the partition after question lists
are known, and frozen/future lists do not enter $C_j$. The whole experiment
draws primaries and freezes first, then independent stage trials using no
lookup and no analytic reference signs (a reference sign may depend on
future primaries but never enters the generative history).

At truth, conditional on frozen variables and earlier trials, the current
summand differences are independent and centered with second moments at
most $4s_j^2\alpha_j$, so
$$\mathbb E|B^j(x)-B^{j-1}(x)|\le\delta_j:=4\sqrt{\alpha_j/(pM)}. \tag{86}$$
For each $j$, let $S_j$ be the first $m_j$ indices of $I_j$ in their fixed
order; delete their summands from $B^j$ to get $B_\circ^j$, and delete only
slot $i$ to get $B^j_{\neg i}$. Deleting $S_j$ lets one orientation be chosen
from the remaining score for every tested slot; deleting only $i$ gives the
background for varying slot $i$.

### 8.5 Smoothing, comparison forms, and the funding schedule

For $\xi>0$ use the probability density
$$f_\xi(a)=\frac{15}{16\xi}\Big(1-\frac{a^2}{\xi^2}\Big)^2\mathbf 1_{[-\xi,\xi]}(a),$$
even, continuously differentiable after extension by zero, decreasing on
$[0,\xi]$, with
$$\int|f_\xi'|=\frac{15}{8\xi},\qquad
\int_0^\xi2b\,[-f_\xi'(b)]\,db=1. \tag{87}$$
For every $z\in C_\ell$ let $\theta_{\ell,z}$ have this density with scale
$\xi_\ell$, independently; put $\Theta_\ell=\sum_{z\in C_\ell}
\theta_{\ell,z}\mathbf 1_z$, $\Theta_{\le j}=\sum_{\ell\le j}\Theta_\ell$.
With partitions fixed, set
$$h_j(B)=\mathbb E_\theta h(B+\Theta_{\le j}),\qquad
K_{j,z}(B)=\frac{\partial}{\partial a}h_j(B+a\mathbf 1_z)\big|_{a=0}.$$
(Translation of the density proves continuous differentiability even for
measurable $h$; derivatives on empty cells vanish.) Write $K_j=K_j(B^j)$,
$|K_j|_1=\sum_z|K_{j,z}|$. The map $\pi$ sums fine coordinates on each
parent cell. Define the common reference descriptor
$$\sigma^j=\operatorname{sign}K_{j-1}(B_\circ^j) \tag{88}$$
(ties positive, using partitions through level $j-1$), 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$, probability
$\beta_j=\alpha_j/(2L2^{J_{j-1}})$. Mark a consistent cell in $C_j$ if any
holds: some mode/descriptor match fraction in $S_j$ exceeds $2\beta_j$; some
vertical mode/descriptor hit fraction exceeds $2\beta_jp_{\mathrm{law}}$;
the shared-and-primary-one fraction in $I_j$ exceeds $2p$. (The first marks
every consistent cell.) All rules use actual query and trial data, never
$h$; every descriptor is checked, so on an unmarked cell the empirical
bounds also hold for the lookup-dependent $\sigma^j$. At a fixed witness,
conditioning on frozen data and earlier trials, the counting indicators are
independent over current slots, with means $\beta_j$, $\beta_jp_{\mathrm{law}}$,
and at most $p$; Chebyshev with a union bound over descriptors gives
$$\Pr(x\text{ is in a marked cell})\le
\frac{2L2^{J_{j-1}}}{m_j\beta_jp_{\min}}+\frac2{n_jp}. \tag{89}$$

**The raw forms.** (All expectations include the indicated score
experiment; numerical noises are shared when their levels appear on both
sides.) For a set $A$ of level-$j$ cells define
$$N_j(B;A)=\mathbb E\sum_{z\in A}\int_0^{\xi_j}[-f_{\xi_j}'(b)]
\big|h(B+\Theta_{\le j}^{z,+b})-h(B+\Theta_{\le j}^{z,-b})\big|\,db,$$
where the superscript fixes coordinate $(j,z)$ and averages the rest.
Translating the density and pairing $b$ with $-b$ gives
$$K_{j,z}(B)=\int_0^{\xi_j}[-f_{\xi_j}'(b)]\,
\mathbb E_{\text{other} }[h(B+\Theta_{\le j}^{z,+b})-h(B+\Theta_{\le j}^{z,-b})]\,db,$$
so $N_j$ dominates the expected variation on its cells, with truth cost at
most the probability the witness cell is in $A$ (the contributing integral
is one by (87)). Include $N_M(B^M;C_M)$ with weight one and
$N_j(B^j;\text{marked cells})$ with weight $T_0/a_j$,
$a_j=\min(p,\Delta\beta_j)$.

For $A=B^{j-1}$ or $A=B_\circ^j$, include with weight $T_0M$ the form
$$P_j(A)=\mathbb E\sum_{z\in C_{j-1}}\int_{-\xi_{j-1}}^{\xi_{j-1}}
|f_{\xi_{j-1}}'(b)|\big|h(B^j+\Theta_{<j}^{z,b}+\Theta_j)
-h(A+\Theta_{<j}^{z,b})\big|\,db.$$
Differentiating the fixed preceding coordinate shifts all its children
equally in the first argument (derivative $(\pi K_j)_z$) and gives the second
derivative $K_{j-1,z}(A)$, so
$\mathbb E|\pi K_j-K_{j-1}(A)|_1\le P_j(A)$; with
$\Lambda_{j-1}=15J_{j-1}/(8\xi_{j-1})$ its unweighted truth cost is at most
$\Lambda_{j-1}(\delta_j+\xi_j)$ for the first $A$ and
$\Lambda_{j-1}(m_js_j+\xi_j)$ for the second.

Include also ordinary coupled raw differences: (a) $B^0$ vs
$B^j+\Theta_{<j}$, weight $T_0M/e$; (b) uniform $i\in I_j$ forced shared,
$B^j+\Theta_{\le j}$ vs $B^j+\Theta_{<j}$, weight $T_0/(e\,p\,s_j^2)$;
(c) each mode and endpoint, forcing uniform $i\in S_j$ into that mode with
independent uniform descriptor and $\chi=+1$ and rebuilding $C_j$ from its
fresh path data, comparing $B^j_{\neg i}+s_jD^\pm+\Theta_{\le j}$ to the same
without $\Theta_{\le j}$, weight $T_0/(s_j\Delta 2^{-J_{j-1}})$. Forced trials
have their prescribed conditional law; the primary presentation stays in the
query list. The last two types have unweighted truth cost at most $\xi_j$;
the first at most $\sum_{k\le j}\delta_k+\sum_{\ell<j}\xi_\ell$. All
coefficients are nonnegative; the lookup-dependent $\sigma^j$ of (88) appears
only in the analysis.

**Sequential rational funding.** Put $\eta=1/[100M(L+1)]$,
$d_{\mathrm{cap}}=\eta e/(4T_0M^2)$, and choose rational
$0<\xi_0\le d_{\mathrm{cap}}$. At stage $j$ (with $J=J_{j-1}$,
$\Lambda=\Lambda_{j-1}$ known):

1. choose rational $0<\alpha_j\le\min(1/2,e)$ small enough that
   $\delta_j\le\min(d_{\mathrm{cap}},\eta/(2T_0M\Lambda))$ (square the
   right-hand bound for a rational sufficient condition); set
   $\beta_j=\alpha_j/(2L2^J)$, $a_j=\min(p,\Delta\beta_j)$;
2. choose an integer $m_j\ge2T_0(2L2^J)/(\eta a_j\beta_jp_{\min})$;
3. choose an even integer
   $$n_j\ge\max\Big(2m_j,\,4k,\,\tfrac4{pM},\,\tfrac{4T_0}{\eta a_jp},\,
   \tfrac{16T_0^2M\Lambda^2m_j^2}{\eta^2p}\Big),$$
   and rational $s_j$ in (76) ($n_j\ge4/(pM)$ ensures $s_j\le1$);
4. choose rational $\xi_j>0$ with
   $\xi_j\le\min(d_{\mathrm{cap}},\eta/(2T_0M\Lambda),
   \eta e p s_j^2/T_0,\eta s_j\Delta2^{-J}/T_0)$.

The marked form costs at most $\eta$ by (89) (each term $\eta/2$ after the
$T_0/a_j$ weight). Each projected-gradient form costs at most $\eta$ (for
deletion use $m_js_j\le\eta/(2T_0M\Lambda)$ from the last bound on $n_j$).
Each forced form costs at most $\eta$. The cumulative demand comparison costs
at most $(T_0M/e)2Md_{\mathrm{cap}}=\eta/2$. There are $5+2L$ tunable forms
per stage, so total truth cost is less than $M(5+2L)\eta<1$; with resampling
and final variation this is less than three, in particular at most four. All
earlier truth-cost estimates are uniform over later primary backgrounds, so
subsequent choices preserve them.

The consequences of (78) are
$$
\mathbb E|K_M|_1\le T_0\nu,\qquad
\mathbb E\sum_{z\text{ marked}}|K_{j,z}|\le a_j\nu,
$$
$$
\mathbb E|\pi K_j-K_{j-1}|_1\le\nu/M,\quad
\mathbb E|\pi K_j-K_{j-1}(B_\circ^j)|_1\le\nu/M,\quad
\mathbb E|h(B^0)-h_{j-1}(B^j)|^2\le e\nu/M, \tag{90}
$$
the square bound from averaging raw comparisons and $|u-v|^2\le|u-v|$ for
$u,v\in[0,1]$. Moreover
$$\mathbb E^{i\ \text{uniform shared}}|h_j(B^j)-h_{j-1}(B^j)|
\le e\,p\,s_j^2\nu, \tag{91}$$
and each uniform-descriptor endpoint experiment satisfies
$$\mathbb E|h_j(B)-h_{j-1}(B)|\le s_j\Delta2^{-J_{j-1}}\nu. \tag{92}$$

### 8.6 Orientation and clipping

Comparison measures and parameters are now fixed. Put
$$U=\max_{0\le j\le M}\mathbb E[|K_j|_1|\mathcal B],\qquad
v=\mathbb E[U|\mathcal Z],\qquad
E_j=\mathbb E[|\pi K_j-K_{j-1}|_1|\mathcal B].$$
The pointwise $|K_{j-1}|_1\le|K_j|_1+|\pi K_j-K_{j-1}|_1$ gives
$U\le\mathbb E[|K_M|_1|\mathcal B]+\sum_jE_j$, so
$$\mathbb E U=\mathbb E v\le(T_0+1)\nu. \tag{93}$$
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\le
2|a-b|_1$; applying with $a=\pi K_j$, $b=K_{j-1}(B_\circ^j)$ and then the
across-stage comparison,
$$\sum_zd_{j,z}\le|K_j|_1-|K_{j-1}|_1+|\pi K_j-K_{j-1}|_1
+2|\pi K_j-K_{j-1}(B_\circ^j)|_1,$$
and summing (dropping $-|K_0|_1$) proves
$$\sum_j\mathbb E\sum_zd_{j,z}\le(T_0+3)\nu. \tag{94}$$
Call $j$ **good** when its expected defect is at most $\Delta\nu$.

Signal transfer needs both smoothing levels: a current predicate $r_i$ can
split a cell of $C_{j-1}$, so preceding smoothing need not permit
differentiation in its direction, whereas $h_j$ does (since $r_i$ is
constant on every cell of $C_j$); but $h_j$'s smoothing law can depend on
the predicate's presentation, while $h_{j-1}$ omits that partition while
still containing $r_i$'s contribution. So the coarse component is kept as
the response source and 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 forcing $i$ shared,
$$s_jb_i=\mathbb E^{i,\mathrm{sh}}[h_{j-1}(B^j)|\mathcal B,a_i]
-\mathbb E^{i,\mathrm{sh}}[h_{j-1}(B^j)|\mathcal B];$$
define $b_i^+$ replacing $h_{j-1}$ by $h_j$, and $g_i=\mathbb
E[b_i|\mathcal Z,\mathcal R_i,a_i]$. Forcing shared does not alter the
primary/freeze law; on replacement the score and partition ignore the primary
amplitude $a_i$, so the ordinary-law amplitude projection is exactly
$(1-\alpha_j)s_jb_i$, and conditional Bessel applied to the last line of (90)
gives $\|((1-\alpha_j)b_i-b_i^0)_i\|_\Sigma^2\le e\nu$. Since
$\alpha_j\le e\le1/2$ and $\|b^0\|_\Sigma\le\sqrt\nu$,
$$\|b-b^0\|_\Sigma\le4\sqrt{e\nu},\qquad
\|b^+-b\|_\Sigma\le\sqrt{2e\nu} \tag{95}$$
(the second from projection contraction in each forced experiment,
Equation (91), and $|I_j|s_j^2\le2/(pM)$).

Fine differentiation along the primary amplitude gives, for every $a$,
$$|b_i^+(a)|\le\frac4{1-\alpha_j}\mathbb E\Big[\mathbf 1_{\{i\ \text{shared}\}}
\sum_z|K_{j,z}|r_i(z)\Big|\mathcal B\Big]\le8U \tag{96}$$
(bound the centered amplitude value by the integral of absolute derivatives
on $[-1,1]$, whose Lebesgue measure is at most $4\lambda$; divide by the
shared probability). Averaging over $I_j$, on unmarked cells the shared-hit
fraction is at most $2p$ and on marked cells at most one, so (90) and (93)
give
$$\mathbb E\operatorname{avg}_{i\in I_j}|b_i^+|\le
16p(T_0+1)\nu+8p\nu\le K_\ast p\nu. \tag{97}$$

Clip the fine component: put $A=\{U\le B_\ast,\ v\le B_\ast\}$ (a
$\mathcal B$-measurable event), $\widetilde b_i=b_i^+\mathbf 1_A$,
$\widetilde g_i=\mathbb E[\widetilde b_i|\mathcal Z,\mathcal R_i,a_i]$.

*Table of amplitude components.*
- $b_i^0,g_i^0$: centered amplitude component of the demand lookup
  $h(B^0)$ over $s_j$ and its projection onto $(\mathcal Z,\mathcal R_i,a_i)$
  — the initial signal.
- $b_i,g_i$: component of the coarse lookup $h_{j-1}(B^j)$ when $i$ is
  forced shared and the same projection; expressed through the common
  deleted-slot background in Section 9.
- $b_i^+$: fine-smoothing component in the same forced experiment — gives
  pointwise/first-moment bounds.
- $\widetilde b_i,\widetilde g_i$: clipped component
  $b_i^+\mathbf 1_{\{U\le B_\ast,\,v\le B_\ast\}}$ and its projection —
  bounded quantities for norm comparisons.

By (80) (with the weaker upper cap one) and Markov,
$\|b^0\mathbf 1_{A^c}\|_\Sigma^2\le\Pr(A^c)\le2(T_0+1)\nu/B_\ast$.
Projection contraction, (95), and the triangle inequality give
$$
\|\widetilde g-g^0\|_\Sigma\le[6\sqrt e+\sqrt{2(T_0+1)/B_\ast}]\sqrt\nu,\qquad
\|\widetilde g-g\|_\Sigma\le[10\sqrt e+\sqrt{2(T_0+1)/B_\ast}]\sqrt\nu. \tag{98}
$$
For every family $q_i$, (76) implies the norm conversion
$$\frac p2\|q\|_\Sigma^2\le
\operatorname{avg}_j\mathbb E\operatorname{avg}_{i\in I_j}|q_i|^2
\le2p\|q\|_\Sigma^2. \tag{99}$$
The first bracket of (98) is at most $\sqrt c/25$ and the second at most
$\sqrt c/20$ by (83). With the amplitude signal and (99),
$$\operatorname{avg}_j\mathbb E\operatorname{avg}_{i\in I_j}
|\widetilde g_i|^2\ge c_1p\nu,\qquad
\operatorname{avg}_j\mathbb E\operatorname{avg}_{i\in I_j}
|\widetilde g_i-g_i|^2\le\tfrac1{10}c_1p\nu. \tag{100}$$
Also $|\widetilde g_i|\le8B_\ast$, its averaged first moment is at most
$K_\ast p\nu$ at each stage by (97), and it vanishes when $v>B_\ast$.

At most $(T_0+3)/\Delta$ stages are bad, contributing at most
$8B_\ast K_\ast p\nu$ each to the unaveraged second moment of
$\widetilde g$; (85) caps their average contribution at $c_1p\nu/4$. On
$|g_i|<\gamma$ the elementary inequality
$|\widetilde g_i|^2\le2\gamma|\widetilde g_i|+|\widetilde g_i-g_i|^2$
(expand the last square, use $|g_i|<\gamma$) holds, with average at most
$(1/8+1/10)c_1p\nu$. So at least $c_1p\nu/2$ of the average second moment
remains on good stages with $|g_i|\ge\gamma$ and $v\le B_\ast$;
$|\widetilde g_i|^2\le64B_\ast^2$ then forces some good stage $j$ with
$$\Pr_{\mathcal Z,\ i\text{ uniform in }I_j,\ \mathcal R_i,a_i}
\big(|g_i|\ge\gamma,\ v\le B_\ast\big)\ge b_\ast p\nu. \tag{101}$$
We fix this stage for the rest of the analytic argument.

---
## 9. Conditional kernels and ordered paths

Fix the good stage of (101); abbreviate $s=s_j$, $\alpha=\alpha_j$,
$\beta=\beta_j$, $I=I_j$, $S=S_j$, $J=J_{j-1}$. All backgrounds run through
stage $j$ only. The goal is to turn the amplitude signal $g_i$ into a single
common Boolean response $W$ on actual conjunction predicates, whose successes
and failures are bounded by multiples of $\nu$ — so that Lemma 7.1 applies.

The obstacle is that a slot's presentation can leak into the partition, so
the amplitude response $g_i$ might depend on how a predicate is described
instead of what it is. The fix is a common **deleted-slot background**,
shared by every tested slot, over which the response becomes a function of
the actual predicate. Three families of comparison paths (vertical, ordered,
amplitude) then supply the three rare-event bounds.

### 9.1 The deleted-slot background

Fix an exterior $\mathcal Z=z$ (it fixes the freeze sets, frozen variables,
and $I,S$). Let $Y_i=(\mathcal R_i,a_i)$ for $i\in I$ with common law
$P_Y=P_{\mathcal R}\otimes\lambda$. Let $X$ contain all unfrozen primary
samples and actual trial variables before stage $j$, all future primaries,
and the fixed frozen contributions. It determines the preceding partition
window $C^-=C_{\le j-1}$ and the score $B_{\mathrm{out}}$ of slots outside
$I$ after earlier stages; it contains no reference gradients or signs.
(Actual earlier trials used only preceding query partitions to interpret
independent descriptors, so $X$ is independent of the current unfrozen
primaries given $z$.)

For a preceding partition sequence $C$ write the current trial kernel
$$q_C=(1-\alpha)\delta_{\mathrm{shared}}
+\frac\alpha L\sum_{m=1}^L P_m(dE)\,
\operatorname{Unif}(\{-1,+1\}^J)(d\tau)\,
\operatorname{Unif}[0,1](du)\,\operatorname{Unif}\{-1,+1\}(d\chi),$$
where $P_m$ is mode $m$'s fresh data law (with fresh amplitude if required),
and the descriptor is interpreted on $C_{j-1}$. Writing $T_i$ for the
current trial,
$$P_z(dX,dY,dT)=q_z(dX)\prod_{i\in I}
\big[P_Y(dY_i)\,q_{C^-(X)}(dT_i)\big]. \tag{102}$$
This conditional-on-$X$ product is the independence we use; after mixing over
$X$, no mutual independence of interpreted trials is asserted.

With $V_C(Y_i,T_i)$ the current slot summand (including factor $s$),
$$B^j_{\neg i}=B_{\mathrm{out}}+\sum_{k\in I\setminus\{i\}}V_{C^-}(Y_k,T_k),
\qquad
B_\circ^j=B_{\mathrm{out}}+\sum_{k\in I\setminus S}V_{C^-}(Y_k,T_k).$$
For every $i\in I$, the pair $(B^j_{\neg i},C^-)$ uses none of $Y_i$;
(102) shows its conditional law given $z$ is independent of the entire
primary presentation and amplitude in that slot, and permutation symmetry
makes it the same for every $i\in I$. Call this common law
$\kappa_z(dB,dC)$. The actual fine partition $C_j$ is *not* a coordinate of
this kernel.

Write $\phi_C(B)$ for the lookup smoothed through $C$. In the forced-shared
experiment put $F_i=\phi_{C^-}(B^j_{\neg i}+sa_ir_i)$, with $r_i$ the
predicate of $\mathcal R_i$. The definition of $b_i$ and the tower property
give
$$s\,g_i=\mathbb E^{i,\mathrm{sh}}[F_i|\mathcal Z,\mathcal R_i,a_i]
-\mathbb E^{i,\mathrm{sh}}[F_i|\mathcal Z,\mathcal R_i]$$
(indeed $\sigma(\mathcal Z,\mathcal R_i,a_i)\subseteq\mathcal B\vee
\sigma(a_i)$, and $a_i\perp\mathcal B$, so the subtracted
$\mathcal B$-conditional expectation removes $a_i$; forcing shared preserves
the background law). So the projected response is
$$s\,g_z(r,a)=\int\Big[\phi_C(B+sar)-\int\phi_C(B+sa'r)\,d\lambda(a')\Big]
\,d\kappa_z(B,C), \tag{103}$$
a version of every $g_i$ evaluated at the predicate $r$ and amplitude $a$,
depending on the *actual* predicate, not its presentation; in particular
$g_z(0,a)=0$. An unused queried position in a zero-predicate presentation
can change $C_j$ but not (103), which uses only preceding partitions.
(Independent sampled predicates may share bit names; independence is of
samples, not supports on the cube.)

For $i\in S$ extend the 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$, call it
$\kappa_z^S$, with $(B,C)$-marginal $\kappa_z$. This extended independence is
asserted only for $i\in S$ (the sign can correlate with the rest of the
background). Define the **coarse width** on any predicate $r$ by
$$F_z(r)=\int\frac{\phi_C(B+s\sigma r)-\phi_C(B-s\sigma r)}s\,
d\kappa_z^S(B,C,\sigma). \tag{104}$$
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 (103), supplying one common background for the three values
$ar,-\sigma r,+\sigma r$.

### 9.2 Forcing a slot and rebuilding the fine state

Fix a mode $m$ and $i\in S$. Let $\mathcal H_i$ contain $z$, $X$, every
current primary pair $Y_k$, and all current trials except $T_i$ (it retains
$Y_i$, whose original question list still enters the fine partition after
its summand is replaced). The preceding partitions, $B_\circ^j$, and
$\sigma$ are $\mathcal H_i$-measurable. The event
$$E_i=\{T_i\text{ replacement in mode }m,\ \tau_i=\sigma,\ \chi_i=+1\}$$
has exact conditional probability
$$\Pr(E_i|\mathcal H_i)=\frac\alpha{2L2^J}=\beta. \tag{105}$$
The number of formal parent cells is deterministic; empty cells and
collisions have not reduced $J$. Given $E_i,\mathcal H_i$, the path data
keep their mode law and $u$ is independent uniform.

Let $\Gamma(\mathcal H_i,T_i)$ construct the entire stage state, including
the score and the fine partition rebuilt from all unchanged primary question
lists and the trial's new path question list. For every nonnegative
measurable full-state function $Q_0$, the forced experiment preserves the
ordinary marginal law of $\mathcal H_i$ and satisfies
$$\mathbb E_{\mathrm{forced}}[Q_0(\Gamma)|\mathcal H_i]
=\mathbb E_{\mathrm{actual}}\big[Q_0(\Gamma)\mathbf 1_{E_i}/\beta
\,|\,\mathcal H_i\big]. \tag{106}$$
This is conditional expectation under (105); it holds for integrable signed
functions by subtraction, and $Q_0$ may depend on the new $C_j$, its fine
gradient, marks, and all current questions (there is no conditioning on
$C_j$ — it is an output of $\Gamma$). Deleting the whole subbatch in
$B_\circ^j$ keeps the reference sign fixed as $T_i$ is redrawn; it is
essential not to retain the old trial's fine partition.

Apply (106) for each $i\in S$ and average. On the resulting single actual
state there is one $C_j$, one $K_j$, one $\sigma$. Put
$d_z=|K_{j,z}|-\sigma_{\operatorname{par}(z)}K_{j,z}$ and
$f_m=\operatorname{avg}_{i\in S}\mathbf 1_{E_i}$. Then
$$\operatorname{avg}_{i\in S}\mathbb E_{\mathrm{forced}}\sum_zd_z
=\mathbb E_{\mathrm{actual}}\sum_zd_z\frac{f_m}{\beta}
\le2\mathbb E\sum_zd_z+\frac2\beta\mathbb E\sum_{z\text{ marked}}|K_{j,z}|
\le4\Delta\nu. \tag{107}$$
Indeed all descriptor counts are tested, so the realized $\sigma$'s count 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, not an
independence claim; goodness and the marked-gradient budget pay the last two
terms.

For a vertical mode, retain the hit: $f_{m,z}^{\mathrm{hit}}
=\operatorname{avg}_{i\in S}\mathbf 1_{E_i}r_i^{\mathrm{path}}(z)$. The same
calculation, conditional on $\mathcal Z$, gives
$$\operatorname{avg}_{i\in S}\mathbb E_{\mathrm{forced}}
\Big[\sum_z|K_{j,z}|r_i^{\mathrm{path}}(z)\Big|\mathcal Z\Big]
\le2p_{\mathrm{law}}\mathbb E[|K_j|_1|\mathcal Z]
+\beta^{-1}\mathbb E\Big[\sum_{z\text{ marked}}|K_{j,z}|\Big|\mathcal Z\Big].
\tag{108}$$

### 9.3 Endpoint conversion and path inequalities

In the forced experiment take $\tau=\sigma$, $\chi=+1$. Compared with an
independent uniform descriptor, this adaptive choice is dominated by the
factor $2^J$ (the uniform descriptor gives that one probability $2^{-J}$
conditionally); the fine state is rebuilt identically in both experiments.
Thus (92) gives, for either endpoint,
$$\operatorname{avg}_{i\in S}\mathbb E_{\mathrm{forced}}
\frac{|h_j(B^j_{\neg i}+sD^\pm)-h_{j-1}(B^j_{\neg i}+sD^\pm)|}{s}
\le\Delta\nu. \tag{109}$$

For fixed path questions, mode, descriptor, and amplitude data the rebuilt
fine partition is fixed as $u$ varies. Along
$B(u)=B^j_{\neg i}+s[(1-u)D^-+uD^+]$,
$$\frac1s\frac{d}{du}h_j(B(u))=\sum_zK_{j,z}(B(u))(D^+(z)-D^-(z)). \tag{110}$$
Each slope is $\sigma_{\operatorname{par}(z)}w_z$ with $0\le w_z\le2$, whose
negative part is at most $2\sum_zd_z(B(u))$ (if $\sigma K\ge0$ the coordinate
contributes nothing; if $\sigma K<0$, then
$-w_z\sigma K\le2(-\sigma K)\le2d_z$). Integrating in $u$ and using (106)
identifies the uniform-time law with the actual gradient, and (109) converts
the endpoints, proving for every mode
$$\operatorname{avg}_{i\in S}\mathbb E_{\mathrm{forced}}
\Big(\frac{h_{j-1}(B^j_{\neg i}+sD^-)-h_{j-1}(B^j_{\neg i}+sD^+)}s\Big)_+
\le10\Delta\nu. \tag{111}$$
(Eight units for the fine negative variation, two for the endpoints;
uniform in slots, cells, descriptors.)

For a vertical mode the absolute slope in (110) is at most
$2\sum_z|K_{j,z}|r(z)$. Equation (108) with
$\mathbb E[|K_j|_1|\mathcal Z]\le v$ bounds its conditional expected
integral by $4p_{\mathrm{law}}v$ plus a nonnegative error of expectation at
most $2\Delta\nu$; the two endpoint errors add at most $2\Delta\nu$ in
expectation. Conditional Jensen and (104) give a nonnegative
$e_{\mathrm{law}}(\mathcal Z)$ with
$$\mathbb E_{r\sim P_{\mathrm{law}}}|F_{\mathcal Z}(r)|
\le4p_{\mathrm{law}}v+e_{\mathrm{law}}(\mathcal Z),\qquad
\mathbb E e_{\mathrm{law}}\le4\Delta\nu \tag{112}$$
(covering zero-probability laws: no division by honest probability is used).

For an ordered coupling $(r,r')\sim\Pi$, write the difference of widths as
the upper-endpoint difference plus the reversed lower-endpoint difference;
the menu has exactly $+\sigma r\to+\sigma r'$ and $-\sigma r'\to-\sigma r$.
Positive part of a sum is at most the sum of positive parts, so conditional
Jensen and (111) twice give
$$\mathbb E_{\mathcal Z,r,r'}\big(F_{\mathcal Z}(r)-F_{\mathcal Z}(r')\big)_+
\le20\Delta\nu \tag{113}$$
(the same background serves both endpoints, fresh data drawn independently).

For the amplitude comparison use the common extended kernel of (104). At a
realization abbreviate $H_a=\phi_C(B+sar)$, $H_-=\phi_C(B-s\sigma r)$,
$H_+=\phi_C(B+s\sigma r)$, and let $a'$ be fresh. For any four reals of this
form,
$$|H_a-H_{a'}|\le H_+-H_-+\sum_{b\in(a,a')}
\big[(H_--H_b)_++(H_b-H_+)_+\big]. \tag{114}$$
Indeed $H_a-H_{a'}=(H_a-H_+)+(H_+-H_-)+(H_--H_{a'})$; bound the first and
third terms by positive parts and add the two nonnegative terms; repeating
with $a,a'$ exchanged proves the absolute-value form with no ordering
assumption. Divide by $s$, average over the background and $a'$ at fixed
$\mathcal Z,r,a$: the left average is $|g_{\mathcal Z}(r,a)|$ by (103), the
width term averages to $F_{\mathcal Z}(r)$, and the four positive-part
errors come from the two amplitude modes (once for $a$, once for $a'$).
Averaging the iid predicate and amplitude laws and (111) four times gives
$$\mathbb E_{\mathcal Z,r,a}\big(|g_{\mathcal Z}(r,a)|-F_{\mathcal Z}(r)\big)_+
\le40\Delta\nu. \tag{115}$$
The constants of (112)–(115) are $4,20,40$, independent of later scales
(the oriented-path constant was ten).

### 9.4 Selecting an exterior and threshold

Draw a threshold $\vartheta$ uniformly from $[\gamma/4,\gamma/2]$. For each
exterior $(\mathcal Z,\vartheta)$ define the common Boolean response on
actual predicates
$$W(r)=\mathbf 1_{\{F_{\mathcal Z}(r)>\vartheta\}}. \tag{116}$$
Equation (101) concerns a uniform index in $I$; (103) makes its response
exactly the common $g_{\mathcal Z}(r,a)$ under the independent iid
conjunction and amplitude laws. On $|g_{\mathcal Z}(r,a)|\ge\gamma$ but
$F_{\mathcal Z}(r)\le\gamma/2$ the positive part in (115) is at least
$\gamma/2$, so the lost mass is at most $80\Delta\nu/\gamma$; with (84),
$$\mathbb E_{\mathcal Z,\vartheta}
\big[\mathbf 1_{\{v\le B_\ast\}}\Pr_{P_\ast^t}(W=1)\big]
\ge\frac{b_\ast p\nu}{2}. \tag{117}$$
For every vertical law and fixed exterior, (112) and
$\vartheta\ge\gamma/4$ give
$$\Pr_{\mathrm{law}}(W=1)\le\frac{16}\gamma p_{\mathrm{law}}v
+\frac4\gamma e_{\mathrm{law}}(\mathcal Z), \tag{118}$$
each final term of expectation at most $16\Delta\nu/\gamma$. For real
$u,u'$ the threshold probability that $\mathbf 1_{u>\vartheta}>
\mathbf 1_{u'>\vartheta}$ is at most $4(u-u')_+/\gamma$ (the interval has
length at most $(u-u')_+$), so (113) gives, for each ordered law,
$$\mathbb E_{\mathcal Z,\vartheta}\Pr(W(r)>W(r')|\mathcal Z,\vartheta)
\le\frac{80\Delta\nu}{\gamma}. \tag{119}$$

Let $e_{\mathrm{tot}}(\mathcal Z,\vartheta)$ be the sum of all $V$
upper-error terms in (118) and all $Q$ violation probabilities in (119); it
is nonnegative and
$$\mathbb E e_{\mathrm{tot}}\le\frac{A_t\Delta\nu}{\gamma}. \tag{120}$$
Discard exteriors with $e_{\mathrm{tot}}>\varepsilon v$. The iid law is
among the vertical laws, so (118) bounds the integrated iid success on the
discarded set by $\big(16p/(\gamma\varepsilon)+1\big)\mathbb E e_{\mathrm{tot}}
\le b_\ast p\nu/4$. With (117) and (120) at least $b_\ast p\nu/4$ integrated
success remains on exteriors with $v\le B_\ast$ and
$e_{\mathrm{tot}}\le\varepsilon v$. An exterior in this set with $v=0$ has
zero success (iid upper bound). Since $\mathbb E v\le(T_0+1)\nu$ by (93) and
$b_0(T_0+1)=b_\ast/8$, some remaining exterior has $v>0$ and
$$\Pr_{P_\ast^t}(W=1)\ge b_0\,v\,p \tag{121}$$
(else integrated success would be at most $b_\ast p\nu/8$). At this exterior
every error summand is at most $\varepsilon v$, so every fixed type pattern
and prescribed ordered law satisfy
$$\Pr_{\mathrm{pat}}(W=1)\le v(K_0p_{\mathrm{pat}}+\varepsilon),\qquad
\Pr(W(r)>W(r'))\le\varepsilon v,\qquad 0<v\le B_0. \tag{122}$$
This is exactly Lemma 7.1 (with a single response depending only on the
conjunction), producing the valuation forbidden by Lemma 6.1 in a NO
instance. The contradiction proves soundness of Theorem 8.1.

### 9.5 The interface for finite compilation

We record the effective structure of the construction. For fixed $T_0$, all
choices in (83), the conjunction length, the path menu, $\Delta$, $M$, and
the sequential stage parameters are constants; the upper bounds on the
required integers and numerical precision can be huge functions of $T_0$ but
never depend on instance size. The primitive test samplers use fixed
mixtures of uniform choices from polynomial-size finite sets.

**Proposition (finite form structure).** *The demand law and raw comparison
measures of Theorem 8.1 have polynomially enumerable discrete seeds, whose
positive probabilities are at least an inverse polynomial in input size. For
each seed, after finitely many fixed subdivisions of numerical boxes, the
conditional densities are nonnegative rational polynomials and the score
table entries are rational polynomials of bounded degree in a fixed number of
numerical variables. There are only finitely many such numerical polynomial
patterns, independent of input size. The total raw comparison mass is finite
and bounded by a constant. For any fixed finite grid and deterministic
entrywise rounding rule, every positive rounded demand mass or comparison-pair
mass has an inverse-polynomial lower bound.*

*Proof.* Each sampled predicate has bounded arity and a polynomially
enumerable presentation law; a conjunction, a comparison path, and each slot
use a fixed number of samples, and the number of slots, stage choices, freeze
subsets, formal descriptors, and resampling indicators is fixed. Enumerating
their products takes a polynomial number of steps, and all discrete
probabilities are rational with polynomial bit length (products of a fixed
number of primitive probabilities and fixed rational weights), preserving an
inverse-polynomial lower bound. Descriptor interpretation and list refinement
need only fixed-size truth tables.

Separate the amplitude atom at zero from its uniform part. The remaining
variables are amplitudes, interpolation times, and noises in rational
intervals, with the integration variables of the derivative forms; their
joint densities are products of rational polynomial densities (absolute
derivative weights are polynomial on the two half intervals; $-f'_\xi$ is
already nonnegative on its interval). No lookup-dependent descriptor occurs
in any measure. All forms are positive measures on these fixed rectangular
pieces.

Fix a seed and an assignment to its bounded list of queried positions. Each
predicate value is $0$ or $1$, each descriptor a fixed sign, and each mark
determined by the finite trial counts; the scores are sums of rational
multiples of amplitudes, times, products of time and fresh amplitude, and
noises, multiplied by these fixed Booleans. So every score entry is a bounded
degree polynomial with rational coefficients; the possible local Boolean
tables, label-collision patterns, descriptor vectors, and mark sets range over
fixed finite sets (the numerical coefficients $s_j,\xi_j$ and external
weights are already fixed). Thus the polynomial patterns form a fixed finite
family; actual bit names only select where a table is evaluated, giving a
uniform bound on arity and range. Each derivative integral has mass at most
$15/(8\xi_j)$ per differentiated coordinate with finitely many formal cells;
ordinary comparisons have mass one before their finite external weights, so
total raw mass is bounded.

Fix a finite grid and entrywise rounding. For one numerical pattern, each
possible rounded local table, or pair of tables, has mass equal to the
integral of its fixed polynomial density over a fixed region of its numerical
box; these regions depend only on the pattern and the rounding rule. Finitely
many patterns and rounded tables give a positive minimum of their positive
masses. Renaming queried positions or identifying collisions adds no
numerical patterns. Any positive global rounded mass has at least one
contributing discrete seed; multiplying its inverse-polynomial probability by
the fixed positive minimum proves the last assertion (identifying identical
scores only adds masses). This completes the proposition and the remaining
effective assertions of Theorem 8.1. $\square$

**Parameter order.** $T_0$ fixes the resampling and signal constants; these
fix $e,B_\ast,\gamma,b_0,K_0,B_0$; Lemma 7.1 fixes $t,\varepsilon$; then
$\Delta$ fixes $M$; finally each stage fixes $\alpha_j,m_j,n_j,s_j,\xi_j$ in
that order. The path constants above do not grow when a later scale is made
smaller or a stage size larger.

---
## 10. Finite graphs with exactly uniform demands

We now convert Theorem 8.1 into an actual graph in which the ratio
$\Phi(G)=\mathrm{cap}(\partial S)/(|S|(N-|S|))$ is the objective. Two
obstacles must be handled.

- **Exactness.** The demand of Theorem 8.1 is a real measure, not uniform
  all-pairs counting. We retain a slightly smaller *rational* demand $l$
  in a way that preserves the denominator $|S|(N-|S|)$ exactly.
- **Arbitrarily small masses.** Replacing the demand by an additive
  approximation would not suffice, since the separated mass can be as
  small as one prefers.

The fix is to compile every score to a finite rational table, replicate
copies so that demand pairs are uniform, add heavy "cluster" edges whose
capacity exceeds any target cut, and add "tether" edges from leftover keys
to every retained vertex so any extra separated demand is expensive.

### 10.1 The choice of constants

Fix $C'>C$ and set
$$A_0=10^{12},\qquad \kappa=C'A_0,\qquad T_0=100\kappa. \tag{123}$$
Apply Theorem 8.1 with this $T_0$, and write $\mu$ for its demand law and
$\mathcal D$ for its raw comparison sum. At a satisfying witness $x$ the
total truth cost is at most $4$, and
$$\mu\{B^0(x)\ge1/4\}\ge10^{-4},\qquad
\mu\{B^0(x)\le-1/4\}\ge10^{-4}, \tag{124}$$
and for every measurable binary lookup $h$ with $\nu=\mathrm{Var}_\mu(h)>0$
in a NO instance, $\mathcal D(h)>T_0\nu$. The completeness target is the
following: define the cut $S_x$ from the honest witness by $h_{S_x}=\mathbf
1_{\{B^0>0\}}$, i.e. $S_x$ the keys whose score is positive. Then
$\mathcal D(h_{S_x})\le4$, and $\nu_{S_x}\ge10^{-8}$. The cut $S_x$ has
$|S_x|(N-|S_x|)\ge N^2\cdot10^{-8}$, so its ratio in the compiled graph is
at most the computable rational
$$a:=\frac{A_0}{N^2}, \tag{125}$$
where $N$ is the number of vertices. In a NO instance we will show (Section
10.6) every cut has ratio greater than $\kappa/N^2=C'a$; since $C'>C$, this
is the hardness factor.

### 10.2 Canonical keys

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

### 10.3 Rational compilation

**Lemma (rational compilation).** In polynomial time one can compute
nonnegative rationals $c_{ij}$ and $l_i$ such that
$$c_{ij}\ge c^0_{ij},\qquad \sum_{i<j}(c_{ij}-c^0_{ij})\le1, \tag{126}$$
$$0\le l_i\le\mu_i,\qquad L:=\sum_i l_i\ge1-10^{-6}. \tag{127}$$
Their binary encoding lengths are polynomial; every positive $l_i$ is at
least an inverse polynomial in the input size, with the polynomial
depending only on $C$.

*Proof.* Enumerate the discrete seeds in the demand and comparison
experiments; there are polynomially many (the number of samples per
experiment is fixed, and every bit-test sampling space has polynomial
size), their probabilities are rational with polynomial encoding length,
and every positive discrete sampling probability is at least an inverse
polynomial.

Subdivide each numerical box into rational boxes. For every grid boundary
and every table entry, first check whether the polynomial entry is
identically equal to that boundary; if so, resolve the tie by the fixed
rounding rule. Otherwise its equality set has Lebesgue measure zero (in
one variable, a nonzero polynomial has finitely many roots; in higher
dimension, expand in the last variable, apply the induction hypothesis to
simultaneous vanishing of its coefficients, and apply the one-variable
assertion on the fibres).

Coefficient bounds on a bounded box give a rational Lipschitz bound for
every polynomial entry; comparing its value at a rational corner with this
bound times the mesh identifies every box on which rounding is determined.
Apart from the finitely many null boundary sets, each point is eventually
in such a box, and the total weighted mass of unresolved boxes tends to
zero.

On a resolved box integrate its polynomial weight term by term, obtaining
an exact rational mass. For demand, discard unresolved boxes. For
capacities, assign the full box mass to every table pair that could occur
there. One may conservatively use every grid-valued table on the queried
coordinates: each has at most $Q_\ast<k$ essential names and hence a key
in the enumerated universe; their number is a constant independent of the
instance. Comparing a polynomial entry at a rational corner with its
rational Lipschitz bound times the mesh resolves every box away from a null
boundary set. Take the mesh fine enough that demand loses at most
$10^{-6}$ and capacity gains at most $1$ in total. Because the numerical
patterns form a fixed finite collection, one fixed mesh works for every
seed and every input. Let $U_{f,\omega,\ell}$ be the unresolved polynomial
mass of rectangular piece $\ell$ in comparison form $f$, conditional on seed
$\omega$, with its external form weight included. If $\pi_{f,\omega}$ is
the seed probability and $R_{f,\omega,\ell}$ bounds the number of
candidate unordered distinct key pairs, require
$$\sum_f\sum_\omega\pi_{f,\omega}
\sum_\ell R_{f,\omega,\ell}U_{f,\omega,\ell}\le1.$$
Averaging over seed probabilities (not summing without them) gives
(126) and the rational structure. All formal-cell, derivative-coordinate,
and rectangular pieces are counted with their multiplicities; the demand
sum, with no pair factor, must be at most $10^{-6}$. At this fixed mesh,
the positive retained conditional-demand masses belong to a fixed finite
set of positive rationals (the same over all mesh depths up to the fixed
bound), each with a positive constant lower bound. A positive $l_i$ is one
of these times a positive seed probability, so $l_i\ge$ inverse polynomial.
There are polynomially many seeds and a constant number of boxes and table
entries per seed, so rational arithmetic is polynomial bit complexity.
$\square$

Normalize retained demand by $\widehat\mu_i=l_i/L$, so
$\widehat\mu_i\le2\mu_i$ and $\widehat\mu(E)\ge\mu(E)-10^{-6}$ for every key
and set $E$.

### 10.4 Replication and heavy edges

Use the $4$-wise refinement of the collection $\{c_{ij}\}\cup\{l_i\}$: each
rational has a rational fourth root. Subdivide every key by a factor
$D_i\ge1$ chosen so the subdivided cluster weights $w_i=D_i m_i$ satisfy
$w_i/L\in[1-10^{-3},1+10^{-3}]$ for every retained $i$; this is achieved by
taking $D_i=O(1)$ (the $w_i/L$ lie in a fixed bounded rational interval).
Specialization follows: for every $i<j$ retained, the fractional pair
capacity and fractionally retained demand differ by at most $\alpha_\ast
\hat\mu_j\hat\mu_i/L^2$ with $\alpha_\ast\le10^{-3}$, and the expected
cut fraction equals the split probability $\Pr[h(Z)\ne h(Z')]$ up to
$\alpha_\ast$, where $Z$ is governed by the subdivisional demand law.

Introduce two auxiliary keys $K_i^{s_1},K_i^{s_2}$ per retained key, each
tagged by one of two distinct grid values assigned by the fixed rounding
rule; both compute the same essential table $K_i$, so their scores are
identical functions of the bit cube. For an honest coloring their labels
determine the cut: in a candidate cut the two copies are differently
labeled iff the subdivisional key is resolved as retained on one side.
Give each tag pair a common anchor vertex, joining both tag copies to it
by edges of capacity $2\kappa$ each. Any cut of capacity at most
$\kappa/4$ keeps the two tag copies on the same side, so the cut coloring
of a retained key is well-defined.

For each retained cluster $i$, join every copy to a fixed anchor vertex
of the cluster by an edge of capacity $2\kappa$. Any cut that splits the
cluster pays at least $2\kappa$.

For each unretained key $i$ (with $\hat\mu_i=0$), put a single vertex and
give it tether edges of total capacity $2\kappa\hat\mu_j$ to the vertex
set of every retained cluster $j$ (distributing this bandwidth equally
among the copies of cluster $j$); if the cut places key $i$ opposite
cluster $j$, the corresponding block of tethers contributes
$2\kappa\hat\mu_j$.

Then the total tether capacity cut by any key coloring $h$ is
$2\kappa L_{\mathrm{aux}}$, and the capacity across any cut that does not
split a cluster is
$$\mathrm{cap}(S)=\sum_{h_i\ne h_j}c_{ij}+2\kappa L_{\mathrm{aux}}.
\tag{134}$$

### 10.5 Completeness

From a satisfying assignment $x$, the projected score coloring
$h_x(i)=\mathbf 1_{\{B^0(x)>0\}}$ is a lookup on scores; every tag copy
and every auxiliary vertex inherits its label from the score. Place each
key $i$ on side $h_x(i)$ with all its $m_i$ copies, so no heavy or tag
edge is cut, and every tether joins two keys with $h_x$ agreement, so
$L_{\mathrm{aux}}=0$.

Then
$$\mathrm{cap}(S_x)=\sum_{h_x(i)\ne h_x(j)}c_{ij}\le D(h_x)+1\le5,
\tag{135}$$
because $D(h_x)\le4$ by Theorem 8.1 and the excess capacity sum is at
most $1$ by (126). By (124) the demand law assigns mass at least $10^{-4}$
to each of $\{B^0>1/4\}$ and $\{B^0<-1/4\}$ at any satisfying witness, so
$\nu_x\ge10^{-8}$. Thus
$$|S_x|(N-|S_x|)\ge N^2\cdot10^{-8},\qquad
\Phi(G)\le\frac{5}{N^2\cdot10^{-8}}=\frac{5\cdot10^8}{N^2}\le a
=\frac{A_0}{N^2}, \tag{136}$$
where $A_0=10^{12}\ge5\cdot10^8$.

Soundness of the opposite direction is the content of Section 10.6.

### 10.6 Soundness

Suppose a nonempty proper cut $S$ of the compiled graph has ratio at most
$C'a=\kappa/N^2$. Let $z=|S|/N$ and let $T$ be its total capacity. Then
$$T\le C'a\cdot|S|(N-|S|)=C'aN^2z(1-z)=\kappa z(1-z)\le\kappa/4. \tag{137}$$
A split cluster or a split tag pair would cut an edge of capacity
$2\kappa>\kappa/4\ge T$, so every cluster is monochromatic and every tag
pair is consistent: the cut determines a binary coloring $h_i$ of keys,
hence a measurable lookup $h$ on scores. Set
$$\nu=\operatorname{Var}_\mu(h),\qquad
L_{\mathrm{aux}}=\sum_{\hat\mu_i=0}w_i\sum_j\hat\mu_j|h_i-h_j|. \tag{138}$$
The tethers contribute exactly $2\kappa L_{\mathrm{aux}}$ to $T$, so
$\kappa L_{\mathrm{aux}}\le T/2$.

**Lemma (variance transfer).** *$z(1-z)\le36\nu+L_{\mathrm{aux}}$.*

*Proof.* Draw a key with the cut-vertex distribution $w$ (so
$w_i=m_i/N$ for retained $i$ and $w_i=1/N$ for unretained, and
$z=w(h=1)$, $1-z=w(h=0)$). Retain it when its $\hat\mu$ mass is positive;
otherwise replace it by an independent $\hat\mu$ draw. The color changes
with probability $L_{\mathrm{aux}}$. The replacement distribution
$$\rho_j=\mathbf 1_{\{\hat\mu_j>0\}}w_j+\alpha\hat\mu_j
\le3\hat\mu_j\le6\mu_j$$
absorbs the unretained mass (each $w_j\le2\hat\mu_j$ on retained keys,
$\alpha\hat\mu_j\le\hat\mu_j$, and the total is normalized). Apply the same
coupling independently to two $w$ draws: their original disagreement is
$2z(1-z)$; their replacement disagreement is at most $36\cdot2\nu=72\nu$
by $\rho\otimes\rho\le36\mu\otimes\mu$ and the identity
$\Pr_\mu[h(B)\ne h(B')]=2\nu$; and a union bound over the two color changes
gives
$$2z(1-z)\le72\nu+2L_{\mathrm{aux}},$$
i.e. the claimed bound after dividing by two. $\square$

Then $T\le 36\kappa\nu+\kappa L_{\mathrm{aux}}\le36\kappa\nu+T/2$, so

$$T\le72\kappa\nu. \tag{139}$$

Moreover $\nu>0$: otherwise $T=0$ from (139), $L_{\mathrm{aux}}=0$ from
the tether bound and the variance transfer, $\kappa z(1-z)\le0$ from
$\nu=0$ and $L_{\mathrm{aux}}=0$, contradicting proper nonempty cut. With
(126)–(138),

$$\mathcal D(h)\le T\le72\kappa\nu<T_0\nu \tag{140}$$

by $T_0=100\kappa$. This contradicts Theorem 8.1 in a NO instance, so every
nonempty proper cut of any NO-instance graph has ratio strictly greater
than $C'a$.

### 10.7 Complexity and conclusion (Theorem 2.1)

To finish the proof of Theorem 2.1, fix $C>1$ and choose $C'>C$. Sections
10.1–10.6 turn every $3$CNF formula $F$ of size $n$ into an $N$-vertex
graph $G(F)$ with $N$ polynomial in $n$, such that with the target rational
$a=A_0/N^2$ we have

* (completeness, Section 10.5) if $F$ is satisfiable then $\Phi(G(F))\le a$;
* (soundness, Section 10.6) if $F$ is unsatisfiable then every nonempty
  proper cut has ratio $>C'a=\kappa/N^2>C\cdot A_0/N^2\ge Ca$.

Neither direction inspects a satisfying assignment.

**The complexity of the whole construction.** Enumerate the primitives:
formula -> bit-test space $\mathcal S$ (size $2^{O(d)}$ with $d=O(\log
n)$); score experiments (poly-enumerable rational seeds, fixed finite
numerical boxes); canonical keys (poly many, since $k$ is constant and $g$
is constant); rational compilation (poly many boxes over a fixed-mesh grid);
replication ($m_i$ poly many, since $l_i$ inverse-poly); graph ($O(N^2)$
vertices). Each step is polynomial in $n$; the exponent may depend on
$C$, never on $N$.

**Decision procedure.** Given a $3$CNF formula of size $n$:
- compute $G$ (poly time);
- approximate $\Phi(G)$ within factor $C$ (poly time by assumption);
- if ratio $\le Ca$, accept; else reject.

In a YES instance, Theorem 10.7's completeness gives a cut of ratio
$\le a$, and the approximator returns ratio $\le Ca<C'a$.
In a NO instance, every cut has ratio $>C'a>Ca$, so any returned ratio
$>Ca$. So $C$-approximating Uniform Sparsest Cut to within $C'a/Ca=C'/C$
ratio decides $3$CNF, contradicting $\mathbf P\ne\mathbf{NP}$.

Fix $C>1$ as in Section 2.2 (say $C=1+10^{-12}$): then $C'>C$ exists and
the construction gives, unconditionally, a factor-$C'$ approximation gap
for Uniform Sparsest Cut with exactly uniform all-pairs demands. Theorem
2.1 follows. $\square$

---

## 11. Where the paper sits and what stays open

- **Unconditionality.** Theorem 2.1 holds without assuming Unique Games,
  Small-Set Expansion, or any complexity conjecture beyond $\mathbf
  P\ne\mathbf{NP}$. The classical conditional results (Raghavendra 2008,
  Raghavendra–Steurer 2010, Raghavendra–Steurer–Tulsiani 2012) are not
  contradicted; they address a different (balanced) objective and a
  different reduction.
- **Non-uniform sparsest cut.** The Chawla–Krauthgamer–Kumar–Rabani–
  Sivakumar conditional hardness is over cutset-output search under Cook
  reductions; the direct reduction of Theorem 2.1 is independent of it.
  d'Orsi–Jones–Ruotolo–Vadhan–Zhang (2025) recently studied the analogous
  low-degree question on Abelian Cayley graphs. They are not contradicted.
- **Exact NP-hardness of uniform sparsest cut.** Matula–Shahrokhi (1990)
  and BBPP (2012) give NP-hardness; Theorem 2.1 gives a constant-factor
  approximation gap. The two are compatible.
- **The exponent.** The proof gives $2^{O_r(d)}$ test size and $2^{O_r(d)}$
  computation, hence a reduction in polynomial time with exponent depending
  on the fixed hardness factor $C$. The exponent is not optimized.
- **Higher factors.** For every $C>1$, some $C'>C$ is achieved. The gap is
  $C'/C$, which can be made as large as one likes.

---

## References

The references below are cited where their statements are used.

- Arora, Rao, Vazirani (2009). Expander flows, geometric embeddings and
  graph partitioning. *J. ACM* 56(2):5:1--5:37.
- Alon, Chung (1988). Explicit construction of linear sized tolerant
  networks. *Discrete Math.* 72(1--3):15--19.
- Arora, Safra (1998). Probabilistic checking of proofs. *J. ACM*
  45(1):70--122.
- Arora, Lund, Motwani, Sudan, Szegedy (1998). Proof verification and the
  hardness of approximation problems. *J. ACM* 45(3):501--555.
- Ambühl, Mastrolilli, Svensson (2011). Inapproximability results for
  maximum edge biclique, sparsest cut and balanced cut. *SIAM J. Comput.*
  40(6):1701--1717.
- Bonsma, Broersma, Patel, Pyatkin (2012). The complexity of finding
  uniform sparsest cuts in various graph classes. *J. Discrete Algorithms*
  14:136--149.
- Beelen, Ghorpade, Høholdt (2010). Affine Grassmann codes. *IEEE Trans.
  Inform. Theory* 56(7):3166--3176.
- Blum, Luby, Rubinfeld (1993). Self-testing/correcting with applications
  to numerical problems. *J. CSS* 47(3):549--595.
- Chawla, Krauthgamer, Kumar, Rabani, Sivakumar (2006). On the hardness of
  approximating multicut and sparsest cut. *Comput. Complexity* 15(2):
  94--114.
- Dinur (2007). The PCP theorem by gap amplification. *J. ACM* 54(3):12.
- d'Orsi, Jones, Ruotolo, Vadhan, Zhang (2025). Low-degree hardness of
  sparsest cut on Abelian Cayley graphs. (Preprint.)
- Efron, Stein (1981). The jackknife estimate of variance. *Ann. Statist.*
  9(3):586--596.
- Garcia, Stichtenoth (1996). A tower of Artin–Schreier extensions of
  function fields attaining the Drinfeld–Vladut bound. *Invent. Math.*
  121:211--222.
- Gemmell, Lipton, Rubinfeld, Sudan, Wigderson (1991). Self-testing/
  correcting for families of functions. *J. CSS* 54(1):16--25.
- Gupta, Talwar, Witmer (2013). Sparsest cut on bounded treewidth graphs.
  *STOC 2013*.
- Hoeffding (1948). A class of statistics with asymptotically normal
  distribution. *Ann. Math. Statist.* 19:293--325.
- Holenstein (2009). Parallel repetition: simplifications and the
  no-signaling case. *Theory Comput.* 5:141--172.
- Khot, Vishnoi (2015). The unique games conjecture, integrality gap for
  cut problems, and embeddability of negative-type metrics. *J. ACM*
  62(1):3:1--3:39.
- Leighton, Rao (1999). Multicommodity max-flow min-cut theorems.
  *J. ACM* 46(6):787--832.
- Manurangsi, Trevisan (2018). Mildly exponential time approximations for
  vertex cover, balanced separator and uniform sparsest cut.
  *APPROX/RANDOM 2018*, LIPIcs 116:20:1--20:17.
- Matula, Shahrokhi (1990). Sparsest cuts and bottlenecks in graphs.
  *Discrete Appl. Math.* 27:113--123.
- Raghavendra (2008). Optimal algorithms and inapproximability results
  for every CSP? *STOC 2008*.
- Raghavendra, Steurer (2010). Graph expansion and the unique games
  conjecture. *STOC 2010*, 755--764.
- Raghavendra, Steurer, Tulsiani (2012). Reductions between expansion
  problems. *CCC 2012*, 64--73.
- Raz (1998). A parallel repetition theorem. *SIAM J. Comput.*
  27(3):763--803.
- Rubinfeld, Sudan (1996). Robust characterizations of polynomials.
  *SIAM J. Comput.* 25(2):252--271.
- Stichtenoth (2001). Explicit constructions of towers of function fields.
  *European Congress of Mathematics*, Prog. Math. 202:219--224.
- OpenAI (2026). The Unique Games Theorem.
  \texttt{github.com/openai/math}, September 23, 2026.

The references above are informational; none of them is needed to *check*
the proof, which is self-contained in Sections 3--10 once the parameters
$\lambda$, $r$, $\gamma$, $C$, $A_0$, $T_0$, $\kappa$ are fixed.