betaFeedback

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 kk-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 UU 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 3×23\times2 grid and of the full 3×33\times3 grid level have flattening-rank sums at least N2N^2, N3N^3 and N8N^8, while N9N^9 is open; the row cut of the permanent has rank (nk)\binom nk, which on paper gives U≥nlog⁡2(n/s)U\ge n\log_2(n/s) for row-local networks; algebras in which the permanent is a functional of a product have dimension at least (nn/2)\binom n{n/2}; pieces have saving ρ≥1/2\rho\ge1/2 (rank form; Anthropic's observation); and exact colouring filters for Hamiltonicity need q≥n−4q\ge n-4 colours. On paper we prove U≥(1−o(1))nlog⁡2nU\ge(1-o(1))n\log_2n for vertex-local networks for the Tutte polynomial off the integer hyperbolas, and ρ≥3/8\rho\ge3/8 for correlated decompositions of full grid levels. We cite 4545 Lean theorems, with standard axioms only. Every barrier is about a named model: in Anthropic's general model no unconditional bound on UU exists without separating P\mathrm P from P#P\mathrm P^{\#\mathrm P}, and an unconditional cap on oblivious algebraic algorithms would separate VP\mathrm{VP} from VNP\mathrm{VNP}.

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 kk-CNF on nn variables in time 2Ok(n/log⁡n)2^{O_k(n/\sqrt{\log n})} 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 O(n)O(n) 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 π(x)\pi(x) [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 1/log⁡2K1/\log_2 K per edge bit; Dias and Lima [29] prove that the clause-product form of [O]’s interpolation algorithm costs 2Ω(tw)2^{\Omega(\sqrt{tw})} at treewidth twtw, 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 2o(n)2^{o(n)} 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 π(x)\pi(x)) are exactly the ones they seem to miss.

The problem and the running example

We consider the engine barrier problem. For a counting problem PP and a stated class of networks, bound from below the number UU of shared bits of every network in the class whose value is PP; and for a stated class of recursions, bound from below the rate eKe_K at which the recursion evaluates the dense (K,λ)(K,\lambda)-clique. The two numbers combine: the engine’s own guarantee on a network is at least 2eKU2^{e_KU} (Theorem 2.4), and eK=Θ(1/log⁡K)e_K=\Theta(1/\sqrt{\log K}) in [A]. So a dense problem is out of reach of the engine’s guarantee when UU is of order nlog⁡nn\log n and eKe_K is not o(1/log⁡K)o(1/\log K). For grid recursions with product terms, eK=Ω(1/log⁡K)e_K=\Omega(1/\log K) 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 g2g^2 nodes as a g×gg\times g grid. Each pair of rows and pair of columns spans a rectangle with corner legs x,y,u,v∈[D]x,y,u,v\in[D] and tensor F=[x=v][y=u]F=[x=v][y=u]. Evaluated row by row, a term costs the rank of its row flattening (xy∣uv)(xy\mid uv); evaluated column by column, the rank of its column flattening (xu∣yv)(xu\mid yv). For FF both are permutation matrices of rank D2D^2. The recursion therefore splits FF into pieces, terms that are cheap in one of the two groupings, and the saving ρ\rho per level decides its rate. At D=2D=2 the split F=I+(F−I)F=I+(F-I) has rank profiles (4,1)(4,1) and (1,4)(1,4): each piece pays 2 bits in one grouping and none in the other, half of the 4 bits of FF. We come back to this example in § 2 (what a shared bit buys) and in § 4: on two rectangles and on the 3×23\times2 grid no decomposition, correlated or not, does better asymptotically, and on the 3×33\times3 level the question is open.

Running example: a grid with crossing equalities and tensor flattenings

Figure 1. The running example. One level of [A]’s recursion evaluates a clique on a g×gg\times g grid of nodes; each pair of rows a<ba<b and columns j<j′j<j' carries a rectangle, two crossing equalities of λ\lambda bits each. Its tensor FF has both flattenings of full rank D2D^2, D=2λD=2^\lambda. At D=2D=2 the split F=I+(F−I)F=I+(F-I) gives two terms, each cheap in one grouping: this is the profile of saving ρ=1/2\rho=1/2.

The naive route and the principle

At first one might try to prove that the dense permanent needs 2Ω(n)2^{\Omega(n)} steps in the engine, for example by bounding UU from below for every network whose value is per⁡(A)\operatorname{per}(A). 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 U=0U=0, and a network with U=0U=0 and one setting exists if and only if per⁡∈FP\operatorname{per}\in\mathrm{FP} (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 2w2^w, where ww 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 P\mathrm{P} from P#P\mathrm{P}^{\#\mathrm{P}} (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, [O][O]’s M0M_0-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 UU and eKe_K are each controlled by one rank: UU by the rank of the value across a cut of the input, and eKe_K 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 Ω(nlog⁡n)\Omega(n\log n) shared bits in the local networks we can analyse: U≥nlog⁡2(n/s)U \ge n\log_2(n/s) for row-local networks for the permanent (rank and counting steps in Lean), (nn/2)\binom{n}{n/2} for algebras (Lean), and, on paper, (1−o(1))nlog⁡2n(1-o(1))n\log_2 n 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 N2N^2, N3N^3 and N8N^8 on two rectangles, the 3×23\times2 grid and the 3×33\times3 level (Lean, rank form), ρ≥3/8\rho\ge3/8 on full levels (on paper), and a proof that flattening certificates stop at 8 on the 3×33\times3 level (§ 4.4).

  • We machine-check the rank form of ρ≥1/2\rho\ge1/2 for pieces ([A]’s Appendix H observation, generalised in [43]), and prove on paper ρ≥1/2−o(1)\rho\ge1/\sqrt{2}-o(1) for graded two-order pieces and α′≤1\alpha' \le1 for every family of groupings of the grid rectangles (Sections 4.1 to 4.3); and we prove that [O]’s M0M_0-template is tight at R≈QR\approx\sqrt{Q} (Section 5).

  • We prove floors for three of our own linear encodings of Hamiltonicity: q≥n−4q\ge n-4 colours, k∗(Ht)≥(log⁡2t−10)/20k^*(H_t)\ge(\log_2t-10)/20 turn bits, and a support threshold tp≤log⁡2#St_p\le\log_2\#S 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 cc has flattening rank at most 2c2^c” 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 ρ≥3/8\rho\ge3/8 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 λ=1\lambda=1 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 nlog⁡nn\log n 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 2ϵKU2^{\epsilon_K U}. 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 2(1−δ)npoly⁡(n,m)2^{(1-\delta)n}\operatorname{poly}(n,m)-time algorithm” survive, since its theorem “gives a running-time guarantee for each fixed clause width kk, while this hypothesis allows the width to grow with nn”; 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 2o(n)2^{o(n)} 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 [g][g] has, for every node aa, a set SaS_a of settings of at most PP bits and a weight table WaW_a, and for every pair a≠ba \ne b an interaction Ψa,b\Psi_{a,b} that factors through ca,bc_{a,b} shared bits: Ψa,b(z,z′)=∑θ∈{0,1}ca,bfa,b(z,θ)fb,a(z′,θ)\Psi_{a,b}(z,z') = \sum_{\theta\in\{0,1\}^{c_{a,b}}} f_{a,b}(z,\theta)f_{b,a}(z',\theta). Its value is ∑aWa(za)∏a<bΨa,b(za,zb)\sum_a W_a(z_a)\prod_{a<b}\Psi_{a,b}(z_a,z_b), and its total is U=∑a∑b≠aca,bU = \sum_a\sum_{b \ne a}c_{a,b}, so every shared bit is counted at both ends. The skeleton is (g,(ca,b))(g,(c_{a,b})). 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(ss) and Model V(ss); barrier.md Definitions 5.1, 5.2) Let the input be a matrix A∈{0,1}n×nA \in\{0,1\}^{n \times n} (or a graph on [n][n]). In Model R(ss) the rows are partitioned into clusters of size at most ss, every node is assigned to one cluster or is a routing node that reads nothing, the skeleton does not depend on AA, and the data of a node depend on AA only through the rows of its cluster. In Model V(ss) the 2n2n rows and columns (or the nn vertices) are partitioned into clusters of size at most ss, 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 K≥2K \ge2, g=3K8g = 3K^8. A network on [g][g] with parameters P,B,τP,B,\tau and total UU is evaluated within (Kτ+T⋅2qP/K)(g(P+B))C1(K^\tau+ T \cdot2^{qP/K})(g(P+B))^{C_1} operations, where TT bounds the cost of a (K,L)(K,L)-clique with L=[(U+qP/K)/K2]L = [(U+qP/K)/K^2] (Lemma 8(i), Lean ExplicitCost.groupingExplicit). If parameters (ρ,c)(\rho,c) exist, one algorithm evaluates the (Kℓ,λ)(K_\ell,\lambda)-clique within 2eκKℓ2λ(Kℓ(λ+B))C0Kℓ22^{e_\kappa K_\ell^2\lambda}(K_\ell(\lambda+B))^{C_0K_\ell^2} operations, where log⁡Kℓ=(3x0+6)2ℓ−6ℓ−2x0−6\log K_\ell= (3x_0+6)2^\ell-6\ell-2x_0-6 and 12ρℓ≤eℓ≤0.85ρℓ\frac{1}{2}\rho^\ell\le e_\ell\le0.85\rho^\ell, x0≥18x_0 \ge18 (Theorem A, Lean ExplicitCost.recursionSolves). Pieces with ρ=1/2\rho= 1/\sqrt{2} exist (Theorem B, Lean PiecesCounted.halfPieces).

The (K,λ)(K,\lambda)-clique C(K,λ)C(K,\lambda) is the network on KK nodes in which every pair shares one λ\lambda-bit label through Ψw,w′=[zw(w′)=zw′(w)]\Psi_{w,w'} = [z_w(w') = z_{w'}(w)], with arbitrary tables. Its cost is written 2eKK2λ2^{e_KK^2\lambda}; brute force has eK=(K−1)/(2K)e_K = (K-1)/(2K). One level of Theorem A maps a (g2,λ)(g^2,\lambda)-clique, viewed as the g×gg \times g grid of Figure 1, to networks on gg nodes grouped by rows or by columns. The straight edges inside a row or column cost O(N/g)O(N/g) of the N=g4λN = g^4\lambda shared bits; the rest sits on the (g2)\binom{g}{2} rectangles. A family of pieces writes d⋅F=∑i∈IAid\cdot F = \sum_{i \in I} A_i with ∣I∣=(2λ)c|I| = (2\lambda)^c and certified costs cirow,cicolc_i^{\mathrm{row}}, c_i^{\mathrm{col}} with cirow+cicol≤4ρλ+clog⁡(2λ)c_i^{\mathrm{row}} + c_i^{\mathrm{col}} \le4\rho\lambda+ c\log(2\lambda) ([A], Definition 7). Every term ℓ∈IR\ell\in I^R of the expansion of ∏qFq\prod_q F_q is a row network and a column network, and the level pays the cheaper one, which saves the factor ρ\rho. Since Kℓ+1≥Kℓ2K_{\ell+1} \ge K_\ell^2 while ee drops by ρ\rho, the rate is eK≍(log⁡K)−α′e_K \asymp(\log K)^{-\alpha'} with α′=log⁡2(1/ρ)\alpha' = \log_2(1/\rho); ρ=1/2\rho= 1/\sqrt{2} gives α′=1/2\alpha' = 1/2.

What a shared bit buys. In Figure 1 a rectangle carries 4λ4\lambda shared bits at both ends. A piece with (crow,ccol)=(2λ,0)(c^{\mathrm{row}},c^{\mathrm{col}})=(2\lambda,0) costs nothing in the column grouping, and at D=2D=2 the split F=I+(F−I)F=I+(F-I) realises the profile {(2,0),(0,2)}\{(2,0),(0,2)\}, i.e. ρ=1/2\rho=1/2. For larger DD the same split does not keep this profile (F−IF-I has row rank D(D−1)/2D(D-1)/2), and [A]’s Theorem B pays 1/21/\sqrt{2} instead. The question of § 4 is whether any decomposition beats 1/21/2; 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 kk-CNF with mm clauses in time (n+m)Ok(1)2Ok(nlog⁡log⁡n/log⁡n)(n+m)^{O_k(1)}2^{O_k(n\log\log n/\sqrt{\log n})} and polynomial space. Its Engine I needs a layout ([O], Definition def:layout; Lean LayoutSpec.Layout): partitions of the variables at QQ interpolation points, schedules for the factors, measurement matrices of small ℓ1\ell_1 height, and for every occurrence a row polynomial Pf,v(T)P_{f,v}(T) of degree at most RR with Pf,v(0)=δvP_{f,v}(0)=\delta_v that annihilates the measurement kernels of the other groups. The cost exponent is about n[(R/Q)log⁡(2Q/R)+τlog⁡(2D+1)+2/r]n[(R/Q)\log(2Q/R)+\tau\log(2D+1)+2/r]. [O]’s construction (its §4) is a template: a matrix M0M_0 acting on labels in [r]Q[r]^Q, with support condition (T2), M0[u,w]≠0⇒dH(du,aw)≤R−1M_0[u,w]\ne0\Rightarrow d_H(d_u,a_w)\le R-1. 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 NN be a network with total U≥1U\ge1 to which Lemma 8 is applied with any admissible KK and the clique algorithm of Theorems A(b) and B. Then the guaranteed running time is at least 2E(N)2^{E(N)} with

E(N)≥eKU+2gPK≥U2log⁡U+2x0.E(N)\ge e_KU+\frac{2gP}{K}\ge\frac{U}{2\sqrt{\log U}+2x_0}.

So the guarantee is below 2n2^n only if U<(2+o(1))nlog⁡nU<(2+o(1))n\sqrt{\log n}, and with pieces of saving ρ≥1/2\rho\ge1/2 it is at least 2U/(2(log⁡U+2x0))2^{U/(2(\log U+2x_0))}. Any algorithm for the (K,λ)(K,\lambda)-clique that reads its tables has eK≥(K−1)/K2−o(1)e_K\ge(K-1)/K^2-o(1), which alone gives only E(N)≥2U(1−O(1/K))E(N)\ge\sqrt{2U}(1-O(1/K)).

The proof reads eK≥1/(2log⁡K+2x0)e_K\ge1/(2\sqrt{\log K}+2x_0) off Theorem A(a), notes K2L≥UK^2L\ge U and 2gP/K≥2K2gP/K\ge2K, and splits on whether 2K2K exceeds the bound. The query bound (K−1)/K2(K-1)/K^2 is Majdoddin’s input floor [43 Proposition 2.4(a)] in our normalisation (his exponent is per edge bit, of which the clique has (K2)λ\binom{K}{2}\lambda). The last sentence is the reason § 4 matters: with a hypothetical optimal clique solver, no lower bound on UU of order nlog⁡nn\log n would bar anything. This proposition is about [A]’s guarantee as a function of UU, 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 UU. 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 pp, § 3.6 the Tutte plane, and § 3.7 says why no such bound exists in the general model.

The cut lemma

Let NN be a network and (L,R)(L,R) a partition of its nodes, with w(L,R)=∑a∈L,b∈Rca,bw(L,R)=\sum_{a\in L,b\in R}c_{a,b} crossing bits. Replacing every crossing interaction by its factorisation and exchanging the sums gives value⁡(N)=∑θ∈{0,1}wFL(θ)FR(θ)\operatorname{value}(N)=\sum_{\theta\in\{0,1\}^w}F_L(\theta)F_R(\theta), where FLF_L depends only on the data of the nodes in LL (barrier.md Lemma 3.1, on paper). So if the nodes in LL read only a part XX of the input and those in RR only the rest YY, the matrix value⁡(N(X,Y))X,Y\operatorname{value}(N(X,Y))_{X,Y} factors through 2w2^w 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 KK be a field and X,Y,ΘX,Y,\Theta types with YY and Θ\Theta finite.1 If M[x,y]=∑θ∈ΘF(x,θ)G(θ,y)M[x,y]=\sum_{\theta\in\Theta}F(x,\theta)G(\theta,y) for all x,yx,y, then rank⁡M≤∣Θ∣\operatorname{rank}M\le|\Theta|; for Θ={0,1}w\Theta=\{0,1\}^w this is rank⁡M≤2w\operatorname{rank}M\le2^w. If moreover M[x,y]=∑t∈Tut(x)vt(y)M[x,y]=\sum_{t\in T}u_t(x)v_t(y) over a finite TT with both families (ut)(u_t), (vt)(v_t) linearly independent (X,YX,Y finite), then rank⁡M=∣T∣\operatorname{rank}M=|T|.

Proof. Write M=FGM=FG with F=[F(x,θ)]F=[F(x,\theta)] and G=[G(θ,y)]G=[G(\theta,y)]; the rank of a product is at most its inner dimension ∣Θ∣|\Theta|. For the second statement, M=UVTM=UV^{\mathsf{T}} with UU and VV of full column rank ∣T∣|T|.

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 KK be a field, ι\iota a finite type with nn elements and I⊆ιI\subseteq\iota with ∣I∣=k|I|=k. Let MIM_I be the matrix whose rows are indexed by the 0/10/1 rows X:I→ι→{0,1}X:I\to\iota\to\{0,1\}, whose columns are indexed by Y:Ic→ι→{0,1}Y:I^{\mathsf{c}}\to\iota\to\{0,1\}, and whose entry is per⁡(X;Y)\operatorname{per}(X;Y), the permanent of the matrix with rows II read from XX and the other rows from YY. Then rank⁡MI=(nk)\operatorname{rank}M_I=\binom{n}{k}, and the same holds for the submatrix on one-1-per-row matrices. The proof is the Laplace expansion per⁡(X;Y)=∑∣S∣=kUS(X)VS(Y)\operatorname{per}(X;Y)=\sum_{|S|=k}U_S(X)V_S(Y) along the rows II.

Proof. A permutation of ι\iota maps II onto some SS with ∣S∣=k|S|=k, which gives the Laplace expansion. Evaluated at the one-1-per-row matrix XX that matches II onto S0S_0, US(X)=[S=S0]U_S(X)=[S=S_0], so the USU_S are linearly independent, and likewise the VSV_S; Theorem 3.1 gives rank exactly (nk)\binom{n}{k}, already on the one-1-per-row family.

An aside, not part of the statement above: on one-1-per-row matrices the permanent per⁡(X;Y)\operatorname{per}(X;Y) is the indicator that (X;Y)(X;Y) 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 jj of Model R(ss), cut the nodes into those of cluster jj and the rest. The left side reads the rows VjV_j and the right side the other rows, so Theorem 3.1? Theorem 3.2 give (n∣Vj∣)≤2wj\binom{n}{|V_j|}\leq2^{w_j} with wjw_j 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 wjw_j, 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 JJ be a finite set of clusters, n,s,U∈Nn,s,U\in\mathbb{N}, and k,w:J→Nk,w:J\to\mathbb{N} with 1≤kj≤s1\leq k_j\leq s and ∑jkj=n\sum_j k_j=n. Assume hrank: (nkj)≤2wj\binom{n}{k_j}\leq2^{w_j} for every jj (the cut lemma with the row cut, on paper for a given network), and hU: ∑jwj≤U\sum_jw_j\leq U. Then

nlog⁡2(n/s)≤∑jlog⁡2(nkj)≤U.n\log_2(n/s)\leq\sum_j\log_2\binom{n}{k_j}\leq U.

The second inequality needs only hrank and hU (modelR_bound). For hU: for every assignment cl⁡\operatorname{cl} of nodes to clusters or routing and every cc, ∑j∑a,b[cl⁡(a)=j≠cl⁡(b)]ca,b≤∑a≠bca,b\sum_j\sum_{a,b[\operatorname{cl}(a)=j\ne\operatorname{cl}(b)]}c_{a,b}\leq\sum_{a\ne b}c_{a,b} (sum_crossing_le_total), so hU holds with wjw_j the crossing bits of cluster jj.

Assembled on paper (barrier.md Theorem 6.1): every network family for per in Model R(ss) has U≥nlog⁡2(n/s)U\geq n\log_2(n/s), already if the value is correct only on one-1-per-row matrices; with Theorem 2.4, for s≤n1−ϵs\leq n^{1-\epsilon} the engine’s guarantee on any such network is 2ω(n)2^{\omega(n)} (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 kk rows and kk columns on the small side has rank exactly (2kk)\binom{2k}{k} 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 EE be a finite set of tree edges and U∈NU\in\mathbb{N}, c,k,k′:E→Nc,k,k':E\to\mathbb{N}, with U=2∑eceU=2\sum_{e}c_e. Assume hrank⁡:(ke+ke′ke)≤2ce\operatorname{hrank}:\binom{k_e+k'_e}{k_e}\leq2^{c_e} for every edge ee (the cut lemma with the vertex-cut rank, on paper). Then 2∑elog⁡2(ke+ke′ke)≤U2\sum_e\log_2\binom{k_e+k'_e}{k_e}\leq U. Also ∑i=0k(ki)(k′i)=(k+k′k)\sum_{i=0}^{k}\binom{k}{i}\binom{k'}{i}=\binom{k+k'}{k} for all k,k′k,k'.

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(ss) has U≥2n−o(n)U\geq2n-o(n) for s≤n1/3s\leq n^{1/3}. No single cut gives more: for a vertex cut with kk rows and kk columns on the small side, every fixing of the other entries gives rank at most (2kk)<4k\binom{2k}{k}<4^k. If the skeleton is a tree of maximum

degree Δ\Delta with the clusters {i,i′}\{i,i'\}, then U≥(4/log⁡2(Δ−1)) nlog⁡2n−O(nlog⁡log⁡n)U \ge(4/\log_{2}(\Delta-1))\,n\log_{2}n-O(n\log\log n). On the clusters {i,i′}\{i,i'\}, no star skeleton with one shared bit per leaf computes per⁡\operatorname{per} for n≥3n \ge3. The function [A is a permutation matrix] has a Model V(1) network with U=0U=0 but needs U≥nlog⁡(n/s)U \ge n\log(n/s) in Model R(ss), 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 n=3,4n=3,4; the Catalan cut rank of the family {I+Pσ}\{I+P_{\sigma}\} is checked for b≤5b \le5.

Conjecture 3.6. (Model V; barrier.md Conjecture 6.5) Every network family for per⁡\operatorname{per} in Model V(ss) has U≥(1−o(1))nlog⁡2(n/s)U \ge(1-o(1))n\log_{2}(n/s). Proved: 2n−o(n)2n-o(n) for s≤n1/3s \le n^{1/3}, and (4/log⁡2(Δ−1)−o(1))nlog⁡2n(4/\log_{2}(\Delta-1)-o(1))n\log_{2}n 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 per⁡\operatorname{per} 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 KK be a field and RR a finite-dimensional KK-algebra, not necessarily commutative.3 Let ϕ:R→K\phi:R\to K be KK-linear and rij∈Rr_{ij}\in R (i,j<ni,j<n) with ϕ(r0f(0)r1f(1)⋯rn−1,f(n−1))=[f bijective]\phi(r_{0f(0)}r_{1f(1)}\cdots r_{n-1,f(n-1)})=[f\text{ bijective}] for every f:[n]→[n]f:[n]\to[n]. Then (n⌊n/2⌋)≤dim⁡KR\binom{n}{\lfloor n/2\rfloor}\le\dim_{K}R. For finitely many such algebras AtA_t with ∑tϕt(r0f(0)(t)⋯rn−1,f(n−1)(t))=[f bijective]\sum_t\phi_t(r^{(t)}_{0f(0)}\cdots r^{(t)}_{n-1,f(n-1)})=[f\text{ bijective}], (n⌊n/2⌋)≤∑tdim⁡KAt\binom{n}{\lfloor n/2\rfloor}\le\sum_t\dim_{K}A_t.

Proof. For ∣S∣=n/2|S|=n/2 let uSu_S be the product of the first n/2n/2 factors along a fixed bijection onto SS, and vSv_S the product of the last n/2n/2 along a bijection onto the complement. Then ϕ(uSvS′)=[S=S′]\phi(u_Sv_{S'})=[S=S'], so the (nn/2)\binom{n}{n/2} elements uSu_S are linearly independent in RR. For several algebras apply this to the product algebra with the functional ∑tϕt\sum_t\phi_t. □

Theorem 3.8. (EthFollowup.Barriers.PermModP.permanent_eq_zero_of_low_rank; machine-checked) Let RR be a commutative ring of characteristic pp, pp prime, and ι,κ\iota,\kappa finite types.4 If A=UVTA=UV^{\mathsf T} with U,V∈Rι×κU,V\in R^{\iota\times\kappa} and ∣κ∣(p−1)<∣ι∣|\kappa|(p-1)<|\iota|, then per⁡A=0\operatorname{per} A=0.

Proof. Expanding A=UVTA=UV^{\mathsf T} column by column gives per⁡A=∑ℓ:ι→κ(∏iViℓ(i))per⁡Uℓ\operatorname{per} A=\sum_{\ell:\iota\to\kappa}\left(\prod_{i}V_{i\ell(i)}\right)\operatorname{per}U_{\ell}, where column ii of UℓU_{\ell} is column ℓ(i)\ell(i) of UU. If ∣κ∣(p−1)<∣ι∣|\kappa|(p-1)<|\iota|, some value of ℓ\ell is taken at least pp times, so UℓU_{\ell} has pp equal columns; a pp-cycle permuting them acts freely on the terms of per⁡Uℓ\operatorname{per}U_{\ell} and leaves each orbit sum pp times one term, which is 00 in characteristic pp. □

So every saving that characteristic pp gives through low rank dies once pp is of order nn, and the Chinese remainder theorem needs primes up to to about 0.9nln⁡n0.9n\ln n.

Proposition 3.9. (on paper; wild-ideas.md F1, perm-mod-p.md Lemma B4) If per⁡(A)=∑t≤Twt#SAT⁡(Ft)\operatorname{per}(A)=\sum_{t\le T}w_t\#\operatorname{SAT}(F_t) for all 0/10/1 matrices AA, with integers ∣wt∣≤2W|w_t|\le2^W, for some FtF_t has at least log⁡2n!−W−T=nlog⁡2n−1.45n−W−log⁡2T\log_{2}n!-W-T=n\log_{2}n-1.45n-W-\log_{2}T variables. The same holds modulo any MM with log⁡2M≥log⁡2n!+2\log_{2}M\ge\log_{2}n!+2.

So plain #SAT encodings of per⁡\operatorname{per} have nlog⁡n−O(n)n\log n-O(n) variables, where the Lean #kk-SAT bounds of both labs cost 2Θ(nlog⁡nlog⁡log⁡n)2^{\Theta(n\sqrt{\log n}\log\log n)} or more.

The Tutte plane off the hyperbolas

Write q=(x−1)(y−1)q=(x-1)(y-1), Hq={(x,y):(x−1)(y−1)=q}H_q=\{(x,y):(x-1)(y-1)=q\} and H=⋃q∈{1,2,…}Hq\mathcal{H}=\bigcup_{q\in\{1,2,\ldots\}}H_q, L={y=1}\mathcal{L}=\{y=1\}. On H∪L\mathcal{H}\cup\mathcal{L} 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 y≠1y\ne1 and (x−1)(y−1)∉{1,2,…}(x-1)(y-1)\notin\{1,2,\ldots\}. Let NN be a Model V(ss) family on subcubic graphs (maximum degree 6 at x=0x=0), with a fixed skeleton and s≤⌈n/log⁡2n⌉s\le\lceil n/\log_{2}n\rceil, that computes c(n,m,k(G))TG(x,y)c(n,m,k(G))T_G(x,y) for some nonzero normalization cc. Then U≥∑groupslog⁡2Bell⁡(bG)≥(1−o(1))nlog⁡2nU\ge\sum_{\mathrm{groups}}\log_{2}\operatorname{Bell}(b_G)\ge(1-o(1))n\log_{2}n for a sum of NnetN_{\mathrm{net}} such networks on one common clustering, some summand has U≥(12−o(1))nlog⁡2n−2log⁡2NnetU\ge(\frac{1}{2}-o(1))n\log_{2}n-2\log_{2}N_{\mathrm{net}}. The ingredients are Lindström’s factorisation [41, 66] [q∣P∨Q∣]P,Q∈Πb=ζdiag⁡((q)∣S∣)ζT[q^{|P\vee Q|}]_{P,Q\in\Pi_b}=\zeta\operatorname{diag}((q)_{|S|})\zeta^{\mathsf{T}}, whose rank over Q\mathbb{Q} is Bell⁡(b)\operatorname{Bell}(b) for q∉{0,…,b−1}q\notin\{0,\ldots,b-1\} and ∑j≤qS(b,j)\sum_{j\le q}S(b,j) 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 v=y−1≠0v=y-1\ne0 the gluing matrix is [q∣P∨Q∣][q^{|P\vee Q|}] up to invertible diagonal scalings, so the rank depends on (x,y)(x,y) only through qq and on whether v=0v=0; at q=0q=0 (that is, x=1x=1) the matrix [P∨Q=1^][P\vee Q=\hat{1}] takes its place and has rank Bell⁡(b)\operatorname{Bell}(b) by Möbius inversion, and on L\mathcal{L} (v=0v=0) 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 2(1/2−o(1))nlog⁡n2^{(1/2-o(1))n\sqrt{\log n}}, and for any pieces with ρ≥1/2\rho\ge1/2 it is at least 2(1/2−o(1))n2^{(1/2-o(1))n}.

Remark 3.12. (checked numerically) The ranks of [q∣P∨Q∣][q^{|P\vee Q|}] were computed exactly for b≤6b\le6, the cut ranks of the test families for b≤4b\le4 at fifteen points, and the acyclic gluing rank on L\mathcal{L} equals the Catalan number for b≤6b\le6 and is at least Cat⁡(7)\operatorname{Cat}(7) at b=7b=7. That it equals Cat⁡(b)\operatorname{Cat}(b) for all bb 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 ZG(q,v)Z_G(q,v) is a Lagrange combination of n+1n+1 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 Θ(nlog⁡n)\Theta(n\log n) off H∪L\mathcal{H}\cup\mathcal{L} and the whole question is the rate ϵK\epsilon_{\mathsf{K}}.

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 per⁡\operatorname{per} with g=1g=1, one setting, U=0U=0 and τ=poly⁡(n)\tau=\operatorname{poly}(n) exists if and only if per⁡∈FP\operatorname{per}\in\mathrm{FP}; so an unconditional lower bound U≥1U\ge1 in the general model would imply P≠P#P\mathrm{P}\ne\mathrm{P}^{\#\mathrm{P}};

(b) Ryser’s formula [51] is a network with g=1g=1, U=0U=0 and P=nP=n;

(c) “a network with U+∑aPa+log⁡τ=o(n)U+\sum_a P_a+\log\tau=o(n)” is equivalent to “per⁡∈TIME⁡(2o(n))\operatorname{per}\in\operatorname{TIME}(2^{o(n)})”.

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 2o(n)2^{o(n)} 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 ρ\rho of one level, and hence the rate exponent α′=log⁡(1/ρ)\alpha'=\log(1/\rho), 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, N=D=2λN=D=2^\lambda is the alphabet of one crossing equality.

Pieces have ρ≥1/2\rho\ge1/2

Contract the legs yy and uu of a piece with vectors β,α\beta,\alpha. On FF this gives ⟨β,α⟩\langle\beta,\alpha\rangle times the identity on (x,v)(x,v), 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 KK be a field, LL a finite type and Ti:L4→KT_i:L^4\to K (i∈Ii\in I, II finite) with ∑iTi(x,y,u,v)=d⋅[x=v][y=u]\sum_iT_i(x,y,u,v)=d\cdot[x=v][y=u] for all x,y,u,vx,y,u,v and some d≠0d\ne0. Then

∣L∣≤∑i∈Imin⁡(rank⁡Ti(xy∣uv),rank⁡Ti(xu∣yv)),|L|\le\sum_{i\in I}\min\left(\operatorname{rank}T_i^{(xy|uv)},\operatorname{rank}T_i^{(xu|yv)}\right),

and if I≠∅I\ne\varnothing some piece has both flattening ranks at least ∣L∣/∣I∣|L|/|I|.

Proof. Contract yy and uu with a common basis vector. The target becomes dd times the identity on (x,v)(x,v), of rank ∣L∣|L|, 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 ρ≥1/2\rho\ge1/2 for pieces is not new: it is the observation of [A]’s Appendix H that one piece needs 2λ−O(log⁡λ)2\lambda- O(\log\lambda) 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 min⁡(rank⁡row,rank⁡col)\min(\operatorname{rank}^{\mathrm{row}},\operatorname{rank}^{\mathrm{col}}) 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 KK and matrices AsA_s (s∈Is \in I, II finite) over KK of a common shape, rank⁡∑sAs≤∑srank⁡As\operatorname{rank} \sum_s A_s \le\sum_s \operatorname{rank} A_s. If I≠∅I \ne\varnothing and rank⁡∑sAs=22λ\operatorname{rank} \sum_s A_s = 2^{2\lambda}, some ss has log⁡2rank⁡As≥2λ−log⁡2∣I∣\log_2 \operatorname{rank} A_s \ge2\lambda- \log_2 |I|.

With certified costs at least log⁡2\log_2 of the ranks and ∣I∣≤(2λ)c|I| \le(2\lambda)^c, this gives ρ≥1/2−(3c/4)log⁡2(2λ)/λ\rho\ge1/2 - (3c/4)\log_2(2\lambda)/\lambda 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 ρ=1/2\rho= 1/2 (rho-lower-bound.md §2.2), so no counting argument on ranks alone beats 1/21/2, and the simplest profiles (N2,1)+(1,N2)+⋯(N^2,1) + (1,N^2) + \cdots are excluded only by a finer argument (a piece of operator-Schmidt rank 1 forces the others to carry rank at least N(N−1)/10N(N-1)/10, rho-lower-bound.md Proposition 2.3, on paper).

Graded two-order pieces have ρ≥1/2\rho\ge1/\sqrt{2}

[A]’s Theorem B builds its pieces from a graded space V=⨁EVEV = \bigoplus_E V_E: a piece is a slice QsQ_s of a locality identity of order HH, and its certified cost is the dimension of the spaces the products pass through, “max over the terms”. Write D(E)=dim⁡VED(E) = \dim V_E and f=log⁡2Df = \log_2 D.

Theorem 4.3. (EthFollowup.Barriers.Spread.spread_lemma, EthFollowup.Barriers.Spread.spread_slice, EthFollowup.Barriers.Spread.spread_slice_zero; machine-checked) Let D:Z→ND : \mathbb{Z} \to\mathbb{N}, h∈Zh \in\mathbb{Z}, TT a finite set of terms with degrees rjr_j, and Rrow=∑j∈TD(h+rj)R^{\mathrm{row}} = \sum_{j \in T} D(h + r_j), Rcol=∑j∈TD(h−rj)R^{\mathrm{col}} = \sum_{j \in T} D(h - r_j).5 With f=log⁡2Df = \log_2 D (and f=0f = 0 where D=0)D = 0),

f(h+rmax⁡)+f(h−rmin⁡)≤⌈log⁡2Rrow⌉+⌈log⁡2Rcol⌉f(h+r_{\max}) + f(h-r_{\min}) \le\lceil\log_2 R^{\mathrm{row}}\rceil+ \lceil\log_2 R^{\mathrm{col}}\rceil

where rmax⁡=max⁡{rj:D(h+rj)>0}r_{\max} = \max\{r_j : D(h+r_j)>0\} and rmin⁡=min⁡{rj:D(h−rj)>0}r_{\min} = \min\{r_j : D(h-r_j)>0\}, both sets nonempty. For the slice ss of a locality identity of order HH with degrees ri=s−h0+ir_i = s-h_0+i, i=0,…,Hi=0,\ldots,H, the right side is at least f(h−h0+s+H)+f(h+h0−s)f(h-h_0+s+H)+f(h+h_0-s), with no sign hypothesis; for h0=h=hn∈Nh_0=h=h_n\in\mathbb{N}, H=2hnH=2h_n and s=0s=0 it is at least 2f(2hn)2f(2h_n).

The operators and the two-order identity are not modelled; the theorem is about the dimension counts only, and the certified costs ⌈log⁡2Rrow⌉\lceil\log_2 R^{\mathrm{row}}\rceil 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 H=2hH = 2h and λ≤f(h)\lambda\le f(h), the saving is at least f(2h)/(2f(h))−clog⁡(2λ)/(4λ)f(2h)/(2f(h)) - c\log(2\lambda)/(4\lambda). On Fock space (f=log⁡f = \log of the partition function, with the Hardy–Ramanujan bounds) this is ρ≥1/2−O((c+1)log⁡λ/λ)\rho\ge1/\sqrt{2} - O((c+1)\log\lambda/\lambda), and the same holds in every C2C_2-cofinite vertex operator algebra. The spread 2h2h 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 ρ∗<1/2\rho^* < 1/\sqrt{2}?” is the general pieces question.

De Brito [25] proves, after [A]’s Appendix H, a rank floor ∣X∣⋅dim⁡Vh≤TV(h)|\mathcal{X}|\cdot\dim V_h \le T_V(h) for families of the shape of [A]’s Theorem B, which closes the case of growth exponent β<1/2\beta< 1/2 for that shape and gives ρ≥max⁡(2β−1,2−β)≥1/2\rho\ge\max(2^{\beta-1},2^{-\beta}) \ge1/\sqrt{2}. Majdoddin [43 Proposition 4.24 and the remark after it] proves ρ≥2/3−o(1)\rho\ge2/3-o(1) for every concave profile in that shape and the same max⁡(2α−1,2−α)\max(2^{\alpha-1},2^{-\alpha}) for power profiles D(E)=cEαD(E)=cE^\alpha. Our corollary, in a note dated 28 October, gave the branch ρ≥2β−1\rho\ge2^{\beta-1} and left β<1/2\beta< 1/2 open; what Theorem 4.4 adds is the C2C_2-cofinite generality and the converse. Outside the shape, “ρ∗<1/2\rho^* < 1/\sqrt{2}?” is open.

Remark 4.5. (checked numerically) For h≤10h \le10 the true ranks of the Theorem B pieces are 93–97% of the certified counts wherever the count is below N2N^2. This says nothing about the asymptotic ρ\rho.

Any min-over-groupings recursion has α′≤1\alpha' \le1

Proposition 4.6. (on paper; clique-evaluation.md §4.3) Let a level write each rectangle as F=∑s∈IAsF = \sum_{s\in I} A_s with ∣I∣=2o(λ)|I| = 2^{o(\lambda)}, expand the product over the rectangles, and evaluate every term in the cheaper of the row and column groupings. Then ρ≥1/2−o(1)\rho\ge1/2 - o(1), and with Kℓ+1≥Kℓ2K_{\ell+1} \ge K_\ell^2 the recursion has eK≥c/log⁡Ke_K \ge c/\log K, for any pieces, any algebra and any subexponential term count.

The proof uses Theorem 4.2: some piece srs_r has row cost at least 2λ−o(λ)2\lambda- o(\lambda) and some scs_c column cost at least 2λ−o(λ)2\lambda- o(\lambda); the mixed term using srs_r on half of the rectangles and scs_c on the other half costs (1/2−o(1))N(1/2 - o(1))N 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 1/log⁡2K1/\log_2 K per edge bit, with the exact constant and without assuming Kℓ+1≥Kℓ2K_{\ell+1} \ge K_\ell^2; 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 ∣R∣=(g2)2|R| = \binom{g}{2}^2 grid rectangles as F=∑s∈IAsF = \sum_{s\in I} A_s with ∣I∣=2o(λ)|I| = 2^{o(\lambda)} and expand the product over the rectangles. Let GG be any family of MM partitions of the g2g^2 grid nodes into blocks of size at most gg, and let every term choose its grouping from GG, adaptively or at random. Then the level saving satisfies ρeff≥1/2−1/(g−1)−ln⁡(2M)/(2∣R∣)−o(1)\rho_{\mathrm{eff}} \ge1/2 - 1/(g-1) - \sqrt{\ln(2M)/(2|R|)} - o(1); for all partitions, ρeff≥1/2−O(log⁡g/g)\rho_{\mathrm{eff}} \ge1/2 - O(\sqrt{\log g}/g). So α′≤1\alpha' \le1 for every level of this kind that expands into 2o(N)2^{o(N)} terms and picks the best grouping.

Proof. Call a rectangle with corners x,y,u,vx,y,u,v (Figure 1) diagonal under a partition π\pi if x,vx,v or y,uy,u lie in one block of π\pi. A pair of nodes in one block, in different rows and columns, is a diagonal of exactly one rectangle, so at most ∑B(∣B∣2)≤g(g2)=2∣R∣/(g−1)\sum_B \binom{|B|}{2} \le g\binom{g}{2} = 2|R|/(g-1) rectangles are diagonal. A rectangle that is not diagonal is row-like if x,yx,y or u,vu,v share a block, column-like if x,ux,u or y,vy,v do, and four-block otherwise; it cannot be both row-like and column-like, since for instance x∼yx \sim y and x∼ux \sim u would put y,uy,u in one block. For a row-like rectangle the row cut (xy∣uv)(xy \mid uv) 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 sr,scs_r,s_c of row, respectively column, log-rank at least 2λ−o(λ)2\lambda- o(\lambda). Draw ι∈{sr,sc}R\iota\in\{s_r,s_c\}^R uniformly. For a fixed π\pi, each row- or column-like rectangle pays its full cost with probability 1/21/2, independently, and each four-block one always does, so Hoeffding’s inequality and a union bound over the MM partitions give a term that pays at least (1−o(1))2λ(12(∣R∣−2∣R∣/(g−1))−∣R∣ln⁡(2M)/2)(1-o(1))2\lambda\left(\frac{1}{2}(|R|-2|R|/(g-1))-\sqrt{|R|\ln(2M)/2}\right) under every π∈G\pi\in G. For all partitions ln⁡M≤g2ln⁡g2\ln M \le g^2 \ln g^2. □

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 1/(g−1)1/(g-1), not 1/g1/g, since ∣R∣=(g2)2|R| = \binom{g}{2}^2 exactly).

Proposition 4.8. (on paper; engine2-algebraic.md Theorems 7.1, 7.3, Corollary 7.4) For gadget recursions with mm groupings whose gadgets meet exactly two classes in every grouping, the saving satisfies ρ≥E[1/dγ]−o(1)\rho\ge E[1/d_\gamma] - o(1) over the number dγd_\gamma of distinct cuts of a gadget, and, under homogeneity and regularity with exceptional fraction δ<1/(d−1)\delta< 1/(d-1), the node count grows as K′≥Kd−o(1)K' \ge K^{d-o(1)}. Hence α′≤1+O(δ/ln⁡d)\alpha' \le1 + O(\delta/\ln d): each additional distinct cut costs one factor KK in the node count.

Majdoddin argues the same for line merges of the dd-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 e≥1/4e \ge1/4 (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 eKe_K over Z\mathbb{Z} is the maximum over primes; monomial pieces in any product basis have ρ→1\rho\to1; the best contraction tree has e=min⁡(ω/9,1/4)+O(1/K)e = \min(\omega/9,1/4) + O(1/K); and recursion on the bits of λ\lambda gives nothing.

Correlated decompositions: N2N^2, N3N^3, N8N^8

All the caps above assume that the terms form a full product ∏qIq\prod_q I_q 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 ∑t∈CTt\sum_{t\in C} T_t 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 2cost⁡2^{\operatorname{cost}} (engine2-decorrelated.md §1, on paper), and the rank sum S=∑t2cost⁡tS=\sum_t 2^{\operatorname{cost}_t} satisfies max⁡tcost⁡t≥log⁡2S−log⁡2∣C∣\max_t \operatorname{cost}_t \ge\log_2 S-\log_2 |C|. So S≥NQS\ge N^Q on a configuration of QQ rectangles is ρ≥1/2−o(1)\rho\ge1/2-o(1) 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 KK be a field and α\alpha a nonempty finite alphabet.6 For every finite family of tensors TtT_t on the eight legs x1y1u1v1x2y2u2v2x_1y_1u_1v_1x_2y_2u_2v_2 with ∑tTt=[x1=v1][y1=u1][x2=v2][y2=u2]\sum_t T_t=[x_1=v_1][y_1=u_1][x_2=v_2][y_2=u_2],

∣α∣2≤∑tmin⁡(rank⁡Tt(x1y1x2y2∣u1v1u2v2),rank⁡Tt(x1u1x2u2∣y1v1y2v2))|\alpha|^2 \le\sum_t \min\left(\operatorname{rank} T_t^{(x_1y_1x_2y_2\mid u_1v_1u_2v_2)},\operatorname{rank} T_t^{(x_1u_1x_2u_2\mid y_1v_1y_2v_2)}\right)

and some term has this minimum at least ∣α∣2/#terms|\alpha|^2/\#\mathrm{terms}.

Proof. Fix y1=u1=y2=u2=oy_1=u_1=y_2=u_2=o. The contraction of ∑tTt\sum_t T_t is the identity on (x1,x2)∣(v1,v2)(x_1,x_2)\mid(v_1,v_2), of rank ∣α∣2|\alpha|^2, and the contraction of each TtT_t 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 (x,y,u,v)↦(v,u,y,x)(x,y,u,v)\mapsto(v,u,y,x) of FF; both readings are on paper. So for every pair of rectangles, correlation buys nothing: max⁡tcost⁡t≥2λ−log⁡2T\max_t\operatorname{cost}_t\ge2\lambda-\log_2 T.

The running example, twice. Return to Figure 1 at D=2D=2 and take two rectangles. The product of the splits F=I+(F−I)F=I+(F-I) gives four terms I⊗II\otimes I, I⊗(F−I)I\otimes(F-I), (F−I)⊗I(F-I)\otimes I and (F−I)⊗(F−I)(F-I)\otimes(F-I), whose minima of the two flattening ranks are 1, 4, 4, 1: rank sum 10 and maximum cost 2 bits, which is QλQ\lambda. Theorem 4.9 says that no decomposition, correlated or not, has rank sum below N2=4N^2=4. A correlated decomposition can repack constants (exhaustive search finds rank sum 7, Theorem 4.14), but it cannot change the exponent, for any λ\lambda. At λ=1\lambda=1 the term count is not o(λ)o(\lambda), so the example illustrates the bound and is no evidence about ρ\rho.

Theorem 4.10. (Grid32.rankSum_ge, Grid32.exists_expensive, Grid32.H_eq_rowTwist_T0, Grid32.rank_colFlat_T0; machine-checked) Let KK be a field and α\alpha a nonempty finite alphabet.7 Let HH be the tensor of the three rectangles abab, acac, bcbc on one column pair of the 3×23\times2 grid (12 legs). For every finite family with ∑tTt=H\sum_t T_t=H,

∣α∣3≤∑tmin⁡(rank⁡flat⁡b∣acTt,rank⁡flat⁡j∣j′Tt)|\alpha|^3 \le\sum_t \min\left(\operatorname{rank}\operatorname{flat}_{b|ac}T_t,\operatorname{rank}\operatorname{flat}_{j|j'}T_t\right)

and some term has this minimum at least ∣α∣3/#terms|\alpha|^3/\#\mathrm{terms}. Moreover HH is a row-local relabelling of a tensor T0T_0 whose column flattening has rank at most 1.

The proof pairs the two legs at one node and fixes the bcbc legs; one leg straddles the row cut and one the column cut, each at a factor NN, while the target gains N2N^2. 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 HH 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 KK be a field, α\alpha a finite alphabet and LL a finite set of legs.8 For disjoint KX,KY⊆LK_X,K_Y\subseteq L, a cut S⊆LS\subseteq L and a tensor T:αL→KT:\alpha^L\to K, the contraction keeping KXK_X as rows, KYK_Y as columns and fixing the other legs satisfies rank⁡(contr⁡T)≤∣α∣∣KX∩S∣+∣KY∖S∣⋅rank⁡(flat⁡ST)\operatorname{rank}(\operatorname{contr}T)\le|\alpha|^{|K_X\cap S|+|K_Y\setminus S|}\cdot\operatorname{rank}(\operatorname{flat}_S T); for a graph tensor whose kept edges match KXK_X with KYK_Y and whose other edges are fixed, the contraction is a permutation matrix of rank ∣α∣∣KX∣|\alpha|^{|K_X|}. Let GG be the tensor of the full 3×33\times3 level (the graph tensor of the 18 crossing edges of K3×K3K_3\times K_3, 36 legs). If α\alpha is nonempty, then for every finite family with ∑tTt=G\sum_t T_t=G,

∣α∣8≤∑tmin⁡(rank⁡flat⁡rowTt,rank⁡flat⁡colTt)|\alpha|^8 \le\sum_t \min\left(\operatorname{rank}\operatorname{flat}_{\mathrm{row}}T_t,\operatorname{rank}\operatorname{flat}_{\mathrm{col}}T_t\right)

with SrowS_{\mathrm{row}} the legs in row cc and ScolS_{\mathrm{col}} the legs in column 3, and some term has this minimum at least ∣α∣8/#terms|\alpha|^{8}/\#\mathrm{terms}. The side conditions (disjointness, matching, ∣KX∣=12|K_X| = 12, four straddlers per cut) are proved by decide.

Proof sketch. Keep the 12 legs at the block {a,b}×{1,2}\{a,b\}\times\{1,2\} on edges leaving the block as rows and their partners as columns, and fix the other legs. The contraction of GG is a permutation matrix of rank ∣α∣12|\alpha|^{12}. 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 ∣α∣4|\alpha|^{4} times either flattening rank. Subadditivity gives ∣α∣12≤∣α∣4∑tmin⁡(⋅,⋅)|\alpha|^{12} \le|\alpha|^{4}\sum_t \min(\cdot,\cdot).

With “a row network has rank flat⁡Srow≤dacdbc≤2cost\operatorname{flat}S_{\mathrm{row}} \le d_{ac}d_{bc} \le2^{\mathrm{cost}}” (on paper), Theorem 4.11 is S≥N8S \ge N^{8} on the 3×33\times3 level, i.e. ρ≥4/9\rho\ge4/9 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 g×gg\times g level, g=2hg=2h, into row and column networks has ∑t2costt≥N3h4−2h3\sum_t 2^{\mathrm{cost}_t} \ge N^{3h^{4}-2h^{3}} out of Q=h2(2h−1)2Q=h^{2}(2h-1)^{2}, hence ρ≥h(3h−2)/(2(2h−1)2)−o(1)→3/8\rho\ge h(3h-2)/(2(2h-1)^{2})-o(1)\to3/8 and α′≤log⁡2(8/3)≈1.415\alpha' \le\log_{2}(8/3)\approx1.415.

Proposition 4.13. (on paper; engine2-decorrelated.md Proposition 7.6, §8.2, §8.3) No two-party lossy contraction certifies more than (3/4+O(1/g))Q(3/4+O(1/g))Q on a full level, so 3/83/8 is the limit of the method. On the 3×33\times3 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 mm-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 D3=8D_3=8 is computed, by an exact integer program (Theorem 4.14).

Remark 4.14. (checked numerically) Exact integer programs give the flattening optimum Dg=8,32,84,189D_g=8,32,84,189 for g=3,4,5,6g=3,4,5,6, equal to the single balanced contraction in each case. At λ=1\lambda=1, GF(2) SAT search finds rank sums 7 for two rectangles (bound 4, product 10) and none below 8 on the 3×23\times2 grid. Data at λ≤2\lambda\le2 cannot separate ρ=1/2\rho=1/2 from anything, since log⁡∣C∣\log|C| is not o(λ)o(\lambda) there.

Conjecture 4.15. (network rank of the 3×33\times3 level; engine2-decorrelated.md Conjecture 8.1) For every field and alphabet of size NN, every family of tensors TtT_t with ∑tTt=G\sum_t T_t=G in which each TtT_t is a row network or a column network of cost ctc_t satisfies ∑t2ct≥N9\sum_t 2^{c_t}\ge N^9. The weakest new statement would be S≥N8+εS\ge N^{8+\varepsilon}, or a decomposition with maximum cost at most (9−ε)λ(9-\varepsilon)\lambda. Its g×gg\times g form S≥NQS\ge N^Q is ρ≥1/2\rho\ge1/2 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 1/log⁡2K1/\log_2 K per edge bit (his Theorem 4.13 and Corollary 4.19), and at least (log⁡2K)−3(\log_2 K)^{-3} for two balanced homogeneous merges (Theorem 4.12). For product terms this contains Theorem 4.6 with the exact constant and without assuming Kℓ+1≥Kℓ2K_{\ell+1}\ge K_\ell^2, 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 ∑tTt=G\sum_t T_t=G 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 (N8N^8 of 9 on the 3×33\times3 level, ρ≥3/8\rho\ge3/8 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 min⁡(rank⁡row,rank⁡col)\min(\operatorname{rank}^{\mathrm{row}},\operatorname{rank}^{\mathrm{col}}) 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 M0M_0-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 ρ≥1/2\rho\ge1/2 the ceiling of [A]’s framework is 2O(U/log⁡U)2^{O(U/\log U)} (rate.md §0, on paper), and with U=Θ(nlog⁡n)U = \Theta(n\log n) this is 2Θ(n)2^{\Theta(n)}. For the permanent the bound is sharper: assignment-count networks have engine exponent at least (3x0+6)n/2≥30n(3x_0 + 6)n/2 \ge30n, with [A]’s published x0≥18x_0 \ge18, for every ρ∈[1/2,1)\rho\in[1/2,1) (wild-ideas.md F3, on paper). Table 1 collects the mechanisms.

mechanismcapstatus
pieces, any family ([A], Def. 7)ρ≥1/2−o(1)\rho\ge1/2 - o(1)Lean (rank form); [A], App. H; [43]
graded two-order piecesρ≥1/2−o(1)\rho\ge1/\sqrt{2} - o(1)Lean (counts), paper
two groupings, product termsα′≤1\alpha' \le1paper; exact in [43], Thm. 4.13
any family of groupings, adaptive or randomα′≤1\alpha' \le1paper
gadget recursions, mm groupingsα′≤1+O(δ/ln⁡d)\alpha' \le1 + O(\delta/\ln d)paper
correlated, two rectangles / 3×23 \times2 / 3×33 \times3S≥N2S \ge N^2, N3N^3, N8N^8Lean (rank form)
correlated, full levels g=2hg = 2hρ≥3/8\rho\ge3/8, α′≤1.415\alpha' \le1.415paper
tensor rank, transforms, characteristic pp, treeseK≥conste_K \ge\text{const} or unchangedpaper

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 Q\sqrt{Q}

In this section we bound every instance of [O]’s M0M_0-template, whatever the matrix M0M_0 (commuting with the swaps or not), the label set and the number QQ of points. The template needs M0M_0 with (T1) every row of I−M0I - M_0 in the row space of the measurement matrix, so that #measurements≥rank⁡(I−M0)\#\text{measurements} \ge\operatorname{rank}(I - M_0), and the support condition (T2). The core is a triangular submatrix of I−M0I - M_0.

Theorem 5.1. (EthFollowup.Barriers.Triangular.triangular_rank_bound_hamming, EthFollowup.Barriers.Triangular.independent_sets_rank_bound; machine-checked) Let KK be a field, BB a finite set of coordinates and a,d:B→[r]Qa,d : B \to[r]^Q.9 Let φ:[r]Q→R\varphi: [r]^Q \to\mathbb{R} satisfy ∣φ(x)−φ(y)∣≤dH(x,y)|\varphi(x) - \varphi(y)| \le d_H(x,y), let R∈NR \in\mathbb{N}, and let M∈KB×BM \in K^{B \times B} satisfy (T2) in the form M[u,w]≠0⇒dH(du,aw)+1≤RM[u,w] \ne0 \Rightarrow d_H(d_u,a_w) + 1 \le R. Then

#{u∈B:φ(du)−φ(au)≥R}≤rank⁡(I−M).\#\{u \in B : \varphi(d_u) - \varphi(a_u) \ge R\} \le\operatorname{rank}(I - M).

For any distance on the labels and sets A,B′A,B' at distance at least RR, if M[u,w]≠0⇒dist⁡(du,aw)<RM[u,w] \ne0 \Rightarrow\operatorname{dist}(d_u,a_w) < R, then #{u:du∈A,au∈B′}≤rank⁡(I−M)\#\{u : d_u \in A, a_u \in B'\} \le\operatorname{rank}(I - M).

Proof. Order the set UU on the left by non-increasing φ(au)\varphi(a_u). For uu before or equal to ww in UU, φ(du)−φ(aw)≥φ(du)−φ(au)≥R\varphi(d_u) - \varphi(a_w) \ge\varphi(d_u) - \varphi(a_u) \ge R, so dH(du,aw)≥Rd_H(d_u,a_w) \ge R and M[u,w]=0M[u,w] = 0 by (T2). Hence (I−M)[U,U](I - M)[U,U] 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 ([r]×[r])Q([r] \times[r])^Q with every label used equally often, the measurement fraction satisfies ε≥Pr⁡[Bin⁡(2Q,12)≥Q+R]\varepsilon\ge\Pr[\operatorname{Bin}(2Q,\frac{1}{2}) \ge Q + R], so R≥(1−o(1))Qln⁡(1/ε)R \ge(1-o(1))\sqrt{Q\ln(1/\varepsilon)} when ln⁡(1/ε)≫ln⁡Q\ln(1/\varepsilon) \gg\ln Q; this matches [O]’s window R≈2Qln⁡(1/ε)R \approx\sqrt{2Q\ln(1/\varepsilon)} up to a factor at most 2\sqrt{2}. Modulo the Arora–Rao–Vazirani structure theorem [1], for r≥3r \ge3, any schedules obeying the group bound, any coordinate layout and any MM satisfying (T2), on (c′,κ)(c',\kappa)-linked bounded-occurrence formulas, R≤bQ/(8log⁡n)R \le bQ/(8\sqrt{\log n}) implies rank⁡(I−M)≥κn/2\operatorname{rank}(I - M) \ge\kappa n/2. Hence every instance of the template costs 2Ω(nlog⁡log⁡n/log⁡n)2^{\Omega(n\log\log n/\sqrt{\log n})} on such formulas.

So within Engine I the main-text template is tight up to a factor log⁡log⁡n\log\log n, and neither a non-commuting M0M_0 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 2Ω(tw)2^{\Omega(\sqrt{tw})} at treewidth twtw, and 2Ω(n)2^{\Omega(\sqrt n)} 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 2Ω(nlog⁡log⁡n/log⁡n)2^{\Omega(n\log\log n/\sqrt{\log n})} as the template does is open: it is strictly weaker as a constraint (“runs instead of windows” reach ε=0.1\varepsilon= 0.1 at R=9R = 9 for all Q≤4096Q \le4096, where every M0M_0 needs R≥59R \ge59 at Q=4096Q = 4096), 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 (Q,R)=(3,2)(Q,R)=(3,2) a non-commuting M0M_0 beats every commuting one, with rank⁡(I−M0)=8\operatorname{rank}(I-M_0)=8 against 10 (floating-point search), and the general interface was checked exactly for Q≤6Q\le6. 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 KK be a field of characteristic 0, n,q∈Nn,q\in\mathbb{N} with q>0q>0, z:[q]→Kz:[q]\to K and rr a vertex of [n][n].10 For a 2-factor XX let its value be z0∣Cr∣∏C≠Crzj∣C∣z_0^{|C_r|}\prod_{C\ne C_r}z_j^{|C|} over the components CC of XX, CrC_r the root’s. If for every graph GG on [n][n] there is μ≠0\mu\ne0 with ∑X∈2F(G)value⁡(X)=μ⋅#HC(G)\sum_{X\in2F(G)}\operatorname{value}(X)=\mu\cdot\#\mathrm{HC}(G) (ExactFilter with root colour 0; μ\mu may depend on GG), then n≤q+4n\le q+4.

Proof sketch. The nn-cycle has one 2-factor, which is Hamiltonian, so z0≠0z_0\ne0. For 3≤k≤n−33\le k\le n-3 the graph Cn−k⊔CkC_{n-k}\sqcup C_k, with the root in Cn−kC_{n-k}, has one 2-factor, which is disconnected, so its value z0n−k∑jzjkz_0^{n-k}\sum_j z_j^k must be 0. This is hvan, and Theorem 6.2 applies: grouping the zjz_j by value gives an exponential polynomial with at most qq bases and positive multiplicities that vanishes at n−5n-5 consecutive integers, which the Vandermonde matrix forbids if n−5≥qn-5\ge q. □

Theorem 6.2. (EthFollowup.Barriers.Colouring.colouring_barrier, EthFollowup.Barriers.Colouring.colouring_threshold_upper; machine-checked) Let KK be a field of characteristic 0 and z:[q]→Kz:[q]\to K with zj0≠0z_{j_0}\ne0 for some j0j_0 (module ColouringBarrier). If (hypothesis hvan) ∑jzjk=0\sum_j z_j^k=0 for every kk with 3≤k≤n−33\le k\le n-3, then n≤q+4n\le q+4. Conversely, for a primitive (n−2)(n-2)-th root of unity ζ\zeta, ∑j=1n−2(ζj)k=0\sum_{j=1}^{n-2}(\zeta^j)^k=0 for 1≤k≤n−31\le k\le n-3. The hypothesis hvan is derived from the graphs Cn−k⊔CkC_{n-k}\sqcup C_k inside the proof of Theorem 6.1.

So exact colouring filters need about log⁡2n\log_2 n bits per vertex, and the threshold lies in [n−4,n−2][n-4,n-2]; 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 (v;u,w)(v;u,w) of a vertex and two distinct neighbours. A labelling FF of the turns of G−rG-r by GF(2)k\mathrm{GF}(2)^k is good if every directed simple cycle of G−rG-r has nonzero label sum; k∗(G)k^*(G) is the least such kk. A good labelling gives a signed CNF for n⋅#HC(G)n\cdot\#\mathrm{HC}(G) with O(km)O(km) variables on bounded-degree graphs (linear-encoding-2.md Theorem G, on paper), so k∗=O(1)k^*=O(1) would have been a route to #HC on all bounded-degree graphs.

Theorem 6.3. (Kstar.theoremL, Kstar.theoremL_log; machine-checked) Let HtH_t be the crossing grid on 2t22t^2 vertices (row paths, column paths and rungs; maximum degree 3), given as the Boolean adjacency gridAdj⁡t\operatorname{gridAdj}_t.11 If FF assigns a vector in GF(2)k\mathrm{GF}(2)^k to every triple (v,u,w)(v,u,w) of vertices and every list of vertices that is a directed simple cycle of HtH_t (isDirCycle) has nonzero label sum, then t<220k+10t<2^{20k+10}; for t≥1t\ge1, ⌈log⁡2t⌉≤20k+10\lceil\log_2 t\rceil\le20k+10. So k∗(Ht)≥(log⁡2t−10)/20k^*(H_t)\ge(\log_2 t-10)/20.

The proof lifts a balanced 24-cycle of H4,4H_{4,4} 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 1/161/16, and every bounded-degree expander contains HtH_t with t2=Ω(n/log⁡n)t^2 = \Omega(n/\log n) as a minor [20] (kstar.md §3, on paper). So the gap gadget cannot be made smaller than Θ(mlog⁡m)\Theta(m\log m) on expanders by turn labels.

Residues. Deterministic decision from residues of #HC modulo small qq needs a query whose residue is nonzero. For a finite family SS of edge sets (the Hamiltonian cycles) put cT=#{H∈S:T⊆H}c_T = \#\{H \in S : T \subseteq H\} and tq(S)=min⁡{∣T∣:cT≢0modq}t_q(S) = \min\{|T| : c_T \not\equiv0 \mathbin{\mathrm{mod}} q\}.

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 EE be a type with decidable equality and SS a finite family of finite subsets of EE.12 Then min⁡{∣D∣:#{H∈S:H∩D=∅}≢0modq}=tq(S)\min\{|D| : \#\{H \in S : H \cap D = \varnothing\} \not\equiv0 \mathbin{\mathrm{mod}} q\} = t_q(S). If cT≡0modqc_T \equiv0 \mathbin{\mathrm{mod}} q for all ∣T∣<t|T| < t, then for every S0S_0 with ∣S0∣<t|S_0| < t and every ff, ∑H∈Sf(H∩S0)≡0modq\sum_{H \in S} f(H \cap S_0) \equiv0 \mathbin{\mathrm{mod}} q. For every prime pp and nonempty SS, tp(S)≤⌊log⁡2∣S∣⌋t_p(S) \le\lfloor\log_2 |S|\rfloor.

Proof sketch. The duality is inclusion–exclusion and Möbius inversion between deletion counts and containment counts. For the support statement, #{H:H∩S0=A}=∑A⊆T⊆S0(−1)∣T∖A∣cT≡0\#\{H : H \cap S_0 = A\} = \sum_{A \subseteq T \subseteq S_0} (-1)^{|T\setminus A|}c_T \equiv0. For the bound, fix an inclusion-maximal H0∈SH_0 \in S and count the sets H0∖HH_0 \setminus H modulo pp: the resulting function is nonzero and orthogonal to all monomials of degree below tpt_p, so it has at least 2tp2^{t_p} nonzero values, and ∣S∣≥2tp|S| \ge2^{t_p}. □

So every restriction, weighted or CNF-constrained query of support below tqt_q returns 0, and restriction search is deterministic 2o(n)2^{o(n)} exactly when tQ=o(n)t_Q = o(n); the bound tp≤log⁡2#HCt_p \le\log_2 \#\mathrm{HC} says that the obstruction is the only one. A black-box algorithm that sees HC(G)\mathrm{HC}(G) only through weighted counts modulo q≤Qq \le Q needs at least (2N/lcm⁡(1..Q)−1)/ln⁡Q(2^N/\operatorname{lcm}(1..Q)-1)/\ln Q 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 π(x)\pi(x), and a deterministic prime finder by this route, need to isolate ω(m)=1\omega(m) = 1, and the only identities we know do so through a kk-fold product m=d1⋯dkm = d_1 \cdots d_k with k=Θ(n/log⁡n)k = \Theta(n/\log n) (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 TT with positive integer leaf weights ℓi\ell_i and L=∑iℓiL = \sum_i \ell_i, where cost⁡(T)=∑internal vwt⁡(v)\operatorname{cost}(T) = \sum_{\text{internal }v} \operatorname{wt}(v),13 we have Llog⁡2L≤cost⁡(T)+∑iℓilog⁡2ℓiL\log_2 L \le\operatorname{cost}(T) + \sum_i \ell_i \log_2 \ell_i. If all kk leaves have weight w>0w > 0, then kwlog⁡2k≤cost⁡(T)kw\log_2 k \le\operatorname{cost}(T).

Theorem 7.2. (EthFollowup.IterProd.rank_prodMatFixed_1e, EthFollowup.IterProd.rank_prodMat_pow; machine-checked) Over Q\mathbb{Q}, the matrix with rows u∈[1,2a]u \in[1,2^a], columns (v,m)∈[1,2b]×[1,2a+b](v,m) \in[1,2^b] \times[1,2^{a+b}] and entries [uv=m][uv = m] has rank 2a2^a. With m≠0m \ne0 fixed, the matrix [uv=m][uv = m] over any finite sets of rows and columns has rank at most τ(m)\tau(m).

So in a tree verifier the cut above a node vv carries at least wt⁡(v)\operatorname{wt}(v) bits (?? 3.1?? 7.2, the link on paper), U≥cost⁡(T)≥nlog⁡2kU \ge\operatorname{cost}(T) \ge n\log_2 k, 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 KnKn by a parsimonious label system with U=O(size)U = O(\mathrm{size}). Hence a lower bound U=ω(n)U = \omega(n) for all parsimonious verifiers of m=∏idim = \prod_i d_i would be a superlinear lower bound on the circuit size of an explicit TC0\mathrm{TC}^0 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 π(I)\pi(I) mod MM queried by a deterministic strategy vanish as long as consecutive endpoints are far apart; against it, at least x0.525/(Mlog⁡M)x^{0.525}/(M\log M) queries are needed.

problembest knownwhy out of reachproved
dense #HC, TSP2nn22^n n^2 [5, 32]; 2nn2/2Ω(log⁡n)2^n n^2/2^{\Omega(\sqrt{\log n})} [54]; 1.657n1.657^n decision, randomised [8]; directed #HC 2n−Ω(n)2^n-\Omega(\sqrt{n}) [39]permutation witness; vertex-local networks have U=Θ(m)U=\Theta(m); even U=Θ(nlog⁡n)U=\Theta(n\log n) is fatal at ρ≥1/2\rho\ge1/2Lean: ?? 3.1?? 3.4; paper: ?? 2.4?? 3.5
permanent, #PM, hafnian2n2^n [51]; 2n−Ω(n)2^n-\Omega(\sqrt{n}) [39]; (2−10−40)n(2-10^{-40})^n over any commutative ring [38]nlog⁡nn\log n bits in row-local networks; algebras of dimension (n2)\binom{n}{2}; #SAT encodings need nlog⁡nn\log n variables; char. pp savings die at p≈np\approx nLean: ?? 3.2?? 3.3?? 3.7?? 3.8; paper: ?? 3.9?? 3.13, Theorem 3.6
chromatic number2n2^n [13]; kk-colouring (2−εk)n(2-\varepsilon_k)^n randomised [68, 48]; 1.99982n1.99982^n under the asymptotic rank conjecture [10]growing kk needs n⌈log⁡k⌉n\lceil\log k\rceil variables; dense encodings need P=Θ(nlog⁡k)P=\Theta(n\log k); inclusion–exclusion over 2n2^n sets is not a networknone; heuristic rank count (ambitious-targets.md §2.4)
Subset Sum, Partition2n/22^{n/2} [33]; space 2n/42^{n/4} [52], improved [44]each party’s partial sum carries bb bitspaper: Theorem 7.5
dense Max-Cut, Max-2-SAT2ωn/32^{\omega n/3} [67]Θ(n2)\Theta(n^2) edge terms; the pair interaction has rank 2rank⁡E2^{\operatorname{rank} E}, so P=Θ(n)P=\Theta(n) on dense graphsnone; one-line rank count
directed HC, dense2n2^n; 2n−Ω(n)2^{n-\Omega(\sqrt{n})} counting [39]as dense #HC; sparse digraphs are done (theoremDHC)as dense #HC
prime findingx1/2+o(1)x^{1/2+o(1)} [37]; parity on short intervals x1/2−cx^{1/2-c} [55]residues of cheap counts can all vanish; exact isolation needs kk-fold products, k=Θ(n/log⁡n)k=\Theta(n/\log n)Lean: ?? 7.1?? 7.2; paper: ?? 7.3?? 7.4
exact π(x)\pi(x)x1/2+o(1)x^{1/2+o(1)} [37]; x2/3/log⁡2xx^{2/3}/\log^2 x [27]product-tree verifiers have U=Θ(nlog⁡n)U=\Theta(n\log n), giving 2Θ(nlog⁡n)2^{\Theta(n\sqrt{\log n})}as prime finding; Theorem 8.3
Tutte off H∪L\mathcal{H}\cup\mathcal{L}2n2^n [12]boundary states are all set partitions, rank Bell(b)(b); interpolation needs Θ(n)\Theta(n) hyperbolaspaper: 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 gg clusters its items privately and shares partial sums of b+log⁡nb+\log n bits along a tree.

Proposition 7.5. (on paper; ambitious-targets.md §2.5) For nn items with bb-bit weights, a clustered partial-sum network has engine exponent about (4εK+6/K)gb≥18K7b(4\varepsilon K+6/K)gb\ge18K^7b in case (i) of Lemma 8. Beating 2n/22^{n/2} needs b<n/(36K7)b<n/(36K^7), where the O(n2b)O(n2^b) dynamic programme is already faster; case (ii) and [O]’s model fail similarly. So no clustered-partial-sum network in either engine beats 2n/22^{n/2} at b=Θ(n)b=\Theta(n).

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.

  1. A decomposition of the 3×33\times3 level with ∑t2ct<N9\sum_t 2^{ct}<N^9 (Theorem 4.15 false), or more generally a correlated decomposition with ρ<1/2\rho<1/2 on full levels. This is the grid-level case of the “open door” of [43 §4.8 and Open Problem 5].

  1. Pieces outside the graded two-order family with ρ<1/2\rho<1/\sqrt{2}: a statement of the Hurwitz–Hrubeš–Wigderson–Yehudayoff type [34], since ρ→1/2\rho\to1/2 would give sum-of-squares formulas of nearly linear size.

  • (iii) An algorithm for (K,λ)(K,\lambda)-cliques that is not a sum of 2o(N)2^{o(N)} clique-type sub-instances, for example one that eliminates variables or adapts to the tables.

  • (iv) For prime counting, a parsimonious verifier of a kk-fold product with o(nlog⁡n)o(n\sqrt{\log n}) 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 (K,λ)(K,\lambda)-clique oblivious algebraic if it is a straight-line program over Q\mathbb{Q} 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 D=2λD=2^\lambda and PK(T)=∑X⊆[K]∏a∈XTa(X∣δ(a))P_K(T)=\sum_{X\subseteq[K]}\prod_{a\in X}T_a(X|_{\delta(a)}), the value of the (K,λ)(K,\lambda)-clique as a polynomial in the table entries: it is set-multilinear of degree KK in Nin=K⋅DK−1N_{\mathrm{in}}=K\cdot D^{K-1} variables with 0/10/1 coefficients, and its cost 2eKK2λ2^{e_KK^2\lambda} equals (Nin/K)eKK2/(K−1)(N_{\mathrm{in}}/K)^{e_KK^2/(K-1)}.

Proposition 8.1. (on paper; engine2-algebraic.md M6.1) Take λ=K\lambda=K, so that K≈log⁡NinK\approx\sqrt{\log N_{\mathrm{in}}}, and index the family by NinN_{\mathrm{in}}: for NN between consecutive values of NinN_{\mathrm{in}}, which differ by a factor Nino(1)N_{\mathrm{in}}^{o(1)}, take PKP_K for the largest KK with Nin≤NN_{\mathrm{in}}\leq N, padded with unused variables. Work over Q\mathbb{Q}.

(i) The family lies in VNP by Valiant’s criterion [64] ([17 Proposition 2.20]): PKP_K has degree K≈log⁡NinK\approx\sqrt{\log N_{\mathrm{in}}} and NinN_{\mathrm{in}} variables, both polynomial in NinN_{\mathrm{in}}, and its coefficient function is 0/1 and computable in polynomial time (it checks that the KK indices of a monomial agree on every edge).

(ii) If, for all sufficiently large KK, every oblivious algebraic algorithm that computes PKP_K has size at least 2eKK2λ2^{e_KK^2\lambda} with eK≥φ(K)/Ke_K\geq\varphi(K)/K for a function φ→∞\varphi\to\infty, then the size is at least (Nin/K)φ(K)(N_{\mathrm{in}}/K)^{\varphi(K)}, superpolynomial in NinN_{\mathrm{in}}, so the family is not in VP and VP≠VNP\mathrm{VP}\ne\mathrm{VNP}. With φ=cK/log⁡K\varphi=cK/\log K this covers “no oblivious algebraic algorithm beats c/log⁡Kc/\log K”.

(iii) The value is computable in time NinK/2+o(1)=2O(log⁡3/2Nin)N_{\mathrm{in}}^{K/2+o(1)}=2^{O(\log^{3/2}N_{\mathrm{in}})}, so the same lower bound for Boolean circuits would put a quasi-polynomial-time function outside P/poly, that is QP⊈P/poly\mathrm{QP}\not\subseteq\mathrm{P/poly}, and hence EXP⊈P/poly\mathrm{EXP}\not\subseteq\mathrm{P/poly}; 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 (K−1)/K2(K-1)/K^2 is the only unconditional lower bound on eKe_K 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-KK form of this observation: at K=4K=4, a bound above N3N^3 “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) (g=3K8≤mg=3K^8\leq m, P=2k⌈m/g⌉P=2k\lceil m/g\rceil, U<2kmU<2km), reduces #3-SAT on a bounded-occurrence formula with nn variables and m=O(n)m=O(n) clauses to one (K,L)(K,L)-clique with K2L=O(n)K^2L=O(n), at overhead 2O(n/K+K8log⁡K)2^{O(n/K+K^8\log K)}. With K=Θ(n1/9)K=\Theta(n^{1/9}) the overhead is 2O(n8/9log⁡n)2^{O(n^{8/9}\log n)} and log⁡K=Θ(log⁡n)\log K=\Theta(\log n), so eK=o(1/log⁡K)e_K=o(1/\log K) would give bounded-occurrence #3-SAT in 2o(n)2^{o(n)}. So the hypothesis Hlog⁡H_{\log}, “bounded-occurrence #3-SAT needs 2Ω(n/log⁡n)2^{\Omega(n/\log n)},” implies eK=Ω(1/log⁡K)e_K=\Omega(1/\log K) for all algorithms. Hlog⁡H_{\log} is consistent with everything known but is not a standard hypothesis.

Any K=ncK=n^c with 0<c≤1/90<c\leq1/9 works; the constraint g=3K8≤mg=3K^8\leq m is what rules out larger KK in case (i) of Lemma 8.

For (iv). Theorem 7.3 plays the role of the meta-barrier: an ω(n)\omega(n) bound for all verifiers would be a superlinear circuit lower bound for an explicit TC0\mathrm{TC}^0 function.

Open questions. We state them as precisely as we can. Theorem 4.15 (the 3×33\times3 level) and Theorem 3.6 (Model V) are above.

Question 8.3. (aa-party verification of a product: iterated-product.md §6) The witness (d1,…,dk,m)(d_1,\ldots,d_k,m) with ∑ibits⁡(di)=bits⁡(m)=n\sum_i\operatorname{bits}(d_i)=\operatorname{bits}(m)=n and k≈n/log⁡nk\approx n/\log n is distributed, as the designer likes, among a≈n1/5a\approx n^{1/5} parties

holding at most n4/5n^{4/5} 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 ∏idi=m\prod_i d_i = m and none otherwise. What is the least total UU of label bits? Known: Ω(n)≤U≤(1/5+o(1))nlog⁡2n\Omega(n) \le U \le(1/5 + o(1))n\log_2 n; tree verifiers have U≥nlog⁡2kU \ge n\log_2 k (Theorem 7.1). U=o(nlog⁡n)U = o(n\sqrt{\log n}) would give exact π(x)\pi(x) and deterministic prime finding in xo(1)x^{o(1)}.

Question 8.4. (the pieces constant; rho-lower-bound.md §7) Let ρ∗\rho^* be the infimum of the ρ\rho for which pieces with parameters (ρ,c)(\rho,c) exist for some cc. Is ρ∗<1/2\rho^* < 1/\sqrt{2}? Proved: ρ∗≥1/2−o(1)\rho^* \ge1/2 - o(1) (Theorem 4.1); ρ≥1/2−o(1)\rho\ge1/\sqrt{2} - o(1) for graded two-order pieces with top-pole pairing on spaces of square-root growth, in particular all C2C_2-cofinite vertex operator algebras (Theorem 4.4). Open: the zero-mode loophole (pairing in a lower pole), two-order structures of growth below exp⁡(E)\exp(\sqrt{E}), and true ranks below the certified counts.

Conjecture 8.5. (Catalan rank on y=1y = 1; tutte-plane.md Lemma 3.2(c)) For every bb and every u≠0u \ne0, the acyclic gluing matrix Au[P,Q]=u∣P∨Q∣[∣P∣+∣Q∣−∣P∨Q∣=b]A_u[P,Q] = u^{|P \lor Q|}[|P| + |Q| - |P \lor Q| = b] on the partitions of [b][b] has rank Cat⁡(b)\operatorname{Cat}(b). Proved: rank at most 22b−12^{2b-1}. Checked: b≤6b \le6, and at least Cat⁡(7)\operatorname{Cat}(7) at b=7b = 7 (Theorem 3.12).

Question 8.6. (the two Tutte loopholes; tutte-plane.md §5) Does Theorem 3.10 hold for sums of 2o(nlog⁡n)2^{o(n\log n)} 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.

modulecontentlines
RankBoundscut lemma, subadditivity, Model R and tree summations, pieces373
RowCutLaplace expansion, row-cut rank (nk)\binom{n}{k}312
AlgebraRankalgebra dimension (nn/2)\binom{n}{n/2}168
PermModPper A=0A = 0 for low rank in characteristic pp135
SpreadLemmaspread inequality for graded two-order pieces123
DecorrelatedRanktwo rectangles, N2N^2126
DecorrelatedGrid323×23 \times2 grid, N3N^3; row-local no-go260
DecorrelatedGrid33lossy flattening lemma; 3×33 \times3 level, N8N^8286
TriangularRanktriangular rank bound for the M0M_0-template121
ColouringBarriercolouring barrier, polynomial form, converse114
ColouringBarrierGraphcolouring barrier for graphs566
KstarBasic, KstarLowerturn labellings, Theorem L53, 768
Derandduality, support lemma, tp≤log⁡2∣S∣t_p \le\log_2 |S|573
IterProdTree, IterProdCutRankproduct trees, rank of the product indicator142, 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 (X;Y)(X;Y)), word (the ordered product r0f(0)⋯rn−1,f(n−1)r_{0f(0)} \cdots r_{n-1,f(n-1)}), 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 cc has flattening rank at most 2c2^c 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 λ=1\lambda= 1 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 3×33 \times3 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 2n2^n. 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 pp, 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 (2−ε)n(2-\varepsilon)^n algorithm with ε=10−40\varepsilon= 10^{-40} 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 π(x)\pi(x), 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 1/log⁡2K1/\log_2 K 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 β<1/2\beta< 1/2 for that shape; Majdoddin [43 Proposition 4.24] proves ρ≥2/3−o(1)\rho\ge2/3-o(1) for every concave profile in that shape. Our Corollary (the law ρ≥2β−1\rho\ge2^{\beta-1}, note of 28 October) is dated before both and left β<1/2\beta< 1/2 open; outside the shape the question remains open (Theorem 8.4). Bhattacharjee [7] states (his Theorem 7.10) that the Tutte polynomial on HqH_q is computable for bounded-degree graphs and integer q≥1q \ge1 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 DCΔk/log⁡kD^{C\Delta k/\sqrt{\log k}}, 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 nlog⁡nn\log n 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 2o(λ)2^{o(\lambda)} pieces, row and column network decompositions, [O]’s M0M_0-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 log⁡2\log_2 of a flattening rank” and “a network gives a factorised matrix” are on paper, as are the hypotheses hrank and hU.

  • Numerics are not evidence about ρ\rho. Data at λ≤2\lambda\le2 cannot separate ρ=1/2\rho= 1/2 from anything (Theorem 4.14).

  • Scope of the caps. They cover [A]’s framework. For [O]’s engine they cover the M0M_0-template of its main text (Section 5), not the general interface, which Dias and Lima bound by 2Ω(w)2^{\Omega(\sqrt{w})} [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 N9N^9.

  • 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 nlog⁡nn\log n 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 1/log⁡K1/\log K (Theorem 4.6, and sharper [43 §4.8], Theorem 4.13), while correlated decompositions of full grid levels do no better than (log⁡K)−1.415(\log K)^{-1.415} (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 3×33 \times3 grid level, where N8N^8 is proved and N9N^9 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 (9−ε)λ(9-\varepsilon)\lambda. An interesting direction on the number-theoretic side is the gg-party verification of a product (Theorem 8.3), whose answer would decide whether exact π(x)\pi(x) 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. [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. [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. [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. [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. [5]Richard Bellman, Dynamic programming treatment of the travelling salesman problem, J. ACM 9 (1962), no. 1, 61–63.DOI
  6. [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. [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. [8]Andreas Björklund, Determinant sums for undirected Hamiltonicity, SIAM J. Comput. 43 (2014), no. 1, 280–299, Preliminary version in FOCS 2010.
  9. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [20]Julia Chuzhoy and Rachit Nimavat, Large minors in expanders, arXiv:1901.09349, 2019.arxiv.org/abs/1901.09349
  21. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [38]Radu Curticapean, Get permanent results faster by counting stars, arXiv:2611.03636, 2 November 2026.
  39. [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. [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. [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. [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. [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. [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. [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. [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. [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. [48]Kevin Pratt, Breaking the 2nd barrier for graph k-coloring, arXiv:2607.27159, 2026.arxiv.org/abs/2607.27159
  49. [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. [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. [51]Herbert J. Ryser, Combinatorial mathematics, Carus Mathematical Monographs, vol. 14, Math. Assoc. America, 1963.
  52. [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. [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. [54]Mihail Stoian, TSP escapes the O(2^n) curse, arXiv:2405.03018, 2024.
  55. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [68]Or Zamir, k-coloring is faster than computing the chromatic number, arXiv:2607.25973v2, 2026.arxiv.org/abs/2607.25973

Paper details

vlnc:W_py8r3393
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 16

downloads · 1

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Anthropic Claude Fable

View statement
Looking for related papers…
Contents