HEXAGONbeta

The partition exponent in the graded pieces of the Claude 3-SAT algorithm is optimal for pieces of that shape

Primarily AI-generated textHuman understanding: some partscs.CC — Computational Complexitymath.CO — Combinatorics

Contributed by Carlos Stein Naves de Brito ↗

Version 1 / Oct 31, 2026 / CC BY 4.0

Abstract

In Appendix B of "A 2o(n)2^{o(n)} time algorithm for 3-SAT" (Claude, Anthropic, hexagon:2610.00577) the gain parameter ρ=1/2\rho = 1/\sqrt{2} comes from the Hardy--Ramanujan growth log⁡p(E)∼cE\log p(E) \sim c\sqrt{E} of the partition numbers, and Appendix H observes that growth of order EαE^\alpha would give ρ=2α−1\rho = 2^{\alpha-1} by the same calculation. We point out that the rank floor stated in the same Appendix H already excludes α<1/2\alpha < 1/2 for every graded family of the same shape: the pieces at weight hh have total rank at most (4h+1)dim⁡V≤4h(4h+1)\dim V_{\le 4h} in one of the two directions, and the crossing they must add up to has rank (dim⁡Vh)2(\dim V_h)^2, so the construction needs log⁡dim⁡V≤4h≥2log⁡dim⁡Vh−O(log⁡h)\log \dim V_{\le 4h} \ge 2\log\dim V_h - O(\log h), that is α≥1/2\alpha \ge 1/2. Restoring the rank with a larger weight costs ρ≥2−α\rho \ge 2^{-\alpha} in the weight count, so the count never goes below max⁡(2α−1,2−α)≥1/2\max(2^{\alpha-1}, 2^{-\alpha}) \ge 1/\sqrt{2}, with equality only at α=1/2\alpha = 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))2^\alpha/(2(4^\alpha-1)), which exceeds 1 for α<0.357\alpha < 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 hh, for partitions into squares (α=1/3\alpha = 1/3) it fails for all h≥5891h \ge 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\rho \ge 1/2 remains open.

Provenance statement

Found and written by Claude (Anthropic) in a session directed by the author; the proofs and all numbers were independently rechecked by multiple agents with varied instructions. The author has checked the main argument and takes responsibility for the content.

Tools used

Anthropic
Claude FableVersion 5.1
SymPy
SymPyVersion 1.14.0

References

  1. Claude (Anthropic). A 2o(n)2^{o(n)} time algorithm for 3-SAT. hexagon:2610.00577v1, 26 October 2026.hexagon
  2. OpenAI. The Exponential Time Hypothesis is False. 17 October 2026, revised 25 October 2026.
  3. G. H. Hardy, S. Ramanujan. Asymptotic formulae in combinatory analysis. Proc. London Math. Soc. (2) 17 (1918), 75--115.
  4. E. M. Wright. Asymptotic partition formulae. III. Partitions into kk-th powers. Acta Math. 63 (1934), 143--191.

Version history

  1. v1Submitted by Carlos Stein Naves de BritoInitial depositCurrentOct 30, 2026