WorksComputer Science
Circuit Lower Bounds for Extended Gate Bases from Subexponential Counting
Abstract
We study circuit lower bounds for extended gate bases using exact CNF counting and an extension-ring form of the contraction theorem of OpenAI. The deterministic counting theorem of Claude (Anthropic) yields an language requiring gates over unbounded AND/OR with binary XOR, infinitely often. Using that contraction theorem, a bounded binary base with a linear budget of arbitrary XOR and symmetric gates requires gates infinitely often. These results extend the binary-gate lower bound of OpenAI. Signed long-clause selectors reduce the first counting problem to the difference of two ordinary 3-CNF counts. Affine characters and unit-separated interpolation give the second counting interface, with logarithmic cost per symmetric-gate arity. A quantitative local-reduction transfer accounts for auxiliary variables, branch counts, and integer recovery.
Introduction
Problem and motivation
Faster circuit counting can yield lower bounds for explicit languages through the algorithm-to-lower-bound paradigm. Extending the gate basis changes the cost of verifying a guessed witness circuit. Long defining clauses and high-arity symmetric relations must be represented without exhausting the quantitative saving of the counter.
Main results
Let consist of arbitrary-fan-in AND/OR, binary XOR, and unary NOT/COPY gates, with signed edges and constants allowed. Size counts noninput gates. The first result uses the exact CNF counting theorem of Claude (Anthropic), stated as Theorem 3.
Theorem 1. There are a language and such that, at infinitely many input lengths , every circuit computing has more than
noninput gates. No depth restriction is imposed.
| Source / task | Bound and scope |
| OpenAI [5 Corollary 1.4 and Appendix C.1] | Binary gates: infinitely often in . |
| Theorem 1 | Unbounded AND/OR and binary XOR: infinitely often. |
| Theorem 2 | Binary base with : infinitely often, using the extension-ring form of D.1. |
Table 1. Gate models and quantitative lower bounds. The gain is the extended basis supported by each counting interface.
For the second model, ordinary binary gates are supplemented by arbitrary-fan-in XOR and other symmetric gates. Define by charging one per designated XOR gate and per other designated symmetric gate of arity . Binary gates count toward size and have zero exceptional budget. Gate lists contain no duplicate signed wires; depth and fanout are unrestricted.
Theorem 2. Using the contraction theorem of OpenAI as extended in Theorem 4, there are constants and a language such that, for infinitely many input lengths , every circuit for with has at least gates. Depth and fanout are unrestricted. Consequently, for a sufficiently small fixed , the same lower bound allows simultaneously arbitrary-fan-in XOR gates and other arbitrary symmetric gates, with all remaining gates bounded binary.
Technical overview
The proof follows the algorithm-to-lower-bound paradigm: a sufficiently fast exact counter can verify a succinctly represented satisfying assignment faster than a nondeterministic time hierarchy permits. Extending the circuit basis changes the verifier’s gate relations. The central task is to count the resulting assignments while charging every auxiliary variable, algebraic branch, and recovery operation. The transfer theorem separates this task from the hierarchy argument, and the two counting interfaces instantiate it with different costs.
The transfer starts with a hard unary language. A local reduction represents a computation on unary input by a 3-CNF whose clauses can be decoded using binary gates. The bits of its first satisfying assignment define a language in . If that language had small circuits at every sufficiently large relevant length, a verifier could guess one such circuit, make three copies, and count the clause addresses it violates. A zero count certifies satisfaction. The general transfer theorem takes the full counting time as its input, including an additive branch budget in the exponent, and chooses constants so that the resulting verifier contradicts the hierarchy.
The first interface preserves the variable budget. An arbitrary-fan-in AND or OR gate has one long defining clause and many short implication clauses. Replacing its long clause by a chain of bounded-width clauses would charge variables to its fan-in. A signed selector instead represents the long-clause indicator as a sum of weights: the selector value one has weight and forces every literal false. Summing over that selector gives one when the clause is true and zero otherwise. Each long clause thus contributes one selector. Binary XOR gates already have constant-size 3-CNF definitions.
Two ordinary counts recover the signed count. A unique-extension XOR chain records the parity of all negative-weight selectors. Its even and odd cases give two ordinary 3-CNFs, and their model-count difference equals the required circuit count. For inputs and gates, each formula has at most variables; its clauses are polynomial in the full circuit description. The variable-dependent term of Anthropic’s counting theorem [2] therefore applies at arbitrary clause density. This gives the counter used for unbounded AND/OR with binary XOR, and the transfer yields an lower bound.
The second interface pays a logarithmic cost per symmetric gate. An ordinary bounded-fan-in encoding of a high-arity symmetric gate computes its input Hamming weight and then evaluates a truth table. That representation charges auxiliary gates to the arity. The intended budget instead charges for a gate of arity . Unit-separated interpolation achieves this budget by expressing its truth table as a sum of products of unary weights. Selecting one summand per gate gives branches. Each branch has the original bounded-arity constraints and accumulated unary weights, so its network size is independent of those symmetric input lists except through polynomial-time weight accumulation.
Affine characters handle arbitrary-fan-in XOR. An affine subsystem of rank has an exact character expansion with terms. Each term contributes unary signs, and the complete sum is times the desired count. Evaluating modulo retains the whole numerator when there are Boolean variables. The algorithm takes the canonical integer residue and divides by . This treats long XOR relations without adding a chain proportional to their input occurrences. The total branch exponent is .
Extension-ring arithmetic supports the weighted branches. The interpolation coefficients live in a finite unramified extension of , where residue-distinct points have unit differences. The contraction theorem used here follows the proof of OpenAI’s Theorem D.1 [5] over that coefficient ring. If the input residue field is too small for its interpolation grid, a tower extension provides enough points with logarithmic total degree. Appendix A checks the ring arithmetic, coordinatewise precision, recursion identity, and recovery of the original coordinates. This supplies a deterministic polynomial-space counter with time up to polynomial factors.
The lower bounds are the final compositions. The first counter enters the transfer with the slowly growing denominator . The second enters with and a branch budget linear in the witness input length. Three witness copies multiply that budget by at most three. The same transfer theorem then gives the two stated lower bounds, with their gate models and budgets carried explicitly. Figure 1 displays this common argument and the distinct counting inputs.

Figure 1. Two counting interfaces feed the same quantitative transfer theorem.
Related work
Williams [7] develops the algorithm-to-lower-bound connection; Jahanjou–Miles–Viola [3] give the local reductions used in its quantitative form. The bounded-binary transfer with the present counting exponents appears in [5 Appendix C.1]. The circuit results here extend its gate interfaces. Signed large-clause reductions are developed in [4, 1]. Tamaki [6] gives counting algorithms and lower bounds for depth-two circuits with symmetric and threshold gates; our symmetric-gate statement allows arbitrary depth under the stated exceptional-gate budget. Claude (Anthropic) [2 Theorem 1] proves the counting bound used in our first interface. Its clause-dependent term also gives time for fixed-width CNFs with clauses. The corresponding exact-counting statement is formalized in Lean 4 [2 Appendix E].
Organization
Section 2 states the external counting theorem and the extension-ring contraction theorem. Section 3 proves the common quantitative transfer. Sections 4 and 5 construct the two counters. Section 6 composes them with the transfer to prove the main results. Appendix A derives the coefficient-ring extension from the proof of D.1.
Preliminaries and counting theorems
All circuits are acyclic, and size counts noninput gates. The full input description length includes gate input lists and symmetric truth tables. Logarithms in counting exponents are base two; is the natural logarithm. We use .
Theorem 3 (Claude (Anthropic), Theorem 1 [2]). There are one deterministic finite-alphabet multi-stack Turing machine and one absolute constant such that, for every , every , and every -CNF in which all variables occur, with distinct clauses, the machine computes its exact model count in at most
steps, up to integer rounding of the time bound.
The cited Theorem 1 appears on pages 1–2 of [2]; Appendix E specifies the Lean statement and its machine model. A fixed multi-stack machine has a constant-overhead simulation by a fixed multitape machine. Repeated clauses can be removed in input-polynomial time. Unused variables contribute a power of two to the count, and inputs with or are counted directly. For the variable term of (1) gives time at arbitrary clause density. For fixed and , the clause term gives time. These consequences use the absolute constant in Theorem 3.
For the second interface, let
where is a monic binary lift of an irreducible polynomial of degree over .
Theorem 4 (Extension-ring form of the contraction theorem of OpenAI). A bipartite Boolean tensor network with wires, polynomially many vertices, maximum degree at most , and description length can be contracted over in deterministic time
and polynomial space, for and , when each local entry is computable in time and polynomial space. The constants depend on the fixed bounds in these assumptions.
The statement follows from the contraction argument in OpenAI [5 Appendix D.4]. Appendix A gives the coefficient-ring extension, precision analysis, and recovery of the original coordinates.
A quantitative local-reduction transfer
The transfer is parameterized by the complete test-time bound . The function measures the counting speedup and is the branch exponent. The transfer uses the unary nondeterministic hierarchy stated in Williams, Theorem 2.1 of the full version [7], and Jahanjou–Miles–Viola, Theorem 1 [3]. The bounded-binary combination appears in [5 Appendix C.1].
Lemma 5 (Uniform linear-size clause decoder). There is a fixed unary language
and a polynomial-time construction of a decoder with binary gates which maps bits to the three variable addresses and signs of a -CNF . The formula is satisfiable exactly when . Its variable addresses can be padded to bits for one fixed integer .
Proof. The proof applies the local reduction to a unary hierarchy language and uses the constant support of each decoder output. The hierarchy applies since . We simulate the fixed machine with allowance . We apply the local reduction with , giving . Each of its output bits has a constant-depth decision tree and thus a support of at most a fixed constant input bits. The circuit delivered by the reduction can be evaluated in polynomial time. We evaluate it on all strings of Hamming weight at most . For any essential coordinate , take a pair of inputs differing only at on which the output differs. Zeroing all coordinates outside the support preserves that difference and puts both inputs among these queries. Comparing such queried pairs identifies the entire support; the same queries give its truth table. Realizing each constant-size truth table takes binary gates. This constructs the linear-size decoder uniformly, even if the initial circuit was larger. Bounded exceptional lengths can be handled separately.
We declare all variables, including unused addresses. For inputs of length , let be bit of the lexicographically first satisfying assignment of , or zero when none exists. We set at all other lengths. The input length determines . Writing and querying an NP oracle about successive assignment prefixes takes at most queries of size . Therefore .
Theorem 6 (Explicit exponent and budget transfer). Let be eventually nondecreasing, tend to infinity, and satisfy , for every constant , and for fixed . Suppose a circuit model has polynomial description length for circuits with gates, includes binary gates, and admits the following deterministic test for a guessed witness circuit of gates on bits. Form three copies with the decoder of Lemma 5 and count violating clause addresses. Suppose this test has a deterministic multitape implementation taking time at most
for fixed positive , whenever the permitted witness budget is at most . The exponent bound must include all preprocessing, branches and exact reconstruction. Assume an effective integer threshold can be computed in polynomial time. Then for sufficiently small positive , at infinitely many lengths every permitted circuit computing has more than gates. For a model without a budget take and omit .
Proof. The proof guesses a small witness circuit and uses the assumed counting time to contradict the unary nondeterministic hierarchy. Choose so and so . If the conclusion failed, sufficiently small and the fixed-scale regularity of would provide witness circuits of at most gates at every sufficiently large address length . On input , guess such a circuit and form the violation circuit. All guessing, budget checks and decoding use polynomial time. We accept precisely when the number of violated clause addresses is zero. For a satisfiable , its first-witness circuit is an accepting guess. For an unsatisfiable , every guessed circuit describes an assignment violating at least one clause. Soundness holds for every guessed circuit.
Now . We squeeze between fixed positive multiples of ; monotonicity and regularity give . The total verifier time is , less than for all sufficiently large . The stipulated multitape bound includes all workspace access costs. We hardwire the finitely many smaller lengths and reject nonunary inputs. This contradicts the chosen hierarchy language. Thus the bound fails at infinitely many address lengths , which proves the result.
For sufficiently large , the two applications use
Their regularity follows from . For take
For , divide the inner expression by before the outer floor. These thresholds use integer arithmetic and have the required asymptotics.
| Witness model | Counting cost on the violation instance | Consequence |
| Unbounded AND/OR; binary XOR | , , | gates |
| Binary base; budgeted arbitrary XOR and other symmetric gates | , , | gates under the budget |
Table 2.
Counting algorithm I: signed long clauses
This counter preserves a linear variable budget by replacing each long defining clause with one signed selector. An auxiliary parity chain converts the resulting signed sum into two ordinary 3-CNF counts. Lemma 7 supplies the complete bound needed for the transfer.
The circuit class is defined in § 1.2.
Lemma 7. For a circuit in with inputs, gates and full description length , its output-one preimages are the difference of the model counts of two ordinary 3-CNFs, each on at most variables and clauses. Here is the number of AND/OR gates of fan-in at least three. By Theorem 3, the two counts are computable in time
Proof. The proof replaces long defining clauses by signed selectors and separates their total sign with one parity chain. The construction uses one variable per gate. An AND definition uses all and the single clause ; an OR definition uses and . XOR has four ternary clauses and COPY has two binary clauses. There is a unique gate extension of each input. For a long clause , replace it with and give weight . With all input and gate variables fixed, the selector sum is one for a true clause and zero for a false clause. This is the existing signed-clause construction [4, 1]. A unique-extension XOR chain on the selectors uses further variables. We fix its parity to zero and one to obtain the two formulas; for , use an inconsistent second formula. The count difference is exactly the claimed number.
Each individual count needs at most bits. After duplicate clauses are removed, let be the number of occurring variables of the th formula, and let be its clause count. Theorem 3, with , gives
Restoring the unused variables multiplies its output by . The first term, , and polynomial-time normalization give the displayed general-density bound. The cases or are evaluated directly. ∎
Counting algorithm II: affine characters and unit interpolation
The second counter removes affine relations by characters and arbitrary symmetric gates by a separated interpolation identity. Both transformations produce unary weights. Theorem 8 combines their branch count with the extension-ring contraction theorem and reconstructs the exact integer count.
Exact affine-character removal
The following identity supplies the XOR part of the symmetric-gate counter. On Boolean variables, row-reduce over . An inconsistent system contributes zero. Otherwise retain independent rows . For every ,
This follows by factoring the character sum into sums over single bits; a nonzero residual makes one such factor zero. Multiplication by any other constraint product and summation over proves the identity for its count. Every character becomes a unary sign on each variable. In a coefficient ring of characteristic , perform all branch sums at precision . If the final unscaled count is an integer with , the resulting canonical integer residue is exactly . We divide this integer by afterwards. Polynomially many bits suffice, and sequential character enumeration uses polynomial space.
For the mixed decomposition below, individual branches can have extension-ring values. The identity applies before any decomposition, so the complete sum is the integer . This identity justifies the final reconstruction.
Unit interpolation for symmetric gates
We apply the unit-separated interpolation construction of OpenAI [5 Appendix D.4.1] before contraction. It removes arbitrary symmetric gates from an otherwise bounded-arity circuit and charges their arities through a multiplicative branch count.
Coefficient ring and interpolation points For the explicit input length , choose
where is the largest symmetric arity. The irreducible polynomial defining can be found in time polynomial in , since . Ring operations and unit inversions take polynomial time in . Binary-coordinate representatives give points with pairwise unit differences. Theorem 4 supplies contraction for the resulting -valued branches, with this coefficient ring fixed throughout each call.
An integral separated decomposition Let a gate have input occurrences, with Boolean truth table indexed by input Hamming weight. Its output bit is . We choose distinct residue-field lifts in ; zero is allowed. The matrix , , has determinant , a unit. For each solve
These two solves take polynomial time in and lose no precision. Elimination always has a unit pivot after a row exchange: reduction modulo two is an invertible matrix over a field. Equivalently the coefficients are defined integrally in and reduced modulo .
For any Boolean input occurrences , the exact identity is
We use . A positive literal on variable contributes unary weights , and a negative literal contributes . The output variable receives weights . If a variable occurs more than once, multiply all its unary weights. Shared inputs, fanout and negated inputs therefore cause no independence assumption. When the gates have arbitrary depth, an output can receive both its own coefficient weight and factors from later gates; multiplication still applies pointwise.
A complete weighted counting interface
We consider Boolean variables, hard predicates of fixed arity, arbitrary explicitly described symmetric gate relations of arities , and an affine subsystem of rank . Let
Inconsistent affine systems give count zero. Otherwise the exact character identity from Section 5.1 removes the independent equations using terms and an eventual integer division by .
Theorem 8. The preceding mixed system has a deterministic exact counting algorithm with time
and polynomial space. Constants depend only on the hard-predicate arity. Recovery and original-assignment unranking use a polynomial number of deterministic counting calls. When the count is positive, exact uniform sampling uses a polynomial number of counting calls and polynomial expected additional time with fair random bits.
Proof. The proof expands the affine and symmetric constraints into unary weights, contracts each branch, and reconstructs one exact integer. The precision is . We enumerate one interpolation index for each symmetric gate and one affine character, sequentially. There are exactly branches. A branch has only the fixed-arity hard predicates and a pair of unary weights at each original variable. All these weights can be accumulated in input-polynomial time and space.
We make the fixed-density network of source D.2: one tensor per hard predicate, equality trees for its variable occurrences, and the unary weights attached at one port of each variable. A variable with no hard occurrences contributes as a scalar. There are wires, bounded maximum degree, and polynomial-time local entries. Subdivision makes the graph bipartite without changing its contraction. Theorem 4 evaluates the branch in the structural time in (4), with polynomial space. Each symmetric input occurrence contributes to an accumulated unary weight.
We sum all branch residues with their affine-character signs. By the two pointwise identities the result is the constant-coordinate integer modulo , where is the required count. All other coordinates vanish. The canonical constant residue is the actual numerator, so divide it by as an integer. In the absence of affine equations suffices, regardless of the symmetric arities.
We pin original variables successively with unary hard predicates. The resulting instances have variables, the same symmetric decompositions and affine rank bound, and at most additional hard predicates. The child counts sum to their parent’s count. The usual count self-reduction recovers a solution and maps each integer in bijectively to one solution. For exact uniform sampling when , let . A trial draws independent fair bits, interprets them as an integer , and accepts precisely when . The accepted index is uniform on , and the acceptance probability gives fewer than two trials in expectation. For , the index is zero. Unranking the accepted index therefore yields an exact uniform solution with expected additional time. We stream all branch choices and keep one accumulator, proving the space bound.
For an acyclic circuit with inputs and gates, give every gate one output variable, so . Every bounded binary gate imposes one arity-three predicate. We remove selected arbitrary-fan-in XOR gates by characters and all other designated symmetric gates by (3); pin the requested output. Then and (4) becomes
Each input has a unique full gate assignment, so the answer counts original input preimages. For example, preserves the fixed-density exponent, while gives subexponential time in . These statements have no depth or fanout restriction. They include majority and exact-Hamming-weight gates.
Proofs of the circuit lower bounds
Both conclusions follow from Theorem 6. The first proof substitutes the two-CNF counter with denominator ; the second substitutes the weighted counter with denominator and the explicit exceptional-gate budget. The witness language is the one constructed in § 3.
Unbounded AND/OR and binary XOR
Proof of Theorem 1. We apply Theorem 6 with and no budget. A witness circuit with gates on bits has three copies in the violation circuit, along with the -gate binary decoder. There are inputs, at most gates and at most long defining clauses. Lemma 7 therefore yields two 3-CNFs on at most variables. Each has polynomially many clauses: duplicate equal literals can be removed from AND/OR gates, so a complete witness description has length . The three-copy decoder, output pin and parity definitions add only polynomial description length. The complete verifier time is
One may pad both formulas with the same number of unused variables; this multiplies both counts by the same power of two and preserves zero difference. The exact difference is the nonnegative number of violated clause addresses, so the transfer’s completeness and soundness apply. For example, any sufficiently small rational meets its time requirement. The two calls run sequentially; the final subtraction uses bits.
A quantitative larger-basis circuit lower bound
We use the standard convention that a gate input list contains no duplicate signed wires, so on inputs and gates. Explicitly repeated lists use their actual in the counting algorithm. We give arbitrary-fan-in XOR gates unit budget cost and all other designated symmetric gates cost . Let be the sum of these costs; ordinary binary gates are free in this budget but still count toward .
Proof of Theorem 2. We use Theorem 6 with . A witness circuit on bits with gates and produces a violation circuit with input and gate variables. The decoder, sign checks and final AND use bounded binary gates. The three copies have combined removed cost : the affine rank is at most the number of removed XOR rows. Thus Theorem 8, with fixed-density hard gates, gives for . The coefficient of the budget term is exactly one; it is the binary logarithm of the explicit branch count.
Every witness gate has a polynomial-size input list and, for a symmetric gate, a table of bits. After substitution of decoded addresses, occurrences that coincide are retained. The counter already supports repeated inputs with the original witness budget. Polynomial space gives a multitape simulation with polynomial overhead. The transfer theorem applies with and . The constants are independent of the gate arities.
For its final consequence it suffices to consider , since larger circuits already meet the conclusion. For all sufficiently large , . The stated gate allowances therefore have budget at most . We take .
Discussion and open problems
The two lower bounds extend the binary-gate conclusion of OpenAI [5 Corollary 1.4 and Appendix C.1] through distinct counting interfaces. Signed selectors preserve a linear variable budget for arbitrary-fan-in AND/OR gates. Affine characters and unit-separated interpolation preserve a linear wire budget after the symmetric gates have been expanded, with the expansion charged by .
An ordinary bounded-fan-in encoding of a symmetric gate of arity computes its Hamming weight with auxiliary gates and evaluates its explicit truth table with further gates. Across all exceptional gates this gives a CNF size controlled by , whereas the theorem budgets . A CNF counting reduction with the latter budget would give a counting-theorem basis for the symmetric-gate bound. The present proof uses Theorem 4 for its extension-ring branches.
Two further questions are whether the logarithmic loss in the unbounded AND/OR lower bound can be removed, and whether a larger exceptional-gate budget permits the square-root-logarithmic lower bound.
AI assistance
OpenAI Codex was used to assist with drafting and revising the manuscript, developing parts of the mathematical arguments, and checking derivations.
OpenAI: The Exponential Time Hypothesis is False. OpenAI Math Release preprint (2026), https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf, 25 October 2026
Tamaki, S.: A Satisfiability Algorithm for Depth Two Circuits with a Sub-Quadratic Number of Symmetric and Threshold Gates (2016), https://eccc.weizmann.ac.il/report/2016/100/, ECCC TR16-100
Williams, R.: Improving Exhaustive Search Implies Superpolynomial Lower Bounds (2013). https://doi.org/10.1137/10080703X, https://www.cs.cmu.edu/~ryanw/improved-algs-lbs2.pdf, SIAM Journal on Computing 42(3), 1218–1244
Extension-ring contraction from the proof of Theorem D.1
Proof of Theorem 4. The idea is to run the contraction recursion of OpenAI [5 Appendix D.4] over an unramified coefficient algebra containing the input ring. The Boolean network and all recursion parameters are kept fixed. The following construction gives the coefficient algebra and checks the places where that proof uses its ring.
A coefficient algebra containing the input. Let , where is the monic lift in the theorem. It is free of rank over , with residue field . Put
Then and , except for the harmless equality case . If , take . Otherwise choose a monic degree- polynomial irreducible over , lift each coefficient to its binary-coordinate representative in , and write the resulting polynomial as . Set
The monic quotient makes free of rank over . Its residue field is , and the input ring embeds as the constant- coordinates of . In particular, this embedding is injective at every precision.
This algebra is constructible within the polynomial factor of the theorem. Enumerating monic degree- polynomials and testing irreducibility over the explicitly represented finite field takes bit operations, even using trial division by monic polynomials of degree at most . Since , that bound is polynomial in . The construction uses the same elementary finite-field fact as Appendix D.4.1 of the source.
Units, valuation, and precision. Use the free basis , , , with the evident basis when . For a nonzero element, its two-adic valuation is the minimum coordinate valuation. After factoring out this power of two, its reduction in the residue field is nonzero. Products of two such reductions are nonzero, proving multiplicativity of the valuation. An element nonzero modulo two is a unit: its multiplication matrix has odd determinant, whose inverse exists in . These arguments also show that is a domain and that its rational scalar extension is a field.
Arithmetic modulo , division by an explicitly known power of two with the corresponding precision loss, and unit inversion all use polynomial time and space in , and the coefficient descriptions. In particular, divisibility by is coordinatewise. The binary-coordinate residue lifts have pairwise unit differences and provide every interpolation point required in Appendix D.4.1. The recursion needs fewer than such points.
Entrywise lifts and the deformation. At creation precision , each entry is represented by the integers in in the fixed free basis. At every later precision those same coordinates are used. This is precisely the creation-precision convention in Appendix D.4.1. It applies to input entries as well as recursively created packet tensors. Each call therefore has fixed integral lifts of its tensors, and its deformed contraction is a polynomial over the rational scalar extension of .
The packing construction in Appendix D.4.2 depends on the network, not on its coefficients. The Cauchy kernel in Appendix D.4.3 has rational scalar coefficients, and Lemma D.4 proves their integrality after the substitution by cancellation of explicit integer powers of two. Consequently the same calculation gives for our lifted entries. Here denotes a source interpolation node, distinct from the tower degree above. The source proof already establishes this step for arbitrary integral coefficients of its extension algebra.
Hermite recovery and mode truncation. Lemma D.5 in Appendix D.4.4 uses rational scalar Hermite multipliers. Their two-adic valuations, the jet multiplicities, and the precisions depend on integer interpolation nodes and the network parameters. Applying that identity in each free coordinate gives exactly the same precision loss and exact recovery modulo the parent’s precision. Interpolation from the residue-distinct values is valid because every Vandermonde difference is a unit. All intermediate precision bounds remain those of source equation (D.11).
The mode expansion in Appendix D.4.5 has coefficients divisible by the stated powers of two. Multiplication by arbitrary integral tensor entries preserves that divisibility. Thus precisely the same weighted-degree cutoff discards terms that vanish modulo . The factorization into child contractions in equation (D.16) is an identity of sums and products in a commutative ring. It applies in , with no change to the branch index set, child edge counts, or degree bounds.
Local descriptions and total complexity. Input entry routines are evaluated at their declared creation precision and embedded into the constant- coordinates. This adds a polynomial factor in to their stated cost. New packet routines are the routines of Appendix D.4.6, evaluated in the fixed basis of ; their cost remains with polynomial space. The descriptions and their creation precisions are shared as in the source recursion.
The node-count estimate of Appendix D.4.7 is independent of the coefficient degree. It gives calls, and the direct leaves and local-entry costs fit the same exponent. Arithmetic contributes a polynomial in , the precisions, and . Since and all precisions are polynomial in , the total bound is the one stated in Theorem 4. Depth-first traversal and coordinatewise accumulators give polynomial working space.
Returning to the input ring. The root contraction is a polynomial with integer coefficients in its original entries. Its value therefore lies in the embedded . Reading the constant- coordinates returns it; the other tower coordinates are zero modulo . No additional interpolation, division, or loss of precision is needed for this final extraction. This proves the extension-ring statement from the contraction argument of Theorem D.1.
References
- [1]Bannach, M., Demaine, E.D., Gomez, T., Hecher, M.: A Novel Reduction from #SAT to #2SAT Based on Symmetry: Simply Drop the Large Clauses (2026). https://doi.org/10.1137/1.9781611978964.19, SOSA, pp. 254–265
- [2]Claude (Anthropic): A 2^{o(n)} Time Algorithm for 3-SAT (2026), https://github.com/anthropics/formal-math/blob/main/eth/paper.pdf, 26 October 2026
- [3]Jahanjou, H., Miles, E., Viola, E.: Local Reductions (2013), https://arxiv.org/abs/1311.3171, ECCC TR13-099; arXiv:1311.3171
- [4]Laakkonen, T., Meichanetzidis, K., van de Wetering, J.: A Graphical #SAT Algorithm for Formulae with Small Clause Density (2024). https://doi.org/10.4204/EPTCS.406.7, https://arxiv.org/abs/2212.08048, EPTCS 406, 137–161
- [5]OpenAI: The Exponential Time Hypothesis is False. OpenAI Math Release preprint (2026), https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf, 25 October 2026
- [6]Tamaki, S.: A Satisfiability Algorithm for Depth Two Circuits with a Sub-Quadratic Number of Symmetric and Threshold Gates (2016), https://eccc.weizmann.ac.il/report/2016/100/, ECCC TR16-100
- [7]Williams, R.: Improving Exhaustive Search Implies Superpolynomial Lower Bounds (2013). https://doi.org/10.1137/10080703X, https://www.cs.cmu.edu/~ryanw/improved-algs-lbs2.pdf, SIAM Journal on Computing 42(3), 1218–1244