\documentclass[11pt]{article} \usepackage[margin=1in]{geometry} \usepackage{amsmath,amssymb,amsthm,mathtools} \usepackage[T1]{fontenc} \usepackage{lmodern} \usepackage[ colorlinks=true, linkcolor=blue, citecolor=blue, urlcolor=blue ]{hyperref} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newcommand{\Q}{\mathbb{Q}} \newcommand{\E}{\mathbb{E}} \newcommand{\ind}{\mathbf{1}} \DeclareMathOperator{\Bin}{Bin} \DeclareMathOperator{\poly}{poly} \begin{document} \title{On counting satisfying assignments via polynomial separation} \author{Scott Duke Kominers% \thanks{% \textsc{Harvard Business School; Department of Economics and Center of Mathematical Sciences and Applications, Harvard University; and a16z Frontier Research.} This note was developed in the process of navigating, reading, and attempting to distill the arguments in~\cite{OAI} with the assistance of GPT-6 Astra and Claude Opus 5.5 (accessed in part via Poe with the support of Quora, where I am an advisor). \textit{This draft is highly preliminary and heavily LLMathed; I expect to refine it further.} I thank Ittai Abraham, Quang Dao, Joachim Neu, Tim Roughgarden, Justin Thaler, and Kai Zhe Zheng for helpful comments. This work was conducted while I was visiting the Technological Innovation, Entrepreneurship, and Strategic Management (TIES) Group at the MIT Sloan School of Management; I greatly appreciate their hospitality. }% } \date{Preliminary Version -- October 26, 2026} \maketitle The number of satisfying assignments of a formula in conjunctive normal form is a sum of products of clause indicators. If the variables were partitioned into small groups and each indicator depended on just one group, this sum would factor into local sums, each computed by enumerating assignments to one group. The algorithm of OpenAI's \emph{The Exponential Time Hypothesis is false}~\cite{OAI} obtains such a factorization after deforming the inputs and fixing the values of certain integer linear forms. Low-degree polynomial interpolation then recovers the original count. We give a qualitative exposition of the construction, separating the general counting procedure from the particular construction that supplies its input. For every fixed clause width $k \ge 2$, the OpenAI paper gives an exact-counting algorithm with time bound $(n+m)^{O_k(1)} 2^{O_k(n\log\log n/\sqrt{\log n})}$ and polynomial space~\cite[Theorem~1.1]{OAI}, which is quantitatively stronger than Theorem~\ref{thm:main} below. Our recovery procedure and swap construction follow the ideas of~\cite[Sections~3--4]{OAI}. For the qualitative result, we use cyclic balancing of finitely many label types and exploit the two-group support of each exceptional basis vector; these replace the estimates in~\cite[Lemma~4.5]{OAI} and~\cite[equation~(4.16)]{OAI}, respectively. \section{Statements and proof strategy}\label{sec:intro} Throughout, a \emph{$3$-CNF} is a conjunction of clauses containing at most three literals, and $n$ counts all declared variables, including unused ones. \emph{Time} means deterministic bit complexity. Polynomial exponents in time and space bounds are absolute, independent of the fixed parameters; implicit multiplicative constants may depend on parameters indicated by subscripts. We write $[a] = \{1,\ldots,a\}$ for a nonnegative integer $a$. \begin{theorem}\label{thm:main} For every $\varepsilon > 0$, satisfiability of a $3$-CNF on $n$ variables with $m$ clauses can be decided in time $O_\varepsilon(2^{\varepsilon n}(n+m)^{O(1)})$ and polynomial space. \end{theorem} Here $\varepsilon$ is fixed independently of the input size. The implicit constant may depend on $\varepsilon$, so the statement does not give a running-time bound for an arbitrary choice $\varepsilon = \varepsilon(n) \to 0$. Arbitrarily small fixed positive exponential rates suffice to contradict the Exponential Time Hypothesis of Impagliazzo and Paturi~\cite{IP}, which asserts that for some $\delta > 0$ there is no deterministic $O(2^{\delta n}(n+m)^{O(1)})$-time algorithm for $3$-SAT. The algorithmic statement we prove is the following counting result. \begin{theorem}\label{thm:bounded} For every $b \ge 1$ and $\alpha > 0$, the number of satisfying assignments of a $3$-CNF on $n$ variables with $m$ clauses, in which each variable occurs at most $b$ times, can be computed in time $O_{b,\alpha}(2^{\alpha n}\poly(n+m))$ and polynomial space. \end{theorem} \begin{proof}[Proof of Theorem~\ref{thm:main} from Theorem~\ref{thm:bounded}] The sparsification lemma~\cite{IPZ}, in the bounded-occurrence formulation stated in~\cite[Lemma~1]{CIP}, expresses the input as a disjunction of at most $2^{\sigma n}$ $3$-CNFs on the same variables, each with occurrence bound $b_\sigma$. Unused variables can be retained as declared variables. After removing duplicate clauses, the input has $O(n^3)$ clauses. For fixed $\sigma$, sparsification takes $2^{\sigma n} n^{O_\sigma(1)}$ time; depth-first traversal generates its leaves one at a time in polynomial space. Take $\sigma = \varepsilon/3$ and count each formula at rate $\alpha = \varepsilon/3$. The original formula is satisfiable exactly when one of these counts is positive. The combined time is $2^{2\varepsilon n/3} n^{O_\varepsilon(1)}$, in addition to polynomial-time input preprocessing. The unused $\varepsilon n/3$ in the exponent absorbs the parameter-dependent polynomial in $n$. Processing the formulas sequentially gives the asserted bounds. \end{proof} To apply the counting procedure, we express the formula algebraically: Remove tautological clauses and repeated literals, retaining unused variables. An empty clause gives count $0$; if no clauses remain, the count is $2^n$. This preprocessing takes polynomial time in $n+m$. If no empty clause is present, the occurrence bound implies that at most $bn$ clauses remain, so the subsequent counting algorithm has polynomial factors in $n$ alone. For each remaining clause $e$, let $I_e \subseteq [n]$ be its set of variables. For $v \in I_e$, put $\ell_{ev}(y) = y$ for a positive literal and $\ell_{ev}(y) = 1-y$ for a negative literal. The polynomial \[ \Phi_e((y_{ev})_{v \in I_e}) = 1 - \prod_{v \in I_e}(1-\ell_{ev}(y_{ev})) \] is $1$ on assignments satisfying clause $e$ and $0$ on the others. Thus the desired count is \[ \sum_{x \in \{0,1\}^n} \prod_e \Phi_e((x_v)_{v \in I_e}). \] Each occurrence of $x_v$ in clause $e$ is replaced by its own form $L_{ev}(T,x)$, linear in $x$ and polynomial in $T$, with $L_{ev}(0,x) = x_v$. At each of $Q$ designated points $T = t$, fixing a few integer linear forms (\emph{measurements}) makes every clause depend only on variables in one small group. The count then factors into local sums. Section~\ref{sec:recovery} shows how Taylor coefficients at these points reduce to such sums, so Hermite interpolation recovers the value at $T = 0$. Sections~\ref{sec:balance}--\ref{sec:construction} construct the forms by writing the identity operator as a sum of terms that use variables outside their assigned groups at only a few designated points, plus an exact remainder whose value on an assignment is determined by measurements. Factors $1-T/t$ cancel each term at those points. The number of vanishing factors bounds the degree, and hence the Taylor order required for recovery. Assignments remain Boolean, although the deformed inputs need not be. \section{Separated deformations and recovery}\label{sec:recovery} We work with a general finite family of factors, indexed by $e$. For each factor, let $I_e \subseteq [n]$ and let $F_e \in \Q[(y_{ev})_{v \in I_e}]$ be a nonzero polynomial, supplied as a list of monomials and rational coefficients. Write \[ Z_F = \sum_{x \in \{0,1\}^n} \prod_e F_e((x_v)_{v \in I_e}), \qquad M = \sum_e \deg F_e. \] A zero factor gives $Z_F = 0$ and is handled separately. For clause indicators, $M = \sum_e |I_e| \le bn$ when the occurrence bound is $b$. \begin{definition}\label{def:sep} Let $\rho,w,\mu$ be nonnegative integers and $Q,B$ positive integers. A \emph{separated deformation} of $(F_e)$ with parameters $(\rho,Q,w,\mu,B)$ consists of forms \[ L_{ev}(T,x) = \sum_{i=1}^n \lambda_{evi}(T)x_i, \qquad \lambda_{evi} \in \Q[T], \quad \deg \lambda_{evi} \le \rho, \] with $L_{ev}(0,x) = x_v$, and the following data at each of $Q$ distinct designated rational points $t$: \begin{enumerate} \item a finite indexed family of disjoint groups $\mathcal V_{t,g}$, $g \in \mathcal G_t$, with union $[n]$ and sizes at most $w$, allowing empty groups, and an assigned group $g_t(e) \in \mathcal G_t$ for each factor; \item integer linear forms $m_{t,1},\ldots,m_{t,\mu_t}$ in $x$, called \emph{measurements}, where $\mu_t \le \mu$, each supported in one group (that is, with zero coefficients outside that group) and taking values in $[-B,B]$ on the Boolean cube; \item separation: if $x,x' \in \{0,1\}^n$ agree on $\mathcal V_{t,g_t(e)}$ and have the same measurement values, then $L_{ev}(t,x) = L_{ev}(t,x')$ for every $v \in I_e$. \end{enumerate} The groups, factor assignments, and measurements may depend on $t$. \end{definition} The algorithm enumerates measurement values. Once they are fixed, each factor depends only on its assigned group, although the forms $L_{ev}$ may initially involve variables anywhere in $[n]$. All data are listed explicitly, with sparse encodings permitted. Let $N$ be their total binary encoding length plus $n+M+\rho+Q$. \subsection{The recovery algorithm} Suppose a separated deformation is given. Define \[ H(T) = \sum_{x \in \{0,1\}^n} \prod_e F_e((L_{ev}(T,x))_{v \in I_e}). \] Then $H(0) = Z_F$ and $\deg H \le M\rho$. The values at the $Q$ designated points need not determine $H$, but its Taylor coefficients through order $q = \lfloor M\rho/Q \rfloor$ at each point do, since $M\rho < Q(q+1)$. We retain only these orders, performing computations in $\mathcal T = \Q[z]/(z^{q+1})$. To recover Taylor coefficients, we keep $x$ in the base inputs $L_{ev}(t,x)$ and introduce auxiliary variables $X$ in the perturbations $L_{ev}(t+z,X)-L_{ev}(t,X)$. Setting $X = x$ restores the desired inputs; setting $X$ to a fixed Boolean vector instead makes the perturbations independent of $x$, preserving separation. Each auxiliary variable brings a factor of $z$, so each monomial in the order-$j$ coefficient involves at most $j$ auxiliary variables. The proof below shows how inclusion--exclusion converts this observation into local sums with at most $j$ original variables fixed to $1$. The local routine takes a designated point $t$, a set $J \subseteq [n]$, and shifts $c = (c_{ev})$ in $\mathcal T$, independent of $x$. It computes \begin{equation}\label{eq:local-sum} \mathcal S_t(J,c) = \sum_{\substack{x \in \{0,1\}^n\\x_i=1\ (i \in J)}} \prod_e F_e((L_{ev}(t,x)+c_{ev})_{v \in I_e}). \end{equation} Assign each measurement to a group containing its support. Enumerate $\beta = (\beta_1,\ldots,\beta_{\mu_t}) \in \{-B,\ldots,B\}^{\mu_t}$, where $\beta_j$ is the proposed value of $m_{t,j}$. A group assignment is \emph{compatible with $\beta$} if it realizes every measurement assigned to that group. Initialize a running sum to zero, and for each $\beta$: \begin{enumerate} \item Enumerate assignments to each group $\mathcal V_{t,g}$ and retain a compatible representative $\xi_g^\ast$, without imposing the constraints $x_i = 1$. If any group has no compatible assignment, discard $\beta$. \item For each group, enumerate its compatible assignments $\xi$ satisfying $\xi_i = 1$ for $i \in J \cap \mathcal V_{t,g}$. Let $y^{g,\xi}$ combine $\xi$ with the representatives in the other groups, and compute \[ Z_g(\beta) = \sum_{\substack{\xi\text{ compatible with }\beta\\ \xi_i=1\ (i \in J \cap \mathcal V_{t,g})}} \prod_{e:g_t(e)=g} F_e((L_{ev}(t,y^{g,\xi})+c_{ev})_{v \in I_e}). \] The representatives provide values outside the current group; separation makes their choice irrelevant to the factors assigned to this group. They need not satisfy the constraints in the other groups: those constraints are imposed when computing the other local sums. \item Add $\prod_g Z_g(\beta)$ to the running sum. \end{enumerate} Return the running sum. An empty product is $1$, so a group assigned no factors still contributes its number of compatible assignments satisfying the constraints. For recovery, evaluations at indicator vectors determine the auxiliary multilinear coefficients by inclusion--exclusion. Write $\ind_U$ for the indicator vector of $U \subseteq [n]$ and proceed as follows. \begin{enumerate} \item At each designated point $t$, initialize $H_t(z) = 0$ in $\mathcal T$. For every $E \subseteq [n]$ with $|E| \le q$ and every $U \subseteq E$, form \[ c^{t,U}_{ev}(z) = L_{ev}(t+z,\ind_U)-L_{ev}(t,\ind_U) \quad\text{in }\mathcal T \] and add $(-1)^{|E|-|U|}\mathcal S_t(E,c^{t,U})$ to $H_t(z)$. \item By Hermite interpolation, find the unique polynomial $\widetilde H$ of degree less than $Q(q+1)$ satisfying \[ \widetilde H(t+z) \equiv H_t(z) \pmod{z^{q+1}} \qquad\text{at every designated point }t. \] \item Return $\widetilde H(0)$. \end{enumerate} Process the measurement tuples and pairs $(E,U)$ sequentially, retaining the Taylor coefficient arrays for interpolation. \subsection{Correctness and cost} We verify the local routine and the recovery step in turn, then bound the arithmetic cost and storage. \begin{lemma}\label{lem:recovery} Suppose a separated deformation of $(F_e)$ with parameters $(\rho,Q,w,\mu,B)$ is given. Put $M = \sum_e \deg F_e$ and $q = \lfloor M\rho/Q \rfloor$, and let $N$ be the binary encoding length of the factors and deformation data plus $n+M+\rho+Q$. The recovery algorithm returns $Z_F = \sum_{x \in \{0,1\}^n}\prod_e F_e((x_v)_{v \in I_e})$ in time \begin{equation}\label{eq:recovery-cost} \poly(N)\,2^w(2B+1)^\mu \sum_{j=0}^{\min(q,n)} \binom{n}{j}2^j \end{equation} and polynomial space in $N$. \end{lemma} \begin{proof} Fix $t$ and a feasible measurement tuple $\beta$. Since each measurement is supported in its assigned group, the compatible assignments satisfying $x_i = 1$ for $i \in J$ form a Cartesian product. Separation makes each shifted factor depend only on its assigned group and on $\beta$. Thus the product of the local sums $Z_g(\beta)$ is exactly the contribution of $\beta$ to~\eqref{eq:local-sum}. Summing over $\beta$ proves correctness of the local routine. For the recovery step, introduce auxiliary variables $X = (X_1,\ldots,X_n)$ and put \[ G_x(X,z) = \prod_e F_e\Bigl( (L_{ev}(t,x)+L_{ev}(t+z,X)-L_{ev}(t,X))_{v \in I_e} \Bigr) \quad\text{in }\mathcal T[X]. \] At $X = x$ the inputs become $L_{ev}(t+z,x)$, so $\sum_x G_x(x,z) = H(t+z)$. Each correction is linear in $X$ and divisible by $z$. Consequently the coefficient $[z^j]G_x$ has $X$-degree at most $j$. Reduce $G_x$ modulo $X_i^2-X_i$ for every $i$, obtaining a multilinear polynomial $\overline G_x$ with the same Boolean values. Write \[ \overline G_x(X,z) = \sum_{E \subseteq [n]} g_{x,E}(z)\prod_{i \in E}X_i. \] The degree bound implies $g_{x,E} = 0$ for $|E| > q$. At $X = \ind_U$, only monomials indexed by subsets of $U$ survive, so $G_x(\ind_U,z) = \sum_{E \subseteq U}g_{x,E}(z)$. Inverting these subset sums by inclusion--exclusion gives \[ g_{x,E}(z) = \sum_{U \subseteq E}(-1)^{|E|-|U|}G_x(\ind_U,z). \] For Boolean $x$ we have \[ G_x(x,z) = \sum_{|E| \le q}g_{x,E}(z)\prod_{i \in E}x_i. \] The monomial on the right is $1$ exactly when $x_i = 1$ for every $i \in E$. Moreover, \[ G_x(\ind_U,z) = \prod_e F_e((L_{ev}(t,x)+c^{t,U}_{ev}(z))_{v \in I_e}). \] The shifts $c^{t,U}_{ev}(z)$ are independent of $x$, so fixing the measurements still separates these factors. Summing over $x$ and substituting the coefficient formula therefore yields \begin{equation}\label{eq:taylor-recovery} H(t+z) = \sum_{\substack{E \subseteq [n]\\|E| \le q}} \sum_{U \subseteq E}(-1)^{|E|-|U|} \mathcal S_t(E,c^{t,U}) = H_t(z) \quad\text{in }\mathcal T. \end{equation} Both $H$ and $\widetilde H$ have degree less than $Q(q+1)$, and their difference is divisible by $(T-t)^{q+1}$ at each of the $Q$ distinct designated points. It must therefore be zero. This is the uniqueness step in Hermite interpolation~\cite[Chapter~5]{vzGG}, and proves that the algorithm returns $H(0) = Z_F$. Each enumeration of a group examines at most $2^w$ assignments, and there are at most $(2B+1)^\mu$ measurement tuples. Each call to the local routine uses $2^w(2B+1)^\mu\poly(N)$ arithmetic operations. There are $\sum_{j=0}^{\min(q,n)}\binom{n}{j}2^j$ pairs $(E,U)$ at each point; the number $Q$ of points is included in $N$. This proves the operation bound in~\eqref{eq:recovery-cost}. The numerical terms added to the encoding length in $N$ bound the degrees and coefficient-array sizes polynomially. The operands also have polynomial bit length in $N$: the shifts are obtained from the input polynomials. A common denominator for the input data, raised to a polynomially bounded power, clears the denominators in the truncated evaluations; their numerators also have polynomial bit length. Summation adds at most the logarithm of the number of terms, again polynomial in $N$. The Hermite system has polynomial dimension and entry bit length, so exact rational linear algebra has polynomial bit cost. Sequential enumeration stores only the current assignments, representatives, running sums, and coefficient arrays, using polynomial space. \end{proof} The three nonpolynomial factors in~\eqref{eq:recovery-cost} account for local enumeration, measurement values, and Taylor recovery. The following criterion bounds their combined exponential rate. \begin{corollary}\label{cor:rate} Fix $b \ge 1$. Suppose that for every $\delta \in (0,1]$ one can construct a separated deformation of the clause indicators of each preprocessed $3$-CNF with occurrence bound $b$, at least one clause, and no empty clause, in time $O_{b,\delta}(\poly(n))$, with $N = O_{b,\delta}(\poly(n))$, such that \begin{equation}\label{eq:targets} \begin{aligned} w &\le \delta n + O_{b,\delta}(1),\\ \mu\log_2(2B+1) &\le \delta n + O_{b,\delta}(1),\\ M\rho &\le \delta Qn. \end{aligned} \end{equation} Then Theorem~\ref{thm:bounded} holds for this $b$. \end{corollary} \begin{proof} Here $q \le \delta n$. Since $0 < \delta \le 1$, the binomial theorem gives \[ \sum_{j=0}^{\min(q,n)} \binom{n}{j}2^j \le \delta^{-q}\sum_{j=0}^n \binom{n}{j}(2\delta)^j \le \delta^{-\delta n}(1+2\delta)^n. \] Lemma~\ref{lem:recovery} bounds the time by \[ O_{b,\delta}\!\left( 2^{n(2\delta+\delta\log_2(1/\delta)+\log_2(1+2\delta))} \poly(n) \right). \] The exponential rate tends to zero with $\delta$, so it can be made smaller than any prescribed $\alpha > 0$. Adding the input preprocessing cost gives the $\poly(n+m)$ factor in Theorem~\ref{thm:bounded}. \end{proof} The second bound in~\eqref{eq:targets} concerns the ranges of the measurements as well as their number. A single integer linear form, such as $\sum_i 2^{i-1}x_i$, can encode the entire Boolean assignment. Thus controlling the number of measurements alone does not suffice; their ranges must also be controlled. \section{Balanced labels}\label{sec:balance} Fix an occurrence bound $b \ge 1$ and a formula after the preprocessing in Section~\ref{sec:intro}, with at least one clause and no empty clause. An \emph{incidence} is a pair $(e,v)$ with $v \in I_e$; their number is $M = \sum_e |I_e| \le bn$. Fix an integer $s \ge 6$ independently of $n$, and use $Q = s^6$ designated points. The parameter choice is explained in Section~\ref{sec:conclusion}. Let $\mathcal A = [s]^Q$, with $\Lambda = s^Q$ elements. Assign a label vector $d_e \in \mathcal A$ to each clause and $a_v \in \mathcal A$ to each variable. At designated point $t \in [Q]$, variable $v$ belongs to group $a_v(t)$ and clause $e$ is assigned to group $d_e(t)$. The incidence label is the pair $(a_v,d_e)$, with $D = \Lambda^2$ possible values. Balancing the variable labels makes the groups small; balancing incidence labels allows coordinate swaps after bounded padding. \begin{lemma}\label{lem:balance} In polynomial time one can assign labels so that each variable label occurs $n/\Lambda + O_{b,s}(1)$ times and each incidence label occurs $M/D + O_{b,s}(1)$ times. \end{lemma} \begin{proof} For each clause size, distribute clauses cyclically among the vectors in $\mathcal A$. If $M_d$ counts incidences in clauses with label $d$, then $M_d = M/\Lambda + O(1)$, with error at most $1+2+3 = 6$. Classify each variable by the multiset of labels on its incident clauses, including the empty multiset for unused variables. There are at most $(\Lambda+1)^b$ types. For any clause label $d$, every variable of a given type has the same number of incidences with clauses labeled $d$. Distributing the variables of each type cyclically among $\mathcal A$ therefore balances all these incidence counts at once. A type $\kappa$ with $n_\kappa$ variables contributes $n_\kappa/\Lambda + O(1)$ to each variable label. Summing proves the first bound. If $\nu_{\kappa,d}$ is the multiplicity of $d$ in type $\kappa$, the incidence count for label $(a,d)$ is \[ \sum_\kappa \nu_{\kappa,d} \bigl(n_\kappa/\Lambda + O(1)\bigr) = M_d/\Lambda + O_{b,s}(1) = M/D + O_{b,s}(1). \] For fixed $b,s$ the numbers of labels and types are constant, so the assignments take polynomial time. \end{proof} We give every incidence label the same number of positions so that coordinate swaps preserve the coordinate set. Write $n_{ad}$ for the number of incidences with label $(a,d)$ and put $h = \max_{a,d}n_{ad}$. Place those incidences in positions $(a,d,1),\ldots,(a,d,n_{ad})$; the remaining positions $(a,d,n_{ad}+1),\ldots,(a,d,h)$ are padding. Thus the coordinate set is \[ \Omega = \mathcal A \times \mathcal A \times [h], \qquad |\Omega| = Dh = M + O_{b,s}(1). \] For $\omega = (a,d,r)$ write $a_\omega = a$ and $d_\omega = d$. Define $\zeta(x) \in \Q^\Omega$ by placing $x_v$ at the incidence position of $(e,v)$ and zero at each padding position. No Boolean variables are added. Exactly $\Lambda/s$ label vectors have any prescribed value at coordinate $t$. Lemma~\ref{lem:balance} therefore gives $|\mathcal V_{t,g}| = n/s + O_{b,s}(1)$ for the groups $\mathcal V_{t,g} = \{v:a_v(t)=g\}$, $g \in [s]$. Unused variables remain in these groups and contribute their factors of $2$ through the local sums. \section{The tensor construction}\label{sec:construction} Use the groups and clause assignments from Section~\ref{sec:balance}, with designated points $1,\ldots,Q$. We first identify a sufficient operator decomposition, then construct it using swaps. \subsection{From a decomposition to a deformation} Call a linear operator $A$ on $\Q^\Omega$ \emph{local at $t$} if, at each incidence position $\omega$ of clause $e$, the form $(A\zeta(x))_\omega$ depends only on variables in group $d_e(t)$. Linear combinations of operators local at $t$ remain local at $t$. We will decompose the identity into such operators and an exact remainder $\Delta$, called the \emph{residual operator}. Its value $\Delta\zeta(x)$ is the \emph{residual vector}: the correction needed to recover $\zeta(x)$ from the other terms. \begin{lemma}\label{lem:decomposition} Suppose we have an exact decomposition into linear operators on $\Q^\Omega$, \begin{equation}\label{eq:decomposition} I = \Delta + \sum_{\substack{S \subseteq [Q]\\|S| \le \rho}}\gamma_S A_S, \end{equation} where $\gamma_S \in \Q$, each $A_S$ is local at every $t \notin S$, and $\Delta\zeta(x)$ is determined at each point by bounded integer measurements, each supported in one group. Then \begin{equation}\label{eq:general-deformation} P(T) = \Delta + \sum_{|S| \le \rho}\gamma_S \prod_{t \in S}\left(1-\frac{T}{t}\right)A_S \end{equation} defines forms $L_{ev}(T,x) = (P(T)\zeta(x))_\omega$, where $\omega$ is the position of $(e,v)$, with degree at most $\rho$, $L_{ev}(0,x) = x_v$, and separation after fixing the measurements. \end{lemma} \begin{proof} Every multiplier equals $1$ at zero, so $P(0) = I$ and $L_{ev}(0,x) = x_v$. At $T = t$, the terms with $t \in S$ vanish, making $P(t)-\Delta$ local at $t$. Specifying the measurements determines the residual vector $\Delta\zeta(x)$ and gives the separation condition for the input forms. Also $\deg P \le \rho$. \end{proof} It remains to construct a decomposition with few possible locality failures per summand and measurements satisfying Corollary~\ref{cor:rate}. \subsection{Why swaps give the decomposition} For each fixed position number $r$, pair the coordinates $a(t)$ and $d(t)$ of the two labels. This identifies \[ \Q^{\mathcal A \times \mathcal A} \cong \bigl(\Q^s \otimes \Q^s\bigr)^{\otimes Q}. \] For $t \in [Q]$, let $\Pi_t$ exchange $a(t)$ and $d(t)$, leaving all other coordinates and $r$ unchanged. At an incidence position of clause $e$, this permutation reads a position whose variable label has $t$th coordinate $d_e(t)$. If that position contains a variable, the variable belongs to the assigned group; if it is padding, the value is zero. Thus $\Pi_t$ is local at $t$. Swapping other coordinate pairs does not change this $t$th coordinate, so it preserves that property. The swaps commute and satisfy $\Pi_t^2 = I$. Write $\Pi_S = \prod_{t \in S}\Pi_t$, with $\Pi_\varnothing = I$, and put $V = \Pi_{[Q]}$. The full swap is local at every designated point, but feeding $V\zeta(x)$ to the clauses generally gives them values of other variables or padding zeros. It therefore cannot replace the original inputs. Its usefulness comes from the identity \[ V\Pi_S = \Pi_{[Q]\setminus S}. \] This operator performs every swap except those in $S$, and is local at every designated point outside $S$. Here the designated point $T = t$ corresponds to coordinate pair $t$: the multiplier $1-T/t$ cancels each term that omits that swap and may therefore fail to be local there. Consequently, multiplying a polynomial of total degree at most $\rho$ in the swaps by $V$ gives a linear combination of operators with at most $\rho$ possible locality failures each. It remains to find such a polynomial whose product with $V$ agrees with the identity on a subspace of small codimension. The complementary components will supply the measurements. The bounds below require their proportion to be $o(1/Q)$, since each measurement value uses $O(Q)$ bits. For one coordinate pair, the standard vectors $\mathbf b_{ij}$ of $\Q^{[s]\times[s]}$ give the orthogonal eigenbasis \[ \mathbf b_{ii}\ (i \in [s]), \qquad \mathbf b_{ij}+\mathbf b_{ji}, \quad \mathbf b_{ij}-\mathbf b_{ji}\ (1 \le i < j \le s). \] The eigenvalues of the swap are respectively $+1,+1,-1$. The antisymmetric vectors comprise $s(s-1)/2$ of the $s^2$ basis vectors, a proportion $p = (s-1)/(2s)$. Tensor this basis over the $Q$ coordinate pairs and take a copy for each $r \in [h]$, obtaining a common eigenbasis $\mathcal H$ for all swaps. Set \[ W = \frac{1}{2}\sum_{t=1}^Q(I-\Pi_t). \] On a basis vector with $k$ antisymmetric factors, $V$ multiplies the $Q$ swap eigenvalues and therefore acts by $(-1)^k$. Each summand $(I-\Pi_t)/2$ acts by $1$ on an antisymmetric factor and by $0$ otherwise, so $W$ acts by $k$. A uniformly chosen tensor basis vector chooses its factors independently, each antisymmetric with probability $p$. Hence $k \sim \Bin(Q,p)$, with standard deviation at most $\sqrt Q/2$. Set $R = s^5$ and choose the \emph{central window} \[ k_0 = \lfloor Qp-(R-1)/2 \rfloor, \qquad I_0 = \{k_0,\ldots,k_0+R-1\}. \] This window contains the values of $k$ for most basis vectors, yet $R/Q = 1/s$ is small. Let $f \in \Q[\tau]$ be the unique polynomial of degree less than $R$ with $f(k) = (-1)^k$ for $k \in I_0$, and put $K = Vf(W)$. Then $K$ is the identity on the span of those basis vectors. A term in $W^j$ is a product of at most $j$ swaps; cancelling repeated swaps by $\Pi_t^2 = I$ cannot increase that number. Thus we can expand $f(W) = \sum_{|S|