OctoInformBeta

OpenAI preprint, October 2026 · §1. Introduction

Corollary 1.2 [Unshifted rank and exact lifts]: For every fixed C>0C>0, real positive semidefinite rank and exact affine lift size exceed nCn^C for sufficiently large even nn

Superpolynomial bounds for unshifted matching rank and lifts.

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

The representation sizes for the perfect matching polytope considered here are the real positive semidefinite (PSD) rank of its unshifted slack matrix and the order of an exact affine PSD lift.

Let Vn={1,…,n}V_n=\{1,\ldots,n\}, let KnK_n be the complete graph on VnV_n, and let EnE_n be its edge set, the set of unordered pairs of distinct vertices in VnV_n.✦ A perfect matching MM on VnV_n is a subset of EnE_n in which every vertex belongs to exactly one edge. Write ℳn\mathcal{M}_n for the set of perfect matchings on VnV_n.

An odd cut UU is a subset of VnV_n of odd cardinality; let 𝒪n\mathcal{O}_n be the set of these subsets.✦ An edge crosses UU when exactly one of its endpoints belongs to UU.✦ The cut δ(U)\delta(U) and the crossing count cU(M)c_U(M) are given by (1). δ(U)={e∈En:|e∩U|=1},cU(M)=|M∩δ(U)|.\delta(U)=\{e\in E_n:|e\cap U|=1\}, \qquad c_U(M)=|M\cap\delta(U)|.(1)

The incidence vector χM∈ℝEn\chi^M\in\mathbb{R}^{E_n} of a perfect matching MM records edge membership.✦ The perfect matching polytope Pn⊆ℝEnP_n\subseteq\mathbb{R}^{E_n} is the convex hull of the incidence vectors of the perfect matchings on VnV_n, as in (2).✦ χeM={1,e∈M,0,e∉M,Pn=conv⁡{χM:M∈ℳn}.\chi^M_e= \begin{cases} 1,&e\in M,\\ 0,&e\notin M, \end{cases} \qquad P_n=\operatorname{conv}\{\chi^M:M\in\mathcal{M}_n\}.(2)

The row set Rn=En⊔𝒪nR_n=E_n\sqcup\mathcal{O}_n distinguishes edge rows from odd-cut rows.✦ The unshifted slack matrix Tn(0)T_n(0) has columns indexed by ℳn\mathcal{M}_n and entries (3). Write An(0)A_n(0) for the submatrix of Tn(0)T_n(0) consisting of the odd-cut rows. (Tn(0))e,M=χeM,(Tn(0))U,M=cU(M)−1.\bigl(T_n(0)\bigr)_{e,M}=\chi^M_e, \qquad \bigl(T_n(0)\bigr)_{U,M}=c_U(M)-1.(3)✦

For a nonnegative integer rr, let 𝕊+r\mathbb{S}_+^r denote the cone of real symmetric PSD matrices of order rr. A real PSD trace factorization of Tn(0)T_n(0) of order rr is a pair of families Ai,BM∈𝕊+rA_i,B_M\in\mathbb{S}_+^r, indexed by i∈Rni\in R_n and M∈ℳnM\in\mathcal{M}_n, satisfying (4). (Tn(0))i,M=tr⁡(AiBM)(i∈Rn,M∈ℳn).\bigl(T_n(0)\bigr)_{i,M}=\operatorname{tr}(A_iB_M) \qquad(i\in R_n,\ M\in\mathcal{M}_n).(4)✦ The real PSD rank of Tn(0)T_n(0) is the least positive factor order in (5). rank⁡psdTn(0)=min⁡{r∈ℕ:r>0 and Tn(0) has a real PSD trace factorization of order r}.\operatorname{rank}_{\mathrm{psd}}T_n(0) =\min\{r\in\mathbb{N}:r>0\text{ and }T_n(0) \text{ has a real PSD trace factorization of order }r\}.(5)✦

An exact affine PSD lift of PnP_n of order rr consists of an affine subspace L⊆ℝr×rL\subseteq\mathbb{R}^{r\times r} and an affine map π:ℝr×r→ℝEn\pi:\mathbb{R}^{r\times r}\to\mathbb{R}^{E_n} satisfying (6).✦ The size of an exact affine PSD lift of PnP_n of order rr is rr. π(L∩𝕊+r)=Pn.\pi(L\cap\mathbb{S}_+^r)=P_n.(6)

The Claim

Theorem 1. Fix a real C>0C>0. With an integer threshold n0≥4n_0\ge4 chosen sufficiently large, every even n≥n0n\ge n_0 satisfies (7). nC<rank⁡psdTn(0).n^C<\operatorname{rank}_{\mathrm{psd}}T_n(0).(7)✦ Fix a nonnegative integer pp. With an integer threshold np≥4n_p\ge4 chosen sufficiently large, every even n≥npn\ge n_p satisfies (8). np<rank⁡psdTn(0).n^p<\operatorname{rank}_{\mathrm{psd}}T_n(0).(8)✦ Fix a real C>0C>0. With an integer threshold n1≥4n_1\ge4 chosen sufficiently large and even n≥n1n\ge n_1, every exact affine PSD lift of PnP_n of order rr satisfies (9). nC<r.n^C<r.(9)✦

In the paper, the result reads: there are c0>0c_0>0 and an integer n1n_1 such that, for every even n≥n1n\ge n_1, both An(0)A_n(0) and Tn(0)T_n(0) have real PSD rank at least 2c0n2^{c_0n}, and every exact semidefinite lift of PnP_n has size at least 2c0n2^{c_0n}.

What Is Checked

The rank bounds (7) and (8) are stated over the full edge and odd-cut slack matrix with real PSD factors. The lift bound (9) concerns exact affine images of slices of real PSD cones, with exactness given by (6).

Theorem 2. Let n≥4n\ge4 be even, and suppose that PnP_n has an exact affine PSD lift of order rr. There are families Ai,BM∈𝕊+rA_i,B_M\in\mathbb{S}_+^r, indexed by i∈Rni\in R_n and M∈ℳnM\in\mathcal{M}_n, with the matrix identity (10). Tn(0)=(tr⁡(AiBM))i∈Rn,M∈ℳn.T_n(0)=\bigl(\operatorname{tr}(A_iB_M)\bigr)_{i\in R_n,\,M\in\mathcal{M}_n}.(10)✦