Proof. The uniform law of \(m\) and the restrictions (2) are equivariant under permutations of the \(k\) vertices. Since the symmetric group is transitive on \(X\), the marginal law of \(a\), obtained by first sampling \(m\) and then \(a\sim\pi_y^m\), is uniform. This proves (5).

Fix \(b\) and \(y\), and write \(T=T_y\). Equip the function spaces on \(X\) and \(\mathcal M\) with the inner products for uniform probability, and put \(K=T^*T\). This is a positive semidefinite self-adjoint operator. The marginal identity gives \(K1=1\). We will show that \(\mathop{\mathrm{tr}}(K^2)=o(k)\), while every nonconstant eigenspace has dimension at least \(k/2\). Together these estimates force the largest eigenvalue on the orthogonal complement of the constants to tend to zero.

The two-sample kernel. Sample \(m\) uniformly, and then sample \(a,a'\) independently from \(\pi_y^m\) conditional on \(m\). Let \(J(a,a')\) be their joint probability, and let \(N=|X|\). The density of this joint law relative to two independent uniform elements of \(X\) is \(D(a,a')=N^2J(a,a')\). Indeed, for scalar functions \(B_1,B_2\), \[\langle B_1,KB_2\rangle =\sum_{a,a'\in X}J(a,a')B_1(a)B_2(a').\] Consequently the ordinary matrix entries of \(K\) are \(D(a,a')/N\), and symmetry gives \[ \mathop{\mathrm{tr}}(K^2)=\frac1{N^2}\sum_{a,a'\in X}D(a,a')^2. \tag{8}\]

The joint law is permutation-invariant, so \(D(a,a')\) depends only on \(|a\cap a'|\). Conditional on \(m\), the two subsets choose independent \(g\)-subsets of the \(h\) internal pairs. If the second choice replaces exactly \(j\) pairs of the first, their intersection has size \(s+2(g-j)=w-2j\). The probability of this event is \[P_j=\frac{\binom gj\binom{h-g}j}{\binom hg}, \qquad 0\le j\le g_*:=\min(g,h-g).\] For two independent uniform elements of \(X\), the probability of the same intersection size is \[Q_j=\frac{\binom w{2j}\binom{k-w}{2j}}{\binom kw}.\] Both laws are uniform within each intersection class. The density there is therefore \(P_j/Q_j\), and it vanishes on the remaining classes. The identities \(w=2g+s\) and \(k-w=2(h-g)+(d-s)\) ensure that every displayed \(Q_j\) is positive. Equation (8) becomes \[ \mathop{\mathrm{tr}}(K^2) =\sum_{j=0}^{g_*}\frac{P_j^2}{Q_j} =\frac{\binom kw}{\binom hg^2} \sum_{j=0}^{g_*} \frac{\binom gj^2\binom{h-g}j^2} {\binom w{2j}\binom{k-w}{2j}}. \tag{9}\]

A trace estimate. Since \(k=2h+d\), \(w=k/2+O(1)\), and \(g=h/2+O_d(1)\), the central binomial estimates give \[ \frac{\binom kw}{\binom hg^2}=O_d(\sqrt h), \tag{10}\] uniformly in \(b\) and \(y\). Moreover, \(\binom w{2j}\ge\binom{2g}{2j}\) and \(\binom{k-w}{2j}\ge\binom{2(h-g)}{2j}\). For integers \(0\le j\le u\), the identity \[\frac{\binom uj^2}{\binom{2u}{2j}} =\frac{\binom{2j}j\binom{2(u-j)}{u-j}}{\binom{2u}u}\] and the bounds \(\binom{2v}v\asymp4^v/\sqrt{v+1}\) imply \[ \frac{\binom uj^2}{\binom{2u}{2j}} \le C\sqrt{\frac{u+1}{(j+1)(u-j+1)}} \tag{11}\] with an absolute constant \(C\), including at the endpoints \(j=0,u\). Applying this bound with \(u=g\) and \(u=h-g\) shows that the sum in (9) is at most \[C^2\sum_{j=0}^{g_*} \frac{h+1}{(j+1)(g_*-j+1)} =\frac{2C^2(h+1)}{g_*+2}\sum_{j=1}^{g_*+1}\frac1j.\] By (4), \(g_*=h/2+O_d(1)\), so this is \(O_d(\log(h+2))\). Thus \[ \mathop{\mathrm{tr}}(K^2)=O_d(\sqrt h\log(h+2)). \tag{12}\]

From trace to contraction. We now use permutation symmetry to ensure that every nonconstant eigenvalue contributes many times to the trace. This is the multiplicity principle used, in a different setting, in (Gowers 2008, Lemma 3.2); here an elementary argument suffices.

We claim that, for even \(k\ge6\), every nonzero permutation-invariant subspace \(V\subseteq\mathbb R^X\) orthogonal to the constants has dimension at least \(k/2\). Choose \(k/2\) disjoint transpositions of the vertices. Their actions on \(V\) are commuting orthogonal involutions, so they admit simultaneous diagonalization with sign patterns in \(\{1,-1\}^{k/2}\). If a nonzero simultaneous eigenspace has a pattern with \(j\) negative signs, where \(0<j<k/2\), permutations of the vertex pairs give \(\binom{k/2}j\) distinct patterns. Their eigenspaces are linearly independent, whence \(\dim V\ge\binom{k/2}j\ge k/2\).

Otherwise every occurring pattern is constant, and the product of any two of the chosen transpositions acts as the identity on \(V\). Invariance of \(V\) under all permutations implies the same for every product of two disjoint transpositions. Given five distinct labels \(a,b,c,e,f\), the identity \[[(ab)(ef)]\,[(bc)(ef)]=(ab)(bc)\] then shows that every three-cycle acts as the identity. Thus the alternating group fixes \(V\) pointwise. It is transitive on \(X\): a permutation taking one \(w\)-subset to another can have its parity corrected by a transposition inside the latter subset or its complement. Such a transposition exists for the present values of \(k\) and \(w\). Every function on \(X\) invariant under the alternating group is therefore constant, contrary to the choice of \(V\). This proves the claim.

The permutation invariance of the kernel means that \(K\) commutes with every vertex permutation. Each full eigenspace of its restriction to the orthogonal complement of the constants is therefore an invariant subspace of the kind just considered. Writing \(\mu\) for the largest eigenvalue on that complement, positive semidefiniteness and (12) imply \[\frac k2\mu^2\le\mathop{\mathrm{tr}}(K^2)-1, \qquad \mu=O_d\bigl(k^{-1/4}\sqrt{\log(k+2)}\bigr).\] For \(B_0=B-\mathbb E_aB(a)\), it follows that \[\mathbb E_m|(TB)(m)-\mathbb E_aB(a)|^2 =\langle B_0,KB_0\rangle \le\mu\,\mathbb E_a|B_0(a)|^2.\] All estimates were uniform in \(b\) and \(y\), so a single choice of \(\theta_d(k)\) proves (6). Summing that inequality over the entries of a matrix proves (7), with exactly the same constant. ◻

Proof. We first record the two-matrix estimate that gives the decomposition. For positive semidefinite \(A,B\), let \(P\) be the spectral projection of \(A-B\) onto its nonnegative eigenspaces, and let \(Q=I-P\). This is the same spectral projection used in binary quantum discrimination (Helstrom 1967); here we need a bound on squared Frobenius norms of the compressed matrices. In the block decomposition associated with \(P\) and \(Q\), write \(A=(A_{uv})_{u,v=1}^2\) and \(B=(B_{uv})_{u,v=1}^2\). Since \(P\) commutes with \(A-B\), we have \(A_{12}=B_{12}\), \(A_{11}\succeq B_{11}\), and \(B_{22}\succeq A_{22}\). Thus \[ \begin{split} \mathop{\mathrm{tr}}(AB) &=\mathop{\mathrm{tr}}(A_{11}B_{11})+\mathop{\mathrm{tr}}(A_{22}B_{22}) +2\left\lVert A_{12}\right\rVert_{\mathrm F}^2\\ &\ge \left\lVert PBP\right\rVert_{\mathrm F}^2+\left\lVert QAQ\right\rVert_{\mathrm F}^2. \end{split} \tag{14}\] Here we used the nonnegativity of the trace of a product of two positive semidefinite matrices.

We now induct on \(L\). The assertion for \(L=1\) holds with \(P_1=I\). For \(L\ge2\), apply the preceding construction to \(A=A_1\) and \(B=\sum_{j=2}^L A_j\), and put \(P_1=P\). Apply the induction hypothesis to the compressions \(QA_jQ\), \(2\le j\le L\), on the range of \(Q\). Extend the resulting projections by zero on the range of \(P\), obtaining \(P_2,\ldots,P_L\) on the original space.

The terms on the left of (13) involving either \(P_1\) or \(A_1\) have sum at most \[ \sum_{j=2}^L\left\lVert PA_jP\right\rVert_{\mathrm F}^2 +\sum_{s=2}^L\left\lVert P_sA_1P_s\right\rVert_{\mathrm F}^2 \le \left\lVert PBP\right\rVert_{\mathrm F}^2+\left\lVert QA_1Q\right\rVert_{\mathrm F}^2 \le \mathop{\mathrm{tr}}(A_1B). \tag{15}\] The first inequality uses nonnegative pairwise trace products in the first sum and the orthogonal block decomposition of \(QA_1Q\) in the second. To bound the overlaps introduced by compression, observe that for distinct \(j,j'\ge2\), \[ \begin{split} \mathop{\mathrm{tr}}(A_jQA_{j'}Q) &=\left\lVert A_j^{1/2}QA_{j'}^{1/2}\right\rVert_{\mathrm F}^2\\ &\le 2\mathop{\mathrm{tr}}(A_jA_{j'})+2\mathop{\mathrm{tr}}(A_jPA_{j'}P). \end{split} \tag{16}\] This is the squared triangle inequality applied to \(Q=I-P\). Moreover, \[\sum_{\substack{j,j'\ge2\\j\ne j'}}\mathop{\mathrm{tr}}(A_jPA_{j'}P) \le \left\lVert PBP\right\rVert_{\mathrm F}^2 \le \mathop{\mathrm{tr}}(A_1B).\] Combining these estimates with the induction hypothesis bounds the left side of (13) by \[(1+2C_{L-1})\mathop{\mathrm{tr}}(A_1B) +2C_{L-1}\sum_{\substack{j,j'\ge2\\j\ne j'}}\mathop{\mathrm{tr}}(A_jA_{j'}).\] The full ordered overlap sum is \(2\mathop{\mathrm{tr}}(A_1B)+\sum_{j\ne j',\,j,j'\ge2}\mathop{\mathrm{tr}}(A_jA_{j'})\). Since \(C_{L-1}\ge1\), the preceding bound is at most \(2C_{L-1}\) times this sum. Taking \(C_L=2C_{L-1}\) completes the induction. ◻

Proof. For a matrix-valued function \(Z\) on \(X_i\), use the notation \[T_{i,y}Z(m)=\sum_{x\in X_i}\pi_{i,y}^m(x)Z(x).\] Applying (18) to each entry and summing gives \[ \mathbb E_m\left\lVert T_{i,y}Z(m)-\mathbb E_xZ(x)\right\rVert_{\mathrm F}^2 \le\theta\mathbb E_x\left\lVert Z(x)\right\rVert_{\mathrm F}^2. \tag{25}\] This inequality holds in every finite matrix dimension, with the same \(\theta\).

Proof. Write \(t=2l\), split the vertices into two sets of size \(l\), and take the union of \(d\) independent uniform perfect matchings between the two sides. Equivalently, choose \(d\) independent uniform permutations of \([l]\).

It suffices to check vertex sets of size \(w\leq l\). Fix such a nonempty set \(W\), containing \(a\) vertices on the first side and \(b\) on the second, so that \(a+b=w\). Always \(|\delta_H(W)|\geq d|a-b|\). Thus a failure of (34) is possible only when \(|a-b|<.1w\), in which case \[.45w\leq a,b\leq .55w.\] If the cut has fewer than \(\beta dw\) edges, fewer than \(.05da\) of the \(da\) images of the first-side vertices can lie outside the second-side subset: indeed their number is at most \(\beta dw\leq (.01/.45)da<.05da\).

There are at most \(\exp(.21da)\) choices for these exceptional images, where an image is specified by its domain vertex and permutation label. Here we used \[\sum_{j\leq .05N}\binom Nj \leq \exp\bigl(N[-.05\log(.05)-.95\log(.95)]\bigr) \leq \exp(.21N).\] For any prescribed set of nonexceptional images, sampling without replacement within each permutation bounds the probability that they all lie in the second-side subset by \((b/l)\) to their number. Independence between permutations therefore gives \[\Pr\bigl[|\delta_H(W)|<\beta dw\bigr] \leq \exp(.21da)(.55w/l)^{.95da}.\] The exponent \(.21+.95\log(.55w/l)\) is negative. Using \(da\geq45w\) and \(\binom{2l}{w}\leq(2el/w)^w\), a union bound over all sets of size \(w\) is consequently at most \[\exp\!\left( w\left[\log(2e)+45\bigl(.21+.95\log(.55)\bigr) +41.75\log(w/l)\right]\right) \leq e^{-8w}.\] The last inequality uses \(w/l\leq1\) and \(\log(2e)+45(.21+.95\log(.55))<-8\); all logarithms here are natural. Since \(\sum_{w\geq1}e^{-8w}<1\), some choice of the permutations satisfies (34). A nontrivial connected component would have an empty cut, so the expansion inequality also gives connectivity. ◻

Proof. We specify \(\mathcal D\) on characters. First map any set of incidences to the edges having an odd number of incidences in that set. A character index \(p\) selects the incidences \((i,j)\) for which \(j<d\) and \(p_{i,j}=1\); denote their image by \(E(p)\subseteq E(H)\). This incidence map is linear over \(\mathbb F_2\), so \[E(p+p')=E(p)\mathbin\triangle E(p'),\] where \(\triangle\) denotes symmetric difference.

If incidence signs agreed across every edge, \(\chi_p\) would be the product of the edge signs on \(E(p)\). Multiplying the vertex parity identities over a set \(S\) would prescribe the sign \((-1)^{\sum_{i\in S}b_i}\) for the product on \(\delta_H(S)\): the signs of edges internal to \(S\) occur twice and cancel. Complementary sides of a cut prescribe opposite signs because the total prescribed parity is odd. When \(E(p)\) is a cut and \(p\) has low block degree, expansion selects a unique small side and hence a value for the functional.

Choosing the values on characters. Suppose that \(|p|_{\mathrm{blk}}\leq2D\) and that \(E(p)\) is a cut of \(H\). Since \(|E(p)|\leq2Dd\), expansion gives a side \(S(p)\) of this cut with \[ |S(p)|\leq\frac{2D}{\beta} \leq\frac{2\tau t}{\beta}=\frac t5. \tag{41}\] This side is unique: connectivity implies that two vertex sets with the same cut are equal or complementary. Define \[ \mathcal D(\chi_p)= \begin{cases} (-1)^{\sum_{i\in S(p)}b_i}, & |p|_{\mathrm{blk}}\leq2D \text{ and }E(p)\text{ is a cut},\\ 0,&\text{otherwise}. \end{cases} \tag{42}\] Extending linearly defines \(\mathcal D\) on every real function on \(Y\). The trivial character has \(S(0)=\varnothing\), so \(\mathcal D(1)=1\).

Positivity on low-degree squares. Let \(\mathcal I_D=\{p\in\Lambda^t:|p|_{\mathrm{blk}}\leq D\}\), and consider the matrix \[M_{p,p'}=\mathcal D(\chi_p\chi_{p'}) =\mathcal D(\chi_{p+p'}) \qquad(p,p'\in\mathcal I_D).\] The cut sets of \(H\) form a vector subspace of \(\mathbb F_2^{E(H)}\). Partition \(\mathcal I_D\) according to the coset of this subspace containing \(E(p)\). Entries between different classes are zero. Within a class every entry is a sign, and every diagonal entry is one.

To show that such a block is positive semidefinite, take any three indices \(p_1,p_2,p_3\) in it. Each pair sum has block degree at most \(2D\), and so has a small cut side \(S_{ab}=S(p_a+p_b)\). Linearity of both the incidence map and the cut map gives \[\delta_H(S_{12}\triangle S_{23}\triangle S_{31})=\varnothing.\] The set inside the cut has size at most \(3t/5<t\), by (41). Connectivity forces it to be empty. Therefore \[M_{p_1,p_2}M_{p_2,p_3}M_{p_3,p_1}=1.\] Fixing a reference index \(p_0\) in the class and setting \(\sigma_p=M_{p,p_0}\), we obtain \(M_{p,p'}=\sigma_p\sigma_{p'}\). Each block is thus a rank-one positive semidefinite matrix. If \(g=\sum_{p\in\mathcal I_D}\widehat g(p)\chi_p\), it follows that \[\mathcal D(g^2)= \sum_{p,p'\in\mathcal I_D}\widehat g(p)\widehat g(p')M_{p,p'} \geq0.\]

Values on disagreements. We next show that \(\mathcal D\) assigns value one to the product of the two bit signs on every edge. For a fixed edge \(e=uv\), let \(T\subseteq\{u,v\}\) be the endpoints where the incidence of \(e\) is in the last position. On \(Y_i\) the parity constraint gives \[(-1)^{y_{i,d}}=(-1)^{b_i} \prod_{j=1}^{d-1}(-1)^{y_{i,j}}.\] Using this identity at the vertices in \(T\), we can write \[(-1)^{y_{u,e}+y_{v,e}} =(-1)^{\sum_{i\in T}b_i}\chi_p(y) \qquad\text{with }|p|_{\mathrm{blk}}\leq2.\] Before these replacements, the two selected incidences belong to the same edge and give the empty edge set under the incidence map. Replacing a last incidence by the other \(d-1\) incidences toggles the full star at that vertex. Its image under the incidence map is \(\delta_H(\{i\})\). Hence \(E(p)=\delta_H(T)\), including when \(u\) and \(v\) have parallel edges. For sufficiently large \(t\), we have \(2\leq2D\) and \(|T|\leq2\leq t/5\), so \(T\) is the small side used in (42). The two signs cancel, giving \[\mathcal D\bigl((-1)^{y_{u,e}+y_{v,e}}\bigr)=1.\] Since \(\mathbf1_{\{y_{u,e}\ne y_{v,e}\}} =(1-(-1)^{y_{u,e}+y_{v,e}})/2\), every disagreement indicator has functional value zero. This proves \(\mathcal D(f_\epsilon)=-\epsilon\).

Norm bound. Finally, all \(L^t\) character values in (42) have absolute value at most one. For any real function \(h\), uniform orthonormal Fourier expansion gives \(\widehat h(p)=\mathbb E_{y\in Y}h(y)\chi_p(y)\), and therefore \(|\widehat h(p)|\leq\left\lVert h\right\rVert_\infty\). Thus \[|\mathcal D(h)| \leq\sum_{p\in\Lambda^t}|\widehat h(p)| \leq L^t\left\lVert h\right\rVert_\infty,\] completing the proof. ◻

Proof. Compress to the span of the images of all column factors. This preserves their pairings with the row factors and reduces the size to some \(r\ge1\). The average column factor is positive definite on this span. Hence the compact convex hull of the column factors contains a positive definite matrix \(J\) maximizing the determinant. The one-sided derivative of \(\log\det\) in the direction \(G_m-J\) is nonpositive, giving \[\mathop{\mathrm{tr}}(J^{-1}G_m)\le r.\] Replace the column factors by \(J^{-1/2}G_mJ^{-1/2}\) and the row factors by \(J^{1/2}F_aJ^{1/2}\). These congruences preserve PSD and trace pairings. The new column traces have the required bound. The new row trace is \(\mathop{\mathrm{tr}}(F_aJ)\), a convex combination of entries of the original row, and is at most \(B\). ◻

Proof of Theorem 1. Use the constants \(d=100\), \(\beta=1/100\), and \(\tau=1/1000\) of Section 5, and put \(L=2^{d-1}\). Let \(C_L\) be the constant in Lemma 4. First choose \(\lambda>1\) so that \[ \lambda^\tau\ge64L^4. \tag{43}\] Next fix an even integer \(k\) large enough for the local construction and for \[ L\lambda^2C_L\theta_d(k)\le1. \tag{44}\] Lemma 3 permits this choice. These constants are fixed independently of \(n\) and \(\rho\).

Fix \(0<\rho<1\) and set \(\epsilon=1-\rho\). For a large even \(n\), let \(t\) be the largest even integer satisfying \(kt\le n\). Then \[ kt\le n<k(t+2). \tag{45}\] Take a \(d\)-regular bipartite multigraph \(H\) on \(t\) vertices as in Lemma 6, and give its vertices charges \(b_i\in\{0,1\}\), with exactly one charge equal to one. Order the \(d\) incidences at each vertex. Write \(Y_i\) for the parity-\(b_i\) incidence assignments, identified with the Boolean group on their first \(d-1\) bits.