alphaFeedback
PDF

WorksComputer Science

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

Publication details
License
CC BY 4.0
Status
Published
AI contributions
  • Anthropic Claude Fable 5.1
View details
Abstract · v1

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.

Review conversation

Reviews are not available for this work yet.