ETH.pdf
Number of Pages: 22
A simplified proof of ETH is false
Shiva Kintali ∗
October 26, 2026
Abstract
For every fixed ε > 0, we give a deterministic 3-SAT algorithm on n variables and m
clauses using Cε(n + m + 1) cε 2εn bit operations, refuting ETH. Our simplified exposition of OpenAI’s proof [1] combines sparsification, bounded occurrences, spectral replacement, and rational interpolation.
1 The goal and the proof strategy
A Boolean variable takes a value in {0, 1}, where zero means false and one means true. A literal is a variable or its negation. A clause is satisfied when at least one of its literals is true. A 3-CNF is a conjunction of clauses of at most three literals. Given such a formula on n declared variables with m clauses, 3-SAT asks whether some assignment satisfies every clause. An assignment specifies all declared variables, including any that occur in no clause. We allow n = 0 and m = 0, with the conventions below. Our goal is an algorithm with an arbitrarily small exponential rate.
Theorem 1.1. For every fixed ε > 0, there are positive constants Cε, c ε and a deterministic algorithm deciding 3-SAT in at most
Cε(n + m + 1) cε 2εn
bit operations.
We use ETH in its standard positive-rate formulation [2, p. 368]: there is a constant δ > 0 for which no deterministic 3-SAT algorithm runs in 2 δn (n + m + 1) O(1) time. Theorem 1.1 contradicts this assertion by taking, for example, ε = δ/ 2. The theorem asserts a family of algorithms, one for each fixed rate parameter ε. This parameter is fixed before the input is given; the algorithm and its polynomial time factor may depend on it.
The main idea. If the variables could be divided into small groups so that every clause used only one group, we could count satisfying assignments separately in each group and multiply the answers. The difficulty is that clauses link different groups. We remove these links algebraically. First express each clause by a polynomial equal to its truth value on Boolean inputs. In these polynomials, replace each variable occurrence by a linear expression whose coefficients depend polynomially on a parameter T . At T = 0 the expression is the original variable. At selected positive integers T = t, each deformed clause factor depends on variables in just one group and on a small collection of integer linear measurements (linear sums with integer coefficients). Each measurement uses variables from a single group. Once their values are fixed, both the factors and the constraints realizing those values separate by group, so the group
> ∗Email: shiva.kintali@gmail.com Homepage: shivakintali.github.io
1sums can be multiplied. Summing the product of the deformed clause polynomials over all original Boolean assignments defines a polynomial H(T ). At zero it equals the desired count. At the other integer nodes its values need not be positive or integral; we use them as interpolation data to recover
H(0). Specifically, we compute Taylor coefficients up to an order that is a small fraction of the variable count, at each selected integer, and interpolate. There are two main tasks. Section 2 shows how such a replacement gives a counting algorithm; its key observation is that a monomial in a low-order Taylor coefficient uses only a few formal variables. Section 3 constructs the replacement using commuting swap matrices and a polynomial that corrects their action on most basis directions. Section 4 chooses the parameters and accounts for exact arithmetic. After the two reductions below, we first deduce the main theorem from the counting proposition. The remaining sections then prove that proposition. We use elementary linear algebra, polynomial interpolation, and basic probability; the Boolean coefficient-extraction identity is derived when it is used. The only result about SAT complexity that we invoke without proof is the sparsification lemma stated below.
Conventions. All logarithms have base two except ln, which is natural. For an integer k ≥ 0, write [k] = {1, . . . , k }. Repeated input clauses count separately. An empty conjunction is true; an empty disjunction, including an empty clause, is false. A clause is tautological if it contains both a variable and its negation. After deleting tautological clauses and repeated literals within a clause, the number of occurrences of a variable is the number of clauses containing it. Variables are indexed by [ n], and input clauses are listed explicitly using binary variable indices and clause delimiters. Running-time bounds count bit operations and include reading this encoding; intermediate arithmetic-operation counts are explicitly identified. We write poly θ(u) for a polynomial upper bound in u whose constants and degree may depend on the fixed parameter θ; we use this notation with θ = s or
θ = ε. Empty products equal one and empty sums equal zero. The coefficient `1 norm is the sum of the absolute values of the coefficients. This norm will bound the range of our integer measurements and the size of the numbers used in exact arithmetic.
1.1 Reducing to bounded occurrences
The first reduction makes the number of clauses linear in the number of variables. It produces several formulas, and the original formula is satisfiable exactly when at least one of them is satisfiable.
Lemma 1.2 (Decision sparsification [3, Corollary 1, p. 523]) . For every fixed η > 0, a deterministic algorithm expresses a 3-CNF F on n declared variables as
F ≡
> L∨ > i=1
Fi, 0 ≤ L ≤ 2ηn ,
where each Fi is a 3-CNF on the same declared variables with at most Cηn clauses. The total construction time is 2ηn (n + m + 1) Oη (1) . Here Cη depends only on η.
To apply the cited result, first remove tautological clauses, repeated literals within a clause, and duplicate clauses. These operations preserve the satisfying assignments and take polynomial bit time in n + m + 1. All declared variables are retained even if they no longer appear. If an empty clause is present, use L = 0; if no clauses remain, use L = 1 with F1 the empty conjunction. These conventions also cover n = 0. For every other input, the cited construction applies to clauses of width at most three; its polynomial work, including binary encoding costs, is absorbed by the 2displayed time bound. The equivalence is an equality of Boolean functions. Disjointness of the solution sets is unnecessary: we only ask whether at least one Fi is satisfiable. The second reduction limits how many clauses can use the same variable. It preserves satisfiability; two formulas with this relationship are called equisatisfiable . We give each occurrence its own copy and enforce agreement with a cycle of implications. Bounded occurrences will later let us balance the formula’s incidences among an auxiliary array’s positions.
Lemma 1.3 (Bound the occurrences) . A 3-CNF with n declared variables and m clauses can be transformed using polynomially many bit operations in n + m + 1 into an equisatisfiable 3-CNF with
N ≤ n + 3 m declared variables in which each variable occurs in at most three clauses. The output has at most 4m clauses. Proof. First remove tautological clauses and repeated literals within a clause. If an empty clause occurs, return the single empty-clause formula on the same declared variables; all claimed bounds hold because then m ≥ 1. Otherwise, let m′ be the number of remaining clauses, and let dx count the occurrences of variable x in them. For d = dx ≥ 2, replace its occurrences by x1 = x, x 2, . . . , x d,preserving their signs. All newly introduced copies are fresh variables, distinct across all original variables. Add the cycle d∧
> i=1
(¬xi ∨ xi+1 ), xd+1 := x1.
The cycle is satisfied exactly when all copies agree. If any copy is one, the implications force every copy around the cycle to be one; the all-zero assignment also satisfies the cycle. This includes d = 2, where the two clauses give the two directions of an equivalence. Every satisfying assignment of the original formula extends to a satisfying assignment of the output by giving each copy its original variable’s value. Conversely, any satisfying assignment of the output has equal copies, and reading x1 for each copied variable satisfies every original clause. Thus the formulas are equisatisfiable. The extension is in fact unique. Variables with zero or one occurrence are retained. Each copy appears in one rewritten original clause and two cycle clauses, so it occurs at most three times. Since ∑
> x
dx ≤ 3m′ ≤ 3m, the exact variable and clause counts obey
N = n + ∑
> x:dx≥2
(dx − 1) ≤ n + 3 m, mout = m′ + ∑
> x:dx≥2
dx ≤ 4m.
The new clauses have width two, so the width bound remains three. Scanning the clauses, assigning fresh indices, and writing the output all take polynomially many bit operations in n + m + 1. It remains to solve these bounded-occurrence formulas at arbitrarily small exponential rates. The following statement will be proved without assuming any of the new lemmas of [1].
Proposition 1.4. For every integer s ≥ 64 , there is a deterministic algorithm that exactly counts the satisfying assignments of a 3-CNF on N declared variables and m input clauses, each variable occurring at most three times after deleting tautological clauses and repeated literals within each clause, in
poly s(N + m + 1) 2 asN bit operations ,
where as > 0 and as = O(log s/s ) → 0. An explicit choice of as is given in (4.2) .
The parameter s is a fixed integer controlling the exponential rate; it is never the input length. All constants depending on s may be large. 31.2 How the counting proposition implies the main theorem
We allocate half of the allowed exponential rate to sparsification and half to solving its output formulas. The bounded-occurrence reduction enlarges the variable count by a constant factor. We therefore choose the counting parameter s only after that factor is known.
Deduction of Theorem 1.1 from Proposition 1.4. It suffices to consider rational ε > 0: a smaller positive rational target implies the bound for any prescribed real ε > 0. Fix such an ε, and put
η = ε/ 2. The case n = 0 is decided directly in O(m + 1) bit operations, so assume n ≥ 1. Apply Lemma 1.2; every resulting formula has mi ≤ Cηn clauses. By Lemma 1.3 it has an equisatisfiable bounded-occurrence formula with
Ni ≤ (1 + 3 Cη)n =: Bηn.
The reduced formula has at most 4 mi ≤ 4Cηn clauses. The constant Bη is fixed before selecting the parameter s. Choose s ≥ 64 sufficiently large that asBη ≤ ε/ 2, which is possible because as → 0. Run Proposition 1.4 on each reduced formula, and accept if any count is positive. If there are no output formulas, reject. Including the copying step, each output formula costs at most poly ε(n + 1) 2 asNi ≤ poly ε(n + 1) 2 εn/ 2.
There are at most 2 ηn = 2 εn/ 2 output formulas. The total time is therefore bounded by 2ηn (n + m + 1) Oη (1) + 2 ηn poly ε(n + 1)2 εn/ 2.
Since η = ε/ 2 is fixed, this is at most Cε(n + m + 1) cε 2εn for suitable positive constants Cε, c ε. All choices and all subsequent computations are deterministic. The rest of the paper proves Proposition 1.4.
2 How a suitable deformation gives an algorithm
In this section we assume the replacement forms exist and explain how to use them. We call the replacement a deformation because it depends on T : it agrees with the original formula at zero and has a form that we can sum efficiently at the selected positive integers. Section 2.4 follows the entire recovery procedure on a four-variable formula.
2.1 The counting polynomial and the required structure
Let F be a 3-CNF on N declared variables and m input clauses, satisfying the bounded-occurrence promise of Proposition 1.4. Remove tautological clauses and repeated literals within a clause, return zero on an empty clause, and retain all N declared variables. No further variable copying is performed here. If N = 0, the remaining formula is the empty conjunction: return one, for its unique empty assignment. This preprocessing takes polynomial bit time in N + m + 1. For the rest of the section assume N ≥ 1. For every unused variable add a dummy factor equal to one with that variable as its scope. A scope records which variable slots belong to a factor, even when the factor is constant. Let F index the clauses and dummy factors, and let Ie be the scope of factor e.An incidence is a pair ( e, v ) with v ∈ Ie; it is one variable slot in one factor. Write M for the total number of incidences. Then
|Ie| ≤ 3, |{ e : v ∈ Ie}| ≤ 3, N ≤ M := ∑
> e∈F
|Ie| ≤ 3N. (2.1) 4The dummy factors leave the product unchanged and give each unused variable one incidence. Thus every variable has between one and three incidences, which proves the bounds on M . All factors have nonempty scopes, so |F| ≤ M ≤ 3N . For a real clause define its satisfaction polynomial Φe(( Xv)v∈Ie ) = 1 − ∏
> v∈Ie
(1 − `e,v (Xv)) ,
where `e,v (Xv) is Xv or 1 − Xv according to the sign of the literal. For a dummy factor put Φ e = 1. On Boolean inputs these polynomials are the clause indicators. For example, the clause ( x1 ∨ ¬ x2)has polynomial 1 − (1 − X1)X2, which is zero exactly on its sole falsifying pair ( x1, x 2) = (0 , 1). The product of the indicators is one exactly on satisfying assignments, so summing this product counts them: #F = ∑
> x∈{ 0,1}N > ∏ > e∈F
Φe(( xv)v∈Ie ). (2.2) Choose an integer r ≥ 2, positive integers Q, R, D , and a positive rational τ ; their values will be fixed in Section 4. Here r is the number of groups, Q the number of interpolation nodes, and R
a degree bound. The parameters τ and D control how many measurements are needed and how many values each can take. For now they are fixed constants; only N grows. For each incidence (e, v ) we seek a form homogeneous and linear in X, Le,v (T ; X) = ∑Ni=1 pe,v,i (T )Xi with pe,v,i ∈ Q[T ], satisfying
Le,v (0; X) = Xv, deg T Le,v ≤ R.
For each integer t ∈ [Q] we require the following additional structure: (i) Disjoint groups [ N ] = St, 1 t · · · t St,r , possibly empty, with |St,g | ≤ 2N/r .(ii) One assigned group σt(e) for each factor e.(iii) Integer linear measurements on the separate groups, with at most 2 τ N measurements in total and coefficient `1 norm at most D for each measurement. (iv) At T = t, every Le,v is a rational linear combination of variables in St,σ t(e) and the measure-ments. Its coefficients are explicitly available. The same assigned group must work for all inputs of a factor. Measurements are allowed to be redundant or identically zero. A measurement is simply an integer linear sum of bits. Its coefficients can be negative. The point is to enumerate its possible values while leaving the bits that realize each value to be summed within their own group.
Proposition 2.1 (Recovery from a deformation) . Fix r, Q, R, D, τ as above. Suppose the normalized factor system satisfies (2.1) . Suppose the coefficient arrays of the rational forms Le,v , the groups, the factor assignments, the measurements, and the rational node representations are supplied and satisfy the zero-value and degree conditions and requirements (i)–(iv). Put q = b3N R/Q c. Then its exact satisfying-assignment count can be recovered deterministically using at most
poly( N + 1)
> > min( q,N ) > ∑ > j=0 > (
Nj
> )
2j
>
(2 D + 1) 2τ N 22N/r (2.3)
arithmetic operations over Q. The polynomial’s constants and degree may depend on the fixed parameters.
5This is a recovery statement from supplied data. For fixed parameters, these arrays have polynomially many entries in N : there are at most 3 N forms, each with N coefficient polynomials of degree at most R. At each of the fixed number of nodes there are O(N ) measurements, and each node representation uses O(N ) rational coefficients. Constructing the data is the task of Section 3. The next two subsections prove this proposition. Its bound counts rational operations; coefficient lengths must also be controlled to obtain a bit-operation bound. For the explicit construction in Section 3, this is done in Section 4.1 and Appendix B.
2.2 Summing after the measurements are fixed
Fix t and abbreviate Sg = St,g . Let xg = ( xi)i∈Sg be the bits in group g, and write Cgxg for its list of measurements, where Cg is an integer matrix with cg rows. Every measurement of a Boolean assignment is an integer in [ −D, D ]. Enumerate all
y = ( y1, . . . , y r), yg ∈ {− D, . . . , D }cg .
A group with no measurements has exactly one empty measurement tuple. An empty group has one empty assignment, and all its measurements are zero. For g = σt(e), property (iv) supplies rational coefficients such that
Le,v (t; x) = ∑
> i∈Sg
αe,v,i xi +
> r
∑
> h=1
γe,v,h · (Chxh).
Here γe,v,h has ch coordinates; dependence of these coefficients on the fixed node t is suppressed. Write λe,v (xg; y) for the right side with Chxh replaced by yh. Thus fixing y leaves a factor assigned to g dependent only on xg.This is the reason for enumerating measurements: once y is fixed, there is no remaining variable dependence between different groups. We can sum all factors assigned to one group over that group’s assignments, then multiply these group sums. Work in Q[z]/(zJ ) for an integer J ≥ 1. Fix corrections be,v (z) ∈ Q[z]/(zJ ) that are independent of the assignment x being summed over. Also fix a subset E ⊆ [N ] of the bits to one; E = ∅
imposes no such restriction. Working modulo zJ means keeping only coefficients of 1 , z, . . . , z J−1
after every operation. The corrections and fixed bits anticipate the Taylor calculation below; taking all corrections to be zero and E = ∅ gives the basic grouped sum. Define
Ag(xg; y, z ) = ∏
> e:σt(e)= g
Φe
((λe,v (xg; y) + be,v (z)) v∈Ie
).
Distributivity gives the identity
∑
> x∈{ 0,1}N > xi=1 ( i∈E)
∏
> e
Φe
((Le,v (t; x) + be,v (z)) v∈Ie
) = ∑
> yr
∏
> g=1
∑
> xg∈{ 0,1}Sg > Cgxg=yg > xi=1 ( i∈E∩Sg)
Ag(xg; y, z ). (2.4) Indeed each full Boolean assignment has a unique measurement tuple, even when measurements are redundant. For a fixed tuple y, the measurement equations and the fixed-bit constraints each involve only one group, so their solution set is a Cartesian product of group solution sets. This proves the identity by finite distributivity in the indicated ring. Infeasible tuples contribute zero; no positivity of the summands is required. The number of tuples is at most (2 D + 1) 2τ N . For each tuple, we compute the group sums separately and then multiply them, enumerating at most
> r
∑
> g=1
2|Sg | ≤ r22N/r
6group assignments. Testing the constraints and evaluating the assigned factors use only polynomial work per group assignment: there are O(N ) factors and measurements with explicitly supplied coefficients. Suppressing polynomial factors in N and J for fixed r, Q, R, D, τ , the ring-operation count is (2 D + 1) 2τ N 22N/r . (2.5)
2.3 Recovering Taylor data without losing the separation
The grouped sum makes the deformed sum accessible at each chosen node. Its degree can be much larger than the number of nodes, so values alone do not suffice in general. We therefore compute several Taylor coefficients at each node. The challenge is to do this while keeping the groups separate.
Which Taylor coefficients suffice? Define the univariate polynomial
H(T ) = ∑
> x∈{ 0,1}N > ∏ > e
Φe(( Le,v (T ; x)) v∈Ie ). (2.6) Then H(0) = # F . A clause factor with |Ie| inputs has T -degree at most |Ie|R, and a dummy factor has degree zero. Products add these degree bounds, and summing over x cannot increase them. Hence deg H ≤ M R ≤ 3N R . Put
q =
> ⌊
3N R Q
> ⌋
, J = q + 1 . (2.7) The polynomial H(t + z) mod zJ records the first J Taylor coefficients at t: the coefficient of zj is
H(j)(t)/j !, for 0 ≤ j < J . These records, for t = 1 , . . . , Q , determine H uniquely. Indeed, if two polynomials of degree less than QJ have the same records, their difference is divisible by ( T − t)J for each node t. The nodes are distinct, so their difference is divisible by ∏Qt=1 (T − t)J . This product has degree QJ , forcing the difference to be zero. Since deg H ≤ 3N R < QJ , this applies to H.There are QJ coefficient unknowns and QJ linear conditions, so this uniqueness proves that the square interpolation matrix is invertible. Whenever a sharper degree bound is available, any positive integer J with QJ > deg H suffices by the same argument. Solving for a polynomial from these records is called Hermite interpolation ; Appendix B gives its exact implementation.
Why low Taylor order gives small supports. Fix a node t and a Boolean assignment x. We keep the base inputs Le,v (t; x) fixed and put their changes into a separate formal vector X:
Gx(X, z ) = ∏
> e
Φe
> (
(Le,v (t; x) + Le,v (t + z; X) − Le,v (t; X)) v∈Ie
> )
.
The base inputs retain the structure required by the grouped sum. Each correction Le,v (t + z; X) −
Le,v (t; X) is linear in X and divisible by z. Substituting X = x restores the full shifted inputs, so
H(t + z) = ∑
> x
Gx(x, z ). In an expanded term, choosing d formal-variable factors from the corrections supplies at least
zd. Thus a coefficient of zj cannot have total X-degree greater than j:deg X [zj ]Gx(X, z ) ≤ j. (2.8) Here [ zj ] means the coefficient of zj . Reduce Gx modulo zJ and replace every positive power of each Xi by Xi. For example, X31 X2 becomes X1X2; the two expressions agree on every Boolean 7vector. This operation is called Boolean multilinearization . It preserves Boolean evaluations and cannot increase the number of distinct variables in a monomial. The set of indices of those variables is the monomial’s support . Since we keep only powers of z below J = q + 1, (2.8) shows that the multilinearized polynomial has the unique expansion
> ∑ > E⊆[N] > |E|≤ q
aE (x, z ) ∏
> i∈E
Xi.
Here aE (x, z ) ∈ Q[z]/(zJ ). These coefficients may still depend on the fixed assignment x; only the separate formal variables X have been multilinearized. We need coefficients indexed only by supports of size at most q.
Extracting a coefficient from Boolean values. For a two-variable multilinear polynomial
p(X1, X 2) = b0 + b1X1 + b2X2 + b12 X1X2, we have
b12 = p(1 , 1) − p(1 , 0) − p(0 , 1) + p(0 , 0) .
The constant and the two linear terms cancel. The same cancellation works for any number of variables, including when the coefficients are themselves truncated polynomials in z. For any U ⊆ [N ], let 1U be its Boolean indicator vector. Boolean inclusion–exclusion extracts each coefficient:
aE (x, z ) = ∑
> U⊆E
(−1) |E|−| U |Gx(1U , z ) (mod zJ ).
To see this, Boolean evaluation agrees with the multilinearized polynomial, so Gx(1U , z ) ≡
> ∑ > A⊆U
aA(x, z ) modulo zJ . If A ⊆ E, its coefficient in the displayed alternating sum is
> ∑ > A⊆U⊆E
(−1) |E|−| U |, equal to one for A = E and zero otherwise. If A 6 ⊆ E, it never appears. This also covers E = ∅.
Returning to the count. For Boolean x, the monomial ∏
> i∈E
xi is one exactly when all bits indexed by E are one. Substitute X = x in the multilinear expansion and use the extracted coefficients. Summing over x gives
H(t + z) ≡ ∑
> E⊆[N] > |E|≤ q > ∑ > U⊆E
(−1) |E|−| U | ∑
> x∈{ 0,1}N > xi=1 ( i∈E)
Gx(1U , z ) (mod zJ ). (2.9) The inner sum has exactly the form (2.4), with fixed corrections be,v (z) = Le,v (t + z; 1U ) − Le,v (t; 1U ). The set U fixes the formal correction inputs; the set E fixes bits of the assignment being summed over. Their roles are distinct. For fixed t and U , these corrections are the same for every assignment
x, which is precisely what the grouped sum requires.
Conclusion of the proof of Proposition 2.1. The algorithm never constructs the multivariate expan-sion above. It enumerates ( E, U ) and performs truncated univariate arithmetic using (2.4). There are ∑min( q,N )
> j=0 > (Nj > )
2j pairs ( E, U ), and each contributes the cost in (2.5). This formula also covers
q = 0, with just the pair ( ∅, ∅), and q ≥ N , when all supports are enumerated. For each pair the correction polynomials can be computed from the supplied arrays using polynomially many rational operations. There are a fixed number Q of nodes, and J = O(N ) coefficients per truncated polyno-mial. Each truncated operation therefore costs polynomially many rational operations. Hermite interpolation uses a linear system of order QJ = O(N ), so it also adds only a polynomial number of rational operations. These observations give (2.3) and recover H(0) = # F .8The three nonpolynomial factors have separate origins: the choices of ( E, U ), the measurement tuples, and the assignments within one group. In Section 4 we make all three exponential rates small at the same time.
2.4 A complete four-variable example
We now follow the same formula through the whole recovery procedure:
F = ( x1 ∨ x3) ∧ (x2 ∨ ¬ x4).
Its clause indicators are Φ1(X1, X 3) = X1 + (1 − X1)X3, Φ2(X2, X 4) = 1 − (1 − X2)X4.
Each clause has three satisfying assignments on its own two variables, so the answer is 3 · 3 = 9. The example illustrates recovery, without claiming an asymptotic saving. Use groups S1 = {1, 2},
S2 = {3, 4}, the single measurement y = x3 + x4 on S2, and forms
L1(T ; X) = X1, L2(T ; X) = X2,L3(T ; X) = X3 + T X 4, L4(T ; X) = X4 + T X 3.
The incidence labels are suppressed because each variable occurs once. At T = 0 these forms give the original variables. At t = 1 both clauses are assigned to S1, because their inputs depend only on x1, x 2, y . For fixed y, put
A = x1 + (1 − x1)y, B = 1 − (1 − x2)y.
Here y replaces the measurement x3 + x4; when we later fix a full assignment x, it always has that assignment’s measurement value. The group-1 sum is ∑
> x1,x 2
AB = (1 + y)(2 − y). Group 2 has no assigned factors, so its sum just counts assignments with x3 + x4 = y. Only y = 0 , 1, 2 have feasible assignments:
y 0 1 2group-1 sum 2 2 0group-2 sum 1 2 1product 2 4 0
H(1) = 2 + 4 + 0 = 6 .
For instance, at y = 2 the factor B takes values −1 and 1; these weighted summands can cancel. Each deformed clause factor is affine in T , so their product and H(T ) have degree at most two. Thus a single node t = 1 and the three Taylor coefficients modulo z3 suffice here; we use this exact degree bound instead of the general upper bound 3 N R . Consequently only supports of size at most two are needed in this example. Keep the assignment x in the base inputs and the formal vector X
in the corrections. The shifted product is
Gx(X, z ) = (A + z(1 − x1)X4
> )(
B − z(1 − x2)X3
> )
= AB − zA (1 − x2)X3 + z(1 − x1)BX 4 − z2(1 − x1)(1 − x2)X3X4.
It is already multilinear in X. For example, inclusion–exclusion recovers its last coefficient from four fixed correction inputs:
a{3,4}(x, z ) = Gx(1{3,4}, z ) − Gx(1{3}, z ) − Gx(1{4}, z ) + Gx(0 , z ) = −z2(1 − x1)(1 − x2).
9Substituting X = x requires this coefficient to be summed only over assignments with x3 = x4 = 1. For those assignments y = 2, and its sum over x1, x 2 is −z2. The other supports are handled in the same way. Their contributions, split by measurement value, are
E y = 0 y = 1 y = 2 ∑
> x:xi=1 ( i∈E)
aE (x, z )
∅ 2 4 0 6
{3} 0 −2z −3z −5z
{4} 0 z 0 z
{3, 4} 0 0 −z2 −z2
For example, when E = {3}, exactly one group-2 assignment is feasible at each of y = 1 , 2, and the group-1 sum is −z(1 + y). All other supports have zero coefficient. Adding the four rows gives
H(1 + z) = 6 − 4z − z2. Because deg H ≤ 2, no higher terms have been discarded: this is an exact polynomial identity. We may therefore substitute z = −1 to recover H(0) = 6 + 4 − 1 = 9, the satisfying-assignment count.
3 Constructing the deformation
This section supplies the structure used above. The construction has a constant-size algebraic part, depending on the chosen parameters, and a polynomial-time placement of the actual variables.
Proposition 3.1 (Construction of a suitable deformation) . Let r ≥ 2, R ≥ 32 , and Q ≥ 6R be integers, let τ > 0 be rational, and put D = r2Q. Consider the normalized factor system of Section 2, with nonempty scopes satisfying (2.1) . Suppose
12 D2 ≤ M, 2Qr 2 ≤ N,
and
2e−R2/(8 Q) ≤ τ
3r . (3.1)
Then one can deterministically construct forms Le,v homogeneous and linear in X, with rational polynomial coefficients satisfying Le,v (0; X) = Xv and deg T Le,v ≤ R − 1, together with groups, factor assignments, integer measurements, and rational node representations satisfying requirements (i)–(iv) of Section 2. For fixed r, Q, R, τ , the construction uses polynomially many bit operations in
N + 1 .
The proof has three stages. First we construct an operator whose error can be described by a few measurements. Next we turn its limited pattern of disagreements into low-degree forms. Finally we place the formula’s incidences in balanced copies of the auxiliary array and restrict every measurement to individual groups.
3.1 An auxiliary array and a low-rank correction
We first build replacement forms on an auxiliary array, without reference to the input formula. At each node, every array position has two labels: the group containing its variable and the group assigned to its form. Swapping the labels gives perfect group matching. Our construction modifies this swap so that it also preserves most linear directions; the few remaining directions will be supplied by measurements. 10 Let
B = ([ r] × [r]) Q, D = |B| = r2Q.
Write u ∈ B as (( au(t), d u(t))) Qt=1 . At node t, a coordinate w belongs to group aw(t), whereas the form associated with u is assigned to group du(t). Let ζ = ( ζw)w∈B be formal coordinates. For t ∈ [Q] let st(u) be the label obtained from u by swapping the two entries in pair t. Define the permutation matrix Π t by (Π tζ)u = ζst(u). These symmetric matrices commute and satisfy Π2
> t
= I. Define
V =
> Q∏ > t=1
Πt, W = 12
> Q∑ > t=1
(I − Πt).
The full swap V has the desired group matching: a nonzero entry V [u, w ] requires aw(t) = du(t) at every node. However, V ζ need not equal ζ, so it cannot by itself recover the original variables at
T = 0. We will use A = V f (W ) for a low-degree polynomial f . Two properties will make this useful:
I − A can be recovered from a few measurements, and A[u, w ] 6 = 0 allows disagreement at only a few nodes. The first property comes from eigenvalues; the second will come from the degree of f .Let eab denote the coordinate unit vector indexed by ( a, b ) ∈ [r]2. For a single pair, an orthogonal eigenbasis for the swap consists of
eaa (a ∈ [r]) , eab + eba (a < b ), eab − eba (a < b ).
The first two types give r(r + 1) /2 vectors of eigenvalue +1; the third gives r(r − 1) /2 vectors of eigenvalue −1. Choose a one-pair basis vector vt independently for each node t. The corresponding product vector has coordinates
ψu =
> Q∏ > t=1
vt(au(t), d u(t)) .
Inner products of these vectors factor into the one-pair inner products, so the D choices give an orthogonal basis Ψ of QB. This is the tensor-product basis; its entries all lie in {0, 1, −1}. We use the usual coordinate inner product throughout. If ψ has j(ψ) negative factors, then
W ψ = j(ψ)ψ, V ψ = ( −1) j(ψ)ψ.
Indeed each summand ( I − Πt)/2 contributes one on a negative factor and zero on a positive factor, while V multiplies all the signs. For a uniformly chosen basis vector, j(ψ) has distribution Bin( Q, p )with p = ( r − 1) /(2 r). This probability statement just counts basis vectors: choose one of the r2
one-pair basis vectors independently at each of the Q positions. The fraction with a given number of negative factors is the corresponding binomial probability. To make A act as the identity on a vector with j negative factors, we need f (j) = ( −1) j .Interpolating at every j ∈ { 0, . . . , Q } would require too much degree. Instead, we interpolate only at R consecutive integers near the mean. A binomial tail bound will tell us when this interval contains most basis vectors. Choosing R, Q accordingly will keep the degree below R while leaving few exceptional vectors. Assume R ≥ 32 and 6 R ≤ Q. Put μ = Qp , and let
b =
> ⌊
μ − R − 12
> ⌋
, I0 = {b, b + 1 , . . . , b + R − 1}.
Since r ≥ 2, we have Q/ 4 ≤ μ ≤ Q/ 2. The inequalities 6 R ≤ Q and R ≥ 32 imply b ≥ 0 and
b + R − 1 ≤ Q: indeed, μ − (R − 1) /2 ≥ R + 1 /2 and μ + ( R − 1) /2 ≤ Q/ 2 + ( R − 1) /2 < Q .Moreover,
b ≤ μ − (R − 1) /2 < μ − R/ 4, b + R − 1 > μ + ( R − 3) /2 > μ + R/ 4.
11 Thus I0 contains every integer at distance less than R/ 4 from μ. Let f ∈ Q[Y ] be the unique polynomial of degree at most R − 1 with
f (j) = ( −1) j (j ∈ I0).
For example, its coefficients are obtained explicitly from
f (Y ) = ∑
> j∈I0
(−1) j ∏
> h∈I0 > h6=j
Y − hj − h .
The matrix A = V f (W ) therefore fixes every ψ with j(ψ) ∈ I0.Let Ψ bad = {ψ ∈ Ψ : j(ψ) /∈ I0}, let c = |Ψbad |, and form a matrix C whose rows are ψT for
ψ ∈ Ψbad .
Lemma 3.2 (Exceptional spectral directions) . The exceptional set satisfies
c ≤ 2D exp( −R2/(8 Q)) . (3.2)
The correction (I − A)ζ is determined by the c measurements Cζ , with the explicit coefficients in
(3.3) below. Each measurement has integer coefficients and coefficient `1 norm at most D.Proof. The exceptional indices lie outside I0, hence at distance at least R/ 4 from the mean. Their fraction is bounded by the binomial estimate Pr( |Y − EY | ≥ h) ≤ 2e−2h2/Q with h = R/ 4; its elementary derivation is in Appendix A. For an orthogonal basis, the expansion of a vector is
ζ = ∑
> ψ∈Ψ
〈ψ, ζ 〉〈ψ, ψ 〉 ψ.
The operator I − A vanishes on all the nonexceptional basis vectors. Applying it to this expansion therefore leaves only the c exceptional terms. In particular, rank( I − A) ≤ c, and the correction can be specified by the c scalar measurements 〈ψ, ζ 〉 with ψ ∈ Ψbad . Coordinate by coordinate, the resulting identity is (( I − A)ζ)u = ∑
> ψ∈Ψbad
βu,ψ 〈ψ, ζ 〉, βu,ψ = (1 − (−1) j(ψ)f (j(ψ))) ψu
〈ψ, ψ 〉 . (3.3) The denominator 〈ψ, ψ 〉 is a positive integer; in fact it is a power of two, since the one-pair basis vectors have squared norm one or two. Thus every βu,ψ is an explicitly computable rational number. No row-space computation is required. Each measurement 〈ψ, ζ 〉 has integer coefficients and coefficient `1 norm at most D, since ψ has D entries in {0, 1, −1}.
3.2 Turn sparse disagreement into low degree
We now use the support of A to build forms that recover the original variables at zero and become local at each node. Each disagreement will cost one linear factor in T , so a small number of disagreements gives a small degree. For u, w ∈ B let Eu,w = {t ∈ [Q] : aw(t) 6 = du(t)}.
Lemma 3.3 (Sparse disagreement) . Every nonzero entry of A disagrees with its assigned group at fewer than R nodes:
A[u, w ] 6 = 0 =⇒ |Eu,w | ≤ R − 1. (3.4) 12 Proof. Since f has degree at most R − 1, expansion of V f (W ) writes A as a rational linear combination of matrices ∏
> t / ∈S
Πt, |S| ≤ R − 1.
Indeed a degree-j term in W is a sum of products of at most j swaps, with repeated swaps canceling. Multiplication by V leaves every pair outside some such S swapped. A nonzero entry of this permutation obeys aw(t) = du(t) for t / ∈ S. If A[u, w ] 6 = 0, at least one permutation in this expansion has a nonzero ( u, w ) entry, so its set S contains every disagreement. This proves (3.4). The basic cancellation is visible in (Π 1Π2Π3)Π 2 = Π 1Π3: only the second of these three nodes loses its swap. Applying this cancellation to V after multiplying it by at most j swaps can lose group matching at at most j nodes. For each nonzero entry define
φu,w (T ) = ∏
> t∈Eu,w
(1 − T /t ),
so that φu,w (0) = 1 and φu,w (t) = 0 at every disagreement node. For instance, disagreement at nodes 2 and 5 gives (1 − T / 2)(1 − T / 5), a degree-two polynomial that preserves the coefficient at zero and removes it at those two nodes. Define an auxiliary form
Pu(T ; ζ) = ∑
> ψ∈Ψbad
βu,ψ 〈ψ, ζ 〉 + ∑
> w∈B > A[u,w ]6=0
A[u, w ]φu,w (T )ζw. (3.5) At T = 0 the two sums are the uth coordinates of ( I − A)ζ and Aζ , so Pu(0; ζ) = ζu. Its degree is at most R − 1. At a node t, the second sum uses only coordinates w with aw(t) = du(t): all other coefficients contain the vanishing factor 1 − T /t . Thus Pu(t; ζ) can be evaluated from the variables in its assigned group and the c measurements Cζ .
3.3 Place the formula in balanced copies of the array
It remains to put the actual variable occurrences into the auxiliary array. At a node t, the variable’s schedule will specify its group, and the factor’s schedule will specify which group is responsible for that factor. The two schedules together give exactly the pair labels used above. Choose a schedule av ∈ [r]Q for each variable and a schedule de ∈ [r]Q for each factor. Give incidence ( e, v ) the label u(e, v ) = ( av, d e) ∈ B . For u ∈ B let cu be the number of incidences with this label, and set nt,g = |{ v : av(t) = g}| . All incidences of a variable share its schedule av, and all inputs of a factor share its schedule de. These two consistencies will preserve the original variables and the common assigned group of each factor. We need two kinds of balance. No variable group should be too large, because we enumerate its assignments. No array label should receive too many incidences, because each extra copy of the array needs another set of exceptional measurements. The next lemma achieves both at once.
Lemma 3.4. If 12 D2 ≤ M and 2Qr 2 ≤ N , the schedules can be constructed deterministically in polynomial time, for fixed r, Q , so that
cu ≤ 2M/D (u ∈ B ), nt,g ≤ 2N/r (t ∈ [Q], g ∈ [r]) .
13 Proof. Initially let all schedules be independent and uniform. Define Φ = ∑
> u
(cu − M/D )2, Ξ =
> Q∑ > t=1 > r∑ > g=1
(nt,g − N/r )2.
These are sums of squared deviations from the two desired averages. We first bound their expectations and then fix every schedule while preserving a bound on their normalized sum. Writing A = {(e, v ) :
v ∈ Ie}, expansion gives Φ = ∑
> (e,v ),(e′,v ′)∈A
1{(av, d e) = ( av′ , d e′ )} − M 2/D.
If two incidences share neither a variable nor a factor, their labels are independent and their equality probability is 1 /D . For a fixed incidence, at most three incidences share its variable and at most three share its factor. Thus at most six incidences, including itself, can violate this independence condition. Bound the equality probabilities of these pairs by one; the other pairs cancel the corresponding terms in M 2/D . This gives EΦ ≤ 6M .For fixed t, g , the count nt,g is a sum of N independent indicators, each with probability 1 /r . It has mean N/r and variance N (1 /r )(1 − 1/r ). Summing this variance over all Qr choices of t, g gives
EΞ = QN (1 − 1/r ) ≤ QN . For the exact computation below, the analogous collision expansion is Ξ =
> Q∑ > t=1 > ∑ > v,v ′∈[N]
1{av(t) = av′ (t)} − QN 2/r.
Both collision sums use ordered pairs, including equal pairs. Fix the schedules in a fixed order, choosing the lexicographically first value that does not increase the conditional expectation of Φ /(6 M ) + Ξ /(QN ). Such a value exists because the current expectation is the average over all values of the next schedule. The final sum is at most two. Both potentials are nonnegative, so Φ ≤ 12 M and Ξ ≤ 2QN . Each individual squared deviation is bounded by its whole potential; taking square roots and using the lemma’s two size assumptions gives
cu ≤ M/D + √12 M ≤ 2M/D, nt,g ≤ N/r + √2QN ≤ 2N/r.
Thus the random choice is used only to prove that a good next value exists; the schedule is actually constructed by exact comparisons of conditional expectations. This is an effective polynomial-time construction. There are K = rQ possible values for each schedule, a constant here. Each indicator in the collision expansion of Φ depends on at most four distinct schedules, and each in that of Ξ on at most two. Conditioned on the schedules already fixed, the remaining schedules are still independent and uniform. For each indicator, enumerate the choices of its distinct unassigned schedules: at most
K4 choices suffice to compute its exact expectation. Summing M 2 + QN 2 terms, trying all K values, and repeating for N + |F| ≤ N + M = O(N ) schedules takes polynomially many operations on rationals with Or,Q (log( N + 1)) bits. To see the bit bound, every unnormalized indicator expectation has denominator dividing the fixed integer K4. After adding the constant terms and normalizing the potentials, a common denominator divides 6 M QN K 4. Using this common denominator keeps all numerators and denominators to Or,Q (log( N + 1)) bits, since M ≤ 3N .Think of h = max u cu copies of the array as h layers, with one slot per label in each layer. There are enough layers to give every incidence with the same label a distinct slot. Take these h copies of
B. Place each incidence ( e, v ) at coordinate u(e, v ) in a different copy from the other incidences 14 with that label. Put the original variable Xv at that position and zero at unused positions. Write
ζ(j)(X) for copy j. Let Oj ⊆ B be its occupied coordinates, and let νj (w) be the variable index stored at w ∈ Oj , so ζ(j)
> w
(X) = Xνj (w). There are at most hD ≤ 2M ≤ 6N positions in total. These arrays introduce no new Boolean variables : repeated copies of a symbol Xv are evaluated using the same bit. If incidence ( e, v ) was placed in copy j(e, v ), set
Le,v (T ; X) = Pu(e,v )(T ; ζ(j(e,v )) (X)) .
It has degree at most R − 1 and equals Xv at zero. Figure 1 follows one incidence through this substitution. The slot labels organize appearances of variables; the vector X still contains exactly the original N variables. incidence ( e, v ) label and layer
−−−−−−−−−−→ u = ( av, d e) in layer j(e, v )
ζ(j(e,v ))
> u
(X) = Xv =⇒ Le,v (T ; X) = Pu
(T ; ζ(j(e,v )) (X)).
Another occupied slot What its stored symbol means
w = ( av′ , d e′ ) in the same layer
j = j(e, v )Its entry is ζ(j)
> w
(X) = Xv′ . It can contribute to the local part of
Pu(t; ζ(j)(X)) only if av′ (t) = de(t).
u′ = ( av , d e′′ ) in a layer k Another occurrence of v stores ζ(k)
> u′
(X) = Xv . Both entries use the same bit when X = x.
Figure 1: From an occurrence to its replacement form. Array positions store original symbols. Locality is determined by the first schedule of the stored variable and the second schedule of the receiving factor. At node t use the actual groups St,g = {v : av(t) = g} and assign factor e to de(t). Every coordinate in the local part of its auxiliary form contains either zero or a variable in that assigned group: an occupied coordinate w contains a variable Xv′ with first schedule av′ = aw, and locality at node t requires aw(t) = de(t). There are hc auxiliary measurements 〈ψ, ζ (j)(X)〉, indexed by j ∈ [h] and ψ ∈ Ψbad . At each fixed node t, a measurement may involve several actual groups, so split it into its r restrictions:
mt,j,ψ,g (X) = ∑
> w∈Oj > aw(t)= g
ψwXνj (w) (g ∈ [r]) .
Each summand uses a variable in St,g , because an occupied coordinate satisfies aw = aνj (w). Moreover,
〈ψ, ζ (j)(X)〉 = ∑rg=1 mt,j,ψ,g (X). This splitting is essential: fixing a sum involving two groups would otherwise leave those groups coupled. For example, if x1 and x2 are in different groups, fixing
x1 + x2 = 1 leaves the two possibilities (0 , 1) and (1 , 0); the choices are not independent. Fixing each group’s contribution separately restores the product structure used in (2.4). Each restricted measurement still has integer coefficients and coefficient `1 norm at most D. Indeed, repeated occurrences of the same original variable add their coefficients, and the triangle inequality shows that this aggregation cannot increase the sum of absolute values. The hypothesis (3.1), together with (3.2), gives c ≤ Dτ / (3 r). At each node, the number of restricted measurements, including any zero or redundant ones, therefore satisfies
rhc ≤ rh Dτ
3r = hDτ
3 ≤ 2τ N.
15 For an incidence ( e, v ), abbreviate u = u(e, v ) and j = j(e, v ). Its explicit node representation is
Le,v (t; X) = ∑
> ψ∈Ψbad
βu,ψ r∑
> g=1
mt,j,ψ,g (X)+ ∑
> w∈Oj, A [u,w ]6=0 > aw(t)= de(t)
A[u, w ]φu,w (t)Xνj (w).
The first sum uses the supplied measurements; the second uses only variables in the factor’s assigned group. Every restriction of a given measurement has the same coefficient βu,ψ . Together with the group-size bound, the measurement count, and the coefficient-norm bound, this verifies all four requirements in Section 2. All auxiliary arrays are fixed rational data generated by the displayed formulas. Lemma 3.4 supplies the schedules in polynomial bit time. For each original variable, substitution into an auxiliary form sums at most D fixed coefficient polynomials. Their coefficient lengths therefore remain bounded in terms of the parameters, as do the node coefficients; measurement coefficients are integers of absolute value at most D. There are O(N ) forms and O(N ) measurements per node, each using at most N variables. Their dense coefficient arrays and node representations have polynomial size and can be constructed in polynomial bit time, including the O(log( N + 1))-bit variable indices. This proves Proposition 3.1.
4 Fixed parameters and the complete running time
We work with the normalized factor system of Section 2. Its empty-clause and N = 0 cases have already been settled, so assume N ≥ 1. The parameters must do two jobs at once. The Taylor cutoff satisfies q/N ≤ 3R/Q , so R/Q should be small. The exceptional fraction is at most 2 e−R2/(8 Q), so
R2/Q should be large. Taking Q = s4 and R = s3 achieves both: the two ratios are 1 /s and s2. We also increase the number of groups and decrease the measurement budget as s grows. Fix an integer s ≥ 64, and choose
r = s, Q = s4, R = s3, τ = s−6, D = r2Q = s2s4
. (4.1) These are constants throughout the algorithm on N variables. The group-enumeration rate is 2/r = 2 /s , and the measurement-enumeration rate will be 2 τ log 2(2 D + 1) = O(log s/s 2). We have
R ≥ 32, 6 R ≤ Q, and 2e−R2/(8 Q) = 2 e−s2/8 ≤ 13s7 = τ
3r .
Indeed, one term of the exponential series gives
es2/8 ≥ (s2/8) 7
7! ≥ 6s7,
where the last inequality follows from s7 ≥ 64 7 > 6 · 87 · 7!. Taking reciprocals proves the claim for every s ≥ 64. The construction is therefore valid whenever
N ≥ N0(s) := max {12 D2, 2Qr 2},
because M ≥ N . For N < N 0(s) we count directly by exhaustive search. Its cost is at most 2N0(s) poly( N + m + 1), so this fallback can be absorbed into a multiplicative constant depending on s.16 For N ≥ N0(s), (2.7) gives q = b3N/s c. Thus the sets E that occur in Taylor recovery contain at most a 3 /s fraction of the variables. Binary entropy bounds the number of such sets. Write
H2(p) = −p log 2 p − (1 − p) log 2(1 − p) (0 < p < 1) , H2(0) = H2(1) = 0 .
The endpoint values are the continuous extensions. For 0 < j < N , put pj = j/N . The jth term in the binomial expansion of 1 = ( pj + (1 − pj )) N is at most one, so
(Nj
)
pjj (1 − pj )N −j ≤ 1,
(Nj
)
≤ 2N H 2(j/N ).
The endpoint cases j = 0 , N are equalities. Since H′
> 2
(p) = log 2((1 − p)/p ) ≥ 0 for 0 < p ≤ 1/2, it follows that bpN c
∑
> j=0
(Nj
)
≤ (N + 1)2 N H 2(p) (0 < p ≤ 1/2) .
Apply this with p = 3 /s < 1/2. Since q = bpN c ≤ N and 2 j ≤ 2pN for j ≤ q, we obtain
> q
∑
> j=0
(Nj
)
2j ≤ (N + 1) 2 N (H2(3 /s )+3 /s ).
Table 1 collects the three costs in Proposition 2.1. These costs count rational arithmetic operations. A rate a means a contribution of at most poly s(N + 1)2 aN to that count. The first rate is controlled by R/Q , the second by τ log 2(2 D + 1), and the third by 1 /r .
What is enumerated Purpose and controlling quantity Rate for (4.1) Supports E and subsets U ⊆ E Recover Taylor coefficients; q/N ≤
3R/Q = 3 /s H2(3 /s ) + 3 /s
Measurement tuples y Separate groups; at most 2 τ N mea-surements, each in [ −D, D ]2τ log 2(2 D + 1) = O(log s/s 2)Assignments in one group Evaluate each group sum; |St,g | ≤
2N/r
2/r = 2 /s
Table 1: The three exponential costs. Their rates add because the enumerations are nested. The number of nodes and all remaining work contribute only polynomial factors for fixed s.Adding the three rates in (2.3) gives the explicit choice promised in Proposition 1.4:
as = H2(3 /s ) + 5
s + 2 s−6 log 2
(
2s2s4
+ 1
)
. (4.2) This number is positive, since its summands are nonnegative and 5 /s > 0. The elementary inequality
−(1 − p) ln(1 − p) ≤ p gives H2(p) ≤ p log 2(e/p ) for 0 < p < 1. Also, 2 D + 1 ≤ 4D yields the explicit estimate 2s−6 log 2(2 s2s4
+ 1) ≤ 4
s6 + 4 log 2 ss2 = O(log s/s 2).
Applying the entropy bound with p = 3 /s now gives as = O(log s/s ) → 0. It remains to justify that exact arithmetic adds only a polynomial factor. 17 4.1 Exact implementation and bit complexity
So far we have counted arithmetic operations. To obtain a bit-operation bound, we must also control the size of the integers and rationals in those operations. There are two stages: evaluating the grouped sums and then solving the interpolation system. The first uses numbers with Os(N ) bits; the second may use larger numbers, but still only polynomially many bits.
Lemma 4.1 (Exact arithmetic) . For the construction of Section 3 with fixed s, the grouped sums and Taylor coefficients can be computed using rationals whose numerators and denominators have Os(N )
bits. The Hermite system has Os(N ) rows and can be solved using integers with Os(N 2 +N log( N +1))
bits. Consequently exact arithmetic adds only a polynomial factor to the operation count.
Appendix B proves the lemma, including bounds for intermediate values before cancellations. Every input coefficient has a fixed common denominator depending only on s. Products use at most 3N inputs, and sums contain at most 2 Os(N ) terms. A common denominator raised to the power 3N therefore keeps coefficient lengths linear in N . For interpolation, determinant bounds control the larger integers created by elimination and exact back substitution.
Completion of the proof of Proposition 1.4. Preprocessing takes polynomial bit time in N + m + 1 and handles the direct-return cases of Section 2. For N ≥ N0(s), construct the data and apply Propositions 3.1 and 2.1 with (4.1). The estimates above bound the arithmetic-operation count by poly s(N + m + 1)2 asN , and Lemma 4.1 gives the same bound in bit operations after enlarging the polynomial. The polynomial construction cost is absorbed as well. For N < N 0(s), the exhaustive-search bound is absorbed into the constant of this polynomial, since s is fixed and 2 asN ≥ 1. Thus the claimed bound covers every input size.
Execution order. For a fixed s, perform the preprocessing of Section 2, returning immediately in its terminal cases, and use exhaustive search below N0(s). Otherwise generate the fixed auxiliary data, construct the schedules by conditional expectations, and place the incidences in copies. Write the replacement forms, restricted measurements, and node representations. For every node t,enumerate the pairs ( E, U ) in (2.9). For each pair enumerate the measurement tuples and the assignments within each group, evaluating (2.4) modulo zJ . Accumulate the resulting Taylor coefficients with the signs ( −1) |E|−| U | from (2.9), and solve the Hermite system to obtain H(0). Every enumeration and arithmetic step has been accounted for in (2.3) and the bit analysis above.
What was simplified. The proof retains the spectral replacement and Taylor recovery ideas of [1, Sections 2–4], but uses only width-three, three-occurrence formulas. The single fixed integer s
replaces the input-dependent optimization of several logarithmic parameters. The explicit orthogonal expansion (3.3) replaces row-space solving. Because the auxiliary data have fixed size, their coefficient bounds may depend arbitrarily on s; Appendix B tracks the remaining growth with N . Ordinary decision sparsification suffices. Exact counting remains an internal device because interpolation uses rational addition and subtraction, but the final conclusion is only the decision theorem. No counting-preserving sparsification, sparse-polynomial-system solver, or tensor-contraction theorem is used. 18 A The binomial tail estimate
We prove the estimate used in (3.2). Let Q ≥ 1 be an integer, let B1, . . . , B Q be independent Bernoulli variables with success probability p ∈ [0 , 1], and put Y = ∑Qi=1 Bi and μ = Qp . We will show that Pr( |Y − μ| ≥ h) ≤ 2e−2h2/Q (h > 0) .
For one Bernoulli variable B with success probability p, define
g(λ) = ln Eeλ(B−p) = ln(1 − p + pe λ) − pλ (λ ∈ R).
We have g(0) = g′(0) = 0, and direct differentiation gives
g′′ (λ) = p(1 − p)eλ
(1 − p + pe λ)2 ≤ 14 .
The last inequality is 4 ab ≤ (a + b)2 with a = 1 − p and b = pe λ. The denominator is positive even when p = 0 or p = 1; in those cases g is identically zero. Taylor’s formula with integral remainder gives
g(λ) = λ2
∫ 10
(1 − u)g′′ (uλ ) du ≤ λ2
8 .
This formula applies to both signs of λ. Independence now yields
Eeλ(Y −μ) =
> Q
∏
> i=1
Eeλ(Bi−p) ≤ eQλ 2/8 (λ ∈ R).
For h > 0 and λ > 0, Markov’s inequality now yields Pr( Y − μ ≥ h) ≤ e−λh Eeλ(Y −μ) ≤ exp( Qλ 2/8 − λh ).
Taking λ = 4 h/Q makes the right side e−2h2/Q . Using the exponential-moment bound at −λ gives the same estimate for Pr( μ − Y ≥ h). Adding the two tail bounds proves the claim. For its application in Lemma 3.2, take p = ( r − 1) /(2 r). As shown there, the number j(ψ) of negative factors in a uniformly chosen basis vector has the distribution of Y , and every integer at distance less than R/ 4 from μ belongs to I0. Hence
cD = Pr( Y /∈ I0) ≤ Pr( |Y − μ| ≥ R/ 4) ≤ 2e−R2/(8 Q).
Multiplying by D proves (3.2). 19 B Exact rational arithmetic
This appendix proves Lemma 4.1. Throughout, s is fixed and N ≥ 1.
Fixed auxiliary data. The index set B and the rational coefficient arrays in Ψ , f, A, β, φ, P
are finite and depend only on s. They can be generated by the explicit formulas above. Their construction cost is a constant depending on s. There is an integer Bs ≥ 1 divisible by all their coefficient denominators, including coefficients after shifts T = t + z for t ∈ [Q]. An actual form is obtained by replacing at most D auxiliary coordinates by original variables or zero. This substitution only merges or deletes monomials, so it cannot increase the coefficient `1
norm and preserves the common denominator Bs. Each form uses the measurements of only its own array copy. After the measurements have been split, it uses at most rc measurement values, with the fixed coefficients (3.3). All enumerated values lie in [ −D, D ], whether or not the tuple is feasible. For the corrections b