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

Setting

We use the notation of [1]; equation and lemma numbers refer to it. Fix $\lambda\ge1$. The crossing is the function $[x = v][y = u]$ of four strings $x,y,u,v \in\{0,1\}^{\lambda}$. A function $F(z,z')$ factors through $c$ bits if $F(z,z') = \sum_{\theta\in\{0,1\}^c} f(z,\theta)f'(z',\theta)$ (Definition 1); as a matrix with rows $z$ and columns $z'$ it then has rank at most $2^c$. Pieces with parameters $(\rho,c)$ (Definition 7) are, for every $\lambda$, integer functions $A_i$ ($i \in I$, $|I| \le(2\lambda)^c$) on four $\lambda$-bit strings with $\sum_i A_i = d[x = v][y = u]$, each factoring through $c_i^{\mathrm{row}}$ bits as a function of $(x,y)$ and $(u,v)$ and through $c_i^{\mathrm{col}}$ bits as a function of $(x,u)$ and $(y,v)$, with $c_i^{\mathrm{row}} + c_i^{\mathrm{col}} \le4\rho\lambda+ c\log(2\lambda)$, all computable fast. Theorem A turns pieces with parameters $(\rho,c)$ into a $2^{O(m/(\log m)^{\alpha'})}$ algorithm for counting satisfying assignments, $\alpha' = \log(1/\rho)$; Theorem B provides pieces with $\rho= 1/\sqrt{2}$, hence the exponent $1/2$ of $\log m$ in the paper’s bound in $m$.

The floor. Appendix H (“What limits the octonions”) gives the lower bound $\rho\ge1/2$: the crossing is a permutation matrix of size $2^{2\lambda}$ in either arrangement of its arguments, so by subadditivity of rank some piece has rank at least $2^{2\lambda}/|I|$ row-wise, that is $c_i^{\mathrm{row}} \ge2\lambda- O(\log\lambda)$, which leaves it at most about $(4\rho- 2)\lambda$ bits column-wise. Definition 7 accordingly restricts $\rho$ to $[1/2,1)$.

The graded pieces. Appendix B works on $V = \mathbb{Q}[t_1,t_2,\ldots]$ graded by weight, $V_E$ the span of the monomials $t^\mu$ with $\mu$ a partition of $E$, so $\dim V_E = p(E)$. For a polynomial $a$ and $r \in\mathbb{Z}$ it defines operators $a[r]: V_E \to V_{E+r}$ (see eq. (47)), and for $b \in V_h$ and $a$ of weight at most $h$ the operators

(see eq. (48)). Lemma 9 states that on $V_E$: (a) $Q_s(a,b)$ is unchanged when the two factors are exchanged in all products at once; (b) $Q_s(a,b)=0$ for $|s|>E+h$; (c) $\sum_{|s|\leq E+h} Q_s(a,b)=(a[-h]b)\cdot\operatorname{Id}$. Lemma 10 gives polynomials $a^\mu,b^\mu$ indexed by the partitions of $h$ with $a^\mu[-h]b^\nu=h![\mu=\nu]$. With $h$ least such that $p(h)\geq2^\lambda$ and $\mu(x)$ the $x$-th partition of $h$, the pieces are

and $\sum_s A_s=h![x=v][y=u]$ by Lemma 9(b),(c) with $E=h$ and Lemma 10 (see eq. (53)). Expanding the intermediate polynomial in monomials gives the two factorizations (see eqs. (54), (55)): the product $a^{\langle i\rangle}[s-h+i]b[h-s-i]$ applied to $t^{\mu(y)}$ passes through $V_{2h-s-i}$, which factors $A_s$ as a function of $(x,u)$ and $(y,v)$ through $R_s^{\mathrm{col}}=\sum_{i=0}^{2h}p(2h-s-i)$ terms; with the factors exchanged (Lemma 9(a)) it passes through $V_{s+i}$, which factors $A_s$ as a function of $(x,y)$ and $(u,v)$ through $R_s^{\mathrm{row}}=\sum_{i=0}^{2h}p(s+i)$ terms. By Hardy–Ramanujan (see eq. (46)), $\lambda\approx c_{\mathrm{HR}}\sqrt{h}$ and

which is eq. (77) and gives $\rho=1/\sqrt{2}$. Appendix H then remarks: if $\log\dim V_E$ grew like $E^\alpha$ with $0<\alpha\leq1$, the same calculation would give $\rho=2^{\alpha-1}$.

That remark is a correct calculation, and it suggests that a graded space with slower growth, $\alpha<1/2$, would improve the exponent. The point of this note is that the floor argument of the same appendix shows no such space can carry the construction.

The rank count

Proof. Insert a basis of $V_{2h-s-i}$ between the two factors:

$\sigma$ running over a basis of $V_{2h-s-i}$ (an empty sum when $2h-s-i<0$). This writes $A_s$ as a sum of $R_s^{\mathrm{col}}=\sum_i\dim V_{2h-s-i}$ products of a function of $(x,u)$ and a function of $(y,v)$, so as a matrix with rows $(x,u)$ and columns $(y,v)$ it has rank at most $R_s^{\mathrm{col}}$. By (b) and (c), $\sum_{s=-2h}^{2h}A_s=d\,[x=v][y=u]$, a nonzero multiple of a permutation matrix of size $|\mathcal{X}|\cdot\dim V_h$ in that arrangement, of full rank. Subadditivity of rank gives $|\mathcal{X}|\dim V_h\le\sum_{s=-2h}^{2h}R_s^{\mathrm{col}}$, which is $T_V(h)$ after $s\mapsto-s$. The last inequality of (4) bounds each inner sum by $\dim V_{\le2h+s}\le\dim V_{\le4h}$.

Proof. Monotonicity gives $\dim V_h\ge\dim V_{\le h}/(h+1)$, so (4) implies

that is $2\le4^\alpha+o(1)$, false for large $h$ when $\alpha<1/2$.

For the partition numbers, $p(h)^2\le T(h)$ must hold at every $h$ since the construction exists, and it does: Table 1 gives the slack $\log_2T(h)-2\log_2p(h)$, which grows like $2\log_2h$. Indeed $T(h)\approx\sum_{j\ge1}jp(4h-j)\approx hp(4h)$, and $p(4h)/p(h)^2\approx\sqrt{3}\cdot h$ by Hardy–Ramanujan’s $p(E)\sim e^{\pi\sqrt{2E/3}}/(4E\sqrt{3})$, so $T(h)=\Theta(h^2)p(h)^2$: the pieces of Theorem B have a total rank budget exceeding the rank of the crossing by a factor $O(h^2)=O(\lambda^4)$ only. The construction is rank-tight up to a polynomial factor. For partitions into squares, where $\ln p_{\square}(E)\sim3.31E^{1/3}$ by Wright [4], the slack peaks at 12.04 bits at $h=160$ and the inequality fails for every $h\ge5891$ (exact arithmetic; $\log_2p_{\square}(5891)=67.4$). For cubes it is 5.9 bits at $h=12000$ and falling.

What the count says about $\rho$

Theorem 2.2 is a nonexistence statement and needs no assumption on costs. To speak about $\rho$ we bound costs the way the construction does, by the dimensions of the weight spaces the two orders pass through: $c_s^{\mathrm{row}}=\lceil\log R_s^{\mathrm{row}}\rceil$, $c_s^{\mathrm{col}}=\lceil\log R_s^{\mathrm{col}}\rceil$. Call the resulting $\rho$ the weight count of the family. The weight count is the only cost a proof via this shape provides; a family whose pieces had rank far below these dimensions would owe its gain to something other than the grading, and is not covered by what follows.

Write $f(W)=\log\dim V_{\leq W}$ and suppose $f(W)=(c+o(1))W^\alpha$. At the balanced piece $s=0$ both orders pass through weight $2h$, and by concavity of $W\mapsto W^\alpha$ this is where $f(2h+s)+f(2h-s)$ is largest, as in (3); so the weight count is $\rho=f(2h)/(2\lambda)$ up to lower-order terms.

Proof. (i) At the least such $h$, $\dim V_{h-1}<2^\lambda\leq\dim V_h$ and $f(h-1)/f(h)\to1$, so $\lambda=f(h)(1+o(1))$ and $f(2h)/(2\lambda)\to2^\alpha/2$; nonexistence for $\alpha<1/2$ is Corollary 2.3. (ii) Theorem 2.2 with $|\mathcal{X}|=2^\lambda$ gives $f(4h)\geq2\lambda-O(\log h)$, and $f(2h)=(2^{-\alpha}+o(1))f(4h)$, so $f(2h)/(2\lambda)\geq2^{-\alpha}-o(1)$. (iii) combines the two; $\max(2^{\alpha-1},2^{-\alpha})$ is minimized where the two agree, at $\alpha=1/2$. (iv) Theorem 2.2 with $|\mathcal{X}|=2^\lambda$ gives $f(4h)\geq\lambda+\log\dim V_h-\log(4h+1)\geq\lambda+f(h)-O(\log h)$, and $f(4h)=(4^\alpha+o(1))f(h)$, so $f(h)\geq(1-o(1))\lambda/(4^\alpha-1)$ and $f(2h)/(2\lambda)=(2^\alpha+o(1))f(h)/(2\lambda)\geq2^\alpha/(2(4^\alpha-1))-o(1). The comparison with \$2^{-\alpha}$ is $4^\alpha\leq2(4^\alpha-1)$, i.e. $4^\alpha\geq2$; and $2^\alpha>2(4^\alpha-1)$ exactly when $2^\alpha<(1+\sqrt{17})/4$.

Slower growth makes the pieces too small to add up to the crossing; faster growth makes the balanced piece too expensive. The $\sqrt{E}$ of Hardy–Ramanujan is the optimum of this shape, not an accident that a better graded algebra could improve. At finite $\lambda$ the counts are not yet asymptotic. For squares, the least weight $h$ with $2^{2\lambda}\leq T_{\square}(h)$ gives a weight count of 0.728 at $\lambda=68$, rising to 0.742 at $\lambda=96$ and 0.750 at $\lambda=120$, while Theorem B’s family at the same $\lambda$ gives 0.776, 0.760, 0.752, falling toward 0.707; the limits are $2^{-1/3}=0.794$ against 0.707, and the order reverses between $\lambda=120$ and $\lambda=128$. So the optimality of $\alpha=1/2$ is asymptotic, in the same sense as the paper’s bound. Under the stronger condition $2^\lambda\dim V_h\leq T_{\square}(h)$ of part (iv), the least such $h$ gives 0.732 at $\lambda=68$ and 0.800 at $\lambda=96$, on the way to the limit $2^{1/3}/(2(4^{1/3}-1))=1.07$.

it for Theorem B’s shape. Part (i) uses that the operators act on the weight space whose dimension carries $\lambda$ bits ($E=h$ in Appendix B). Two shapes escape the count. First, operators of weight $h$ smaller than the acting weight $E$, with $\lambda=f(E)>f(h)$: this needs $2^\lambda$ independent operators of weight $h$, hence an algebra much larger than the module it acts on; the count allows a weight count down to $2^{-\alpha}$ there, which is below $1/\sqrt{2}$ for $\alpha>1/2$ (for $\alpha=0.6$ and $h\approx0.6E$, about $0.66$). In a vertex-algebra-type construction the operators are the fields of vectors of the space itself, and the $2^\lambda$ vectors $b_v$ must be linearly independent (the identity (c) is bilinear in $(a_x,b_v)$), so $\dim V_{\le h}\ge2^\lambda$ and part (i) applies; we know no algebra of the other kind. Second, dimension profiles that are not regularly varying: $f(4h)\ge2f(h)$ together with $f(2h)\ll\sqrt{2}f(h)$ is consistent along a sparse sequence of $h$. Characters of rational $C_2$-cofinite vertex operator algebras are modular (Zhu), hence regularly varying, which excludes the natural candidates. The count says nothing about constructions without a weight grading, such as the octonion pieces of the paper’s main text, and nothing about the floor $1/2$.

Remark 3.3. With the operators of weight $h$ acting on $V_E$, $E\ne h$, the same proof gives $2^{2\lambda}\le\sum_{|s|\le E+h}\sum_{i=0}^{2h}\dim V_{E+h-s-i}\le(2E+2h+1)(2h+1)\dim V_{\le2E+2h}$, from which (ii) follows in the same way.

The sparse Heisenberg algebras

The candidate family for slower growth is the Fock space $V_S=\mathbb{Q}[t_s:s\in S]$ of the Heisenberg algebra on a sparse set of modes $S\subset\mathbb{Z}_{>0}$, graded by weight, with $\dim(V_S)_E=p_S(E)$ the number of partitions of $E$ into parts from $S$; for $S$ the $k$-th powers, $\log p_S(E)\sim c_kE^{1/(k+1)}$ [4]. Theorem 2.2 already excludes it for the squares at the weights Theorem B’s recipe uses, the least $h$ with $p_{\square}(h)\ge2^\lambda$, from $\lambda=68$ on ($h=6023$; at $\lambda=67$, $h=5804$, the count still holds), and Section 3 shows what larger weights would cost. It fails for a second, independent reason at the smallest weights: the operators of Appendix B do not satisfy Lemma 9 once modes are missing, and no change of coefficients helps.

For $n\in S$ the operator of eq. (47) is $t_n[r]=\binom{r-1}{n-1}\nabla_{-r}$ ($\nabla_{-r}$ is multiplication by $t_r$ for $r>0$ and $|r|\partial/\partial t_{|r|}$ for $r<0$; generalized binomial coefficients as in the paper), restricted on $V_S$ to $|r|\in S$. Allow arbitrary coefficients: $t_n[r]=c_n(r)\nabla_{-r}$ for $|r|\in S$, and $0$ otherwise, which is the only form eq. (47) admits for a one-part monomial.

Proof. With $H=n+m$ (so $t_n^{\langle i\rangle}=\binom{H}{i}t_n$), the difference between the two orders of $Q_s(t_n,t_m)$ is

where

is a scalar. The condition for all $s$ says that the $H$-th finite difference of the sequence $g$ vanishes on $\mathbb{Z}$, so $g$ is a polynomial of degree $<H$; it vanishes on the complement of $\pm S$, an infinite set, so $g\equiv0$. Then every product $t_n[r]t_m[-r]$ is zero, $\sum_s Q_s(t_n,t_m)=0$, and (c) forces $t_n[-m]t_m=0$. For the paper’s coefficients $c_n(r)c_m(-r)=\binom{r-1}{n-1}\binom{-r-1}{m-1}\ne0$ for $r\ge n$, so $g\ne0$ at every $r\in S$, $r\ge n$. (For $S=\mathbb{Z}_{>0}$, $g(r)=-r\binom{r-1}{n-1}\binom{-r-1}{m-1}$ is a polynomial of degree $H-1$, which is why the binomial coefficients work.) $\square$

A machine check agrees. We implemented $V_S$, $\nabla_{\pm k}$ for $k\in S$, $a[r]$ through the recursion (O2) of the paper with modes restricted to $S$ (for $S=\mathbb{Z}_{>0}$ this is eq. (47)), and $Q_s$ by (1), and tested Lemma 9(a),(b),(c) on $V_E$ for all monomial pairs $a=t^\mu$ ($|\mu|\le h$), $b=t^\nu$ ($|\nu|=h$) with $E,h\le6$, and Lemma 10 as stated. For $S=\mathbb{Z}_{>0}$ every test passes (3878 triples $(a,b,E)$; Lemma 10 through $h=6$ with the pairing of full rank $p(h)$), which validates the implementation against the paper. For squares, cubes and odd numbers all three parts fail already at $a=b=t_1$ on $V_0$: for squares, $Q_{-3}(t_1,t_1)1=\nabla_4t_4=4$ in one order and 0 in the other (in the full algebra the modes 3 and 2 contribute $-6+2$ and the sum cancels), and $\sum_{|s|\le1}Q_s(t_1,t_1)1=-1$ against the pairing $t_1[-1]t_1=1$. Proposition 4.1 concerns one-part monomials; multi-part operators have more freedom, and for them the exclusion is Theorem 2.2.

What remains

The floor $\rho\ge1/2$ and the value $1/\sqrt{2}$ stand where the paper left them. The note closes the route between them that Appendix H’s last paragraph appears to open: within graded pieces, the exponent $1/2$ cannot be moved by changing the growth of the graded space. What is not excluded is listed in Remark 3.2: an algebra much larger than the module it acts on, a dimension profile that is not regularly varying, or pieces that are not graded at all.

Provenance. This note comes from a project that studies the two October 2026 refutations of the Exponential Time Hypothesis [1, 2] as instances of proof search. The observation, the computations and the text were produced by Claude (Anthropic) in a session directed by the author on 2026-10-29; 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. Three scripts in the ancillary files reproduce every number in the note: anc/rank_count.py (Table 1 and the values of Sections 3 and 4), anc/lemma9_check.py (the Lemma 9 and Lemma 10 checks of Section 4) and anc/kernel_check.py (the kernels behind Proposition 4.1); they need Python 3 only.

all parts ($\alpha= 1/2$)				squares ($\alpha= 1/3$)				cubes ($\alpha= 1/4$)
$h$	$\log_2 p(h)$	ratio	slack	$h$	$\log_2 p_{\square}(h)$	ratio	slack	$h$	$\log_2 p_3(h)$	ratio	slack
2	1.00	4.46	5.43	17	3.17	2.55	9.72	33	2.58	2.38	11.44
9	4.91	2.88	9.16	94	9.78	2.07	11.89	375	10.47	1.82	13.89
38	14.67	2.42	12.92	133	11.87	2.01	12.02	1500	19.10	1.69	12.82
106	28.52	2.27	15.74	265	17.03	1.92	11.86	3000	25.03	1.65	11.35
300	53.04	2.17	18.66	1061	32.75	1.80	9.35	6000	32.30	1.61	9.08
600	78.60	2.13	20.62	4243	59.02	1.73	2.51	12000	41.19	1.58	5.88
				5891	67.40	1.72	−0.00