OctoInformBeta

OpenAI preprint, October 2026 · §6. From matching factors to low-degree squares

§6 (proof architecture): the selected superpolynomial conclusion: Matching cut factorizations and nearly perfect bit tests under quantitative hypotheses

Conditional approximation forces large positive semidefinite factors.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

A real positive semidefinite (PSD) trace factorization of matching cut data assigns PSD matrices to cuts and perfect matchings, with each entry equal to the trace of the corresponding matrix product. Here the cuts are indexed by Boolean strings, and the matching vertices consist of two fixed parts and a family of blocks indexed by the bit positions.

Write [k]={0,…,k−1}[k]=\{0,\ldots,k-1\}. For nonnegative integers s,qs,q, let AsA_s and BsB_s be disjoint copies of [2s+1][2s+1]. The global vertex set is Vs,q=(As⊔Bs)⊔([q]×([s]×{0,1})).V_{s,q}=(A_s\sqcup B_s)\sqcup \bigl([q]\times([s]\times\{0,1\})\bigr).(1)✦

A perfect matching MM on a set VV is a permutation of VV satisfying M2=idM^2=\mathrm{id} and M(v)≠vM(v)\ne v for every v∈Vv\in V; denote the set of these matchings by ℳ(V)\mathcal M(V).✦

For a set VV, a perfect matching MM on VV, and a permutation aa of VV, the relabelling a⋅Ma\cdot M of MM by aa is the perfect matching given by a⋅M=aMa−1.a\cdot M=aMa^{-1}.(2)✦

For sets A,B,C,IA,B,C,I and a Boolean string y∈{0,1}Iy\in\{0,1\}^{I}, the global cut coloring zy:(A⊔B)⊔(I×C)→{0,1}z_y:(A\sqcup B)\sqcup(I\times C)\to\{0,1\} is one on AA, zero on BB, and equal to yiy_i on each vertex (i,u)(i,u) of I×CI\times C.✦ On Vs,qV_{s,q} this is the map given by zy(v)={1,v∈As,0,v∈Bs,yi,v=(i,u)∈[q]×([s]×{0,1}).z_y(v)= \begin{cases} 1,&v\in A_s,\\ 0,&v\in B_s,\\ y_i,&v=(i,u)\in[q]\times([s]\times\{0,1\}). \end{cases}(3)✦

For a perfect matching MM on a finite set VV, a color set CC, a coloring z:V→Cz:V\to C, and a color pair c=(c1,c2)∈C2c=(c_1,c_2)\in C^2, the table coordinate τc(z,M)\tau_c(z,M) is the number of matching endpoints with the specified ordered colors: τc(z,M)=∑v∈V𝟏{z(v)=c1,z(M(v))=c2}.\tau_c(z,M)=\sum_{v\in V} \mathbf 1_{\{z(v)=c_1,\ z(M(v))=c_2\}}.(4)✦ Thus the factorization entries considered here are cut values τ(1,0)(zy,M)−1\tau_{(1,0)}(z_y,M)-1 from (4), with the cuts of (3) and matchings on (1).

The interpolation grid GdG_d for a nonnegative integer dd is the set of triples of integers with coordinates between 00 and dd.✦ For a nonnegative integer dd, the sample index set SdS_d is the disjoint union of the five-element set [5][5] and the interpolation grid GdG_d: Gd={0,…,d}3,Sd=[5]⊔Gd.G_d=\{0,\ldots,d\}^{3},\qquad S_d=[5]\sqcup G_d.(5)✦

The Claim

Definition 1. For nonnegative integers d,td,t, the block size b(d,t)b(d,t) is the nonnegative integer given by b(d,t)=4(d+1)t4.b(d,t)=4(d+1)t^4.(6)✦ The vertex size n(d,t)n(d,t) associated with the block size b(d,t)b(d,t) in (6) is the positive integer given by n(d,t)=2b(d,t)(t+2)+2.n(d,t)=2b(d,t)(t+2)+2.(7)✦

Theorem 1. Let RR be a finite set and qq a nonnegative integer. For each Boolean string y∈{0,1}[q]y\in\{0,1\}^{[q]}, let ρy\rho_y be a real PSD matrix indexed by RR with trace one. Let Fi,bF_{i,b} be real matrices indexed by RR such that 0≤Fi,b0\le F_{i,b} and Fi,0+Fi,1≤IF_{i,0}+F_{i,1}\le I for every i∈[q]i\in[q] and b∈{0,1}b\in\{0,1\}, where II is the identity matrix indexed by RR. Suppose ε≥0\varepsilon\ge0, qε≤1/4q\sqrt{\varepsilon}\le1/4, and tr⁡(ρyFi,yi)≥1−ε\operatorname{tr}(\rho_y F_{i,y_i})\ge1-\varepsilon for every y,iy,i. Then the nearly perfect bit tests satisfy 2q2≤|R|.\frac{2^q}{2}\le |R|.(8)✦

Theorem 2. For every nonnegative integer KK, there exist nonnegative integers d,Hd,H with d>0d>0 and a real number D>0D>0 with the following property. Take positive integers s,q,ℓ,rs,q,\ell,r satisfying H≤3s+1H\le3s+1 and 2ℓd≤s2\ell d\le s, and a real number m>0m>0. Let Qa,yQ_{a,y}, indexed by permutations aa of Vs,qV_{s,q} and strings y∈{0,1}[q]y\in\{0,1\}^{[q]}, and BMB_M, indexed by M∈ℳ(Vs,q)M\in\mathcal M(V_{s,q}), be real PSD matrices of order rr. Suppose their trace bounds and factorization identities are tr⁡(Qa,y)≤m,tr⁡(BM)≤r,tr⁡(Qa,yBa⋅M)=τ(1,0)(zy,M)−1for every a,y,M,\begin{aligned} \operatorname{tr}(Q_{a,y})&\le m,& \operatorname{tr}(B_M)&\le r,\\ \operatorname{tr}(Q_{a,y}B_{a\cdot M}) &=\tau_{(1,0)}(z_y,M)-1 &&\text{for every }a,y,M, \end{aligned}(9) where relabelling is as in (2). Suppose also that the sample set in (5) satisfies the numerical conditions qr4|Sd|(2(3s+1))2K≤(1rm(2ℓ))2,16q2(qD+1)≤2ℓ.\frac{q r^4 |S_d|}{\bigl(2(3s+1)\bigr)^{2K}} \le \left(\frac{1}{rm(2\ell)}\right)^2, \qquad 16q^2(qD+1)\le2\ell.(10) Under (9) and (10), the conditional cell lower bound is 2q2≤r.\frac{2^q}{2}\le r.(11)✦

In the paper, the result reads: local restriction channels, Fourier smoothing, and an expanding parity system exclude factorization size at most 2t2^t with tt proportional to the number nn of vertices.

What Is Checked

The conditional bound (11) is stated over real PSD matrix families on the matchings and relabelled Boolean cuts of Vs,qV_{s,q}; the bit test bound (8) is stated over density matrices and paired effects on an arbitrary finite index set RR.