For every real polynomial threshold function f of degree at most d on the uniform cube {-1,1}^n we prove AS(f) <= min{n, 6 d b_n (n+d)/(n+2d)} <= (6/sqrt(2 pi)) d sqrt(n) < 2.394 d sqrt(n), where b_n = E|B_n - n/2| for B_n ~ Bin(n,1/2). The previous coefficient was 8/sqrt(2 pi) = 3.1915... The new ingredient is an edge comparison with constant 3/2 in place of 2 in OpenAI's weighted-grading argument: for every positive weight and every sign function h, the number of ordered equal-sign edges of h is at most (3/2)||MH+HM||_HS^2. The proof rests on the exact identity (Z_i M Z_i - M)^2 = I - A_i^2, where A_i is the grade-diagonal part of the multiplication by x_i. Combined with OpenAI's original coupling estimate alone, the lemma already gives AS(f) <= 6 d sqrt(n).
Alman and Vassilevska Williams have refuted the 3SUM and APSP hypotheses. Their algorithms rest on counting the triangles through prescribed edges of lopsided tripartite graphs, whose middle part has nε vertices for a small ε. Majdoddin extended the method to every ε<ln4/(5ln5)≈0.172. We determine which of the main conditional lower bounds derived from the refuted hypotheses survive. We also prove that the method extends to every ε<0.17843 when the prescribed edges are known in advance and there are at most n2−ε/2 of them, which confirms Majdoddin's numerical estimate. Whether a bound survives depends mostly on the instances that its reduction produces. The reductions behind most bounds produce instances outside the range of the new algorithms: balanced graphs, or lopsided graphs with a larger middle part. Most of the set-disjointness, dynamic-graph and triangle bounds therefore follow from hypotheses that no known algorithm contradicts. These hypotheses, however, concern mainly such instances, and for several bounds the hypothesis is the bound itself, stated for these instances. Their evidence came largely from the refuted hypotheses. A few bounds are false, among them a lower bound of Goldstein, Lewenstein and Porat for Set Disjointness over small universes; the Strong SetDisjointness Conjecture also fails at small polynomial query times. Other bounds have lost their support, such as the Set Disjointness trade-offs of Kopelowitz, Pettie and Porat over small universes apart from constant query time. Finally, we collect the known obstacles to a larger closed-form range with a different base identity and use border-rank lower bounds to exclude several natural candidates.
Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23716495
A mix of human-written and AI-generated textHuman understanding: all parts
The tensor ⟨4,4,4⟩ of 4×4 matrix multiplication has rank at most 47 over F2, and as it is not known whether 47 is optimal, we ask how far the known decompositions of rank 47 are from one of rank 46. A decomposition is locally optimal to depth D if no D or fewer of its rank-one terms can be replaced by fewer rank-one terms. We prove that five pairwise inequivalent decompositions of rank 47 over F2 are locally optimal to depth 18, as is every decomposition equivalent to one of them, so a decomposition of rank 46 over F2 shares at most 28 terms with any decomposition in these five classes. The five classes include the scheme of Fawzi et al. and every public decomposition of rank 47 over F2 known to us; one of them, found in our flip-graph searches, is new. The proof rests on a peeling lemma and, for four sets of terms that resist the other bounds, on a refinement of the substitution method, which we call substitution over subspaces with lifting. Local optimality to depth 18 is also proved in Lean 4.
Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23721965
A mix of human-written and AI-generated textHuman understanding: all parts
We study (t,n)-selection networks, which move the t largest of n inputs to t given lines in any order, and the least number U^t(n) of comparators in such a network. Alekseev showed that U^t(n)≥(n−t)⌈lg(t+1)⌉. For t=2k≥4 we raise this bound by k−1 for every n>t, and by 2k−5 when t≥32; as far as we know, these are the first improvements at powers of two. The proofs follow the weights of the lines, and a pruning step of Yao extends the gain to every t≥3. For t=3, Yao's upper bound 2n−5+⌊lg(n−3)⌋ is exact for 4≤n≤18. For t=4 the new bound is 3n−11 for all n≥5, and the value 3n−10 that Knuth expected is exact for 6≤n≤12. Their lower bounds rest on exhaustive searches at a few sizes and on the fact that one more input costs at least two more comparators. Most of the results are also proved in Lean 4, some through compiled checks.
Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23801189
A mix of human-written and AI-generated textHuman understanding: all parts
We prove that the rank of the 4×4 matrix multiplication tensor over F2 is at least 35; the previous lower bound was 34. The bound follows by substitution from RF2(⟨3,3,4⟩)≥27, which also gives RF2(⟨3,4,4⟩)≥31. Each of the three bounds is one more than what follows from RF2(⟨3,3,3⟩)=23. A flattening argument reduces the bound for ⟨3,3,4⟩ to lower bounds for two quotients of the tensor, by the span of a matrix of rank two and by the span of a matrix of rank three. These come from exhaustive searches over the possible patterns of a short decomposition, pruned by lower bounds for quotients by larger subspaces. The whole argument, including every step of the searches, is checked in the proof assistant Lean 4, with one compiled evaluation of a verified certificate checker.
Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23749576
A mix of human-written and AI-generated textHuman understanding: all parts
Finster, Kleiner, and Paganini derived from causal fermion systems (CFS) a nonrelativistic effective collapse model whose statistical operator obeys, to leading order, a Kossakowski--Lindblad equation. In the factorized regime of that derivation, the dissipator is built from purely spatial operators Nk,a with positive rates fixed by microscopic time-nonlocal kernels. We translate this CFS-specific generator into quantities accessible to coherent quantum processors. The resulting CFS Dirichlet form obeys an exact purity-loss identity under arbitrary Hamiltonian control, and its null algebra is the commutant of the ∗-algebra generated by the projected Nk,a. For joint eigenbranches we obtain an exact distinguishability functional controlling exponential coherence loss and a lower bound on channel distance from ideal unitary evolution. In an n-qubit dephasing sector, the projected kernels generate a positive-semidefinite covariance matrix C, with GHZ visibility exp[−2T1TC1]. We prove that uniformly summable finite-range correlations yield at most O(n) GHZ decay, whereas O(n2) scaling requires a collective non-summable component. Single- and two-qubit cat coherences reconstruct C, giving a covariance-spectroscopy protocol, while Knill--Laflamme conditions characterize first-order correctability of the projected CFS error algebra. We also derive an explicit compatibility inequality between macroscopic state reduction and long coherent computation and show why absence of probe heating does not imply absence of coherence signatures. The results do not exclude CFS: its covariance strength, $\ellmin$, and hardware projection remain underdetermined. They instead identify the microscopic input required for a genuine no-go theorem and establish scalable quantum processors as direct probes of the CFS collapse sector.
We characterize the signal-energy complexity of distributed agreement over independent Gaussian point-to-point channels. For n processes deciding L binary coordinates under coordinatewise unanimity validity and a joint failure probability of at most ε, every finite causal protocol requires a worst-input expected signal energy of Ω(N0n[L+ln(n/ε)]). This lower bound combines two distinct mechanisms: an exact relative-entropy identity for locally interchanged reception histories yields the reliability term even in the presence of shared randomness and active noisy feedback, while a coordinatewise direct-sum argument establishes the payload term. In the fault-free setting, a deterministic fixed-leader protocol attains this optimal order for all 0<ε≤1/8. In the presence of f≤(1/3−κ)n static Byzantine faults, the same order is achieved in the polynomial-error regime ε≥n−a via public committee sampling and robust joint decoding within explicit finite storage and computation budgets. Consequently, batching amortizes the reliability overhead, yielding an energy cost of Θ(N0n[1+L−1ln(n/ε)]) per coordinate. We then connect this communication optimum to physical dissipation through a stochastic-thermodynamic model of a thermal channel port. Under a non-recovering mode replacement interface, the communication converse translates directly into lower bounds on entropy production and, when the endpoint mean internal energies agree, cyclic work. When work recovery is permitted prior to mode reset, we derive the exact minimum reset entropy production within a bounded-displacement control class as a function of the information accessible to the recovery controller, thereby separating the fundamental communication cost from its control-dependent thermodynamic realization.
Primarily human-written textHuman understanding: all partsByzantine agreementGaussian channelsconsensusenergy complexityentropy production
We describe a natural new example of non-computability in analysis. Namely, the multiplicative autocorrelation of the fractional-part function,
\[
A(x)=\int_0^\infty \{t\}\{xt\}\,\frac{dt}{t^2},
\]
is computable and differentiable almost everywhere, but its finite derivative can be non-computable even for a computable x. We derive these results from an adaptation of our earlier work on computability of Brjuno-like functions.
A mix of human-written and AI-generated textHuman understanding: all parts
Optimization theory proves three kinds of theorems: that optimal points exist, that algorithms converge to them, and that optimality can be certified by duality. We measure how much mathematics each kind needs, using reverse mathematics, Weihrauch complexity and proof mining, and assemble the answers, old and new, into one map stated in the language of optimization. Compactness makes existence cost weak Kőnig's lemma, but convexity (and, format by format, tameness) makes it cheap: we show that RCA0 proves that convex functions on [0,1] attain their minima (and on [0,1]n, for each fixed n, given a modulus of uniform continuity), and that RCA0 proves linear programming duality and the minimax theorem for real data of every size. Convergence costs more: it follows from results of Kohlenbach and Neumann that convergence of gradient descent for convex smooth functions on R is equivalent to ACA0. We explain this by a selection principle: what costs is the particular minimizer the algorithm selects, and uniqueness or an error bound removes the cost. Below convergence lies finitary information. Gradient descent in Rd has at most 2CdD/ε fluctuations of size ε, with Cd depending only on d, which yields rates of metastability; no such bound is dimension-free, by the span-restriction argument behind performance estimation; and the limits of gradient descent on computable instances have d.c.e. coordinates, a proper subclass of the limit-computable reals. The map also covers Ekeland's variational principle (up to Π11-CA0), separation theorems, Kőnig duality (ATR0), proof-mined rates for fixed-point iterations, and the feasible world, where local search captures the NP search problems provably total in T21 and approximate stationary points of smooth functions are complete for CLS=PPAD∩PLS. We close with five principles and open problems.
OpenAI’s openai/math release includes a Lean formalization of “Uniform exclusion of Landau–Siegel zeros” (OpenAI, October 1, 2026). Its Comparator challenge has two checked theorems, whose statements we prove equivalent in Lean. OpenAI proves them by two routes, neither through the paper’s proof of Lemma 3. The catalogued main result, exists_absolute_real_zero_gap, gets its spanning step from a local Bézout argument and does not use OpenAI’s Corollary 4 theorem. The second theorem, dirichletRealZeroBound_proof, proves Corollary 4 by a multiplicity estimate. We formalized the paper’s proofs of Lemma 3 and Corollary 4 in Lean. By reading, the Lean statements match the paper’s, and the declarations use only the axioms propext, Classical.choice and Quot.sound. A +2/-1 substitution puts the paper’s Corollary 4 into dirichletRealZeroBound_proof. Comparator accepts the result with both kernels at openai/math fd4aeeb under a deny list of all 45 socket address families, and that theorem’s closure no longer contains the three named OpenAI lemmas. Our replay of the corpus agrees with an independent replay on all 402 configurations where both have a verdict.
Primarily AI-generated textHuman understanding: some parts
Mutation-acyclicity of integral skew-symmetrizable matrices belongs to NP. Mutation equivalence belongs to promise-NP when at least one input is mutation-acyclic. For pairs of mutation-cyclic matrices, mutation equivalence is RE-complete and strongly NP-hard. Both results hold even for connected skew-symmetric matrices.
Author comments: I am posting this manuscript to share the mathematical results themselves. In doing so, I do not seek to assert ownership of the results or claim priority. I welcome anyone interested in checking the arguments or preparing a finished account, and I believe the eventual scholarly credit should go to those who undertake that work.
A mix of human-written and AI-generated textHuman understanding: some parts
For more than fifty years, since Horowitz and Sahni's meet-in-the-middle algorithm of 1974, the best exponent for worst-case Subset Sum was 1/2. In October 2026 that barrier fell twice within a week, with OpenAI's 20.49n algorithm and, independently, Li and Ye's 2(1/2−1/450000)n≈20.4999978n, and improvements have followed quickly since: within three weeks A. Kapila's modification of the OpenAI approach ("Base") reached 0.4877, a retuning of Base by JoshuaQFEX reached 0.487676, and a refinement by Y. Bills reached 0.4876723. Here we push this line of work further and examine what limits it. Conditional on the cited non-numerical proofs, we give a certified parameter point with threshold T=0.4875754036: for every fixed T′>T, the uniform randomized algorithm uses O(2T′n) word operations on inputs of polynomial bit length, with success probability at least 2/3. In particular, it runs in time O(20.4875755n). A single asymmetric filter replaces Base's family of 43 filters. Independent interval computations certify all required numerical conditions, including both filtering moments and their quadrature errors.
We prove a lower bound on the first filtering moment, valid for all positive continuous densities, that excludes every parameter choice with τ≤0.484 in the original OpenAI proof's sufficient budget. Three algebraic bounds explain the costs at our improved point. Separately, an enumeration phase that inserts at least 2(1−η−o(1))n alias classes, spending a counted step on each, and uses checksum gap at most Δ needs exponent at least (1−Δ)/2. This is a conditional operation-count bound; a global upper bound on achievable checksum capacity remains open. Finally, we isolate a small-layer statement that would yield threshold 0.4873407528, prove combinatorial special cases, and identify the remaining questions.
Author comments: 30 pages, 2 figures. The main result is conditional on the written proofs of OpenAI (4 Oct 2026) and A. Kapila (commit 44c34961); its numerical conditions are certified in interval arithmetic. The companion file SECTION_T_v3.pdf (full proofs of the ternary alias step, Appendix A) is included with the source. Code, certificates, verification scripts and a timestamped research record: https://github.com/jv1000/subset-sum. AI use is described in Section 11.
A mix of human-written and AI-generated textHuman understanding: some partsAI-assisted mathematicsFourier filteringSubset Sumcomputer-assisted proofexact algorithmsinterval arithmeticmeet-in-the-middlerepresentation techniqueworst-case complexity
We prove that quiver mutation equivalence up to relabeling is undecidable even for one fixed source quiver. We also prove strong NP-hardness.
Author comments: I am posting this manuscript to share the mathematical results themselves. In doing so, I do not seek to assert ownership of the results or claim priority. I welcome anyone interested in checking the arguments or preparing a finished account, and I believe the eventual scholarly credit should go to those who undertake that work.
A mix of human-written and AI-generated textHuman understanding: some parts
In October 2026 OpenAI and Anthropic each claimed a deterministic subexponential algorithm for counting the solutions of a k-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 U 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×2 grid and of the full 3×3 grid level have flattening-rank sums at least N2, N3 and N8, while N9 is open; the row cut of the permanent has rank (kn), which on paper gives U≥nlog2(n/s) for row-local networks; algebras in which the permanent is a functional of a product have dimension at least (n/2n); pieces have saving ρ≥1/2 (rank form; Anthropic's observation); and exact colouring filters for Hamiltonicity need q≥n−4 colours. On paper we prove U≥(1−o(1))nlog2n for vertex-local networks for the Tutte polynomial off the integer hyperbolas, and ρ≥3/8 for correlated decompositions of full grid levels. We cite 45 Lean theorems, with standard axioms only. Every barrier is about a named model: in Anthropic's general model no unconditional bound on U exists without separating P from P#P, and an unconditional cap on oblivious algebraic algorithms would separate VP from VNP.
Primarily AI-generated textHuman understanding: some partsExponential Time HypothesisSATTutte polynomialcorrelated decompositionscut rankengine barrier problemtensor networks
In-context learning is often explained as implicit Bayesian inference: given labeled examples of a task drawn from a prior, the learner predicts like the posterior. We determine the computational price of this explanation for task families whose labels depend on few bits of the task description, such as quantized models on sparse data, and we compare it with the price of merely learning. The comparison uses the recent refutations of the Exponential Time Hypothesis by OpenAI and Anthropic.
Bayesian inference in context is counting. For κ-local task families with N-bit descriptions under the uniform prior, the posterior predictive and posterior sampling reduce to #κ-SAT. Without label noise they run in time poly(m)⋅2o(N) on contexts of every length m when κ=o((logN)1/4/loglogN), and label noise is handled by error profiles. A two-variable gadget gives contexts that are always consistent and whose posterior predictive is 2#F/(2#F+1) for a CNF F. So approximating the posterior predictive within 1/4 needs time 2(1−γ)N at locality O(logN) under CNF-SETH, and time 2N/polylogN at locality 3 under a length form of ETH. At constant locality, Bayesian inference in context is SAT parameterized by formula length.
Learning in context is cheap. The Bayes risk of any class with N-bit descriptions is at most N/(m+1) after m examples. For binarized perceptrons and literal disjunctions on sparse data, the very families of the lower bounds, a linear program is a polynomial-time in-context learner with essentially the same sample efficiency. Every κ-local family is linear over ∑j≤κ(jN) local Fourier features, so regression in context learns it from NO(κ) examples, in time polynomial in Nκ and the inverse accuracy.
The average case. For Goldreich's random local functions, the Bayes risk is at most N/(m+1), while every in-context learner yields a distinguisher for Goldreich's generator, with the same running time up to a linear term, whose advantage is 1/2 minus the risk. Under a local pseudorandom generator hypothesis with polynomial stretch, polynomial-time in-context learners need polynomially more examples than the Bayes predictor. Under its length form at linear stretch, which the new algorithms refute below rate 1/2, the Bayes predictor of the refutations is optimal up to polylogarithmic factors in the exponent.
For transformers, these bounds limit the length of a chain of thought that computes the posterior predictive, and they separate Bayes-optimal in-context learning from the regression-type in-context learning that transformers are known to implement.
Primarily AI-generated textHuman understanding: some partsBayesian inferenceCNF-SETHExponential Time HypothesisGoldreich's generatorfine-grained complexityin-context learninglocal pseudorandom generatorsmodel countingposterior predictivetransformers
Alman and Song showed that attention with head dimension O(logn) can be approximated in almost linear time when the entries are o(logn), and needs quadratic time at Θ(logn) under the Strong Exponential Time Hypothesis. In October 2026 the Exponential Time Hypothesis was refuted, and with it SETH. The quadratic lower bound now rests on the hardness of Orthogonal Vectors in dimension clogn (LDOV), which no open hypothesis about satisfiability is known to imply. We measure an instance by its spread W, the largest gap between two logits of a row. At every nontrivial constant precision and in every dimension between ω(logn) and no(1), we show that under LDOV the time exponent of attention is exactly 1+min{W/lnn,1}: uniform sampling of keys is optimal, the cost is min{neW,n2} up to factors no(1), and the transition to quadratic time sits at W=lnn, the spread at which one key can outweigh all others. At polynomial precision and in dimension O(logn) the threshold becomes Θ(logn), with a constant that tends to zero as the precision grows, and the dimension moves it: at precision n−1−O(1/loglogn), spread O(logn/loglogn) is hard in dimension (logn)1+Ω(1) but easy in dimension O(logn). From satisfiability we obtain hardness at spread (1+θ)lnn in dimension no(1), provided the hard CNF formulas have Nc0 clauses for some c0<2, and we show that the construction behind this bound, which builds one instance for each proof of a Merlin–Arthur protocol for disjointness, needs c0<2 for every such protocol. For the entry bound, every reduction that embeds Orthogonal Vectors vector by vector, with polynomial blowup and logit gap Ω(logn), yields a Merlin–Arthur protocol for disjointness; by Klauck's lower bound, such reductions cannot derive B=Θ(logn) from Orthogonal Vectors in dimension (logn)1+Ω(1). We also map the conditional lower bounds for attention in the literature to the hypotheses that now support them, and find two families whose hypotheses are false, one of them in part of its parameter range.
Primarily AI-generated textHuman understanding: some partsCNF-SETHMerlin-Arthur protocolsOrthogonal VectorsStrong Exponential Time Hypothesisattentioncommunication complexityfine-grained complexitypolynomial methodsoftmaxtransformers
Computing the prime-counting function π(x) exactly takes x1/2+o(1) steps by the analytic method of Lagarias and Odlyzko, and to our knowledge its parity is known faster only on short intervals: Tao, Croot and Helfgott decide whether an interval of length at most x1/2+c near x contains an odd number of primes in time x1/2−c+o(1). However, their identity needs the Mobius function μ(d) for all d≤x, and we know of no bound of the form xo(1) for the parity, even conditionally. We present deterministic algorithms that output π(x)mod2 and the parity of the number of primes in any interval [A,B] in time 2O(n/logn)=xo(1), where n is the input bit length. Our approach replaces μ(d) by its residue modulo 2, which is the squarefree indicator again: the number of chains d12∣m, d22∣d1,… of depth L is odd exactly when m is squarefree, for m<22L. The parity of π on [A,B] is then the parity of one count of tuples satisfying O(logn) multiplications, which Anthropic's counting engine evaluates through a network whose variables have geometrically shrinking widths. We prove both theorems in Lean 4 (piParity_TM_rate, piIntervalParity_TM_rate; axioms propext, Classical.choice, Quot.sound). The result does not give deterministic prime finding or the exact value of π(x): the parity can be even on every interval one queries, and exact counts seem to need iterated products, for whose product-tree verifiers we prove a lower bound in Lean. The constants are astronomical, and the result rests on Anthropic's Lean development of its claimed refutation of the Exponential Time Hypothesis, which is under review.
Primarily AI-generated textHuman understanding: some partsExponential Time HypothesisMobius functiondeterministic prime findingdivisor chainsparity of pi(x)prime-counting functionsquarefree numbers
Basic counting problems of computational number theory have proven deterministic bounds that are fixed powers of the input. The class number h(D) of an imaginary quadratic discriminant takes ∣D∣1/2+o(1) steps unconditionally and ∣D∣1/5+o(1) under the generalised Riemann hypothesis (GRH); exact divisor sums ∑m≤xτ(m) take x1/3+o(1). However, none of these bounds is of the form Xo(1), even conditionally. We present deterministic algorithms in time 2O(n/logn), where n is the input bit length, for the number of reduced forms of discriminant −N (for fundamental discriminants, h(−N)) and for ∑m≤xτ(m), ∑m≤xσ(m) and the Gauss circle count. Our approach writes each answer as a count of solutions of equations with one or two products and evaluates it with Anthropic's counting engine through one network library with O(n) shared bits. The same library gives the least square root modulo any m and the least quadratic non-residue modulo a prime. These are not new bounds (OpenAI's results on the quasi-Riemann hypothesis and on deterministic polynomial factorisation over Fp give polynomial time modulo a prime), but they are machine-checked. We prove the seven resulting theorems in Lean 4 (for example hForm_TM_rate; axioms propext, Classical.choice, Quot.sound): a finite-alphabet Mathlib Turing machine outputs the answer within ⌊C⋅2Cn/log2(n+2)⌋ steps on every input. Lean proves the count of Gauss's reduced forms; its equality with the ideal class number is classical and not formalised. The constants are astronomical, the machines use exponential space, and every result rests on Anthropic's Lean development of its claimed refutation of the Exponential Time Hypothesis, which is under review. Version 2 corrects the claims of version 1 about non-residues and square roots.
Primarily AI-generated textHuman understanding: some parts
Classical simulation lower bounds for quantum circuits have been derived from the Exponential Time Hypothesis (ETH). However, in October 2026 OpenAI and Anthropic claimed deterministic subexponential algorithms for #k-SAT, refuting ETH, and neither manuscript mentions quantum circuits. We record the corollary. Assuming three internal results of the Anthropic manuscript, one deterministic Turing machine computes the amplitude ⟨y∣C∣x⟩ of a Clifford+T circuit with G two-qubit gates in arbitrary connectivity exactly, as an element of Z[ω]/2k with ω=eiπ/4, in time 2O(G/logG) whenever the input length L satisfies logL≤G0.9. The proof reads the sum over paths, one bit per wire segment, as an Anthropic-type network, with a Kronecker map for Z[ω] and a Galois bound. We machine-check this theorem in Lean 4 (amplitude_TM_rate', amplitude_TM_rate, amplitude_TM; axioms propext, Classical.choice, Quot.sound) on top of Anthropic's Lean development (sources at https://github.com/xennygrimmato/eth-hamiltonicity). On paper only, the method gives exact marginals and exact sampling, depth-d circuits in 2O(dn/logn), and, through OpenAI's tensor-contraction theorem, polynomial space when the number of Hadamard-type gates is O(G). Conversely, constant-depth circuits with O(n) gates encode #3-SAT with O(n) clauses, so the rate matches that of the refutations. We check the fine-grained supremacy conjectures we found against their sources; a counting form of the Calabro-Impagliazzo-Paturi width reduction refutes the gap conjecture of Morimae and Tamaki's depth-scaling paper. Dense statements (cubic phases, permanents, random circuits) survive. Nothing here concerns approximate sampling, the constants are galactic, and everything is conditional on the claimed refutations, which are under review.
Counting the Eulerian circuits of an undirected graph is #P-complete, even for planar 4-regular graphs, while for directed graphs the BEST theorem counts them in polynomial time. However, we are unaware of any exact algorithm for undirected graphs of bounded degree that runs in time 2o(m), where m is the number of edges. We show that such an algorithm follows from the exact counting of Hamiltonian cycles that we proved earlier on top of Anthropic's claimed #SAT algorithm. The reduction is classical: by Kotzig's description, the Eulerian circuits of G are in bijection with the Hamiltonian cycles of the line graph of the double subdivision of G, which has 3m vertices and at most (Δ+1)m edges. We prove in Lean 4 (theoremEuler, theoremEuler_noIso, theoremEuler_rate; axioms propext, Classical.choice, Quot.sound) that for every δ>0 and Δ a finite-alphabet Mathlib Turing machine outputs the number of Eulerian circuits of every graph of maximum degree at most Δ within ⌊C(n+2)C2δm⌋ steps, and within ⌊C2δm⌋ steps when there is no isolated vertex; and that one machine does so for all graphs within ⌊C(n+2)C2Cmlog2(Δ+2)/log2(m+2)⌋ steps. The factor (n+2)C pays for reading the n2-bit adjacency matrix and cannot be dropped. The bijection is checked by brute force on twelve small graphs, for example 132 circuits for K5. The formal object is Kotzig's transition-system definition; its agreement with Mathlib's Eulerian walks is not formalised. The constants are astronomical, and the proof rests on Anthropic's Lean development of its claimed refutation of the Exponential Time Hypothesis, which is under review.
For d≥3 with −d≡0,1(mod4), let h(−d) be the number of classes of primitive positive definite binary quadratic forms of discriminant −d. We prove that d↦h(−d) is computable in deterministic polynomial time with an oracle for a language in the second level Σ2P of the polynomial hierarchy. The proof uses only reduction theory of binary quadratic forms, Lagrange's theorem and Hermite normal forms; it does not assume the generalized Riemann hypothesis, does not take a generating set of the class group as input, and uses no randomness. A Σ2P oracle finds a generating set of O(logd) forms, and an NP oracle then determines the lattice of relations, whose index is h(−d). Consequently, if P=NP, class numbers of imaginary quadratic fields are computable in polynomial time. As an application, the number Dn of representations of n by the ternary form 8x2+2y2+16z2 in Tunnell's congruent number criterion equals 2h(−4n) for square-free n≡2(mod8) and vanishes for square-free n≡6(mod8); hence Dn lies in FPΣ2P on even square-free n, and an exact counting reduction from #SAT to Dn would collapse the polynomial hierarchy to Δ3P.
Author comments: In this new version, we have added a computer-based numerical verification.
Primarily AI-generated textHuman understanding: all partsHermite normal formTunnell's theorembinary quadratic formsblack-box groupsclass numberscongruent numberscounting complexitypolynomial hierarchy
The subsets of {1}∪{p≤N} reach every integer between 0 and their total, by Bertrand's postulate, so deciding whether a target is a subset sum of the primes is trivial. Counting the solutions is not: the count carries the arithmetic of the primes. We study the generating function FN(z)=Π(1+zw) on the unit circle and follow one object, the arc at a rational a/q, through three settings.
For the primes, the centre of the arc a/q rises above the sea of the minor arcs exactly when q=2k(k≥2) or q=2pj, with excess Λ(q/2)/φ(q), and the neighbourhoods of all the other arcs are bounded uniformly in q; Theorem E gives the expansion arc by arc. The height of an arc is a race of the primes modulo q with weights log∣cos(πra/q)∣. By Landau's theorem a one-sided bound on it is equivalent to GRH for the even characters it sees, unconditionally at q=8, 10 and 14, where the zero-free segments it needs are certified; at q=14 the race changes sign infinitely often. The principal arc carries ζ in the centre and width of its Gaussian.
For arbitrary weights, the arcs become the decision rule of a Subset Sum solver that reads them on the original weights and ends with a meet-in-the-middle filtered by a random residue class. Every answer it returns is verified. The dummy weights of HURS explain why the reading is exact: they blur the counts by a flat window, and the blur is invertible on counts, though not on reachable sets. On random weights of b bits the method has rigorous guarantees, in time 2b/2+o(b) and, with the filter, 2b/3+o(b), resting on a local limit theorem uniform in the size of the weights and on a concentration bound for signed subset sums. Finally, the solver is read inside a general theory of constraint propagation, in which every network factors as T=Tcomp∘Tstruct.
A mix of human-written and AI-generated textHuman understanding: some partsDirichlet L-functionsGRHSubset Sumcircle methodconstraint propagationlocal limit theoremmeet-in-the-middleprime races
Contributed by Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník
Continuous Ulam Metric k-Center asks for at most k permutations whose radius-d balls cover the input rankings. For m rankings of n symbols, a deterministic algorithm takes 2O(kdlog(k+d+2))mn word operations. Permanent reference rankings, short insertion lists, and small obstructions obtained by patience sorting control the search. For one center, this answers a question of Bai, Fomin, Golovach, More, and Wietheger with linear input dependence. An arbitrary-alphabet Hamming embedding with a nonexpansive retraction also gives the matching 2o(dlogd) exclusion under the Exponential Time Hypothesis.
Primarily AI-generated textHuman understanding: some partsExponential Time HypothesisUlam distancecontinuous k-centerparameterized algorithmspatience sortingrank aggregation
Contributed by Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník
In bottleneck multiple subset sum, items with weights are packed into knapsacks with capacities, possibly leaving items unpacked, so as to maximize the minimum load. For identical capacities the best possible approximation ratio is 2/3, and Chen et al.\ asked whether 2/3 is also achievable for arbitrary capacities. We show that it is not: for arbitrary capacities we give a 1/2-approximation using O(nlog(n+1)+mlog(m+1)) arithmetic and comparison operations for n items and m knapsacks, and prove that no fixed ratio above 1/2 is achievable unless P=NP. We also give a short proof of the classical 1/2 guarantee of Friesen and Langston for unit profits.
Contributed by Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník
An edge clique cover has assignment cost equal to the sum of its clique sizes. Unless P=NP, this cost admits no polynomial-time O(N1/2−η)-approximation for any fixed 0<η<1/2, even on connected N-vertex graphs. A universal-clique join transfers coloring hardness without the additive obstruction in earlier reductions. Its exact residual formula also exhibits a change of optimal cover when a universal twin is added. Explicit counterexamples refute two proposed twin-extension rules, while weighted compression of true-twin classes preserves the optimum.
Primarily AI-generated textHuman understanding: some partsGraph coloringassignment costedge clique coverhardness of approximationtwin reductionsuniversal-clique joinweighted clique covers
The Minimum Independent Dominating Set problem asks for a smallest maximal independent set of a graph. Unless P=NP it is not approximable within n1−ε for any ε>0; it is NP-complete on cubic planar bipartite graphs and NP-hard to approximate within δB on bipartite graphs of maximum degree B. We present version 0.0.9 of \textsc{Siriaisa}, an ensemble of eighteen strategies that adapts the vertex cover algorithm \textsc{Salvador} and the independent set algorithm \textsc{Esperanza} to independent domination: its exact subproblems are forests, solved by a conditioned tree dynamic program, in place of the bipartite structures of \textsc{Salvador}; one base strategy splits every vertex of degree larger than ⌊n⌋ into unconnected copies; and the improvers include a weighted swap search. We prove that the output is an independent dominating set computed in O(n+m) expected time, with ratio at most Δ, optimal on forests, and with ratio at most n on three classes of graphs. The degree-splitting strategy computes a dominating set of size at most ⌊n⌋(i(G)+s(G)) on every graph, for an explicit splitting excess s(G), and the output satisfies the same bound when the decoded set is independent. The excess is at most n(n+1), largest on complete graphs, zero for n≥D2 on every family of bounded degree D, among them the NP-hard and UG-hard bounded-degree families, and O(n) on planar graphs; on complete multipartite, crown, wheel and double-star graphs the output is optimal. We conjecture the ratio O(n) on all graphs; a proof would imply P=NP. In a reduction from satisfiability, every independent dominating set of the graph of a formula with N variables and t copies of every clause, t at least the largest clause width W, is a satisfying assignment, with N vertices, or has at least t+N vertices; with t=W, every independent dominating set of ratio smaller than 1+W/N is a satisfying assignment. This proves the n1−ε inapproximability directly from satisfiability, without a gap from the PCP theorem. Through a reduction of Chleb{\'\i}k and Chleb{\'\i}kov{\'a}, with an explicit edge gadget that turns a graph H into a graph h(H) with i(h(H))=τ(H)+2∣E(H)∣, where τ(H) is the minimum vertex cover size, every output on h(H) decodes into a vertex cover of H; we state the conditional consequences under the Unique Games Conjecture, for which a proof has been reported but not yet peer reviewed, on general graphs and, through the result of Austrin, Khot and Safra, on bounded-degree graphs. In reproducible experiments the output is optimal on 9999 of 10000 graphs with an exact integer-program optimum, on all 95 of 112 bipartite graphs whose optimum was proved, on all 18 instances of the set cover reduction, and on 2 of the 30 instances of the vertex cover reduction with a proved optimum; on ten Khot--Regev YES instances the decoded vertex cover has ratio between 1.25 and 1.8665. We also report the results on the 68 complements of the DIMACS clique benchmark.
Primarily AI-generated textHuman understanding: all partsApproximation AlgorithmBoolean satisfiabilityForest Dynamic ProgrammingMinimum Independent Dominating SetMinimum Maximal Independent SetP versus NPUnique Games Conjecturebipartite graphslocal search
We give a deterministic algorithm for binary constraint satisfaction whose exponent
in the input size is sublinear in treewidth on a class of graphs with unbounded treewidth. There
are a class G of graphs of bounded maximum degree, a constant c, and a function f such that
one algorithm correctly decides every binary CSP instance and, on instances I with primal graph
G ∈ G, runs in time
f(G) · ||I||^(c · tw(G) / sqrt(log tw(G)))
.
This contradicts the literal formulation of Conjecture 1.4 of Marx (2010). The algorithm follows
from a domain-uniform counting bound: for every fixed maximum degree ∆, complete-table in-
stances with k variables and domain size D ≥ 2 can be counted in time LO∆ (1)DO∆ (k/√log k) for
sufficiently large k. The constants are independent of D and of the constraint relations. We obtain
this bound from the tensor-network recursion of Claude (Anthropic), and use attributed graph
foundations from OpenAI to construct the required expander family. Support pruning connects
the counting routine to sparse tuple-list inputs without expanding the original domain. The algo-
rithm, its native finite-alphabet machine implementation, and the conjecture counterexample are
formalized in Lean 4.
Primarily AI-generated textHuman understanding: some parts
We prove that the complete prime factorization of an n-bit integer can be computed deterministically in time 2O(n/logn) and polynomial space. This establishes the bound conjectured by Rudich and Rousseau, sharpening their qualitative No(1) result. The proof combines OpenAI's quantitative Boolean tensor-contraction theorem with the linear-size multiplication encoding of Akshima et al. The encoding permits exact counting of divisors with prescribed binary prefixes without loss in the exponent. The least prime factor is then recovered by successive prefix queries, and iteration yields the complete factorization within the same asymptotic bound.
Primarily AI-generated textHuman understanding: all partsBoolean tensor networksdeterministic algorithmsexact countinginteger factorizationsubexponential time
The maximum independent set problem asks for the largest set of pairwise non-adjacent vertices in an undirected graph. It is NP-hard to approximate within n1−ε for every ε>0, and under the Unique Games Conjecture it is hard to approximate within O(Δ/log2Δ) on graphs of maximum degree Δ; the Khot--Regev form of the conjecture, for which a proof has been reported but not yet peer reviewed, also rules out a (2−ε)-approximation of Minimum Vertex Cover. We present version 0.1.6 of \textsc{Esperanza}, which takes the better of a dynamic minimum-degree (Caro--Wei) greedy set and the complement of the \textsc{Salvador} vertex cover, and improves it by three budgeted local searches: repair-and-grow restarts at the cover vertices and at a maximum-degree vertex, chained local restarts realising (k,k+1)-improvements, and an iterated (1,2)-swap search. We prove that it runs in O((n+m)αA(n)) expected time for fixed budgets, with αA the inverse Ackermann function. We prove that the output is a maximal independent set, that its complementary vertex cover has at most 2τ−r vertices, where τ is the minimum cover size and r the number of components with an edge, and that the ratio is at most (Δ+2)/3 on graphs of maximum degree Δ. We prove the ratio 2n on every graph with Δ≤n and on three further classes, and state it for all graphs as a conjecture, whose proof would imply P=NP. We also state the conjecture that the complementary cover has at most 2τ−∣M∣ vertices for the NetworkX minimum maximal matching M; a proof would give a 3/2-approximation for Minimum Vertex Cover and refute the Unique Games Conjecture unless P=NP. In reproducible experiments the returned set is optimal on all 30000 graphs of a suite certified by an exact integer program; on 40 Khot--Regev YES instances with 640 to 2560 vertices the conjectured bound is certified on 38 and open on 2; and on 31 bounded-degree graphs the certified ratio is at most 1.0769 on the families with a planted independent set.
Primarily AI-generated textHuman understanding: all partsApproximation AlgorithmBounded-degree GraphsLinear TimeMaximum Independent SetP versus NPUnique Games ConjectureVertex Coverlocal search
We give a deterministic polynomial-time primality test whose main verification is the congruence (1+X)n=1+Xn in Cn[X]/(Xr−b(Y)), where Cn=(Z/nZ)[Y]/(Φr(Y)). Two identities in the coefficient ring normalize b and ensure compatibility with the main congruence. A finite-field root count and a lattice bound show that an accepted input is a prime power; elementary preprocessing excludes nontrivial perfect powers. We construct b deterministically using Jacobi sums and the uniform Dedekind-zeta zero-free theorem of Cureton and Thorner, which extends OpenAI's Hecke zero-free theorem. The total bit complexity is L32+o(1), where L=⌈log2n⌉, and verification after constructing b costs L6+o(1). More generally, for a fixed real algebraic 1/2≤θ<1, a common zero-free boundary ℜs>θ for the relevant Dedekind zeta functions gives Lmax{6,(1−θ)−1}+o(1). This bound reaches L6+o(1) at θ=5/6, and hence under GRH. We state a fixed-base modification of Agrawal's conjecture for odd integers passing the base-2 Fermat test, using the modulus Xr−2 with r the least positive integer not dividing n(n−1).
In Appendix B of "A 2o(n) time algorithm for 3-SAT" (Claude, Anthropic, hexagon:2610.00577) the gain parameter ρ=1/2 comes from the Hardy--Ramanujan growth logp(E)∼cE of the partition numbers, and Appendix H observes that growth of order Eα would give ρ=2α−1 by the same calculation. We point out that the rank floor stated in the same Appendix H already excludes α<1/2 for every graded family of the same shape: the pieces at weight h have total rank at most (4h+1)dimV≤4h in one of the two directions, and the crossing they must add up to has rank (dimVh)2, so the construction needs logdimV≤4h≥2logdimVh−O(logh), that is α≥1/2. Restoring the rank with a larger weight costs ρ≥2−α in the weight count, so the count never goes below max(2α−1,2−α)≥1/2, with equality only at α=1/2; when the identity holds on the whole weight space, as Lemma 9 of the paper gives it, the bound sharpens to 2α/(2(4α−1)), which exceeds 1 for α<0.357. Theorem B of the paper is rank-tight up to a polynomial factor. The inequality is exact and we tabulate it: for the partition numbers it holds for every h, for partitions into squares (α=1/3) it fails for all h≥5891. We also record that the Heisenberg Fock spaces on a sparse set of modes, the natural candidates for slower growth, do not carry Lemma 9, and that no choice of coefficients repairs it. The floor ρ≥1/2 remains open.
Primarily AI-generated textHuman understanding: some parts3-SATExponential Time Hypothesisinteger partitionsrank bounds
In October 2026 two manuscripts claimed refutations of the Exponential Time Hypothesis by deterministic algorithms for #k-SAT, each with a Lean formalisation of its top-level statement. Neither result applies directly to connectivity problems such as Hamiltonicity, because no linear-size CNF encoding of "this edge set is a single cycle" is known. This paper derives a corollary of the Anthropic manuscript: assuming three of its internal results (a network-to-clique reduction, an algorithm for cliques of all levels, and the existence of its "pieces"), the number of Hamiltonian cycles of a graph with n vertices and at most Dn edges can be computed exactly and deterministically in time O(2δn) for every δ>0, and in time 2O(max(m,n)/logn) for a graph with m edges. A rank-encoded variant of the construction gives 2O(nlogdˉ/logn) for average degree dˉ. Deterministic decision, search and Hamiltonian-path counting follow, and so do exact sparse TSP with polynomially bounded weights, exact counting of directed Hamiltonian cycles, and ATSP. The result is not a standalone breakthrough; it stands or falls with the claimed refutation. The ingredients are known: the folklore matrix-tree identity on 2-factors, the fermionic (Berezin) matrix-tree theorem of Caracciolo, Jacobsen, Saleur, Sokal and Sportiello, and the blob partitions of Cut&Count. What is new is the observation that connectivity can be encoded with O(1) bits per edge through a Grassmann determinant whose only non-local part is a sign, and that this sign costs only O(g3) bits for g blobs, so the whole construction is a network in the sense of the manuscript, whose value is n⋅#HC(G). Every theorem we claim is formally verified in Lean, end to end, on top of the manuscript's own Lean development: the three counting theorems, the decision, search and path corollaries, sparse TSP, directed Hamiltonian cycles and ATSP, using only the standard axioms, with fresh kernel replays. The Lean sources are at https://github.com/xennygrimmato/eth-hamiltonicity. We also record weaker results that rest only on the machine-checked top-level theorems: the parity of #HC(G) for every graph in time 2O((m+n)/log(m+n)) (machine-checked in Lean, with the hypotheses discharged by the labs' own Lean proofs), and one-sided randomized decision. We describe what is proved, what is checked numerically, what is formalised, what is assumed, and what the limitations are.
Two recent works by OpenAI and Anthropic refuted the Exponential Time Hypothesis (ETH). They count the satisfying assignments of a k-CNF on n variables in time 2n/(logn)1/2−o(1). Many fine-grained lower bounds in learning theory rest on ETH and its relatives. We determine what the refutation changes for learning.
The answer is a locality principle: the new algorithms speed up learning when each labeled example constrains few bits of the hypothesis, and under the CNF form of the Strong Exponential Time Hypothesis, which survives, the speed-up ends at Θ(logN) bits. Three transitions make the principle precise.
Locality. Call a class with N-bit descriptions κ-local if each label depends on at most κ description bits, as for quantized models on sparse data. Then proper PAC learning, exact version-space counting and sampling, and the halving algorithm run in time poly(m)⋅2o(N) on samples of size m for κ=o((logN)1/4/loglogN), and proper PAC learning at constant accuracy does so for κ=o(logN). At inverse-polynomial accuracy, proper learning of κ-local classes is equivalent to κ-SAT, up to a factor 2 in the locality. Under CNF-SETH, consistency for binarized perceptrons on O(logN)-sparse data needs time 2(1−γ)N for every γ>0.
Accuracy. Exact empirical risk minimization, proper agnostic learning and the exponential mechanism reduce to tensor contractions over a truncated polynomial ring. As a consequence, the Sparse Max-SAT Hypotheses of Alman and Vassilevska Williams are false. At constant accuracy, proper learning is SAT parameterized by formula length. With quasi-linear PCPs this gives a 2N/polylogN lower bound under a length form of ETH, which replaces Gap-ETH for reductions of quasi-linear size. At accuracy N−3/8, the Max-3-SAT Hypothesis forces time 2(1−o(1))N.
Treewidth. Exact inference in graphical models of bounded degree and arity takes time 2O(n/logn). On expanders this beats every elimination order and every structured DNNF. Under #CNF-SETH, time 2(1−γ)tw is again necessary once a model may have twO(1) variables.
We also take stock of the conditional lower bounds of learning theory: which ones fall, and which ones survive on which hypothesis. The bound for training one ReLU loses its proof, because its hypothesis about Densest k-Subgraph on bounded-degree graphs is false. The next obstacle is a permutation problem. On difference vectors ei−ej, empirical risk minimization for real-valued halfspaces is weighted Feedback Arc Set, which the new algorithms do not reach.
Primarily AI-generated textHuman understanding: some partsExponential Time HypothesisPAC learningStrong Exponential Time Hypothesiscomputational learning theoryempirical risk minimizationfine-grained complexitymodel countingprobabilistic graphical modelstensor networkstreewidth
Reusing a stored Euclidean prefix, we show that every pair a≥b has a derivation of gcd(a,b) from a,b with O(loga/logloga) applications of the remainder function alone; Euclid's algorithm needs order loga in the worst case. These derivations bound the intrinsic complexity of gcd and coprimeness by the same order, refuting Moschovakis's conjectured logarithmic lower bounds for uniform processes; by his best-uniform-process theorem, a single uniform process attains this bound. The Main Conjecture for algorithms remains open. We also prove an Ω(logloga) lower bound on this complexity for almost all coprime pairs and give, for each ε>0, a nondeterministic register program computing gcd that, on every input a≥b≥1, has a successful computation using at most εloga+O(1) remainder calls. The upper bound also answers negatively an open problem of van den Dries and Moschovakis on the closure depth of the gcd. The main bounds and the refutations are formalised in Lean 4; the best-uniform-process theorem is cited.
Primarily AI-generated textHuman understanding: some partsEuclidean algorithmLean 4closure depthgreatest common divisorintrinsic complexityremainder functionuniform processes
Contributed by Isaac Rudich, Louis-Martin Rousseau
The current best upper bound for deterministic factoring is N1/5+o(1). We provide a Lean certificate that there exists a deterministic Turing machine that computes the smallest prime factor of every N in No(1) steps: for every k≥1 it runs within Ck2n/k steps on n-bit inputs. The algorithm reduces factoring to counting divisors with prescribed leading bits, and counts them by leveraging the counting engine used to refute the Exponential Time Hypothesis (ETH). The Lean statement that a reader must check to verify the proof is only 13 lines and only uses Mathlib. The full proof is about 35,000 lines. This note was written less than 24 hours after the ETH refutations were posted. No human-readable explanation of these results exists yet, and their Lean proofs are long: Anthropic's alone runs to about 152,000 lines. Our proof re-proves only the part of the counting engine it needs and imports nothing from those developments. We hope this application, with its short statement, serves as a stepping stone for those working to understand the engine; a follow-up paper will explain this proof in detail.
A mix of human-written and AI-generated textHuman understanding: some partsExponential Time HypothesisLeancounting algorithmsdeterministic factoringformal verificationinteger factorization
The deterministic algorithm of \oai{} that counts the satisfying assignments of a k-CNF in time 2o(n) is reproduced in full and extended from counting to sums of local weights with values in any commutative $\Q$-algebra. The extension gives deterministic 2o(n) algorithms for exact Max-Cut and Max-k-SAT on sparse instances, for the independence polynomial, the maximum independent set and the knapsack problem with a conflict graph on every graph, for 0-1 integer programs whose rows involve boundedly many variables, for Vertex Cover in time $2^{o(k)}+\poly(n)$, for the density of states of Ising and Potts models on bounded-degree graphs, for the Tutte polynomial on the hyperbolas (x−1)(y−1)=q, for the minimum distance and the maximum-likelihood decoding of codes with sparse parity checks, for Max-Cut and Max-k-SAT at every average degree o(logn/loglogn), for Max-Cut on dense graphs close to blow-ups of graphs with o(n/logn) vertices, and for every problem in $\SNP$.
A mix of human-written and AI-generated textHuman understanding: some partsExponential Time HypothesisLDPC codes.Max-SATTutte polynomialVertex Coverindependence polynomialpartition functionsweighted counting
We give a preliminary exposition of a qualitative form of the main result of OpenAI's preprint "The Exponential Time Hypothesis is false": for every fixed ε>0, 3-SAT on n variables with m clauses can be decided in time Oε(2εn(n+m)O(1)) and polynomial space. We separate the general counting procedure from the construction that supplies its input. The procedure deforms the clause inputs so that, at designated points, the count factors into local sums, from which Hermite interpolation recovers the original count; the construction builds such deformations from coordinate swaps in a tensor basis, leveraging a parity interpolation in the spirit of Alman and Williams.
A mix of human-written and AI-generated textHuman understanding: some parts3-SATExponential Time HypothesisHermite interpolationpolynomial interpolationsparsification
This is an exposition of the paper "The Exponential Time Hypothesis Is False" by OpenAI [Oct. 26, 2026], produced through discussion with an LLM. Among other things, it tries to highlight the approximating polynomial for parity, and writes the matrix version of this polynomial using (a light amount of) quantum language.
Primarily AI-generated textHuman understanding: no partsSAT
We refute the Exponential Time Hypothesis (ETH) by presenting a deterministic algorithm for 3-SAT on n variables that runs in 2o(n) time. Our algorithm in fact solves the harder problem #3-SAT, providing a count of the number of satisfying assignments.
The result was discovered by an internal research Claude model and has been formalized in Lean 4.
Primarily AI-generated textHuman understanding: some parts
The rank of the tensor of 3×3 matrix multiplication over the field with two elements is at most 23 by Laderman's algorithm, and Rudich and Rousseau recently proved that it is at least 22. We prove that it equals 23. Hence Laderman's algorithm uses the fewest multiplications among all bilinear algorithms over F2 and among all bilinear algorithms with integer coefficients. The proof uses the substitution method in the form developed by D'Ambrosio, Wang and Yang et al., which bounds the number of first factors of a decomposition that lie in a given subspace of the space of first factors. We sharpen these bounds for 111 of Wang's 496 classes of subspaces, constrain the ranks of the first factors through a 27×27 flattening of the tensor, and list, up to symmetry, all sets of 22 first factors that satisfy these constraints. An exact completion search shows that none of them is the set of first factors of a decomposition. The computation emits certificates, which are checked in the Lean 4 proof assistant. In one formal proof the largest checks are evaluated as compiled code, and in a second one the kernel evaluates every check, so that its final theorem depends only on the three standard axioms of Lean. The Lean proofs build on the formalization of Rudich and Rousseau and import their table of bounds and their reduction for block algorithms.
A mix of human-written and AI-generated textHuman understanding: all parts
We prove that the local-degree potential of a Boolean function of degree at most three is at most 5/4, using the published fact that such a function has at most ten relevant variables. Inserting this cap into Wellens's degree–block-sensitivity recurrence, with the existing exact certificates released by Épi, gives C_44 <= 4.3576549226. The reproduced preceding recurrence gives approximately 4.365467422574458; our exact degree-three cap lowers it by 1/128. Two separately written exact-arithmetic programs check the finite certificates, recurrence, infinite tail and finite cases of the added lemma. The universal argument is written in the paper; the published degree-three classification is cited, not re-enumerated. This preprint is not peer reviewed and not verified in a proof assistant; no optimality is claimed.
Circuit-width restrictions explain several polynomial cases of automatic test pattern generation. We give a different explanation for an arbitrary-size extension of the c432 priority controller, including a subfamily with linear treewidth and net cut-width in its native layout. For a specified first-stage bridge fault, we characterize exactly the reachable qualifier sets and construct a primary input realizing each one. On drive-one inputs where the first selector flag changes, the healthy set is the target singleton; the faulty sets are precisely the target-containing sets with one request bus and all nonempty sets with at least two buses. Drive zero is undetectable. This image reduces detection to comparing decoder values on sets. For supplied guarded decoders, built from zero, positive channel leaves, disjunction and conjunction of one computed child with negative channel literals, supporting paths and dual-Horn reasoning find a detecting set in O((n+q)G) time for n channels, q outputs and counted decoder size G, or O(G) for formula forests. Unsatisfiable instances of the complete guarded native CNF encoding have resolution refutations with O(N³) inferences, where N is the encoding size. Detection is P-complete, while minimum-set optimization and counting detecting sets are NP-hard and #P-complete, respectively. A specified final-qualifier stuck-at fault makes detection NP-complete on shared guarded decoders. The exact first-stage bridge-image statements are formalized in Lean and registered as PALOMAR-2026-10-19-000010, version 1.
A mix of human-written and AI-generated textHuman understanding: all partsBoolean satisfiabilityautomatic test pattern generationfault detectionpriority controllersproof complexity
We prove NP-completeness of deciding whether a finite reversible reaction network contains a productive autocatalytic core when neither a target species nor an allowed-food set is specified. The input is a binary encoding of literal nonnegative integer reactant and product matrices, with a signed real flow on each reaction identity. A nonsingular square-witness characterization gives polynomial certificates. A weighted incidence construction reduces prescribed two-path directed linkage to unrestricted core detection, and an explicit constant-size switch construction reduces SAT to the linkage instances. Actual machine-level NP membership and a total polynomial-time binary transducer complete the classification. The terminal theorem is verified in Lean 4. The result concerns structural possibility in this source model and imposes no elementary reaction arity or conservation constraint.
The computational difficulty of D-stability, raised by Chen, Fan and Yu (1995, doi:10.1016/0167-6911(94)00036-U), is addressed by an explicit integer-matrix reduction from PARTITION. For positive weights of total 2T, the construction produces a matrix of order m + 4 that is D-stable exactly when no subset has weight T. When an equal split exists, some positive diagonal scaling has an eigenvalue with strictly positive real part. A Pell recursion supplies the parameters, with a logarithmic search bound and an explicit bound on every matrix entry. These bounds give polynomial binary output length. Together with the classical NP-completeness of PARTITION, the reduction yields coNP-hardness of D-stability and D-semistability, and NP-hardness of strict D-instability, even for a four-dimensional core with attachments at one coordinate. The hardness is in the weak sense for binary encoding. Running-time analysis and the trivial-instance cases are treated conventionally; registered Lean statements verify the explicit arithmetic encoding, bounds and promise dichotomy.
Primarily AI-generated textHuman understanding: some partsD-stabilityLean formalizationPARTITIONPell equationcoNP-hardnessdiagonal scaling
We give a counterexample to the proposed extension of the effective Hypercube Nullstellensatz from two polynomials to an arbitrary fixed number of polynomials. For every n≥1, we construct three real polynomials in 2n+1 variables, of degrees 2,2,1, respectively. Each is nonzero as a function on the Boolean cube, their product vanishes on the cube, and they have no common Boolean zero. Nevertheless, every polynomial certificate ∑i=13higi=1 on the cube satisfies degh1g1≥n+1, where the bar denotes multilinearization. The construction applies a fresh selector variable to the hard pair of Kothari, Kovacs-Deak, Wang, and Yang. Thus its new ingredient is a short transfer of their existing degree obstruction to the product-zero setting. The full unbounded-degree counterexample has been formalized and checked in Lean 4. HAL deposit: hal-05800244v1.
We construct a family of affine coordinate subspaces of F2N whose union is the entire space, but for which deleting a 1/N fraction from each member removes a fraction larger than N−c from the union, for every fixed c>0 and arbitrarily large N. Each subspace has codimension log2N, and the family has at most 2N2 members. The construction uses all monochromatic coordinate conditions of size k on 2k distinguished coordinates, where N=2k, and deletes their common intersection with the middle Hamming layer. The exact global loss is (k2k)/4k. This disproves the affine-union conjecture of Alekseev and Gaevoy, already for their fixed parameters q=2 and r=1. The all-exponent, arbitrarily-large-dimension counterexample has been formalized and checked in Lean 4. HAL deposit: hal-05800246v1.
Primarily AI-generated textHuman understanding: no partsBoolean cubeLean formalizationaffine subspacescounterexampleunion stability
Minimum Vertex Cover has a classical linear-time ratio of 2, and under the Unique Games Conjecture no polynomial-time algorithm achieves a fixed ratio below 2 unless P=NP. We present version 0.1.4 of \textsc{Salvador}, a linear-time ensemble of seventeen strategies, numbered in the order in which they are computed: twelve base strategies (component amplification before a maximal matching, the maximal matching itself, degree and weight heuristics, reductions to auxiliary problems that are solved exactly, a decomposition into bipartite layers, a weighted subdivision reduction and a bounded-treewidth dynamic program), followed by five improvers (a union pass, local search, reduce-and-search, consensus forcing and a swap-maximize refinement). We prove that every strategy runs in O((n+m)α(n)) time, and that the returned cover has at most 2τ−r vertices, where r is the number of components with an edge, so the ratio is at most 1.999999999 whenever τ≤109r. We prove exactness or a bounded ratio on several classes of graphs, among them every bipartite graph on which the Hopcroft--Karp phases of the layer strategy reach a maximum matching, and we give a per-instance certificate: a cover with at most 2L−∣M∣ vertices, for a lower bound L≤τ and the maximal matching M, is within ratio 3/2 on that instance. In a reproducible suite the returned cover satisfies ∣C∣≤2τ−∣M∣ on all 291 tested graphs with a known optimum and is certified on the six without one, although single strategies violate it; on the 68 DIMACS clique complements it is never worse than Hvala and optimal on 37 instances against 18. Whether ∣C∣≤2τ−∣M∣ holds on every graph is stated as a conjecture: a proof would give a linear-time 3/2-approximation and would refute the Unique Games Conjecture unless P=NP.
Primarily AI-generated textHuman understanding: all partsApproximation AlgorithmBipartite LayersEnsemble HeuristicsLinear TimeMaximal MatchingP versus NPSplit GraphUnique Games ConjectureVertex Cover
We determine the maximum number of relevant variables of a Boolean function of degree at most two on a finite alphabet. For every integer q≥2, this maximum is exactly max{4,q+1}. Here degree means Hamming, or junta, degree: the function is a sum of real-valued functions, each depending on at most two coordinates. We also prove that any such function with more than four relevant variables has a selector coordinate: after that coordinate is fixed, the function depends on at most one other coordinate. The proof combines saturation on a binary four-dimensional restriction with a rigidity argument that applies to every symbol of the original alphabet. Two disjoint interactions force a four-junta; a function with more than four relevant variables has a star of interactions. The exact bound and selector theorem have been formalized in Lean 4, with transitive dependencies using only the standard axioms of Lean and mathlib.
Given an explicitly listed binary pattern of positive length n and a nonnegative integer b in binary, can at most b cyclic rotations of the pattern cover all n positions? We prove that this decision problem is NP-complete. The reduction constructs a pattern in a cyclic group of polynomial order and outputs its entire indicator word. Its principal ingredient is a replicated-marker construction: a cover within the budget must choose one translate in every layer, and each failed difference constraint leaves a block of more holes than the remaining translates can cover. Combining this construction with the known embedding of graph cliques into circulant graphs using distinct three-term sums gives a polynomial-time reduction from 3SAT. The theorem allows every subset, including the empty pattern, and every binary budget. A Lean formalization checks the mathematical reduction, the full-word polynomial-time programs, NP membership, and the unconditional NP-hardness foundation. HAL deposit: hal-05800233v1.
Primarily AI-generated textHuman understanding: no partsLean formalizationNP-completenesscyclic rotationsset cover
Consider the parity decision tree rule that, at every nonconstant restriction, queries a nonzero character maximizing the intersection of the current Fourier support with its translate. We construct an explicit infinite family for which every adaptive policy obeying this rule has polynomial worst-case depth, although an unrestricted parity decision tree has logarithmic depth. For every ℓ≥1, let R=2ℓ. Our function has n=4ℓ−1+R2ℓ+R input bits and exactly k=R6−R5+R nonzero Fourier coefficients. Every history-dependent maximizing policy terminates and computes the function, but has a feasible path of length at least R>k1/6; an explicit unrestricted tree has depth at most 5ℓ≤log2k. The construction places one pointer behind each cell of a finite-field affine partition, with all pointers accessing a shared data table. After any sequence of equal-answer table comparisons, exact signed Fourier coefficients force every maximizing query to compare two remaining table blocks. This invariant accommodates all tie choices and all resulting table partitions. The complete separation, including the specified polynomial-field representation and the existence of every operational policy's finite run, has been checked in Lean. The result concerns this particular support-overlap rule; it is not a lower bound against arbitrary parity decision trees. HAL deposit: hal-05800236v1.
Primarily AI-generated textHuman understanding: no partsFourier analysisLean formalizationadaptive algorithmsparity decision trees