Perfect matching and semidefinite formulation size

Source and verification

This article explains family 126 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Matching polytopes and semidefinite lifts

For even $n\ge 4$, a perfect matching of the complete graph $K_n$ pairs every vertex exactly once. Let ${\mathcal{M}}_n$ be the set of these matchings. Its incidence vector $1_M$ has one coordinate for each edge. The perfect-matching polytope is

$$P_n=\mathrm{conv}\{1_M:M\in {\mathcal{M}}_n\}.$$

A real symmetric matrix is positive semidefinite, written $X⪰0$, when $v^{\mathsf{T}}Xv\ge 0$ for every real vector $v$. A semidefinite lift of size $r$ represents $P_n$ as an affine image of an affine slice of the cone of $r\times r$ PSD matrices.

The size here is the matrix dimension $r$, not the number $r(r+1)/2$ of scalar entries. Auxiliary coordinates may make a convex set simpler to describe, so a large list of inequalities in the original coordinates does not by itself prove that every lift is large.

This is a formulation-complexity question. An algorithm can construct or optimize a matching without storing one small semidefinite description of the entire matching polytope.

🏷️ Odd-cut slack matrices

For an odd vertex set $U$, let $\delta (U)$ consist of edges with exactly one endpoint in $U$. Every matching crosses this cut an odd positive number of times: internal matching edges cover an even number of vertices of $U$, leaving an odd number matched outside.

The odd-cut inequality is therefore ${\sum }_{e\in \delta (U)}{x}_e\ge 1$. Its slack at $1_M$ is $|M\cap \delta (U)|-1$. The manuscript studies the shifted matrix

$$\begin{array}{c}\begin{array}{rl}& A_n(\rho {)}_{U,M}\\ & =|M\cap \delta (U)|-1+\rho ,\end{array}\\ 0\le \rho \le 1.\end{array}$$

For example, with $n=6$ and $U=\{1,2,3\}$, a matching can cross the cut once or three times. Its shifted entry is respectively $\rho$ or $2+\rho$. For $\rho >0$, even the formerly zero slack entries are positive.

The real PSD rank of a nonnegative matrix $A$ is the least $r\ge 1$ admitting factors $F_U,G_M⪰0$ with

$$A_{U,M}=\mathrm{tr}(F_U{G}_M).$$

The factor entries may be arbitrary real numbers. There is no symmetry, sparsity, equivariance, or bounded-precision assumption. All matrix entries must be reproduced exactly.

🏷️ The shifted lower bound and its endpoint

Manuscript statement

There is an absolute $c>0$ such that, for every fixed $0<\rho <1$, all sufficiently large even $n$ satisfy

$${\mathrm{rank}}_{\mathrm{psd}}{A}_n(\rho )\ge 2^{cn}.$$

The threshold may depend on $\rho$, but the exponential rate $c$ does not. (OpenAI, 2026)

The fixed-shift quantifier matters. It does not directly give the same bound for a shift tending to one with $n$.

At $\rho =1$, a polynomial-size factorization is explicit. Use diagonal matrices indexed by the edges of $K_n$, with diagonal entries $1_{e\in \delta (U)}$ and $1_{e\in M}$. Their trace product is $|M\cap \delta (U)|$. Thus

$${\mathrm{rank}}_{\mathrm{psd}}{A}_n(1)\le \left(\genfrac{}{}{0ex}{}{n}{2}\right).$$

The endpoint cannot be included. A positive shift below one also should not be called an arbitrary approximate SDP formulation: the theorem concerns exact factorization of this particular shifted matrix.

🏷️ Recovering unshifted slacks and exact lifts

Suppose $A_n(0)$ has PSD factors of size $r$. Adjoin one scalar block to each factor:

$$\begin{array}{c}{\tilde{F}}_U=F_U\oplus [\rho ],\\ {\tilde{G}}_M=G_M\oplus [1].\end{array}$$

Their trace pairing is the old entry plus $\rho$, so

$${\mathrm{rank}}_{\mathrm{psd}}{A}_n(\rho )\le {\mathrm{rank}}_{\mathrm{psd}}{A}_n(0)+1.$$

Fixing $\rho =1/2$ transfers the exponential lower bound to $A_n(0)$. Adjoining rows $1_{e\in M}$ for edge nonnegativity cannot decrease rank. These rows and the odd-cut slacks form a slack matrix for the matching polytope within the affine space of degree equations ${\sum }_{e\ni v}{x}_e=1$.

The cone-factorization correspondence then identifies this PSD rank with minimum exact lift size. To apply it to an arbitrary affine lift, the source restricts to the smallest face of the PSD cone containing its feasible section, obtaining the required relative-interior condition without increasing size. Redundant tight inequalities do not circumvent the bound. This supplies the claimed exponential lower bound for all exact affine semidefinite lifts, not only a selected symmetric construction.

🏷️ A positive function separated from low-degree squares

The proof begins with parity constraints on an expanding auxiliary graph. Give each incidence at a vertex a bit, prescribing an odd total sum of vertex parities. If the two incidence bits on every edge agreed, summing all vertex constraints would count every edge bit twice and give even total parity, a contradiction. At least one edge must disagree.

Let $D(y)$ count disagreeing edges for an allowed incidence assignment $y$, and define

$$f(y)=D(y)-(1-\rho ).$$

Then $f(y)\ge \rho >0$ pointwise. The source constructs a linear functional $\mathcal{L}$ that is nonnegative on squares of functions involving few vertex blocks, but for which $\mathcal{L}(f)=-(1-\rho )<0$.

Such a functional is not expectation under a true probability distribution: a true expectation cannot assign a negative value to a positive function. Its positivity is restricted to a low-degree class. Consequently it rules out representing $f$ by sums of those low-degree squares, even though unrestricted squares can represent any nonnegative function on a finite set.

This finite parity construction is used here as a combinatorial and analytic interface. The exposition does not develop the associated formal-logic or group-theoretic background.

🏷️ Encoding the parity obstruction in matching

Replace each auxiliary vertex by a cell of a sufficiently large fixed number of vertices. Incidences use designated terminals, while remaining vertices are paired internally. Restrict cuts so that each internal pair receives equal cut bits and the terminal bits obey the prescribed incidence constraints.

Only auxiliary-edge disagreements cross these restricted cuts. The matching-matrix entry becomes precisely the positive function $f$. Therefore a small factorization of the full matching matrix would induce a factorization suitable for this obstruction.

The proof then needs to turn arbitrary PSD factors into approximately low-degree squares. Arbitrary factors begin with no polynomial-degree control, so the parity functional alone is not yet a rank lower bound.

🏷️ Averaging squares without squaring averages

Let $\overline{F}(y)$ be an averaged row factor. Taking square roots of the original factors produces matrix-valued functions, but

$$\mathbb{E}[H^{\mathsf{T}}H]\ne (\mathbb{E}H{)}^{\mathsf{T}}(\mathbb{E}H)$$

in general. The scalar example $H=\pm 1$ with equal probabilities gives left side one and right side zero. Replacing the former by the latter would destroy the exact factorization identity.

Instead, the source keeps an exact decomposition

$$\overline{F}(y)=\sum _q{H}_q(y{)}^{\mathsf{T}}{H}_q(y)$$

with rectangular matrix functions and separate branches $q$. Local averaging and an orthogonal splitting inequality concentrate each branch’s Fourier coefficients near a branch-dependent character. Their estimates are independent of the factor dimension.

The controlled quantity is the squared Frobenius norm of a weighted Gram matrix, a fourth-order expression in the Fourier coefficients. This choice survives repeated direct-sum decompositions, even though those decompositions add rows to the rectangular factors. A scalar coefficient estimate that grew with the number of rows would not suffice.

After truncation near the central character ${\chi }_q$, multiply the branch by ${\chi }_q$. Since ${\chi }_q^2=1$, this preserves its square while moving retained frequencies to low block degree. The low-degree functional is nonnegative on the resulting sum of squares. The source’s quantitative tail bound makes the truncation error too small to explain the negative value $-(1-\rho )$, contradicting a factorization of insufficient size. (OpenAI, 2026)

This last argument requires both the norm controlling the tail and the norm of the separating functional; small unweighted Fourier error by itself would not establish the contradiction. The cell-averaging, splitting, and product estimates are the manuscript’s substantive analytic inputs.

🏷️ Scope of the formalization comparison

The repository’s selected comparator statements record superpolynomial lower bounds for the unshifted matching slack matrix and exact affine lifts: every fixed power $n^C$ is eventually exceeded. They do not state the stronger exponential bound for every fixed positive shift below one.

The article therefore distinguishes the manuscript theorem from that documented formalization scope. It does not infer a local verification of either merely from the presence of comparator links.

🏷️ Key steps and proof outlines

Product averaging must retain a sum of matrix squares

The section “Fourier concentration of squares under product averages” starts with a PSD matrix function $F(x)$ satisfying $\mathrm{tr}F(x)\le B$. Write its square root as $H(x)$. To average over one coordinate with probabilities ${\pi }_y(x)$, stack the matrices $\sqrt{{\pi }_y(x)}H(x)$ in separate row blocks. The square of this rectangular stack is exactly

$$\sum _x{\pi }_y(x)H(x{)}^{\mathsf{T}}H(x).$$

Keeping separate blocks is what eliminates unwanted cross terms. Averaging $H$ first and then squaring would introduce cross terms and generally give a different PSD matrix. The source adds an extra block label for $y$ as well, making products between different new-coordinate values vanish in the Fourier overlap calculation. (OpenAI, 2026)

A fourth-order potential is insensitive to new row dimensions

Let ${\hat{H}}_{q,p}$ be the Fourier coefficient at frequency $p$ of a branch centered at $q$. Penalize distance from that center using ${\lambda }^{\mathrm{dist}(p,q)}$, with $\lambda >1$ chosen subject to $L{\lambda }^2{C}_L\theta \le 1$, where $L$ is the local character count, $\theta$ the local averaging variance bound, and $C_L$ the splitting constant. Concatenate the weighted coefficient matrices horizontally into $U_q$, and let $C_q=U_q{U}_q^{\mathsf{T}}$. Then

$$\begin{array}{rl}\mathrm{tr}{C}_q& =\sum _p{\lambda }^{\mathrm{dist}(p,q)}\Vert {\hat{H}}_{q,p}{\Vert }_F^2,\\ \Vert C_q{\Vert }_F^2& =\sum _{p,p^{\prime }}{\lambda }^{\mathrm{dist}(p,q)+\mathrm{dist}(p^{\prime },q)}\Vert {\hat{H}}_{q,p}^{\mathsf{T}}{\hat{H}}_{q,p^{\prime }}{\Vert }_F^2.\end{array}$$

The second expression measures overlaps, rather than just coefficient sizes. A scalar variance inequality for each local average extends entrywise to matrix-valued functions with the same constant. Character orthogonality subtracts the common mean when two new frequencies differ, so cross-frequency overlaps gain that small variance factor. The splitting lemma organizes the new frequencies into separate branches and bounds the potential’s increase by a factor at most two per coordinate.

After $t$ coordinates, the expected total potential is at most $2^t{B}^2$. To recover a trace bound, use $\mathrm{tr}C\le \sqrt{\mathrm{rank}C}\Vert C{\Vert }_F$. The rank is bounded by the number of concatenated columns, even though stacking has greatly enlarged the row count. This is the reason row-dimension growth does not destroy the estimate.

Concentration becomes low degree after a character shift

The weighted Fourier bound implies that coefficients farther than degree cutoff $D$ from their center have total squared mass at most ${\lambda }^{-D}$ times the weighted budget. Truncate those tails. Multiplying the retained branch by its center character ${\chi }_q$ moves every retained frequency within block degree $D$ of zero. Since ${\chi }_q^2=1$, the branch’s square is unchanged.

The parity functional is nonnegative on these low-degree squares, whereas its value on the target positive function is $-(1-\rho )$. To obtain a contradiction one must bound the functional applied to the difference between original and truncated squares. The identity $H^{\mathsf{T}}H-K^{\mathsf{T}}K=(H-K{)}^{\mathsf{T}}H+K^{\mathsf{T}}(H-K)$ shows why tail norms must be paired with norms of the retained and original factors. The source’s quantitative estimates make the resulting error smaller than $1-\rho$ when factor size is too small.

The shift parameter is fixed below one, so this negative margin is positive and fixed. At $\rho =1$ it vanishes, and the explicit diagonal factorization already shows polynomial size. Thus the endpoint exclusion has a visible place in the contradiction, rather than being a technical omission.

See Also

• Constructing maximum matchings concerns algorithmic search; a large exact lift does not preclude a fast combinatorial algorithm.
• Matching counts and entropy studies probability measures on the same vertices of the matching polytope.
• Semidefinite integrality gaps measures the accuracy of a particular relaxation, whereas this article concerns the size of every exact lift.

🏷️ Manuscripts and verification scope

• Exponential PSD rank of positively shifted matching matrices — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The selected formalization statements are superpolynomial lower bounds for the unshifted slack matrix and exact affine lifts. They are weaker than the manuscript’s exponential claim for every fixed positive shift below one. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. Exponential PSD rank of positively shifted matching matrices.