WorksComputer Science
What the ETH refutations do not give: barriers for the counting engines, with machine-checked lemmas
Abstract
In October 2026 OpenAI and Anthropic each claimed a deterministic subexponential algorithm for counting the solutions of a -CNF; both counting engines sum products of local tables. For SAT itself, Majdoddin bounds the rate of Anthropic's grid recursions with product terms, and Dias and Lima bound OpenAI's clause-product scheme. However, Majdoddin notes that no barrier is known for decompositions whose terms are not products, and neither paper treats the counting problems beyond SAT. We introduce the engine barrier problem: bound from below the shared bits of every network of a stated class that computes a given count, and the rate of every recursion of a stated class. Our approach puts a rank on every cut of a local network, and on one contraction inside both flattenings of a term. Machine-checked in Lean are: correlated (non-product) decompositions of two rectangles, of the grid and of the full grid level have flattening-rank sums at least , and , while is open; the row cut of the permanent has rank , which on paper gives for row-local networks; algebras in which the permanent is a functional of a product have dimension at least ; pieces have saving (rank form; Anthropic's observation); and exact colouring filters for Hamiltonicity need colours. On paper we prove for vertex-local networks for the Tutte polynomial off the integer hyperbolas, and for correlated decompositions of full grid levels. We cite Lean theorems, with standard axioms only. Every barrier is about a named model: in Anthropic's general model no unconditional bound on exists without separating from , and an unconditional cap on oblivious algebraic algorithms would separate from .
Introduction
On 26 October 2026 OpenAI [47] and Anthropic [21] (below [O] and [A]) each posted a claimed refutation of the Exponential Time Hypothesis: a deterministic algorithm that counts the satisfying assignments of a -CNF on variables in time up to lower-order factors, with a Lean 4 development. Both claims are under review. Both engines are counting algorithms for sums of products of local tables, and they reach every problem whose witnesses have bits and are checked locally. Our earlier work used them, with machine-checked proofs, for exact counting of Hamiltonian cycles and TSP tours on sparse graphs [59], Eulerian circuits [58], amplitudes of sparse quantum circuits [61], factoring [62], class numbers [57] and the parity of [63].
For #SAT itself, two papers that appeared while this one was in preparation give negative accounts. Majdoddin [43] defines a rewrite-and-merge class that contains [A]’s recursion and proves that every grid algorithm in it has exponent at least per edge bit; Dias and Lima [29] prove that the clause-product form of [O]’s interpolation algorithm costs at treewidth , in a cost model that charges what the preprint pays. The labs’ own remarks are shorter. [A] writes that its theorem “does not refute the Orthogonal Vectors hypothesis” and that the result “is purely asymptotic” (§ 2). [O] notes that a faster algorithm for a target problem needs “a reduction in the other direction, from that problem to fixed-width SAT, that controls the number of variables”, and that “runtime bounds of the form do not transfer under general polynomial-time reductions”. However, Majdoddin’s class requires every term of a recursion to be a product of one piece per configuration; he calls non-product groupings of terms the “open door” of his class and writes that “for the full model of Signed Network Sums no barrier is known” [43 §4.8]. Neither paper treats a counting problem other than (Max-)SAT. We are unaware of a barrier for non-product decompositions, or of an account of which counting problems beyond SAT the engines cannot be expected to reach, by which mechanism, and what would have to change. This matters because the engines are new, and the obvious targets after sparse #HC (the permanent, dense #HC and TSP, the chromatic number, the Tutte polynomial, Subset Sum, exact ) are exactly the ones they seem to miss.
The problem and the running example
We consider the engine barrier problem. For a counting problem and a stated class of networks, bound from below the number of shared bits of every network in the class whose value is ; and for a stated class of recursions, bound from below the rate at which the recursion evaluates the dense -clique. The two numbers combine: the engine’s own guarantee on a network is at least (Theorem 2.4), and in [A]. So a dense problem is out of reach of the engine’s guarantee when is of order and is not . For grid recursions with product terms, is a theorem of Majdoddin [43 Theorem 4.13]; the question we add is what terms that are not products can do.
Figure 1 is our running example. One level of [A]’s recursion views a clique on nodes as a grid. Each pair of rows and pair of columns spans a rectangle with corner legs and tensor . Evaluated row by row, a term costs the rank of its row flattening ; evaluated column by column, the rank of its column flattening . For both are permutation matrices of rank . The recursion therefore splits into pieces, terms that are cheap in one of the two groupings, and the saving per level decides its rate. At the split has rank profiles and : each piece pays 2 bits in one grouping and none in the other, half of the 4 bits of . We come back to this example in § 2 (what a shared bit buys) and in § 4: on two rectangles and on the grid no decomposition, correlated or not, does better asymptotically, and on the level the question is open.

Figure 1. The running example. One level of [A]’s recursion evaluates a clique on a grid of nodes; each pair of rows and columns carries a rectangle, two crossing equalities of bits each. Its tensor has both flattenings of full rank , . At the split gives two terms, each cheap in one grouping: this is the profile of saving .
The naive route and the principle
At first one might try to prove that the dense permanent needs steps in the engine, for example by bounding from below for every network whose value is . However, in [A]’s Definition 2 the node tables are arbitrary polynomial-time functions of the whole input; Ryser’s formula is then a one-node network with , and a network with and one setting exists if and only if (Theorem 3.13). Instead, we rely on a different principle: every known network is local, and locality lets a cut carry a rank. If the nodes on one side of a cut read one part of the input and the nodes on the other side read the rest, then the value, as a matrix indexed by the two parts, has rank at most , where is the number of shared bits across the cut. The same rank argument bounds the cost of a term of a recursion through its two flattenings, as in Figure 1.
In Anthropic’s general network model a node table may be any polynomial-time function of the whole input, so no unconditional lower bound on shared bits is possible without separating from (Theorem 3.13); every theorem of this paper is about a named class of local networks or recursions.
What we do
In this paper we define the models (row-local and vertex-local networks, pieces, grouping recursions, correlated decompositions, ’s -template, tree verifiers), prove rank lower bounds in each, and assemble them into a map of nine problems. The key observation is that the two numbers and are each controlled by one rank: by the rank of the value across a cut of the input, and by the rank of a contraction that is a submatrix of both flattenings of a term at once. Many ingredients are classical: Nisan’s rank characterisation of noncommutative branching programs [46], Lindström’s factorisation of meet matrices [41], and rank subadditivity. The product-term caps of Sections 4.1 and 4.3 are parallel to, and weaker than, Majdoddin’s [43]. What is new is the correlated decompositions of § 4.4, the walls for the problems beyond SAT (§ 3, § 6 and § 7), and a Lean development that checks every rank statement we cite.
Contributions
Our contributions are:
We introduce the engine barrier problem and its two numbers, and define the network and recursion models in which we bound them (§ 2).
We prove that dense counting costs shared bits in the local networks we can analyse: for row-local networks for the permanent (rank and counting steps in Lean), for algebras (Lean), and, on paper, for vertex-local networks for the Tutte polynomial off the integer hyperbolas (§ 3).
We prove, to our knowledge, the first barriers for correlated (non-product) decompositions, the region that Majdoddin’s class leaves open: rank sums at least , and on two rectangles, the grid and the level (Lean, rank form), on full levels (on paper), and a proof that flattening certificates stop at 8 on the level (§ 4.4).
We machine-check the rank form of for pieces ([A]’s Appendix H observation, generalised in [43]), and prove on paper for graded two-order pieces and for every family of groupings of the grid rectangles (Sections 4.1 to 4.3); and we prove that [O]’s -template is tight at (Section 5).
We prove floors for three of our own linear encodings of Hamiltonicity: colours, turn bits, and a support threshold below which every residue query vanishes (Lean, § 6).
We map nine problems out of reach (Table 2, § 7), state what would have to change and why proving that it will not is itself out of reach (§ 8), and describe the Lean development: 45 cited theorems in 16 modules (§ 9).
Status of each claim
We separate four kinds of claim, and every theorem environment carries its label. Machine-checked in Lean (Theorem, “machine-checked”): the 45 statements named in § 9, with the axioms propext, Classical.choice and Quot.sound only. Two of them have hypotheses that stand for steps proved on paper (?? 3.3?? 3.4), and the bracket says so; the hypothesis of Theorem 6.2 is discharged in Lean by Theorem 6.1. The Lean statements about correlated decompositions bound ranks of flattenings; the step “a network of cost has flattening rank at most ” is on paper. Proved on paper only (Proposition, “on paper”), with the research note and its own number: the engine exponent (Theorem 2.4), the general-model statement (Theorem 3.13), Model V and the Tutte barrier (?? 3.5?? 3.10), the entropy bounds for #SAT encodings (Theorem 3.9), the graded two-order bound and the grouping caps (?? 4.4?? 4.6–4.8), the full-level bound and its limit (?? 4.12?? 4.13), the template bounds (Theorem 5.2), the black-box and adversary statements, the quota accounting for Subset Sum and products (?? 7.3?? 7.5), and the meta-barrier and conditional cap (?? 8.1?? 8.2). Assumed: the statements of [A] and [O] that we quote as Imported Theorems, pinned to commits and sections. They enter only as the object our barriers are about; no barrier of this paper depends on their correctness. Checked numerically (Remark, “checked numerically”): exact rank tables, the searches and the integer programs of § 4.4. They never support an asymptotic claim. No theorem in this paper is about all algorithms.
Outline
§ 2 recalls the engines and defines the models. § 3 proves the wall for shared bits, § 4 the caps on the rate and Section 5 the tightness of [O]’s template. § 6 treats our own encodings, § 7 the nine problems and § 8 what would have to change. § 9 describes the Lean development, and § 10 to § 12 cover related work, limitations and conclusions.
The engines and their two numbers
In this section we recall the statements of [A] and [O] that our barriers are about, define the network models, and prove on paper that the engine’s guarantee on a network is at least . We use [A]’s development at commit 16a5ce4 (anthropics/formal-math, folder eth) and [O]’s at commit 7ef5c0c (openai/math, preprint revised 25 October 2026). Logarithms are to base 2.
The labs’ own limits. [A], Introduction: “Theorem 1 does not refute the Orthogonal Vectors hypothesis, which SETH implies and on which many lower bounds in fine-grained complexity rest”, and “Our result is purely asymptotic”. [O], §1.1.3 (“Implications for fine-grained complexity”): lower bounds that “follow from the hypothesis that unrestricted CNF-SAT admits no -time algorithm” survive, since its theorem “gives a running-time guarantee for each fixed clause width , while this hypothesis allows the width to grow with ”; and “to obtain a faster algorithm for a target problem from our SAT algorithm, we need a reduction in the other direction”. In the remark before its corollary on graph counting, [O] adds that “runtime bounds of the form do not transfer under general polynomial-time reductions”. For SAT itself Majdoddin [43] and Dias and Lima [29] give negative accounts; this paper gives one for the problems beyond SAT and for non-product decompositions.
Networks and shared bits
Definition 2.1. (Networks; [A], Definition 2) A network on has, for every node , a set of settings of at most bits and a weight table , and for every pair an interaction that factors through shared bits: . Its value is , and its total is , so every shared bit is counted at both ends. The skeleton is . A network family for a counting problem is a map from inputs to networks whose value is the count.
In [A] the tables are given by polynomial-time procedures that see the whole input. The known networks are local: in [A]’s 3-SAT network a node reads the clauses of one block, and in our Hamiltonian-cycle network a node reads the edges at one vertex cluster. Two locality classes carry our theorems.
Definition 2.2. (Model R() and Model V(); barrier.md Definitions 5.1, 5.2) Let the input be a matrix (or a graph on ). In Model R() the rows are partitioned into clusters of size at most , every node is assigned to one cluster or is a routing node that reads nothing, the skeleton does not depend on , and the data of a node depend on only through the rows of its cluster. In Model V() the rows and columns (or the vertices) are partitioned into clusters of size at most , and the data of a node depend only on the entries in the rows and columns of its cluster (the edges with an end in it); otherwise as before.
The engine of [A]
Imported Theorem 2.3. ([A], Lemma 8(i), Theorem A and Theorem B; imported, not used as an assumption) Let , . A network on with parameters and total is evaluated within operations, where bounds the cost of a -clique with (Lemma 8(i), Lean ExplicitCost.groupingExplicit). If parameters exist, one algorithm evaluates the -clique within operations, where and , (Theorem A, Lean ExplicitCost.recursionSolves). Pieces with exist (Theorem B, Lean PiecesCounted.halfPieces).
The -clique is the network on nodes in which every pair shares one -bit label through , with arbitrary tables. Its cost is written ; brute force has . One level of Theorem A maps a -clique, viewed as the grid of Figure 1, to networks on nodes grouped by rows or by columns. The straight edges inside a row or column cost of the shared bits; the rest sits on the rectangles. A family of pieces writes with and certified costs with ([A], Definition 7). Every term of the expansion of is a row network and a column network, and the level pays the cheaper one, which saves the factor . Since while drops by , the rate is with ; gives .
What a shared bit buys. In Figure 1 a rectangle carries shared bits at both ends. A piece with costs nothing in the column grouping, and at the split realises the profile , i.e. . For larger the same split does not keep this profile ( has row rank ), and [A]’s Theorem B pays instead. The question of § 4 is whether any decomposition beats ; the question of § 3 is how many rectangles, that is how many shared bits, a dense problem forces.
The engine of [O]
[O]’s Theorem 1.1 counts the solutions of a -CNF with clauses in time and polynomial space. Its Engine I needs a layout ([O], Definition def:layout; Lean LayoutSpec.Layout): partitions of the variables at interpolation points, schedules for the factors, measurement matrices of small height, and for every occurrence a row polynomial of degree at most with that annihilates the measurement kernels of the other groups. The cost exponent is about . [O]’s construction (its §4) is a template: a matrix acting on labels in , with support condition (T2), . Section 5 bounds every instance of this template.
The engine exponent
Proposition 2.4. (on paper; barrier.md Lemmas 2.0, 2.1, 2.2) Let be a network with total to which Lemma 8 is applied with any admissible and the clique algorithm of Theorems A(b) and B. Then the guaranteed running time is at least with
So the guarantee is below only if , and with pieces of saving it is at least . Any algorithm for the -clique that reads its tables has , which alone gives only .
The proof reads off Theorem A(a), notes and , and splits on whether exceeds the bound. The query bound is Majdoddin’s input floor [43 Proposition 2.4(a)] in our normalisation (his exponent is per edge bit, of which the clique has ). The last sentence is the reason § 4 matters: with a hypothetical optimal clique solver, no lower bound on of order would bar anything. This proposition is about [A]’s guarantee as a function of , for all inputs; it is one of the three places (with Section 5 and Theorem 3.11) where a statement concerns the engines as published rather than a class of networks.
Dense counting costs n log n bits in every local network we can analyse
In this section we prove the lower bounds on . We first state the cut lemma in rank form (§ 3.1), then compute the rank of the permanent across a row cut (§ 3.2), and sum the cuts in Model R (§ 3.3) and Model V (§ 3.4). § 3.5 treats algebras and characteristic , § 3.6 the Tutte plane, and § 3.7 says why no such bound exists in the general model.
The cut lemma
Let be a network and a partition of its nodes, with crossing bits. Replacing every crossing interaction by its factorisation and exchanging the sums gives , where depends only on the data of the nodes in (barrier.md Lemma 3.1, on paper). So if the nodes in read only a part of the input and those in only the rest , the matrix factors through terms. The rank form is machine-checked.
Theorem 3.1. (`EthFollowup.Barriers.Rank.rank_le_card_of_eq_sum_mul, EthFollowup.Barriers.Rank.rank_le_two_pow_of_eq_sum_mul, EthFollowup.Barriers.Rank.rank_eq_card_of_linearlyIndependent; machine-checked) Let be a field and types with and finite.1 If for all , then ; for this is . If moreover over a finite with both families , linearly independent ( finite), then .
Proof. Write with and ; the rank of a product is at most its inner dimension . For the second statement, with and of full column rank .
The permanent’s row cut
Theorem 3.2. (EthFollowup.Barriers.RowCut.rowCut_rank, EthFollowup.Barriers.RowCut.rowCut_rank_oneHot, EthFollowup.Barriers.RowCut.permanent_joinMat; machine-checked) Let be a field, a finite type with elements and with . Let be the matrix whose rows are indexed by the rows , whose columns are indexed by , and whose entry is , the permanent of the matrix with rows read from and the other rows from . Then , and the same holds for the submatrix on one-1-per-row matrices. The proof is the Laplace expansion along the rows .
Proof. A permutation of maps onto some with , which gives the Laplace expansion. Evaluated at the one-1-per-row matrix that matches onto , , so the are linearly independent, and likewise the ; Theorem 3.1 gives rank exactly , already on the one-1-per-row family.
An aside, not part of the statement above: on one-1-per-row matrices the permanent is the indicator that is a permutation matrix, so on that family the rank statement is about this indicator.
Model R: U >= n log(n/s)
For a cluster of Model R(), cut the nodes into those of cluster and the rest. The left side reads the rows and the right side the other rows, so Theorem 3.1? Theorem 3.2 give with the bits crossing that cut; this step, from a network to a factorisation, is on paper. Each ordered pair of nodes is counted in at most one , which is machine-checked, and the rest is arithmetic.
Theorem 3.3. (EthFollowup.Barriers.Rank.modelR_bound_nlogn, EthFollowup.Barriers.Rank.modelR_bound, EthFollowup.Barriers.Rank.sum_crossing_le_total; machine-checked with hypotheses hrank and hU on paper) Let be a finite set of clusters, , and with and . Assume hrank: for every (the cut lemma with the row cut, on paper for a given network), and hU: . Then
The second inequality needs only hrank and hU (modelR_bound). For hU: for every assignment of nodes to clusters or routing and every , (sum_crossing_le_total), so hU holds with the crossing bits of cluster .
Assembled on paper (barrier.md Theorem 6.1): every network family for per in Model R() has , already if the value is correct only on one-1-per-row matrices; with Theorem 2.4, for the engine’s guarantee on any such network is (barrier.md Corollary 6.3). This is the analogue of Nisan’s bound for noncommutative branching programs [46], with row-locality in place of the variable order.
Vertex-local networks: trees and the single-cut limit
In Model V a node also reads the columns of its cluster, and the row-cut argument breaks: each side sees part of the other’s input. A vertex cut with rows and columns on the small side has rank exactly for a suitable fixing of the shared entries, by the Vandermonde identity.
Theorem 3.4. (EthFollowup.Barriers.Rank.treeSkeleton_bound, EthFollowup.Barriers.Rank.sum_choose_mul_choose; machine-checked with hypothesis hrank on paper) Let be a finite set of tree edges and , , with . Assume for every edge (the cut lemma with the vertex-cut rank, on paper). Then . Also for all .
Proposition 3.5. (on paper; barrier.md Theorem 6.2 and Proposition 3.5, vertex-local-bound.md Theorems 2.1, 3.1, Corollary 3.2, Propositions 4.1, 4.2) Every network family for per in Model V() has for . No single cut gives more: for a vertex cut with rows and columns on the small side, every fixing of the other entries gives rank at most . If the skeleton is a tree of maximum
degree with the clusters , then . On the clusters , no star skeleton with one shared bit per leaf computes for . The function [A is a permutation matrix] has a Model V(1) network with but needs in Model R(), so the one-1-per-row family gives no bound in Model V.
The star statement uses Cayley’s hyperdeterminant and is checked numerically for ; the Catalan cut rank of the family is checked for .
Conjecture 3.6. (Model V; barrier.md Conjecture 6.5) Every network family for in Model V() has . Proved: for , and for trees of bounded degree; the star with two bits per leaf is the first skeleton on which every cut passes.
Substitution algebras and characteristic p
A different way to evaluate is to substitute ring elements for the entries and read a coefficient, as Clifford, group-algebra and Kronecker tricks do.
Theorem 3.7. (EthFollowup.Barriers.AlgebraRank.algebra_rank_half, EthFollowup.Barriers.AlgebraRank.algebra_rank_sum; machine-checked) Let be a field and a finite-dimensional -algebra, not necessarily commutative.3 Let be -linear and () with for every . Then . For finitely many such algebras with , .
Proof. For let be the product of the first factors along a fixed bijection onto , and the product of the last along a bijection onto the complement. Then , so the elements are linearly independent in . For several algebras apply this to the product algebra with the functional . □
Theorem 3.8. (EthFollowup.Barriers.PermModP.permanent_eq_zero_of_low_rank; machine-checked) Let be a commutative ring of characteristic , prime, and finite types.4 If with and , then .
Proof. Expanding column by column gives , where column of is column of . If , some value of is taken at least times, so has equal columns; a -cycle permuting them acts freely on the terms of and leaves each orbit sum times one term, which is in characteristic . □
So every saving that characteristic gives through low rank dies once is of order , and the Chinese remainder theorem needs primes up to to about .
Proposition 3.9. (on paper; wild-ideas.md F1, perm-mod-p.md Lemma B4) If for all matrices , with integers , for some has at least variables. The same holds modulo any with .
So plain #SAT encodings of have variables, where the Lean #-SAT bounds of both labs cost or more.
The Tutte plane off the hyperbolas
Write , and , . On the engine reaches the Tutte polynomial of sparse graphs, conditionally on [A] and informally (tutte-plane.md Theorems P1, P2; not claimed here). Off them, the information is the connectivity pattern of the private edges, and the shared edges can be fixed to a matching.
Proposition 3.10. (on paper; tutte-plane.md Theorem B, Lemmas 3.2–3.4, Proposition 3.5) Let and . Let be a Model V() family on subcubic graphs (maximum degree 6 at ), with a fixed skeleton and , that computes for some nonzero normalization . Then for a sum of such networks on one common clustering, some summand has . The ingredients are Lindström’s factorisation [41, 66] , whose rank over is for and otherwise (the connection rank of [30, 42]); linear-forest gadgets that realise every boundary partition with triangular gluing vectors; and a deletion–contraction step that replaces forests by connected subcubic graphs. For the gluing matrix is up to invertible diagonal scalings, so the rank depends on only through and on whether ; at (that is, ) the matrix takes its place and has rank by Möbius inversion, and on () the acyclic matrix of Theorem 8.5 does.
Corollary 3.11. (on paper; tutte-plane.md Corollary B′) Under the hypotheses of Theorem 3.10, [A]’s guarantee is at least , and for any pieces with it is at least .
Remark 3.12. (checked numerically) The ranks of were computed exactly for , the cut ranks of the test families for at fifteen points, and the acyclic gluing rank on equals the Catalan number for and is at least at . That it equals for all is a conjecture.
Two loopholes are open: sums of networks over many different clusterings (the analogue of sums of read-once branching programs in different orders), and skeletons that depend on private edges. Nothing in Theorem 3.10 covers either. The matching upper bound holds everywhere: at every point is a Lagrange combination of colour networks with $U\le 2m\log_2(n+1)+g^2` (tutte-plane.md Proposition P3, informal and conditional), so the minimal vertex-local resource is off and the whole question is the rate .
The general model admits no unconditional bound
Proposition 3.13. (on paper; barrier.md Proposition 4.1) In [A]’s Definition 2, with tables given by polynomial-time procedures on the whole input:
(a) a network for with , one setting, and exists if and only if ; so an unconditional lower bound in the general model would imply ;
(b) Ryser’s formula [51] is a network with , and ;
(c) “a network with ” is equivalent to “”.
So in the general model the barrier question is the open algorithmic question itself. The conditional lower bound of Dell, Husfeldt, Marx, Taslaman and Wahlén [28] (no algorithm for the permanent under #ETH) cannot be invoked, since the same engines refute #ETH. What we bound is the information that a local network routes.
The rate is capped in every analysed model
In this section we bound the saving of one level, and hence the rate exponent , in four kinds of model of increasing generality: pieces (Section 4.1), graded two-order pieces (§ 4.2), recursions that take the cheaper of several groupings (Section 4.3), and correlated decompositions that need not be products (§ 4.4). The first three have product terms, and there Majdoddin’s rewrite-and-merge class [43] contains our models with sharper constants; we include them because their rank statements are machine-checked here, because the covering bound for arbitrary families of groupings is not in [43], and because § 4.4 reuses their contraction. § 4.5 says what the caps mean for the engine. Throughout, is the alphabet of one crossing equality.
Pieces have
Contract the legs and of a piece with vectors . On this gives times the identity on , and for any piece the contraction is a submatrix of both flattenings, so its rank is at most the smaller of the two.
Theorem 4.1. (EthFollowup.B arriers.Rank.pieces_trivial_lower_bound, EthFollowup.B arriers.Rank.pieces_exists_large_piece; machine-checked) Let be a field, a finite type and (, finite) with for all and some . Then
and if some piece has both flattening ranks at least .
Proof. Contract and with a common basis vector. The target becomes times the identity on , of rank , and the contraction of each piece is a submatrix of both of its flattenings. Subadditivity of rank gives the first claim and pigeonhole the second. □
The bound for pieces is not new: it is the observation of [A]’s Appendix H that one piece needs bits row-wise, and Majdoddin’s pigeonhole and two-merge floors [43 Propositions 4.6 and 4.8] are its general form, for every configuration. What Theorem 4.1 adds is the Lean check of the rank form, and a contraction that bounds of each term separately, so that no mixed term is needed; § 4.4 uses exactly this.
Theorem 4.2. (EthFollowup.Barriers.Rank.rank_sum_le, EthFollowup.Barriers.Rank.exists_logb_rank_ge; machine-checked) For a field and matrices (, finite) over of a common shape, . If and , some has .
With certified costs at least of the ranks and , this gives in [A]’s Definition 7 (rho-lower-bound.md Corollary 2.2, on paper). The rank inequalities that a piece family must satisfy are themselves satisfiable at (rho-lower-bound.md §2.2), so no counting argument on ranks alone beats , and the simplest profiles are excluded only by a finer argument (a piece of operator-Schmidt rank 1 forces the others to carry rank at least , rho-lower-bound.md Proposition 2.3, on paper).
Graded two-order pieces have
[A]’s Theorem B builds its pieces from a graded space : a piece is a slice of a locality identity of order , and its certified cost is the dimension of the spaces the products pass through, “max over the terms”. Write and .
Theorem 4.3. (EthFollowup.Barriers.Spread.spread_lemma, EthFollowup.Barriers.Spread.spread_slice, EthFollowup.Barriers.Spread.spread_slice_zero; machine-checked) Let , , a finite set of terms with degrees , and , .5 With (and where ,
where and , both sets nonempty. For the slice of a locality identity of order with degrees , , the right side is at least , with no sign hypothesis; for , and it is at least .
The operators and the two-order identity are not modelled; the theorem is about the dimension counts only, and the certified costs are those of [A]’s Lemma 3.2 (Lean Nat.clog 2 (Rrow h s) in its statement of Theorem B).
Proposition 4.4. (on paper; rho-lower-bound.md Corollaries 3.4, 3.5, Lemma 4.1, Propositions 5.1, 5.2; sparse-fock.md Theorem 2.1) For graded two-order decompositions with spread and , the saving is at least . On Fock space ( of the partition function, with the Hardy–Ramanujan bounds) this is , and the same holds in every -cofinite vertex operator algebra. The spread follows from the pairing being the top pole. Conversely, every family of pieces as a graded two-order decomposition on a sparse Fock space at two extra bits per piece, so the question “is ?” is the general pieces question.
De Brito [25] proves, after [A]’s Appendix H, a rank floor for families of the shape of [A]’s Theorem B, which closes the case of growth exponent for that shape and gives . Majdoddin [43 Proposition 4.24 and the remark after it] proves for every concave profile in that shape and the same for power profiles . Our corollary, in a note dated 28 October, gave the branch and left open; what Theorem 4.4 adds is the -cofinite generality and the converse. Outside the shape, “?” is open.
Remark 4.5. (checked numerically) For the true ranks of the Theorem B pieces are 93–97% of the certified counts wherever the count is below . This says nothing about the asymptotic .
Any min-over-groupings recursion has
Proposition 4.6. (on paper; clique-evaluation.md §4.3) Let a level write each rectangle as with , expand the product over the rectangles, and evaluate every term in the cheaper of the row and column groupings. Then , and with the recursion has , for any pieces, any algebra and any subexponential term count.
The proof uses Theorem 4.2: some piece has row cost at least and some column cost at least ; the mixed term using on half of the rectangles and on the other half costs in both groupings. So it is the schedule, not the pieces, that is capped. Majdoddin [43, Theorem 4.13 and Corollary 4.19] proves the sharper statement that every grid algorithm has exponent at least per edge bit, with the exact constant and without assuming ; our note of 29 October [60] has the weaker form above.
Proposition 4.7. (on paper; engine2-probabilistic.md Theorem A, proof as repaired in §7.3) Let a level write each of the grid rectangles as with and expand the product over the rectangles. Let be any family of partitions of the grid nodes into blocks of size at most , and let every term choose its grouping from , adaptively or at random. Then the level saving satisfies ; for all partitions, . So for every level of this kind that expands into terms and picks the best grouping.
Proof. Call a rectangle with corners (Figure 1) diagonal under a partition if or lie in one block of . A pair of nodes in one block, in different rows and columns, is a diagonal of exactly one rectangle, so at most rectangles are diagonal. A rectangle that is not diagonal is row-like if or share a block, column-like if or do, and four-block otherwise; it cannot be both row-like and column-like, since for instance and would put in one block. For a row-like rectangle the row cut is a union of blocks restricted to its corners, so the bonds of the evaluated network that cross it carry at least the row log-rank of its piece; likewise for column-like ones, and a four-block one pays both. By Theorem 4.2 there are pieces of row, respectively column, log-rank at least . Draw uniformly. For a fixed , each row- or column-like rectangle pays its full cost with probability , independently, and each four-block one always does, so Hoeffding’s inequality and a union bound over the partitions give a term that pays at least under every . For all partitions . □
The configurations here are the grid rectangles with per-rectangle product identities. Majdoddin leaves three or more merges open in his class ([43 §4.8 and Open Problem 4]); for rectangles, whose relevant cuts are the row, column and diagonal ones, Theorem 4.7 treats any number of groupings. The first version of the note charged every rectangle that meets at least three blocks both of its costs, which is right only for four-block rectangles; the proof above reclassifies the others (and the constant is , not , since exactly).
Proposition 4.8. (on paper; engine2-algebraic.md Theorems 7.1, 7.3, Corollary 7.4) For gadget recursions with groupings whose gadgets meet exactly two classes in every grouping, the saving satisfies over the number of distinct cuts of a gadget, and, under homogeneity and regularity with exceptional fraction , the node count grows as . Hence : each additional distinct cut costs one factor in the node count.
Majdoddin argues the same for line merges of the -dimensional grid [43 §4.8]; neither statement implies the other.
Other mechanisms fail for exact reasons (engine2-algebraic.md M1–M5, M8, on paper): algorithms based on tensor rank have (Majdoddin’s flattening floor [43 Proposition 2.4(b)] in our normalisation); node-local invertible transforms leave every rank-based cost unchanged; by the Chinese remainder theorem over is the maximum over primes; monomial pieces in any product basis have ; the best contraction tree has ; and recursion on the bits of gives nothing.
Correlated decompositions: , ,
All the caps above assume that the terms form a full product over the rectangles, which is what lets the mixed term exist. Majdoddin’s class makes the same assumption (his (L2)), and he notes that summing terms over a set of choices that is not a product set leaves the class [43 Remark 4.5]. A recursion could instead write the identity of a whole level as over a correlated set of terms, each a row network or a column network. For such a term, the flattening across any union of rows has rank at most (engine2-decorrelated.md §1, on paper), and the rank sum satisfies . So on a configuration of rectangles is there. The trick is one contraction that is a submatrix of a row flattening and of a column flattening at the same time.
Theorem 4.9. (Decorrelated.rankSum_ge, Decorrelated.exists_expensive; machine-checked) Let be a field and a nonempty finite alphabet.6 For every finite family of tensors on the eight legs with ,
and some term has this minimum at least .
Proof. Fix . The contraction of is the identity on , of rank , and the contraction of each is a submatrix of both flattenings. Subadditivity finishes. □
The Lean statement is one statement about two fixed cuts; its file header calls the configuration “C” (disjoint row pairs and column pairs). The two-class cuts of configurations A (one cell shared) and B (shared row pair) are the same two cuts with the legs assigned to rows and columns differently, and the chains D, E reduce to them by the symmetry of ; both readings are on paper. So for every pair of rectangles, correlation buys nothing: .
The running example, twice. Return to Figure 1 at and take two rectangles. The product of the splits gives four terms , , and , whose minima of the two flattening ranks are 1, 4, 4, 1: rank sum 10 and maximum cost 2 bits, which is . Theorem 4.9 says that no decomposition, correlated or not, has rank sum below . A correlated decomposition can repack constants (exhaustive search finds rank sum 7, Theorem 4.14), but it cannot change the exponent, for any . At the term count is not , so the example illustrates the bound and is no evidence about .
Theorem 4.10. (Grid32.rankSum_ge, Grid32.exists_expensive, Grid32.H_eq_rowTwist_T0, Grid32.rank_colFlat_T0; machine-checked) Let be a field and a nonempty finite alphabet.7 Let be the tensor of the three rectangles , , on one column pair of the grid (12 legs). For every finite family with ,
and some term has this minimum at least . Moreover is a row-local relabelling of a tensor whose column flattening has rank at most 1.
The proof pairs the two legs at one node and fixes the legs; one leg straddles the row cut and one the column cut, each at a factor , while the target gains . The last sentence is a no-go: any subadditive functional that is invariant under row-local relabellings and bounded on cost-0 column networks takes the same value on as on a cost-0 term, so it proves nothing.
Theorem 4.11. (Lossy.rank_contr_le, Lossy.rank_contr_graph, Grid33.rankSum_ge, Grid33.exists_expensive; machine-checked) Let be a field, a finite alphabet and a finite set of legs.8 For disjoint , a cut and a tensor , the contraction keeping as rows, as columns and fixing the other legs satisfies ; for a graph tensor whose kept edges match with and whose other edges are fixed, the contraction is a permutation matrix of rank . Let be the tensor of the full level (the graph tensor of the 18 crossing edges of , 36 legs). If is nonempty, then for every finite family with ,
with the legs in row and the legs in column 3, and some term has this minimum at least . The side conditions (disjointness, matching, , four straddlers per cut) are proved by decide.
Proof sketch. Keep the 12 legs at the block on edges leaving the block as rows and their partners as columns, and fix the other legs. The contraction of is a permutation matrix of rank . Exactly four kept legs lie on the wrong side of the row cut and four of the column cut, so each term’s contraction has rank at most times either flattening rank. Subadditivity gives .
With “a row network has rank ” (on paper), Theorem 4.11 is on the level, i.e. there. The same lossy contraction on larger levels gives the following.
Proposition 4.12. (on paper; engine2-decorrelated.md §7.3 and Theorem 5) Every decomposition of the level, , into row and column networks has out of , hence and .
Proposition 4.13. (on paper; engine2-decorrelated.md Proposition 7.6, §8.2, §8.3) No two-party lossy contraction certifies more than on a full level, so is the limit of the method. On the level no flattening certificate, that is no combination of flattening inequalities, certifies more than 8 (a profile of tailored “hub” terms passes every flattening test), and no -party Christandl–Vrana–Zuiddam functional [19], tensor rank, slice rank or geometric rank with straddling legs certifies more than 8. That the optimum of the flattening certificates is exactly is computed, by an exact integer program (Theorem 4.14).
Remark 4.14. (checked numerically) Exact integer programs give the flattening optimum for , equal to the single balanced contraction in each case. At , GF(2) SAT search finds rank sums 7 for two rectangles (bound 4, product 10) and none below 8 on the grid. Data at cannot separate from anything, since is not there.
Conjecture 4.15. (network rank of the level; engine2-decorrelated.md Conjecture 8.1) For every field and alphabet of size , every family of tensors with in which each is a row network or a column network of cost satisfies . The weakest new statement would be , or a decomposition with maximum cost at most . Its form is for all correlated decompositions.
A proof cannot be a rank bound on a node-locally processed flattening (Theorem 4.13); it must use that a row network’s three cuts come from one triple of bonds.
Relation to Majdoddin and to Dias–Lima. Majdoddin [43] defines a rewrite-and-merge class: per-block exact identities on configurations of edges, the terms being all products of one piece per (configuration, block) pair (his (L2)), and merges under which every configuration meets at most two groups (his (L3)). He proves that every grid algorithm of the class has exponent at least per edge bit (his Theorem 4.13 and Corollary 4.19), and at least for two balanced homogeneous merges (Theorem 4.12). For product terms this contains Theorem 4.6 with the exact constant and without assuming , and Theorem 4.1 is the rectangle case of his two-merge floor (Proposition 4.8), itself the counterpart of [A]’s Appendix H. He notes that non-product groupings of terms lie outside his class (Remark 4.5), calls configurations that meet three or more groups of a merge “the open door”, and writes that “for the full model of Signed Network Sums no barrier is known” (§4.8). The correlated decompositions of this section are such non-product groupings: an arbitrary family in which each term is charged its cheapest pairwise network in the row or the column grouping. (A cost model that charged a hyperedge less than its cheapest pairwise simulation would escape ours.) ?? 4.9–4.12 are, to our knowledge, the first bounds there; they are weaker ( of 9 on the level, on full levels) and restricted to the two grid merges, and Theorem 4.15 is the grid case of his open door (his Open Problem 5). The step that makes them possible is the diagonal contraction, which bounds of each term and so needs no mixed term. His Example 4.10 (flattening inequalities do not show that three-cell configurations do not trade) and Theorem 4.13 (flattening certificates stop at 8) are parallel observations in the two models. For [O]’s interpolation algorithm, Dias and Lima [29] prove treewidth barriers for every clause-product scheme; they state that the clause-product form of [O]’s algorithm is an instance of their Definition 5.1, so the -template of Section 5 is a special case, and we compare the bounds there. Neither paper treats a counting problem other than (Max-)SAT, and neither has a Lean development of its barriers.
What the caps mean for the engine
With the ceiling of [A]’s framework is (rate.md §0, on paper), and with this is . For the permanent the bound is sharper: assignment-count networks have engine exponent at least , with [A]’s published , for every (wild-ideas.md F3, on paper). Table 1 collects the mechanisms.
| mechanism | cap | status |
| pieces, any family ([A], Def. 7) | Lean (rank form); [A], App. H; [43] | |
| graded two-order pieces | Lean (counts), paper | |
| two groupings, product terms | paper; exact in [43], Thm. 4.13 | |
| any family of groupings, adaptive or random | paper | |
| gadget recursions, groupings | paper | |
| correlated, two rectangles / / | , , | Lean (rank form) |
| correlated, full levels | , | paper |
| tensor rank, transforms, characteristic , trees | or unchanged | paper |
Table 1. Caps on the rate. “Rank form” means that Lean bounds flattening ranks and the step to costs is on paper. The two correlated rows are the only ones whose terms need not be products.
OpenAI's M0-template is tight at
In this section we bound every instance of [O]’s -template, whatever the matrix (commuting with the swaps or not), the label set and the number of points. The template needs with (T1) every row of in the row space of the measurement matrix, so that , and the support condition (T2). The core is a triangular submatrix of .
Theorem 5.1. (EthFollowup.Barriers.Triangular.triangular_rank_bound_hamming, EthFollowup.Barriers.Triangular.independent_sets_rank_bound; machine-checked) Let be a field, a finite set of coordinates and .9 Let satisfy , let , and let satisfy (T2) in the form . Then
For any distance on the labels and sets at distance at least , if , then .
Proof. Order the set on the left by non-increasing . For before or equal to in , , so and by (T2). Hence is triangular with unit diagonal. □
Proposition 5.2. (on paper; parity-barrier.md Corollary 1.1, Theorem 2, §5) On [O]’s full label space with every label used equally often, the measurement fraction satisfies , so when ; this matches [O]’s window up to a factor at most . Modulo the Arora–Rao–Vazirani structure theorem [1], for , any schedules obeying the group bound, any coordinate layout and any satisfying (T2), on -linked bounded-occurrence formulas, implies . Hence every instance of the template costs on such formulas.
So within Engine I the main-text template is tight up to a factor , and neither a non-commuting nor structured or sparse labels help. This is a statement about [O]’s construction as published. For the clause-product form of the interpolation algorithm in general, Dias and Lima [29] prove at treewidth , and with high probability on random 3-CNF, in a cost model that charges whatever the preprint pays (their Theorems 8.1 and 8.3). They state that the clause-product form of [O]’s algorithm is an instance of their scheme (their §5), so the template is a special case, and Theorem 5.2 is a stronger bound for it, modulo the Arora–Rao–Vazirani theorem, on linked bounded-occurrence formulas. We have not compared linked formulas with their random inputs, and we do not claim to close the gap that they leave open on expanding inputs (their §9). Whether the general interface def:layout, in which the measurement part may vary with the point in a non-polynomial way, costs as the template does is open: it is strictly weaker as a constraint (“runs instead of windows” reach at for all , where every needs at ), but in the regime the engine needs the gain is a constant factor (parity-barrier.md §5 and §7).
Remark 5.3. (checked numerically) At a non-commuting beats every commuting one, with against 10 (floating-point search), and the general interface was checked exactly for . Neither affects the asymptotic bound of Theorem 5.2.
Three linear encodings of Hamiltonicity have size floors
In this section we treat three encodings that we built for Hamiltonian cycles and that would have extended the sparse results to wider classes. These are barriers for our linear encodings (hamiltonicity.md §8, linear-encoding-2.md, derandomization.md), not for the engines. All three are machine-checked without paper hypotheses.
Colouring filters. Cut&Count [24] extracts connectivity from a sum over consistent colourings with local weights; such a filter gives the parity of #HC, and the question is whether it can be exact.
Theorem 6.1. (EthFollowup.Barriers.ColouringGraph.colouring_barrier_graph; machine-checked) Let be a field of characteristic 0, with , and a vertex of .10 For a 2-factor let its value be over the components of , the root’s. If for every graph on there is with (ExactFilter with root colour 0; may depend on ), then .
Proof sketch. The -cycle has one 2-factor, which is Hamiltonian, so . For the graph , with the root in , has one 2-factor, which is disconnected, so its value must be 0. This is hvan, and Theorem 6.2 applies: grouping the by value gives an exponential polynomial with at most bases and positive multiplicities that vanishes at consecutive integers, which the Vandermonde matrix forbids if . □
Theorem 6.2. (EthFollowup.Barriers.Colouring.colouring_barrier, EthFollowup.Barriers.Colouring.colouring_threshold_upper; machine-checked) Let be a field of characteristic 0 and with for some (module ColouringBarrier). If (hypothesis hvan) for every with , then . Conversely, for a primitive -th root of unity , for . The hypothesis hvan is derived from the graphs inside the proof of Theorem 6.1.
So exact colouring filters need about bits per vertex, and the threshold lies in ; the modulo-2 filter escapes because positive multiplicities vanish only in small characteristic. Vertex-dependent weights are not covered.
Turn labellings. A turn is a triple of a vertex and two distinct neighbours. A labelling of the turns of by is good if every directed simple cycle of has nonzero label sum; is the least such . A good labelling gives a signed CNF for with variables on bounded-degree graphs (linear-encoding-2.md Theorem G, on paper), so would have been a route to #HC on all bounded-degree graphs.
Theorem 6.3. (Kstar.theoremL, Kstar.theoremL_log; machine-checked) Let be the crossing grid on vertices (row paths, column paths and rungs; maximum degree 3), given as the Boolean adjacency .11 If assigns a vector in to every triple of vertices and every list of vertices that is a directed simple cycle of (isDirCycle) has nonzero label sum, then ; for , . So .
The proof lifts a balanced 24-cycle of to every choice of four rows and four columns and replaces the Kővári–Sós–Turán theorem [36] of the paper proof by an iterated pigeonhole. The note’s constant via [36] is , and every bounded-degree expander contains with as a minor [20] (kstar.md §3, on paper). So the gap gadget cannot be made smaller than on expanders by turn labels.
Residues. Deterministic decision from residues of #HC modulo small needs a query whose residue is nonzero. For a finite family of edge sets (the Hamiltonian cycles) put and .
Theorem 6.4. (EthFollowup.Barriers.Derand.tp_le_log_of_nonempty, EthFollowup.Barriers.Derand.tq_deleted_eq_contains, EthFollowup.Barriers.Derand.support_query_eq_zero; machine-checked) Let be a type with decidable equality and a finite family of finite subsets of .12 Then . If for all , then for every with and every , . For every prime and nonempty , .
Proof sketch. The duality is inclusion–exclusion and Möbius inversion between deletion counts and containment counts. For the support statement, . For the bound, fix an inclusion-maximal and count the sets modulo : the resulting function is nonzero and orthogonal to all monomials of degree below , so it has at least nonzero values, and . □
So every restriction, weighted or CNF-constrained query of support below returns 0, and restriction search is deterministic exactly when ; the bound says that the obstruction is the only one. A black-box algorithm that sees only through weighted counts modulo needs at least queries (derandomization.md Theorem 2, via the Davenport constant, on paper).
Nine problems out of reach, and why
In this section we map nine natural targets after sparse #HC. Table 2 gives, for each, the best known bound, the reason the engines’ guarantees do not reach it, and what is proved. “Out of reach” always means: no network or recursion of the analysed kinds, not hardness. We then give the two problems with Lean content a paragraph each.
The iterated product. Exact , and a deterministic prime finder by this route, need to isolate , and the only identities we know do so through a -fold product with (prime-finding.md §4, on paper). In the parity note [63] we proved Theorem 7.1 and the first statement of Theorem 7.2 (rank_prodMat_pow); we restate them here. The second statement of Theorem 7.2 (rank_prodMatFixed_1e) is new here.
Theorem 7.1. (EthFollowup.IterProd.BTree.cost_ge_entropy, EthFollowup.IterProd.BTree.cost_ge_equal; machine-checked) For every binary tree with positive integer leaf weights and , where ,13 we have . If all leaves have weight , then .
Theorem 7.2. (EthFollowup.IterProd.rank_prodMatFixed_1e, EthFollowup.IterProd.rank_prodMat_pow; machine-checked) Over , the matrix with rows , columns and entries has rank . With fixed, the matrix over any finite sets of rows and columns has rank at most .
So in a tree verifier the cut above a node carries at least bits (?? 3.1?? 7.2, the link on paper), , and no tree shape helps. A bound for all verifiers is a different matter.
Proposition 7.3. (on paper; iterated-product.md §5) [A]’s engine simulates every Boolean circuit of size at most by a parsimonious label system with . Hence a lower bound for all parsimonious verifiers of would be a superlinear lower bound on the circuit size of an explicit predicate, for which no superlinear bound is known.
Proposition 7.4. (on paper, oracle model; prime-finding.md §3(c)) An adversary consistent with the prime gap bound of [3] and the other known density theorems can make every count mod queried by a deterministic strategy vanish as long as consecutive endpoints are far apart; against it, at least queries are needed.
| problem | best known | why out of reach | proved |
| dense #HC, TSP | [5, 32]; [54]; decision, randomised [8]; directed #HC [39] | permutation witness; vertex-local networks have ; even is fatal at | Lean: ?? 3.1?? 3.4; paper: ?? 2.4?? 3.5 |
| permanent, #PM, hafnian | [51]; [39]; over any commutative ring [38] | bits in row-local networks; algebras of dimension ; #SAT encodings need variables; char. savings die at | Lean: ?? 3.2?? 3.3?? 3.7?? 3.8; paper: ?? 3.9?? 3.13, Theorem 3.6 |
| chromatic number | [13]; -colouring randomised [68, 48]; under the asymptotic rank conjecture [10] | growing needs variables; dense encodings need ; inclusion–exclusion over sets is not a network | none; heuristic rank count (ambitious-targets.md §2.4) |
| Subset Sum, Partition | [33]; space [52], improved [44] | each party’s partial sum carries bits | paper: Theorem 7.5 |
| dense Max-Cut, Max-2-SAT | [67] | edge terms; the pair interaction has rank , so on dense graphs | none; one-line rank count |
| directed HC, dense | ; counting [39] | as dense #HC; sparse digraphs are done (theoremDHC) | as dense #HC |
| prime finding | [37]; parity on short intervals [55] | residues of cheap counts can all vanish; exact isolation needs -fold products, | Lean: ?? 7.1?? 7.2; paper: ?? 7.3?? 7.4 |
| exact | [37]; [27] | product-tree verifiers have , giving | as prime finding; Theorem 8.3 |
| Tutte off | [12] | boundary states are all set partitions, rank Bell; interpolation needs hyperbolas | paper: Theorem 3.10; Theorem 3.12 |
caption: Nine problems out of reach of the engines’ guarantees. “Lean” cites machine-checked steps; the step from a network to a matrix is on paper throughout. Best known bounds are deterministic unless marked.
:::
Subset Sum. The natural network gives each of clusters its items privately and shares partial sums of bits along a tree.
Proposition 7.5. (on paper; ambitious-targets.md §2.5) For items with -bit weights, a clustered partial-sum network has engine exponent about in case (i) of Lemma 8. Beating needs , where the dynamic programme is already faster; case (ii) and [O]’s model fail similarly. So no clustered-partial-sum network in either engine beats at .
What would have to change, and why proving that it will not is out of reach
In this section we list the five changes that would move a problem of Table 2 into reach, say why an unconditional proof that none of them exists is beyond current techniques, and state the open questions precisely.
Five changes.
A decomposition of the level with (Theorem 4.15 false), or more generally a correlated decomposition with on full levels. This is the grid-level case of the “open door” of [43 §4.8 and Open Problem 5].
Pieces outside the graded two-order family with : a statement of the Hurwitz–Hrubeš–Wigderson–Yehudayoff type [34], since would give sum-of-squares formulas of nearly linear size.
(iii) An algorithm for -cliques that is not a sum of clique-type sub-instances, for example one that eliminates variables or adapts to the tables.
(iv) For prime counting, a parsimonious verifier of a -fold product with shared bits (Theorem 8.3).
(v) For the Tutte polynomial, a sum of networks over many different clusterings, or skeletons that depend on private edges.
The meta-barrier. For (iii) the obstacle to an unconditional negative answer is the following. We call an algorithm for the -clique oblivious algebraic if it is a straight-line program over in the table entries, that is, an arithmetic circuit whose sequence of operations is fixed in advance and does not depend on the entries; its size is its number of operations. Let and , the value of the -clique as a polynomial in the table entries: it is set-multilinear of degree in variables with coefficients, and its cost equals .
Proposition 8.1. (on paper; engine2-algebraic.md M6.1) Take , so that , and index the family by : for between consecutive values of , which differ by a factor , take for the largest with , padded with unused variables. Work over .
(i) The family lies in VNP by Valiant’s criterion [64] ([17 Proposition 2.20]): has degree and variables, both polynomial in , and its coefficient function is 0/1 and computable in polynomial time (it checks that the indices of a monomial agree on every edge).
(ii) If, for all sufficiently large , every oblivious algebraic algorithm that computes has size at least with for a function , then the size is at least , superpolynomial in , so the family is not in VP and . With this covers “no oblivious algebraic algorithm beats ”.
(iii) The value is computable in time , so the same lower bound for Boolean circuits would put a quasi-polynomial-time function outside P/poly, that is , and hence ; against uniform algorithms it would be a superpolynomial time lower bound for an explicit problem in quasi-polynomial time, of a kind known today only from diagonalisation.
This is not a theorem about any existing algorithm. It says that the query bound is the only unconditional lower bound on available without a breakthrough in algebraic or Boolean circuit complexity, so barriers must be proved for restricted classes, as in § 4. [A]’s recursion is an oblivious algebraic algorithm in this sense: each modified table is a polynomial in the tables of the nodes it absorbs, with coefficients independent of the entries; its products are over disjoint node sets; its sums are over index sets fixed in advance; and the groupings it searches for depend only on the skeleton, not on the entries. Majorddin makes the fixed- form of this observation: at , a bound above “would be a superlinear lower bound for an explicit degree-4 polynomial, which is out of reach” [43 Remark 2.9].
Proposition 8.2. (on paper; engine2-algebraic.md M6.2) Lemma 8(i) of [A], with the accounting of the proof of its Theorem A(c) (, , ), reduces #3-SAT on a bounded-occurrence formula with variables and clauses to one -clique with , at overhead . With the overhead is and , so would give bounded-occurrence #3-SAT in . So the hypothesis , “bounded-occurrence #3-SAT needs ,” implies for all algorithms. is consistent with everything known but is not a standard hypothesis.
Any with works; the constraint is what rules out larger in case (i) of Lemma 8.
For (iv). Theorem 7.3 plays the role of the meta-barrier: an bound for all verifiers would be a superlinear circuit lower bound for an explicit function.
Open questions. We state them as precisely as we can. Theorem 4.15 (the level) and Theorem 3.6 (Model V) are above.
Question 8.3. (-party verification of a product: iterated-product.md §6) The witness with and is distributed, as the designer likes, among parties
holding at most bits each. Auxiliary labels are allowed, every label is seen by exactly two parties, each party accepts or rejects its own labels, and exactly one accepting labelling exists per witness with and none otherwise. What is the least total of label bits? Known: ; tree verifiers have (Theorem 7.1). would give exact and deterministic prime finding in .
Question 8.4. (the pieces constant; rho-lower-bound.md §7) Let be the infimum of the for which pieces with parameters exist for some . Is ? Proved: (Theorem 4.1); for graded two-order pieces with top-pole pairing on spaces of square-root growth, in particular all -cofinite vertex operator algebras (Theorem 4.4). Open: the zero-mode loophole (pairing in a lower pole), two-order structures of growth below , and true ranks below the certified counts.
Conjecture 8.5. (Catalan rank on ; tutte-plane.md Lemma 3.2(c)) For every and every , the acyclic gluing matrix on the partitions of has rank . Proved: rank at most . Checked: , and at least at (Theorem 3.12).
Question 8.6. (the two Tutte loopholes; tutte-plane.md §5) Does Theorem 3.10 hold for sums of vertex-local networks with different clusterings, and for skeletons that depend on private edges?
The Lean development
In this section we list the modules, the cited theorems and the trusted base. The development is the directory lean/EthFollowup/Barriers of the public repository [60], written in Lean 4 [26] on Mathlib [56] only, toolchain v4.34.1, Mathlib commit d13f23b. It does not use [A]’s or [O]’s developments. In this paper the macro for Lean names is reserved for theorems of this directory; names from other developments (groupingExplicit, theoremDHC, …) are set in plain typewriter type.
| module | content | lines |
RankBounds | cut lemma, subadditivity, Model R and tree summations, pieces | 373 |
RowCut | Laplace expansion, row-cut rank | 312 |
AlgebraRank | algebra dimension | 168 |
PermModP | per for low rank in characteristic | 135 |
SpreadLemma | spread inequality for graded two-order pieces | 123 |
DecorrelatedRank | two rectangles, | 126 |
DecorrelatedGrid32 | grid, ; row-local no-go | 260 |
DecorrelatedGrid33 | lossy flattening lemma; level, | 286 |
TriangularRank | triangular rank bound for the -template | 121 |
ColouringBarrier | colouring barrier, polynomial form, converse | 114 |
ColouringBarrierGraph | colouring barrier for graphs | 566 |
KstarBasic, KstarLower | turn labellings, Theorem L | 53, 768 |
Derand | duality, support lemma, | 573 |
IterProdTree, IterProdCutRank | product trees, rank of the product indicator | 142, 148 |
| total (16 modules) | 4268 |
Table 3. The modules of lean/EthFollowup/Barriers, with line counts (wc -l).
Cited theorems. We cite 45 theorems, all in this directory: from RankBounds twelve (?? 3.1?? 3.3?? 3.4?? 4.1?? 4.2), from RowCut three (Theorem 3.2), from AlgebraRank two (Theorem 3.7), from PermModP one (Theorem 3.8), from SpreadLemma three (Theorem 4.3), from DecorrelatedRank two (Theorem 4.9), from DecorrelatedGrid32 four (Theorem 4.10), from DecorrelatedGrid33 four (Theorem 4.11), from TriangularRank two (Theorem 5.1), from the two colouring modules three (?? 6.1?? 6.2), from KstarLower two (Theorem 6.3), from Derand three (Theorem 6.4), and from the two IterProd modules four (?? 7.1?? 7.2). The repository README counts 38 theorems for an earlier state; the number here is what this paper cites.
Ten statements verbatim. The following are verbatim from the source, up to line breaks; we render Unicode symbols as mathematics and omit the proofs. Section variables are recalled in comments.
-- RowCut: variable {K : Type*} [Field K] {ι : Type*} [Fintype ι] [DecidableEq ι]
-- (I : Finset ι)
theorem rowCut_rank : (rowCutMatrix (K := K) I).rank = (Fintype.card ι).choose I.card
-- RankBounds
theorem modelR_bound_nlogn {J : Type*} (cls : Finset J) (n s U : ℕ) (k w : J → ℕ)
(hk1 : ∀ j ∈ cls, 1 ≤ k j) (hks : ∀ j ∈ cls, k j ≤ s)
(hsum : ∑ j ∈ cls, k j = n)
(hrank : ∀ j ∈ cls, n.choose (k j) ≤ 2 ^ w j) (hU : ∑ j ∈ cls, w j ≤ U) :
(n : ℝ) * Real.logb 2 ((n : ℝ) / s) ≤ ∑ j ∈ cls, Real.logb 2 (n.choose (k j)) ∧
∑ j ∈ cls, Real.logb 2 (n.choose (k j)) ≤ U
-- AlgebraRank: variable {K : Type*} [Field K] {R : Type*} [Ring R] [Algebra K R]
theorem algebra_rank_half {n : ℕ} [FiniteDimensional K R] (φ : R →ₗ[K] K)
(r : Fin n → Fin n → R)
(h : ∀ f, φ (word r f) = if Function.Bijective f then 1 else 0) :
n.choose (n / 2) ≤ Module.finrank K R
-- SpreadLemma: variable ... (D : ℤ → ℕ) ...
theorem spread_slice_zero (hn : ℕ) :
2 * Real.logb 2 (D (2 * hn)) ≤
(Nat.clog 2 (Rrow D hn (range (2 * hn + 1)) (fun i => 0 - hn + i)) : ℝ) +
Nat.clog 2 (Rcol D hn (range (2 * hn + 1)) (fun i => 0 - hn + i))
-- DecorrelatedRank (namespace Decorrelated):
-- variable {K : Type*} [Field K] {α : Type*} [Fintype α] [DecidableEq α]
theorem rankSum_ge [Nonempty α] {ι : Type*} (s : Finset ι) (T : ι → Tensor2 K α)
(hsum : ∑ t ∈ s, T t = FF) :
Fintype.card α ^ 2 ≤ ∑ t ∈ s, min (rowFlat (T t)).rank (colFlat (T t)).rank
-- DecorrelatedGrid33 (namespace Grid33): same variables; L = Fin 18 × Bool (edge, end)
theorem rankSum_ge [Nonempty α] {ι : Type*} (s : Finset ι) (T : ι → Tensor K L α)
(hsum : ∑ t ∈ s, T t = G) :
Fintype.card α ^ 8 ≤ ∑ t ∈ s, min (flat Srow (T t)).rank (flat Scol (T t)).rank
-- TriangularRank: variable {K : Type*} [Field K] {B : Type*} [Fintype B] [DecidableEq B]
theorem triangular_rank_bound_hamming {Q r : ℕ} (a d : B → (Fin Q → Fin r))
(φ : (Fin Q → Fin r) → ℝ) (hφ : ∀ x y, |φ x - φ y| ≤ hammingDist x y)
(R : ℕ) (M : Matrix B B K)
(hM : ∀ u w, M u w ≠ 0 → hammingDist (d u) (a w) + 1 ≤ R) :
(univ.filter fun u => (R : ℝ) ≤ φ (d u) - φ (a u)).card ≤ (1 - M).rank
-- KstarLower (namespace Kstar)
theorem theoremL {t k : ℕ}
(F : Fin (2 * t * t) → Fin (2 * t * t) → Fin (2 * t * t) → (Fin k → ZMod 2))
(hF : Good (gridAdj t) F) : t < 2 ^ (20 * k + 10)
-- IterProdTree (namespace EthFollowup.IterProdTree)
theorem cost_ge_equal (T : BTree) (w : ℕ) (hw : 0 < w) (hT : allLeaves w T) :
(leaves T : ℝ) * w * logb 2 (leaves T) ≤ cost T
-- ColouringBarrier: variable {n : ℕ} {K : Type*} [Field K]
theorem colouring_barrier_graph [CharZero K] {q : ℕ} (hq : 0 < q) (z : Fin q → K)
(r : Fin n) (hex : ExactFilter z r ⟨0, hq⟩) : n ≤ q + 4
The definitions these use are shared and stated in the files: rowCutMatrix and joinMat (the permanent of ), word (the ordered product ), Rrow, Rcol, FF, rowFlat, colFlat, the leg list edges, graphT, flat, Srow, Scol, Good, isDirCycle, gridAdj, BTree, cost, leaves, allLeaves, ExactFilter, compValue, and the 2-factor and Hamiltonian-cycle sets of EthFollowup.HamiltonianParity. Axioms. #print axioms reports propext, Classical.choice and Quot.sound, or a subset, for all 251 theorem declarations of the directory (audit of 5 November 2026). No module contains sorry, native_decide or a new axiom. All 16 modules have build artefacts; the axiom audit imports all of them in one file.
Hypotheses that stand for paper steps. In modelR_bound_nlogn, hrank is the cut lemma applied to the row cut of a given network and hU the pair count (whose counting step is sum_crossing_le_total); in treeSkeleton_bound, hrank is the cut lemma with the vertex-cut rank. The hypothesis hvan of Colouring.colouring_barrier is discharged in Lean by colouring_barrier_graph. The lean statements on correlated decompositions bound flattening ranks; that a network of cost has flattening rank at most is on paper.
What is not formalised. The network models of Theorem 2.2 and the step from a network to a factorised matrix; Model V beyond tree summation; the Tutte barrier; the lossy lemma for general configurations with pairings and Theorem 4.12; the grouping caps; the template corollaries; the meta-barrier. Scratch files of the repository (lean/EthFollowup/Scratch) contain checks by #eval and decide on instances, for example the product decomposition of two rectangles with rank sum 10; they are not part of the audited development and no statement of this paper rests on them.
Related work
We organise related work by idea: rank methods for restricted algebraic models, tensor-network complexity, connection matrices and the Tutte plane, exact algorithms for the dense problems, the recent follow-ups to the two refutations, and the labs’ own limits.
Rank methods for restricted algebraic models. Nisan [46] characterised the size of noncommutative algebraic branching programs by the ranks of partial-derivative matrices along the variable order, and proved exponential lower bounds for the permanent and determinant there. Hrubeš, Wigderson and Yehudayoff [34] reduced lower bounds for noncommutative circuits to the sum-of-squares problem; Raz [49] proved superpolynomial bounds for multilinear formulas; Limaye, Srinivasan and Tavenas [40] for constant-depth circuits; and Bhargava and Tengse [6] relate partial derivatives to commutative ROABPs. Closest to our Model R bound is Nisan’s. In contrast, our cuts are cuts of a network, and locality of the node tables replaces the variable order.
Tensor-network complexity. Austrin, Kaski and Kubjas [2] studied the cost of evaluating multilinear maps by tensor networks. Christandl, Vrana and Zuiddam built the quantum functionals, monotone under restriction and additive under direct sums [19], and computed asymptotic ranks of graph tensors [18]; the complete-graph tensor is exactly the clique of [A]’s recursion. Majdoddin [43] uses these functionals to prove that configurations on at most three cells of two merges cannot trade cost (his Lemma 4.11), and shows that flattening inequalities alone cannot prove this (his Example 4.10), in a model where terms are products. In contrast, our lower bounds are for sums of networks whose terms need not be products, and the level shows where flattening certificates, and these functionals with straddling legs, stop (Theorem 4.13).
Connection matrices and the Tutte plane. Lindström [41] and Wilf [66] factorised meet matrices on lattices; Freedman, Lovász and Schrijver [30] and Lovász [42] related connection ranks to graph parameters. Jaeger, Vertigan and Welsh [35] classified the easy points of the Tutte plane; Dell, Husfeldt, Marx, Taslaman and Wahlén [28] and Brand, Dell and Roth [16] proved #ETH lower bounds across it; Björklund, Husfeldt, Kaski and Koivisto [12] compute it in . Rank methods for treewidth dynamic programmes are due to Cygan, Kratsch and Nederlof [23], Curticapean, Lindzey and Nederlof [22], and, for counting connected spanning edge sets modulo , Groenland, Mannens, Nederlof and Szilágyi [31]. In contrast, we bound the shared bits of networks, not the states of a decomposition, and the bound is unconditional within the model.
Exact algorithms for the dense problems. For TSP and #HC: Bellman and Held–Karp [5, 32], Björklund [8, 9], Björklund and Husfeldt for the parity [11], Stoian [54], and Li [39], who also treats the hafnian. For the permanent: Ryser [51], Curticapean’s algorithm with over every commutative ring (arXiv, 2 November 2026; Binet–Minc with dynamic programming) [38], which answers Knuth’s question and is independent of the engines, Valiant’s #P-completeness [65], Barvinok for fixed rank [4], Björklund, Husfeldt and Lyckberg modulo prime powers [14], and Björklund and Williams over finite rings [15]. For colouring: Björklund, Husfeldt and Koivisto [13], Zamir [68] and Pratt [48], and the conditional bound of [10]. For Max-Cut, Williams [67]; for Subset Sum, Horowitz–Sahni [33], Schroeppel–Shamir [52] and Nederlof–Węgrzycki [44]; for , Lagarias–Odlyzko [37], Déléglise–Rivoal [27] and Tao–Croot–Helfgott [55]. In contrast, we give no algorithm; we explain why the engines’ guarantees stop short of these bounds.
Barriers for the SAT algorithms themselves. Closest to our work are two papers on the SAT algorithms. Majdoddin [43] computes explicit crossover points of [A]’s recursion (and compares them with our crossover note) and proves the class barrier discussed in § 4.4: every grid algorithm of his rewrite-and-merge class, the recursion as written included, has exponent at least per edge (his Theorem 4.13 and Corollary 4.19). Dias and Lima [29] extract the constants of [O]’s tensor-contraction proof and prove treewidth barriers for its clause-product scheme (their Theorems 8.1 and 8.3). Our product-term cap (Theorem 4.6) is an independent and weaker version of Majdoddin’s, from a note dated 29 October, one day before his paper; neither paper cites our barrier notes. In contrast, we bound decompositions whose terms are not products and the counting problems beyond (Max-)SAT, and our rank statements are machine-checked.
The October–November 2026 follow-ups. Rudich and Rousseau [50] and Shunia [53] factor with the engines. De Brito [25] proves, after [A]’s Appendix H, a rank floor for families of the shape of [A]’s Theorem B, which closes the growth case for that shape; Majdoddin [43 Proposition 4.24] proves for every concave profile in that shape. Our Corollary (the law , note of 28 October) is dated before both and left open; outside the shape the question remains open (Theorem 8.4). Bhattacharjee [7] states (his Theorem 7.10) that the Tutte polynomial on is computable for bounded-degree graphs and integer by a white-box extension of [O]’s algorithm; we have not checked the proof. It was public (29 October) before our note on the Tutte plane (30 October), whose positive part we do not claim here. Nguyen [45] (2 November) counts binary CSP solutions on bounded-degree classes in , an independent instance of the same domain-uniform bound, with Lean on imported engine theorems. None of the three cites our notes. In contrast to these three, which are positive or concern one shape of pieces, we bound what the engines do not give.
The labs’ own limits. [A] and [O] name what their theorems do not refute (§ 2): Orthogonal Vectors, CNF-SAT of unbounded width, and transfer under polynomial-time reductions. In contrast, our barriers are about problems that do reduce to bounded-width counting, but only with at least of order variables or shared bits in the models we analyse.
Limitations
Every barrier is for a named model. Model R(s), Model V(s) with a fixed skeleton, pieces with certified costs, min-over-groupings recursions with pieces, row and column network decompositions, [O]’s -template, tree verifiers, clustered partial-sum networks, substitution algebras and plain #SAT encodings. None is about all algorithms.
The general model admits no unconditional barrier (Theorem 3.13), and an unconditional cap on oblivious algorithms would separate VP from VNP (Theorem 8.1).
The Tutte barrier has two loopholes: sums over different clusterings, and skeletons that depend on private edges (Theorem 8.6).
Much is on paper. ?? 4.12?? 4.13, the covering bound (Theorem 4.7), the template corollaries (Theorem 5.2, modulo the Arora–Rao–Vazirani theorem), the Tutte barrier and the meta-barrier are proved on paper only.
The Lean statements are about ranks. The links “cost is at least of a flattening rank” and “a network gives a factorised matrix” are on paper, as are the hypotheses
hrankandhU.Numerics are not evidence about . Data at cannot separate from anything (Theorem 4.14).
Scope of the caps. They cover [A]’s framework. For [O]’s engine they cover the -template of its main text (Section 5), not the general interface, which Dias and Lima bound by [29], and not its Engine II, whose bound we have not verified.
The product-term caps are not the best known. Majdoddin’s bounds for product terms [43] have the exact constant, need no squaring assumption and cover more configurations; ours are independent and weaker. The correlated bounds are restricted to the two grid merges, and they are weaker than the conjectured .
No human has checked the work. The Lean code and this text were written with AI assistance. The barriers are unconditional statements about their models; they do not depend on the refutations being correct, but their interest does.
Conclusion
We have shown that the two counting engines meet the same wall from two sides: dense problems force at least of order shared bits in every local network we can analyse, and every product-term recursion converts shared bits into time at a rate no better than (Theorem 4.6, and sharper [43 §4.8], Theorem 4.13), while correlated decompositions of full grid levels do no better than (Theorem 4.12). The paper is a step towards, not a proof of, the statement that the engines do not reach dense counting; a proof of that statement even for oblivious algebraic algorithms would separate VP from VNP (Theorem 8.1). One instance is open and small: the grid level, where is proved and is conjectured, a case of the “open door” of [43 §4.8]. The cheapest experiment that could change the picture is a decomposition of that level with maximum cost at most . An interesting direction on the number-theoretic side is the -party verification of a product (Theorem 8.3), whose answer would decide whether exact is within the engines’ reach.
Acknowledgements
This work was done with AI assistance (Claude Code, Anthropic): the research notes, the Lean development, the numerical checks and the text were produced in sessions with Claude Code. The Lean theorems are checked by the Lean kernel; everything else awaits human expert review. Responsibility for any errors rests with the author.
References
References
- [1]Sanjeev Arora, Satish Rao, and Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning, J. ACM 56 (2009), no. 2, Art. 5, doi:10.1145/1502793.1502794.DOI
- [2]Per Austrin, Petteri Kaski, and Kaie Kubjas, Tensor network complexity of multilinear maps, Theory Comput. 18 (2022), Art. 16, doi:10.4086/toc.2022.v18a016.
- [3]Roger C. Baker, Glyn Harman, and János Pintz, The difference between consecutive primes, II, Proc. London Math. Soc. (3) 83 (2001), no. 3, 532–562, doi:10.1112/plms/83.3.532.
- [4]Alexander I. Barvinok, Two algorithmic results for the traveling salesman problem, Math. Oper. Res. 21 (1996), no. 1, 65–84, doi:10.1287/moor.21.1.65.DOI
- [5]Richard Bellman, Dynamic programming treatment of the travelling salesman problem, J. ACM 9 (1962), no. 1, 61–63.DOI
- [6]Vishwas Bhargava and Anamay Tengse, Explicit commutative ROABPs from partial derivatives, Proc. 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), LIPIcs, vol. 323, 2024, arXiv:2407.10143, pp. 10:1–10:15.arxiv.org/abs/2407.10143
- [7]Deep Bhattacharjee, Subexponential weighted counting and exact optimisation, Hexagon preprint hexagon:2610.00594v1, 29 October 2026, https://hexagonmath.org/abs/2610.00594, 2026.
- [8]Andreas Björklund, Determinant sums for undirected Hamiltonicity, SIAM J. Comput. 43 (2014), no. 1, 280–299, Preliminary version in FOCS 2010.
- [9]———, Below all subsets for some permutational counting problems, Proc. 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), LIPIcs, vol. 53, 2016, pp. 17:1–17:11.arxiv.org/abs/1211.0391
- [10]Andreas Björklund, Radu Curticapean, Thore Husfeldt, Petteri Kaski, and Kevin Pratt, Fast deterministic chromatic number under the asymptotic rank conjecture, Proc. 36th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2025, arXiv:2404.04987; doi:10.1137/1.9781611978322.91, pp. 2804–2818.DOI
- [11]Andreas Björklund and Thore Husfeldt, The parity of directed Hamiltonian cycles, Proc. 54th IEEE Symposium on Foundations of Computer Science (FOCS), 2013, pp. 727–735.arxiv.org/abs/1301.7250
- [12]Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto, Computing the Tutte polynomial in vertex-exponential time, Proc. 49th IEEE Symposium on Foundations of Computer Science (FOCS), 2008, pp. 677–686.arxiv.org/abs/0711.2585
- [13]Andreas Björklund, Thore Husfeldt, and Mikko Koivisto, Set partitioning via inclusion-exclusion, SIAM J. Comput. 39 (2009), no. 2, 546–563, doi:10.1137/070683933.DOI
- [14]Andreas Björklund, Thore Husfeldt, and Isak Lyckberg, Computing the permanent modulo a prime power, Inform. Process. Lett. 125 (2017), 20–25, doi:10.1016/j.ipl.2017.04.015.DOI
- [15]Andreas Björklund and Ryan Williams, Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors, Proc. 46th International Colloquium on Automata, Languages, and Programming (ICALP), LIPIcs, vol. 132, 2019, pp. 25:1–25:14.
- [16]Cornelius Brand, Holger Dell, and Marc Roth, Fine-grained dichotomies for the Tutte plane and Boolean #CSP, Algorithmica 81 (2019), no. 2, 541–556, Preliminary version in ICPC 2016; arXiv:1606.06581.arxiv.org/abs/1606.06581
- [17]Peter Bürgisser, Completeness and reduction in algebraic complexity theory, Algorithms and Computation in Mathematics, vol. 7, Springer, 2000, doi:10.1007/978-3-662-04179-6.DOI
- [18]Matthias Christandl, Peter Vrana, and Jeroen Zuiddam, Asymptotic tensor rank of graph tensors: beyond matrix multiplication, Comput. Complexity 28 (2019), no. 1, 57–111, doi:10.1007/s00037-018-0172-8.DOI
- [19]———, Universal points in the asymptotic spectrum of tensors, J. Amer. Math. Soc. 36 (2023), no. 1, 31–79, Preliminary version in STOC 2018; doi:10.1090/jams/996.
- [20]Julia Chuzhoy and Rachit Nimavat, Large minors in expanders, arXiv:1901.09349, 2019.arxiv.org/abs/1901.09349
- [21]Claude (Anthropic), A 2^{o(n)} time algorithm for 3-SAT, Preprint dated 26 October 2026. Paper and Lean formalisation in the repository https://github.com/anthropics/formal-math, folder eth; we use commit 16a5ce41304fcdaea4e0be7c132e1c361dc26da5, 2026.
- [22]Radu Curticapean, Nathan Lindzey, and Jesper Nederlof, A tight lower bound for counting Hamiltonian cycles via matrix rank, Proc. 29th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018, arXiv:1709.02311, pp. 1080–1099.arxiv.org/abs/1709.02311
- [23]Marek Cygan, Stefan Kratsch, and Jesper Nederlof, Fast Hamiltonicity checking via bases of perfect matchings, J. ACM 65 (2018), no. 3, Art. 12, Preliminary version in STOC 2013.
- [24]Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk, Solving connectivity problems parameterized by treewidth in single exponential time, Proc. 52nd IEEE Symposium on Foundations of Computer Science (FOCS), 2011, Journal version in ACM Trans. Algorithms 18 (2022), no. 2, pp. 150–159.
- [25]Carlos Stein Naves de Brito, The partition exponent in the graded pieces of the Claude 3-SAT algorithm is optimal for pieces of that shape, Hexagon preprint hexagon:2610.00692v1, 31 October 2026, https://hexagonmath.org/abs/2610.00692, 2026.
- [26]Leonardo de Moura and Sebastian Ullrich, The Lean 4 theorem prover and programming language, Automated Deduction – CADE 28, Lecture Notes in Comput. Sci., vol. 12699, Springer, 2021, pp. 625–635.DOI
- [27]Marc Deléglise and Joël Rivat, Computing π(x): the Meissel, Lehmer, Lagarias, Miller, Odlyzko method, Math. Comp. 65 (1996), no. 213, 235–245, doi:10.1090/S0025-5718-96-00674-6.DOI
- [28]Holger Dell, Thoré Husfeldt, Dániel Marx, Nina Taslaman, and Martin Wahlén, Exponential time complexity of the permanent and the Tutte polynomial, ACM Trans. Algorithms 10 (2014), no. 4, Art. 21.
- [29]Fabio Dias and Yvens Lima, Limits and constants of OpenAI’s claimed ETH refutation, arXiv:2611.00517v1, 31 October 2026.arxiv.org/abs/2611.00517
- [30]Michael Freedman, László Lovász, and Alexander Schrijver, Reflection positivity, rank connectivity, and homomorphism of graphs, J. Amer. Math. Soc. 20 (2007), no. 1, 37–51, doi:10.1090/S0894-0347-06-00529-7.DOI
- [31]Carla Groenland, Isja Mannens, Jesper Nederlof, and Kristzina Szilágyi, Tight bounds for counting colorings and connected edge sets parameterized by cutwidth, Proc. 39th International Symposium on Theoretical Aspects of Computer Science (STACS), LIPIcs, vol. 219, 2022, arXiv:2110.02730, pp. 36:1–36:20.arxiv.org/abs/2110.02730
- [32]Michael Held and Richard M. Karp, A dynamic programming approach to sequencing problems, J. Soc. Indust. Appl. Math. 10 (1962), no. 1, 196–210.
- [33]Ellis Horowitz and Sartaj Sahni, Computing partitions with applications to the knapsack problem, J. ACM 21 (1974), no. 2, 277–292, doi:10.1145/321812.321823.DOI
- [34]Pavel Hrubeš, Avi Wigderson, and Amir Yehudayoff, Non-commutative circuits and the sum-of-squares problem, J. Amer. Math. Soc. 24 (2011), no. 3, 871–898, doi:10.1090/S0894-0347-2011-00694-2.DOI
- [35]François Jaeger, Dirk L. Vertigan, and Dominic J. A. Welsh, On the computational complexity of the Jones and Tutte polynomials, Math. Proc. Cambridge Philos. Soc. 108 (1990), no. 1, 35–53.DOI
- [36]Tamás Kővári, Vera T. Sós, and Pál Turán, On a problem of K. Zarankiewicz, Colloq. Math. 3 (1954), 50–57, doi:10.4064/cm-3-1-50-57.DOI
- [37]Jeffrey C. Lagarias and Andrew M. Odlyzko, Computing π(x): an analytic method, J. Algorithms 8 (1987), no. 2, 173–191, doi:10.1016/0196-6774(87)90037-X.DOI
- [38]Radu Curticapean, Get permanent results faster by counting stars, arXiv:2611.03636, 2 November 2026.
- [39]Baitian Li, Counting perfect matchings and Hamiltonian cycles faster, Proc. 53rd International Colloquium on Automata, Languages, and Programming (ICALP), LIPIcs, vol. 374, 2026, arXiv:2309.15422v2, pp. 138:1–138:16.arxiv.org/abs/2309.15422
- [40]Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas, Superpolynomial lower bounds against low-depth algebraic circuits, Proc. 62nd IEEE Symposium on Foundations of Computer Science (FOCS), 2021, doi:10.1109/FOCS52979.2021.00083, pp. 804–814.DOI
- [41]Bernt Lindström, Determinants on semilattices, Proc. Amer. Math. Soc. 20 (1969), no. 1, 207–208, doi:10.1090/S0002-9939-1969-0238738-4.DOI
- [42]László Lovász, Large networks and graph limits, Amer. Math. Soc. Colloquium Publications, vol. 60, Amer. Math. Soc., 2012, doi:10.1090/coll/060.DOI
- [43]Ruhollah Majdoddin, Lowered crossover points of Anthropic’s subexponential 3-SAT algorithm, arXiv:2610.41622v1, 30 October 2026.arxiv.org/abs/2610.41622
- [44]Jesper Nederlof and Karol Węgrzycki, Improving Schroeppel and Shamir’s algorithm for subset sum via orthogonal vectors, Proc. 53rd Annual ACM Symposium on Theory of Computing (STOC), 2021, doi:10.1145/3450337.3451024, pp. 1670–1683.arxiv.org/abs/2010.08576
- [45]Troy Tri Nguyen, A sublinear treewidth exponent for binary constraint satisfaction, Hexagon preprint hexagon:2611.00004v1, 2 November 2026, https://hexagonmath.org/abs/2611.00004, 2026.
- [46]Noam Nisan, Lower bounds for non-commutative computation, Proc. 23rd Annual ACM Symposium on Theory of Computing (STOC), 1991, doi:10.1145/103418.103462, pp. 410–418.
- [47]OpenAI, The Exponential Time Hypothesis is false, Preprint dated 17 October 2026, revised 25 October 2026. Paper and Lean formalisation in the repository https://github.com/openai/math; we use commit 7ef5c0cc5ca4b0e072b7a050fca09ab24bc6fa3a, 2026.
- [48]Kevin Pratt, Breaking the 2nd barrier for graph k-coloring, arXiv:2607.27159, 2026.arxiv.org/abs/2607.27159
- [49]Ran Raz, Multi-linear formulas for permanent and determinant are of super-polynomial size, J. ACM 56 (2009), no. 2, Art. 8, doi:10.1145/1502793.1502797.
- [50]Isaac Rudich and Louis-Martin Rousseau, Deterministic factoring in time N^{O(1)}, Hexagon preprint hexagon:2610.00600v1, 29 October 2026, https://hexagonmath.org/2610.00600v1, 2026.
- [51]Herbert J. Ryser, Combinatorial mathematics, Carus Mathematical Monographs, vol. 14, Math. Assoc. America, 1963.
- [52]Richard Schroeppel and Adi Shamir, A T = O(2^{n/2}), S = O(2^{n/4}) algorithm for certain NP-complete problems, SIAM J. Comput. 10 (1981), no. 3, 456–464, doi:10.1137/0210033.DOI
- [53]Joseph Shunia, An improved subexponential bound for deterministic integer factorization, Hexagon preprint hexagon:2610.00711v1, 2 November 2026, https://hexagonmath.org/2610.00711v1, 2026.
- [54]Mihail Stoian, TSP escapes the O(2^n) curse, arXiv:2405.03018, 2024.
- [55]Terence Tao, Ernest Croot, III, and Harald Helfgott, Deterministic methods to find primes, Math. Comp. 81 (2012), no. 278, 1233–1246, arXiv:1009.3956; doi:10.1090/S0025-5718-2011-02542-1.DOI
- [56]The mathlib Community, The Lean mathematical library, Proc. 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP), ACM, 2020, pp. 367–381.
- [57]Vaibhav Tulsyan, Class numbers, square roots and quadratic non-residues in time 2^{O(n/√log n)}, assuming the new #SAT algorithms, Hexagon preprint hexagon:2611.00115v1, 5 November 2026, https://hexagonmath.org/abs/2611.00115, 2026.
- [58]———, Counting Eulerian circuits in subexponential time, assuming the new #SAT algorithms, Hexagon preprint hexagon:2611.00088v1, 4 November 2026, https://hexagonmath.org/abs/2611.00088, 2026.
- [59]———, Counting Hamiltonian cycles in sparse graphs in subexponential time, assuming the new #SAT algorithms, Hexagon preprint hexagon:2610.00672v1, 31 October 2026, https://hexagonmath.org/abs/2610.00672, 2026.
- [60]———, eth-hamiltonicity: Lean 4 formalisation and research notes, Public repository https://github.com/xennygrimmato/eth-hamiltonicity, commit 946c49993b78aa163fcac3f8cb78ce351dd5dcc6; Lean sources of this paper in lean/EthFollowup/Barriers, research notes in lean/EthFollowup/Barriers.
- [61]———, Exact amplitudes of sparse quantum circuits in subexponential time, assuming the new #SAT algorithms, Hexagon preprint hexagon:2611.00090v1, 4 November 2026, https://hexagonmath.org/abs/2611.00090, 2026.
- [62]———, An independent machine-checked proof of deterministic factoring in time 2^{O(n/√log n)}, via the new #SAT algorithms, Preprint, November 2026; source in the directory factoring-note/ of [60], 2026.
- [63]———, The parity of the prime-counting function in time x^{O(1)}, Hexagon preprint hexagon:2611.00116v1, 5 November 2026, https://hexagonmath.org/abs/2611.00116, 2026.
- [64]Leslie G. Valiant, Completeness classes in algebra, Proc. 11th Annual ACM Symposium on Theory of Computing (STOC), 1979, doi:10.1145/8001315.804419, pp. 249–261.DOI
- [65]———, The complexity of computing the permanent, Theoret. Comput. Sci. 8 (1979), no. 2, 189–201, doi:10.1016/0304-3975(79)90044-6.DOI
- [66]Herbert S. Wilf, Hadamard determinants, Möbius functions, and the chromatic number of a graph, Bull. Amer. Math. Soc. 74 (1968), no. 5, 960–964, doi:10.1090/S0002-9904-1968-12104-4.DOI
- [67]Ryan Williams, A new algorithm for optimal 2-constraint satisfaction and its implications, Theoret. Comput. Sci. 348 (2005), no. 2–3, 357–365, doi:10.1016/j.tcs.2005.09.023.DOI
- [68]Or Zamir, k-coloring is faster than computing the chromatic number, arXiv:2607.25973v2, 2026.arxiv.org/abs/2607.25973