The lower bound for perfect matching

Written by Claude Opus 5.5 (Anthropic), October 2026. Self-checked by the writing AI. Public domain (CC0).

This lesson proves Theorem 4.3 and Corollary 4.4 of PSD factorizations and semidefinite lifts: the shifted matching matrices \(A_n(\rho)\), \(0<\rho<1\), have PSD rank \(2^{\Omega(n)}\), and every semidefinite lift of the perfect matching polytope has size \(2^{\Omega(n)}\) [OpenAI-PSD, Section 6]. The three ingredients are the local averaging theorem of Averaging within a cell, the Fourier smoothing theorem of Fourier smoothing of matrix squares, and the separating functional of An expanding parity system. The vertices of the expanding graph become cells of vertices of \(K_n\), and averaging a row factor within the cells realizes the parity disagreement function exactly.

1. The constants

Use the constants \(d=100\), \(\beta=1/100\) and \(\tau=1/1000\) of An expanding parity system, put \(L=2^{d-1}\), and let \(C_L=2^{L-1}\) be the constant of the splitting lemma. Choose \(\lambda>1\) with \[ \lambda^\tau\ge64L^4 . \tag{1.1} \] Let \(\theta_d(k)\) be as in Theorem 5.1 of Averaging within a cell. Since \(\theta_d(k)\to0\), we can fix an even integer \(k\), satisfying the size condition of that theorem, with \[ L\lambda^2C_L\,\theta_d(k)\le1 . \tag{1.2} \] These constants are absolute: they do not depend on \(n\) or on \(\rho\). They are very large, and the rate \(c=1/(2k)\) obtained below is correspondingly small.

2. Realizing the parity system by odd cuts and matchings

Let \(n\) be even and large, and let \(t\) be the largest even integer with \(kt\le n\), so that \[ kt\le n<k(t+2). \tag{2.1} \] Assume \(t\ge1000\). Let \(H\) be a bipartite \(d\)-regular multigraph on \([t]\) as in Lemma 1.2 of An expanding parity system, with ordered incidences, and with bits \(b_i\in\{0,1\}\) of which exactly one equals one. For \(e=uv\in E(H)\), let \(j_u(e)\) and \(j_v(e)\) be its positions at \(u\) and at \(v\).

Cells and cuts. Choose disjoint subsets \(C_1,\ldots,C_t\) of \([n]\) with \(k\) elements each, the cells. The remaining \(n-kt\) vertices are even in number; pair them by a fixed perfect matching \(M_{\mathrm{rest}}\). In cell \(i\), let \(w_i\in\{k/2,k/2+1\}\) have the parity of \(b_i\), and let \(X_i\) be the set of subsets of \(C_i\) with \(w_i\) elements. For \(a=(a_1,\ldots,a_t)\in\prod_iX_i\) put \[ U(a)=a_1\cup\cdots\cup a_t . \] Since \(|U(a)|=\sum_iw_i\equiv\sum_ib_i=1\pmod2\), the set \(U(a)\) is odd.

Matchings. Identify each cell with \([k]\), and let \(\mathcal M_i\) be the set of local column data of Section 1 of Averaging within a cell for the cell \(C_i\): terminals \(v^i_1,\ldots,v^i_d\in C_i\) and a perfect matching of the other vertices of \(C_i\). For \(m=(m_1,\ldots,m_t)\in\prod_i\mathcal M_i\), let \(M(m)\) consist of

The \(d\) terminals of cell \(i\) correspond to the \(d\) incidences at the vertex \(i\), and every incidence belongs to exactly one edge of \(H\); so every vertex of \(K_n\) lies in exactly one edge of \(M(m)\), and \(M(m)\) is a perfect matching. Parallel edges of \(H\) use different positions, hence different terminals. Different local data may give the same matching; this does no harm.

Restrictions. Let \(Y_i\subseteq\{0,1\}^d\) be the assignments of parity \(b_i\), as in (2.1) of An expanding parity system; it is the set \(Y_{b_i}\) of Averaging within a cell. For \(y=(y_1,\ldots,y_t)\in\prod_iY_i\) and \(m\in\prod_i\mathcal M_i\), let \(\pi^{m_i}_{y_i}\) be the probability measure of that lesson on \(X_i\), and put \(f=f_\varepsilon\) with \(\varepsilon=1-\rho\), as in (2.2) of the parity lesson.

Lemma 2.1 (realization). If every \(a_i\) lies in the support of \(\pi^{m_i}_{y_i}\), then \[ |M(m)\cap\delta(U(a))|-1+\rho=f(y). \]

Proof. An internal pair of \(m_i\) has equal values of \(\mathbf 1_{a_i}\), so its two vertices are both in \(U(a)\) or both outside, and the pair does not cross \(\delta(U(a))\). The vertices outside the cells are not in \(U(a)\), so \(M_{\mathrm{rest}}\) does not cross either. The edge for \(e=uv\) has the endpoint \(v^u_{j_u(e)}\in C_u\), which lies in \(U(a)\) exactly when \(y_{u,j_u(e)}=y_{u,e}=1\), and likewise at \(v\). So it crosses exactly when \(y_{u,e}\ne y_{v,e}\), and \[ \begin{aligned}&|M(m)\cap\delta(U(a))|-1+\rho\\&\quad=\sum_{e=uv}\mathbf 1_{\{y_{u,e}\ne y_{v,e}\}}-(1-\rho)\\&\quad=f(y). \qquad\square\end{aligned} \]

3. Proof of the main theorem

Proof of Theorem 4.3 of PSD factorizations and semidefinite lifts. Fix \(0<\rho<1\), put \(\varepsilon=1-\rho\), and let \(n\) be even and so large that the \(t\) of (2.1) satisfies \(t\ge1000\). Suppose that \(A_n(\rho)\) has a PSD factorization of size at most \(2^t\). We derive a contradiction when \(n\) is large enough in terms of \(\rho\).

A normalized factorization. The entries of \(A_n(\rho)\) are positive and at most \(n/2\le n\). Lemma 2.3 of PSD factorizations and semidefinite lifts gives a factorization of some size \(r\le2^t\) with \[ \operatorname{tr}F_U\le n,\qquad\operatorname{tr}G_M\le r . \] Put \(F(a)=F_{U(a)}\) for \(a\in\prod_iX_i\), and for \(m\in\prod_i\mathcal M_i\) \[ \overline F_m(y)=\sum_a\Bigl(\prod_{i=1}^t\pi^{m_i}_{y_i}(a_i)\Bigr)F(a). \] Each \(a\) with a nonzero coefficient satisfies Lemma 2.1, and the coefficients are probabilities, so \[ \begin{gathered}\operatorname{tr}\bigl(\overline F_m(y)\,G_{M(m)}\bigr)=f(y)\\ \bigl(y\in\textstyle\prod_iY_i\bigr).\end{gathered}\tag{3.1} \]

Fourier smoothing. Identify each \(Y_i\) with \(\mathbb F_2^{d-1}\) through its first \(d-1\) bits; the characters of Fourier smoothing of matrix squares, with \(a=d-1\), are then the characters \(\chi_p\) of the parity lesson. Theorem 5.1 of Averaging within a cell gives the hypotheses (2.1) and (2.2) of Theorem 2.1 of the smoothing lesson with \(\theta=\theta_d(k)\), since \(\mathbb E|B-\mathbb E B|^2\le\mathbb E B^2\); and (1.2) is its condition (2.3). That theorem, with \(B=n\), gives some \(m\) and functions \(H_q\colon\prod_iY_i\to\mathbb R^{R\times r}\), \(q\in\Lambda^t\), with \[ \begin{aligned}&\overline F_m(y)\\&\quad=\sum_qH_q(y)^{\mathsf T}H_q(y),\end{aligned}\tag{3.2} \] \[ \begin{aligned}&\sum_{q,p}\lambda^{\operatorname{dist}(q,p)}\|\widehat H_{q,p}\|_{\mathrm F}^2\\&\quad\le L^t\sqrt r\,n\,2^{t/2}.\end{aligned}\tag{3.3} \] Fix these data and put \(G=G_{M(m)}\). Since \(\operatorname{tr}(H^{\mathsf T}HG)=\operatorname{tr}(G^{1/2}H^{\mathsf T}HG^{1/2})\), (3.1) and (3.2) give \[ f(y)=\sum_q\bigl\|H_q(y)G^{1/2}\bigr\|_{\mathrm F}^2 . \tag{3.4} \]

Truncation. Let \(D=\lfloor\tau t\rfloor\). In each branch keep the frequencies within distance \(D\) of the center: \[ \begin{gathered} K_q(y)=\sum_{p:\,\operatorname{dist}(q,p)\le D}\widehat H_{q,p}\,\chi_p(y),\\ f_*(y)=\sum_q\bigl\|K_q(y)G^{1/2}\bigr\|_{\mathrm F}^2 . \end{gathered} \] The discarded part satisfies, for every \(y\), \[ \begin{aligned}E(y)^2&:=\sum_q\bigl\|(H_q(y)-K_q(y))G^{1/2}\bigr\|_{\mathrm F}^2\\&\le L^t\sum_{q,\ p:\,\operatorname{dist}(q,p)>D}\bigl\|\widehat H_{q,p}G^{1/2}\bigr\|_{\mathrm F}^2\\&\le L^t\,r\,\lambda^{-\tau t}\,L^t\sqrt r\,n\,2^{t/2}\\&\le n\Bigl(\frac{4L^2}{\lambda^\tau}\Bigr)^t\le n\,(4L)^{-2t}.\end{aligned} \] The first inequality is the triangle inequality, \(|\chi_p|=1\), and the Cauchy–Schwarz inequality over the at most \(L^t\) frequencies of each branch. In the second, \(\|\widehat HG^{1/2}\|_{\mathrm F}^2=\operatorname{tr}(\widehat HG\widehat H^{\mathsf T})\), which is at most \(\|G\|_{\mathrm{op}}\|\widehat H\|_{\mathrm F}^2\le r\|\widehat H\|_{\mathrm F}^2\), by Lemma 1.1(3) of PSD factorizations and semidefinite lifts; an integer distance larger than \(D\) is larger than \(\tau t\), so \(1\le\lambda^{\operatorname{dist}(q,p)-\tau t}\); and (3.3) applies. The last line uses \(r\le2^t\), so \(r^{3/2}2^{t/2}\le4^t\), and (1.1).

The uniform error. For fixed \(y\), let \(\mathbf S\) be the stack of the matrices \(H_q(y)G^{1/2}\) and \(\mathbf S_*\) that of the \(K_q(y)G^{1/2}\). Then \(f(y)=\|\mathbf S\|_{\mathrm F}^2\le n\), \(f_*(y)=\|\mathbf S_*\|_{\mathrm F}^2\) and \(\|\mathbf S-\mathbf S_*\|_{\mathrm F}=E(y)\). Since \[ \begin{aligned}&\bigl|\|\mathbf S\|^2-\|\mathbf S_*\|^2\bigr|\\&\quad\le\|\mathbf S-\mathbf S_*\|\,(2\|\mathbf S\|+\|\mathbf S-\mathbf S_*\|),\end{aligned} \] the bound for \(E(y)^2\) gives \[ \begin{gathered}\|f-f_*\|_\infty\\ \le2n(4L)^{-t}+n(4L)^{-2t}.\end{gathered}\tag{3.6} \]

The separating functional. For each \(q\), the coefficients of \(K_qG^{1/2}\) vanish at the frequencies \(p\) with \(\operatorname{dist}(q,p)>D\). By Lemma 1.2 of Fourier smoothing of matrix squares, every entry of \(\chi_qK_qG^{1/2}\) has block degree at most \(D\), and \(\|\chi_qK_qG^{1/2}\|_{\mathrm F}^2=\|K_qG^{1/2}\|_{\mathrm F}^2\). So \(f_*\) is a finite sum of squares of real functions of block degree at most \(D\). Proposition 3.1 of An expanding parity system gives a functional \(\mathcal D\) with \[ \mathcal D(f_*)\ge0,\qquad\mathcal D(f)=-\varepsilon, \] and, by its norm bound and (3.6), \[ \begin{aligned}|\mathcal D(f-f_*)|&\le L^t\|f-f_*\|_\infty\\&\le2n\,4^{-t}+n\,(16L)^{-t}.\end{aligned} \] Hence \(-\varepsilon=\mathcal D(f_*)+\mathcal D(f-f_*)\), and this is at least \(-(2n4^{-t}+n(16L)^{-t})\). By (2.1), \(t>n/k-2\) with \(k\) fixed, so \(2n4^{-t}+n(16L)^{-t}\le3n\,4^{2-n/k}\), which is smaller than \(\varepsilon\) for all large \(n\). This contradiction shows that, for every even \(n\) beyond a threshold \(n_0(\rho)\), there is no factorization of size at most \(2^t\).

Conclusion. For \(n\ge4k\), (2.1) gives \(t\ge n/k-2\ge n/(2k)\). So for every even \(n\ge n_0(\rho)\), enlarged if necessary, \[ \operatorname{rank}_{\mathrm{psd}}A_n(\rho)>2^t\ge2^{n/(2k)}, \] which is Theorem 4.3 with \(c=1/(2k)\). The constant \(c\) does not depend on \(\rho\); only the final comparison with \(\varepsilon=1-\rho\) makes the threshold depend on \(\rho\). \(\square\)

4. Semidefinite lifts

Proof of Corollary 4.4 of PSD factorizations and semidefinite lifts. Since \(A_n(\rho)=A_n(0)+\rho\mathbf 1\), Lemma 2.2(3) there gives \(\operatorname{rank}_{\mathrm{psd}}A_n(\rho)\le\operatorname{rank}_{\mathrm{psd}}A_n(0)+1\). Take \(\rho=\frac12\). For even \(n\ge n_0(\frac12)\), Theorem 4.3 gives \[ \operatorname{rank}_{\mathrm{psd}}A_n(0)\ge2^{cn}-1 , \] and \(T_n(0)\), which contains the rows of \(A_n(0)\), has at least this PSD rank by Lemma 2.2(1). Now let \(P_n\) have a semidefinite lift of size \(r\); for \(n\ge4\) it has at least two points. The affine functions \(\ell_U\), \(U\in\mathcal O_n\), of Section 4 of that lesson are nonnegative on \(P_n\), and \(\ell_U(\mathbf 1_M)=A_n(0)_{U,M}\). Proposition 3.4 there gives \[ 2^{cn}-1\le\operatorname{rank}_{\mathrm{psd}}A_n(0)\le r+1 . \] So \(r\ge2^{cn}-2\). For large \(n\), \(2^{cn}-2\ge2^{cn/2}\) and \(2^{cn}-1\ge2^{cn/2}\), so \(c_0=c/2\) works. \(\square\)

The argument uses no symmetry of the lift: the factors of a small factorization may be arbitrary. Symmetry enters only through the averaging operators, whose analysis in Averaging within a cell uses permutations of the vertices of a cell.

5. Exercises

5.1. Show that every vertex of \(K_n\) lies in exactly one edge of \(M(m)\).

5.2. Show that \(\|\widehat HG^{1/2}\|_{\mathrm F}^2\le\|G\|_{\mathrm{op}}\,\|\widehat H\|_{\mathrm F}^2\) for a real matrix \(\widehat H\) with \(r\) columns and \(G\in\mathbb S^r_+\).

5.3. Prove \[ \begin{aligned}&\bigl|\|\mathbf S\|^2-\|\mathbf S_*\|^2\bigr|\\&\quad\le\|\mathbf S-\mathbf S_*\|\,(2\|\mathbf S\|+\|\mathbf S-\mathbf S_*\|)\end{aligned} \] for vectors in a Euclidean space.

5.4. Show that \(2n4^{-t}+n(16L)^{-t}\le3n\,4^{2-n/k}\) when \(t>n/k-2\).

5.5. Where does the proof use that exactly one bit \(b_i\) equals one, and where would it fail for the endpoint \(\rho=1\)?

6. Solutions

5.1. A vertex outside the cells lies in exactly one edge of \(M_{\mathrm{rest}}\). A non-terminal vertex of a cell lies in exactly one internal pair. The terminal \(v^i_j\) corresponds to the incidence \((i,j)\), which belongs to exactly one edge \(e\) of \(H\), and \(v^i_j\) lies in the edge of \(K_n\) built from \(e\) and in no other.

5.2. \(\|\widehat HG^{1/2}\|_{\mathrm F}^2=\operatorname{tr}(\widehat HG\widehat H^{\mathsf T})=\sum_hhGh^{\mathsf T}\), summed over the rows \(h\) of \(\widehat H\), and \(hGh^{\mathsf T}\le\|G\|_{\mathrm{op}}\|h\|^2\).

5.3. The number \(\bigl|\|\mathbf S\|^2-\|\mathbf S_*\|^2\bigr|\) equals \(\bigl|\|\mathbf S\|-\|\mathbf S_*\|\bigr|\,(\|\mathbf S\|+\|\mathbf S_*\|)\), and \(\bigl|\|\mathbf S\|-\|\mathbf S_*\|\bigr|\le\|\mathbf S-\mathbf S_*\|\) and \(\|\mathbf S_*\|\le\|\mathbf S\|+\|\mathbf S-\mathbf S_*\|\).

5.4. \((16L)^{-t}\le4^{-t}\), so the left side is at most \(3n4^{-t}\), and \(4^{-t}<4^{2-n/k}\).

5.5. Oddness of \(\sum_ib_i\) makes each \(U(a)\) an odd set, so that its row exists in \(A_n(\rho)\), and makes the disagreement count odd (Lemma 2.1 of the parity lesson). At \(\rho=1\) the function \(f=f_0\) is the disagreement count itself, and \(\mathcal D(f)=0\) gives no contradiction; indeed \(\operatorname{rank}_{\mathrm{psd}}A_n(1)\le\binom n2\).

References