An expanding parity system

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

Put a bit on each end of each edge of a graph, and prescribe at each vertex the parity of its bits. If the prescribed parities have an odd sum, some edge must carry different bits at its two ends: the number of such edges is odd. This lesson constructs, on an expanding graph, a linear functional that assigns the value zero to the number of disagreeing edges, and is nevertheless nonnegative on all squares of functions of low degree [OpenAI-PSD, Section 5]. So the positive function "number of disagreements minus \(\varepsilon\)" is far from every sum of such squares. The construction is a block version of Grigoriev's low-degree functionals for parity and Tseitin contradictions [Grigoriev 2001].

All logarithms are natural. Fix the constants \[ \begin{gathered}d=100,\qquad\beta=\frac1{100},\\ \tau=\frac\beta{10}=\frac1{1000}.\end{gathered}\tag{0.1} \]

1. Expanding multigraphs

The edges of a multigraph are distinguished, even when they have the same endpoints; cuts and degrees count edges with multiplicity. For a multigraph \(H\) and a set \(W\) of its vertices, \(\delta_H(W)\) is the set of edges with exactly one endpoint in \(W\). For \(0<\alpha<1\) let \(\mathrm h(\alpha)=-\alpha\log\alpha-(1-\alpha)\log(1-\alpha)\).

Lemma 1.1. For an integer \(N\ge1\) and \(0<\alpha\le\frac12\), \[ \sum_{0\le j\le\alpha N}\binom Nj\le e^{N\mathrm h(\alpha)} . \] For integers \(1\le w\le n\), \(\binom nw\le(en/w)^w\).

Proof. The terms \(\alpha^j(1-\alpha)^{N-j}=(1-\alpha)^N(\alpha/(1-\alpha))^j\) do not increase in \(j\), so for \(j\le\alpha N\) they are at least \(\alpha^{\alpha N}(1-\alpha)^{(1-\alpha)N}=e^{-N\mathrm h(\alpha)}\). Hence \[ \begin{aligned}1&=\sum_j\binom Nj\alpha^j(1-\alpha)^{N-j}\\&\ge e^{-N\mathrm h(\alpha)}\sum_{j\le\alpha N}\binom Nj .\end{aligned} \] For the second bound, \(\binom nw\le n^w/w!\) and \(w!\ge(w/e)^w\), since \(e^w\ge w^w/w!\). \(\square\)

Lemma 1.2 (expanding multigraphs; [OpenAI-PSD, Lemma 5.1]). For every even \(t\ge2\) there is a bipartite \(d\)-regular multigraph \(H\) on \([t]\) with \[ \begin{gathered}|\delta_H(W)|\\ \ge\beta d\min\{|W|,t-|W|\}\\ (W\subseteq[t]).\end{gathered}\tag{1.1} \] In particular \(H\) is connected.

Proof. Write \(t=2l\), split \([t]\) into two sides of \(l\) vertices, and let \(H\) be the union of \(d\) independent uniform perfect matchings between the sides; equivalently, of \(d\) independent uniform permutations \(\sigma_1,\ldots,\sigma_d\) of \([l]\), the \(c\)-th one joining the \(x\)-th vertex of the first side to the \(\sigma_c(x)\)-th vertex of the second side. Then \(H\) is bipartite and \(d\)-regular. Since \(\delta_H(W)=\delta_H([t]\setminus W)\), it suffices to check (1.1) for the nonempty \(W\) with \(w=|W|\le l\).

Let \(W\) have \(a\) vertices on the first side and \(b\) on the second, \(a+b=w\). The \(da\) edges at the first-side vertices of \(W\) end on the second side, and at most \(db\) of them end in \(W\); so \(|\delta_H(W)|\ge d(a-b)\), and likewise \(\ge d(b-a)\). Thus (1.1) can fail only if \(|a-b|<\beta w\le w/10\), and then \(0.45w\le a,b\le0.55w\).

Suppose that \(|\delta_H(W)|<\beta dw\). Call an image a pair \((x,c)\) with \(x\) a first-side vertex of \(W\) and \(c\le d\), and call it exceptional if \(\sigma_c(x)\) is not a second-side vertex of \(W\). Exceptional images give distinct edges of \(\delta_H(W)\), so there are fewer than \(\beta dw\le(0.01/0.45)\,da<0.05\,da\) of them. By Lemma 1.1 and \(\mathrm h(0.05)<0.2\), there are at most \(e^{0.21da}\) possible sets of exceptional images. For a fixed set, all other images, at least \(0.95da\) of them, must lie among the \(b\) second-side vertices of \(W\). For a single uniform permutation, the probability that \(m\) given points are mapped into a given set of \(b\) points is \(\prod_{i<m}\frac{b-i}{l-i}\le(b/l)^m\); by independence of the permutations, \[ \begin{aligned}&\Pr\bigl[|\delta_H(W)|<\beta dw\bigr]\\&\quad\le e^{0.21da}\Bigl(\frac{0.55w}l\Bigr)^{0.95da}\\&\quad=e^{da\,[0.21+0.95\log(0.55w/l)]} .\end{aligned} \] The bracket is negative, since \(0.21+0.95\log0.55<-0.35\) and \(w\le l\). With \(da\ge45w\) and Lemma 1.1, the probability that some \(W\) with \(|W|=w\) fails is at most \[ \begin{aligned}&\Bigl(\frac{2el}w\Bigr)^we^{45w\,[0.21+0.95\log(0.55w/l)]}\\&\quad=e^{w\,[\log(2e)+45(0.21+0.95\log0.55)]}\\&\qquad\cdot e^{41.75\,w\log(w/l)}\le e^{-8w},\end{aligned} \] because \(\log(w/l)\le0\) and the number \(\log(2e)+45(0.21+0.95\log0.55)\) is less than \(-14\). As \(\sum_{w\ge1}e^{-8w}<1\), some choice of the permutations satisfies (1.1) for all \(W\). A connected component \(W\ne\varnothing,[t]\) would have \(\delta_H(W)=\varnothing\), contradicting (1.1). \(\square\)

2. The parity system

Fix an even \(t\ge2\) and a multigraph \(H\) as in Lemma 1.2, and order the \(d\) incidences at each vertex: each edge \(e=uv\) occupies one position \(j_u(e)\in[d]\) at \(u\) and one position \(j_v(e)\) at \(v\). Choose bits \(b_1,\ldots,b_t\in\{0,1\}\) with odd sum, for instance \(b_1=1\) and \(b_i=0\) for \(i>1\). At vertex \(i\) let \[ \begin{gathered}Y_i=\Bigl\{y_i\in\{0,1\}^d\mid\\ \textstyle\sum_jy_{i,j}\equiv b_i\pmod2\Bigr\},\\ Y=\prod_{i=1}^tY_i .\end{gathered}\tag{2.1} \] The first \(d-1\) bits of \(y_i\) are free and determine the last one, so \(|Y_i|=L=2^{d-1}\); \(Y\) carries the uniform probability measure.

We use the characters of Section 1 of Fourier smoothing of matrix squares in the free coordinates: \(\Lambda=\{0,1\}^{d-1}\) with addition modulo two, and for \(p=(p_1,\ldots,p_t)\in\Lambda^t\) \[ \begin{gathered}\chi_p(y)=(-1)^{\sum_{i=1}^t\sum_{j=1}^{d-1}p_{i,j}y_{i,j}},\\ |p|_{\mathrm{blk}}=|\{i:p_i\ne0\}|.\end{gathered} \] By Lemma 1.1 there, the \(\chi_p\) form an orthonormal basis of the real functions on \(Y\). A function has block degree at most \(D\) if its Fourier coefficients vanish whenever \(|p|_{\mathrm{blk}}>D\).

For an edge \(e=uv\) write \(y_{u,e}=y_{u,j_u(e)}\) and \(y_{v,e}=y_{v,j_v(e)}\) for its two bits. For \(\varepsilon>0\) put, summing over the edges \(e=uv\) of \(H\), \[ \begin{aligned}f_\varepsilon(y)&=\sum_{e=uv}\mathbf 1_{\{y_{u,e}\ne y_{v,e}\}}\\&\quad-\varepsilon .\end{aligned}\tag{2.2} \]

Lemma 2.1. For every \(y\in Y\), the number of edges with \(y_{u,e}\ne y_{v,e}\) is odd. In particular \(f_\varepsilon\ge1-\varepsilon\), which is positive for \(0<\varepsilon<1\).

Proof. Modulo two, \(\mathbf 1_{\{y_{u,e}\ne y_{v,e}\}}\equiv y_{u,e}+y_{v,e}\). Every incidence belongs to exactly one edge, so the sum over the edges is the sum of all bits \(y_{i,j}\), which is \(\sum_ib_i\equiv1\) modulo two. \(\square\)

3. A functional separating low-degree squares

Proposition 3.1 ([OpenAI-PSD, Proposition 5.2]). Let \(t\ge1000\) be even, let \(H\), \(Y\) and \(f_\varepsilon\) be as above, and put \(D=\lfloor\tau t\rfloor\). There is a linear functional \(\mathcal D\) on the real functions on \(Y\) such that \(\mathcal D(1)=1\); \(\mathcal D(g^2)\ge0\) for every \(g\) of block degree at most \(D\); \(\mathcal D(f_\varepsilon)=-\varepsilon\) for every \(\varepsilon>0\); and \(|\mathcal D(h)|\le L^t\|h\|_\infty\) for every real function \(h\) on \(Y\).

The proof occupies the rest of this section.

The incidence map. Send a set of incidences \((i,j)\in[t]\times[d]\) to the set of edges that contain an odd number of them. This map \(\iota\) from subsets of \([t]\times[d]\) to subsets of \(E(H)\) is linear over \(\mathbb F_2\), with symmetric difference as addition. A character index \(p\in\Lambda^t\) selects the incidences \((i,j)\) with \(j<d\) and \(p_{i,j}=1\); let \(E(p)\) be the image of the selected set. Then \[ E(p+p')=E(p)\mathbin\triangle E(p'). \] The cut sets \(\delta_H(S)\), \(S\subseteq[t]\), form a subspace \(\mathcal C\), since \(\delta_H(S)\mathbin\triangle\delta_H(S')=\delta_H(S\mathbin\triangle S')\). Because \(H\) is connected, \(\delta_H(S)=\varnothing\) only for \(S=\varnothing,[t]\), so \(\delta_H(S)=\delta_H(S')\) implies \(S'=S\) or \(S'=[t]\setminus S\).

Lemma 3.2 (small sides). If \(|p|_{\mathrm{blk}}\le2D\) and \(E(p)\in\mathcal C\), there is exactly one \(S(p)\subseteq[t]\) with \(\delta_H(S(p))=E(p)\) and \(|S(p)|\le t/5\).

Proof. Each block selects at most \(d-1\) incidences, so \(|E(p)|\le2Dd\). If \(E(p)=\delta_H(S)\), then (1.1) gives \(\beta d\min\{|S|,t-|S|\}\le2Dd\), so \(\min\{|S|,t-|S|\}\le2D/\beta\), and \(2D/\beta\le2\tau t/\beta=t/5\). Thus \(S\) or its complement has at most \(t/5\) elements. The only other set with the same cut is the complement, and the two cannot both have at most \(t/5<t/2\) elements. \(\square\)

Definition of the functional. Put \[ \mathcal D(\chi_p)=\begin{cases}(-1)^{\sum_{i\in S(p)}b_i}&\text{if }|p|_{\mathrm{blk}}\le2D\\&\text{and }E(p)\in\mathcal C,\\ 0&\text{otherwise},\end{cases} \] and extend \(\mathcal D\) linearly. The trivial character \(\chi_0=1\) has \(E(0)=\varnothing=\delta_H(\varnothing)\) and \(S(0)=\varnothing\), so \(\mathcal D(1)=1\).

Positivity on low-degree squares. Let \(\mathcal I_D=\{p:|p|_{\mathrm{blk}}\le D\}\) and \(M_{p,p'}=\mathcal D(\chi_p\chi_{p'})=\mathcal D(\chi_{p+p'})\) for \(p,p'\in\mathcal I_D\). Call \(p\) and \(p'\) equivalent if \(E(p+p')=E(p)\mathbin\triangle E(p')\in\mathcal C\); the classes are the preimages of the cosets of \(\mathcal C\). Entries between different classes vanish. Within a class, \(|p+p'|_{\mathrm{blk}}\le2D\) and \(E(p+p')\in\mathcal C\), so every entry is a sign, and the diagonal entries equal \(\mathcal D(1)=1\).

Let \(p_1,p_2,p_3\) lie in one class and put \(S_{ab}=S(p_a+p_b)\). By linearity, \[ \begin{aligned}&\delta_H\bigl(S_{12}\mathbin\triangle S_{23}\mathbin\triangle S_{31}\bigr)\\&\quad=E\bigl(2(p_1+p_2+p_3)\bigr)=\varnothing .\end{aligned} \] The set \(S_{12}\mathbin\triangle S_{23}\mathbin\triangle S_{31}\) has at most \(3t/5<t\) elements by Lemma 3.2, so it is empty, and the sum of the \(b_i\) over \(S_{12}\), \(S_{23}\) and \(S_{31}\) is even. Hence \[ M_{p_1,p_2}M_{p_2,p_3}M_{p_3,p_1}=1 . \] Fix \(p_0\) in the class and put \(\sigma_p=M_{p,p_0}\). Taking \((p_1,p_2,p_3)=(p,p',p_0)\) and using that \(M\) is symmetric with entries \(\pm1\) gives \(M_{p,p'}=\sigma_p\sigma_{p'}\). So each block of \(M\) is the positive semidefinite matrix \(\sigma\sigma^{\mathsf T}\). If \(g=\sum_{p\in\mathcal I_D}\widehat g(p)\chi_p\), then \[ \mathcal D(g^2)=\sum_{p,p'\in\mathcal I_D}\widehat g(p)\widehat g(p')M_{p,p'}\ge0 . \]

Values on disagreements. Let \(e=uv\) be an edge, and let \(T\subseteq\{u,v\}\) be the set of its endpoints at which \(e\) occupies the last position \(d\). On \(Y_i\) the parity condition gives \[ (-1)^{y_{i,d}}=(-1)^{b_i}\prod_{j=1}^{d-1}(-1)^{y_{i,j}} . \] Using this at the vertices in \(T\), \[ (-1)^{y_{u,e}+y_{v,e}}=(-1)^{\sum_{i\in T}b_i}\,\chi_p(y) \] for an index \(p\) with \(|p|_{\mathrm{blk}}\le2\). Its selected set arises from the two incidences of \(e\) by replacing each last incidence \((i,d)\), \(i\in T\), with \((i,1),\ldots,(i,d-1)\); that is, by adding the full set of incidences at \(i\), whose image under \(\iota\) is \(\delta_H(\{i\})\). The two incidences of \(e\) have image \(\varnothing\), so \[ E(p)=\mathop{\triangle}_{i\in T}\delta_H(\{i\})=\delta_H(T), \] also when \(u\) and \(v\) are joined by parallel edges. As \(t\ge1000\), we have \(D\ge1\), so \(|p|_{\mathrm{blk}}\le2\le2D\), and \(|T|\le2\le t/5\), so \(T=S(p)\) by Lemma 3.2. The two signs cancel: \[ \begin{aligned}\mathcal D\bigl((-1)^{y_{u,e}+y_{v,e}}\bigr)&=(-1)^{\sum_{i\in T}b_i}\,\mathcal D(\chi_p)\\&=1 .\end{aligned} \] Since \(\mathbf 1_{\{y_{u,e}\ne y_{v,e}\}}=\bigl(1-(-1)^{y_{u,e}+y_{v,e}}\bigr)/2\), every disagreement indicator has value \(0\) under \(\mathcal D\), and \(\mathcal D(f_\varepsilon)=-\varepsilon\,\mathcal D(1)=-\varepsilon\).

The norm bound. All values of \(\mathcal D\) on characters have absolute value at most one, and \(|\widehat h(p)|=|\mathbb E_y\chi_p(y)h(y)|\le\|h\|_\infty\). So \[ |\mathcal D(h)|\le\sum_{p\in\Lambda^t}|\widehat h(p)|\le L^t\|h\|_\infty . \] This proves Proposition 3.1. \(\square\)

By Lemma 2.1 the function \(f_\varepsilon\), for \(0<\varepsilon<1\), is the square of the positive function \(f_\varepsilon^{1/2}\). Proposition 3.1 shows that \(f_\varepsilon\) is nevertheless not a sum of squares of functions of block degree at most \(D\): such a sum would have a nonnegative value under \(\mathcal D\). The proof of the main theorem shows that a small PSD factorization would make \(f_\varepsilon\) uniformly close to such a sum, which the norm bound rules out.

4. Exercises

4.1. Check the numerical facts used in the proof of Lemma 1.2: \(\mathrm h(0.05)<0.2\), \(0.21+0.95\log0.55<-0.35\), and that \(\log(2e)+45(0.21+0.95\log0.55)\) is less than \(-14\).

4.2. Let \(H\) be a connected multigraph. Show that \(\delta_H(S)=\delta_H(S')\) implies \(S'\in\{S,[t]\setminus S\}\).

4.3. Show that \(\iota\) maps the set of all \(d\) incidences at a vertex \(i\) to \(\delta_H(\{i\})\), and the two incidences of an edge to \(\varnothing\).

4.4. Let \(H\) be a single cycle of length four (so \(d=2\)) with \(b=(1,0,0,0)\). Find an assignment \(y\in Y\) with exactly one disagreeing edge.

4.5. Show that \(\mathcal D\) is not nonnegative on all squares, and conclude that \(f_\varepsilon^{1/2}\), for \(0<\varepsilon<1\), has block degree larger than \(D\).

5. Solutions

4.1. \(\mathrm h(0.05)=0.05\log20+0.95\log(20/19)\), with \(\log20<3\) and \(\log(20/19)<1/19\), so \(\mathrm h(0.05)<0.15+0.05=0.2\). Next \(e^{0.597}<1.818<1/0.55\), so \(\log0.55<-0.597\), and \(0.21+0.95\log0.55\) is less than \(0.21-0.567<-0.35\). Finally \(\log(2e)=1+\log2<1.694\) and \(45\cdot(-0.35)=-15.75\), so the last expression is below \(-14\).

4.2. \(\delta_H(S)\mathbin\triangle\delta_H(S')=\delta_H(S\mathbin\triangle S')\) is empty, so no edge leaves \(S\mathbin\triangle S'\); by connectedness this set is \(\varnothing\) or \([t]\).

4.3. Every edge at \(i\) has exactly one incidence at \(i\) (there are no loops), and edges not at \(i\) have none; so the image of all incidences at \(i\) consists of the edges at \(i\), which is \(\delta_H(\{i\})\). An edge contains both of its own incidences, an even number.

4.4. Number the vertices \(1,2,3,4\) around the cycle, with edges \(12,23,34,41\). Put all bits zero except the bit of vertex \(1\) on the edge \(41\). Vertex \(1\) has bit sum \(1=b_1\), the others have sum \(0\), and only the edge \(41\) disagrees.

4.5. For \(0<\varepsilon<1\) the function \(g=f_\varepsilon^{1/2}\) is real and \(g^2=f_\varepsilon\), with \(\mathcal D(g^2)=-\varepsilon<0\). If \(g\) had block degree at most \(D\), Proposition 3.1 would give \(\mathcal D(g^2)\ge0\).

References