================================================================================
THE PSD RANK OF SHIFTED MATCHING MATRICES IS EXPONENTIAL
A self-contained proof for a curious reader
Version 2. October 2026.
================================================================================
ABSTRACT.
Let K_n be the complete graph on n = 2m vertices. A perfect matching
of K_n is a set of n/2 edges that partition the vertices: every vertex
lies in exactly one of the chosen edges. Let M_n be the set of all
perfect matchings. For a subset U of the vertices, write delta(U) for
the set of edges with exactly one endpoint in U (the "cut" of U).
For each fixed 0 < rho < 1, define the matrix A_n(rho) with:
- one row for each odd-cardinality subset U of the n vertices,
- one column for each perfect matching M in M_n,
and entries
A_n(rho)_{U,M} = |M cap delta(U)| - 1 + rho.
Every perfect matching meets the cut delta(U) of an odd set U an odd
positive number of times. So every entry above is positive, with the
+rho term lifting a nonnegative integer to a strictly positive number.
Main theorem. There is a universal constant c > 0 such that, for every
fixed 0 < rho < 1 and all sufficiently large even n = 2m,
rank_psd( A_n(rho) ) >= 2^(c n).
Here rank_psd is the real positive semidefinite rank, defined in
Section 1. The conclusion is that A_n(rho), a matrix indexed by all
odd cuts against all matchings, cannot be factored using fewer than
exponentially many PSD rows.
Consequence. The perfect matching polytope P_n has no semidefinite
lift of subexponential size, even approximately, and without assuming
any symmetry on the lift. This is Corollary 7.2.
CONTENTS.
Section 0. Prologue: what are we proving?
Section 1. Background: matchings, polytopes, PSD rank
Section 2. The four ingredients at a glance
Section 3. Ingredient one: local averaging inside a cell
Section 4. Ingredient two: splitting a stack of PSD matrices
Section 5. Ingredient three: Fourier smoothing
Section 6. Ingredient four: an expanding parity system
Section 7. Assembly: the matching lower bound
Appendix A. An independent smoothing theorem for matching averages
Appendix B. References
================================================================================
SECTION 0. PROLOGUE: WHAT ARE WE PROVING?
================================================================================
0.1 Matchings.
---------------
Fix an even integer n = 2m. The complete graph K_n has vertex set
{1, 2, ..., n} and one edge between every pair of distinct vertices.
A perfect matching is a set M of exactly n/2 edges such that every
vertex is an endpoint of exactly one edge of M. (Picture: split n
people into n/2 pairs so that everyone is partnered.)
The number of perfect matchings of K_n is (n-1)(n-3)(n-5)...(1). For
large n this grows like exp( (n/2) log(n/e) ) times a mild factor, so
M_n is exponentially large in n. The rows of our matrix are indexed by
the 2^(n-1) odd subsets of {1,...,n}, and the columns by the
exponentially many perfect matchings.
0.2 The perfect matching polytope.
-----------------------------------
Let E = C(n,2) be the set of edges of K_n, and identify R^E with the
vector space of real-valued functions on the edges. Each perfect
matching M defines a 0/1 vector x_M in R^E, with entry (x_M)_e = 1 if
e belongs to M and 0 otherwise.
The perfect matching polytope is defined as
P_n = conv{ x_M : M in M_n } subset of R^E.
Here "conv" means the convex hull: the smallest convex set containing
all points x_M, equivalently the set of all convex combinations of
these points. Minimizing a linear cost over P_n is the classical
minimum-weight perfect matching problem, and it is solvable in
polynomial time by Edmonds's blossom algorithm.
Edmonds also gave an explicit description of P_n by inequalities. For
a subset U of the vertices, let delta(U) denote the edges with exactly
one endpoint in U. Then
P_n = { x in R^E : x_e >= 0 for all e,
sum_{e in delta(v)} x_e = 1 for all v,
sum_{e in delta(U)} x_e >= 1 for all odd U }.
The middle family of equations is the degree one condition: every
vertex receives total mass exactly one. The last family is the family
of odd-cut inequalities: for every odd-cardinality U, the total mass
crossing the cut must be at least one. There are 2^(n-1) odd subsets
U, so this is an exponentially large but clean description. It is
separable in polynomial time using a minimum odd cut computation.
0.3 Extended formulations.
---------------------------
A natural question: can we describe P_n using a much smaller system of
constraints, if we allow extra variables and a nonlinear cone? This
is the theory of extended formulations. A lift of size k of P_n is a
set
Q = { y in R^k : A y = b, y in K },
for a nice cone K (the linear cone R^k, the nonnegative orthant, the
PSD cone, etc.), together with a linear map pi : R^k -> R^E whose
image of Q is exactly P_n:
pi(Q) = P_n.
The size of the lift is k. A polytope with a small lift can be
optimized using a smaller LP or SDP than the original description
suggests.
Histories worth knowing:
- Yannakakis (1991) proved that the symmetric LP extension complexity
of P_n is exponential. "Symmetric" means invariant under the
natural vertex symmetry of K_n.
- Rothvoss (2017) proved that even an asymmetric LP extension of P_n
is exponential. That settled the LP question completely.
- On the SDP side, the question stayed open for a long time. Our
main theorem settles it: there is no subexponential SDP lift.
0.4 PSD rank.
------------
A real matrix A of dimensions p x q is called nonnegative if every
entry A_{i,j} >= 0. Its real positive semidefinite rank, rank_psd(A),
is the least integer r such that there exist real symmetric PSD r x r
matrices F_1,...,F_p and G_1,...,G_q with
A_{i,j} = tr(F_i G_j) for every i in {1,...,p}, j in {1,...,q}.
A real symmetric matrix is PSD (positive semidefinite) if all its
eigenvalues are >= 0; equivalently, if it can be written as V^T V for
some rectangular V; equivalently, if x^T M x >= 0 for every real
vector x. The cone of PSD r x r matrices is denoted S^r_+.
The factorization condition above is the PSD analogue of "A = U V^T"
for unconstrained real matrices of rank at most r. One way to see it:
give each row i of A a PSD matrix F_i, each column j a PSD matrix G_j,
and set the (i,j) entry to their trace inner product. The PSD
constraint is what makes the problem different from ordinary rank.
Useful basic comparisons:
rank_psd(A) >= rank(A) for every nonnegative A,
rank_psd(A) <= nonneg_rank(A), since diagonals are PSD.
The connection to lifts is the cone factorization theorem of Gouveia,
Parrilo, and Thomas (2013):
Theorem. If P is a polytope described as { x : S(x) >= 0 } for an
affine family S of slack expressions, then P has an SDP lift of
size rank_psd(S). Conversely, every SDP lift of P of size r yields
a PSD factorization of S of size r.
So a lower bound on rank_psd(S) is a lower bound on the minimum SDP
lift size of P. This is the gate that connects our matrix problem to
polytope theory.
0.5 The matrix A_n(rho).
------------------------
Fix 0 < rho <= 1. Let M_n be the perfect matchings of K_n and O_n the
odd-cardinality subsets of {1,...,n}. Define
A_n(rho)_{U,M} = |M cap delta(U)| - 1 + rho,
for U in O_n, M in M_n.
Observations:
(a) Rows are indexed by all odd cuts: 2^(n-1) of them.
(b) Columns are indexed by all perfect matchings: exponentially
many in n.
(c) Entries are nonnegative integers plus rho. Specifically,
|M cap delta(U)| is an odd positive integer (the cut meets every
perfect matching an odd number of times), so at rho = 0 the
entries take values in {0, 2, 4, 6, ...}. Adding rho > 0
shifts them to strictly positive values in
(0, 1) U (2, 3) U (4, 5) U ... .
The endpoint rho = 1 is special and easy. At rho = 1 the entry is
|M cap delta(U)| exactly, and there is a factorization of size C(n,2):
r = C(n,2). Index coordinates by edges e in E.
For a row U: set F_U = diag(f_U) with f_U(e) = 1 if e in
delta(U), else 0.
For a column M: set G_M = diag(g_M) with g_M(e) = 1 if e in M,
else 0.
Then tr(F_U G_M) = sum_{e in E} f_U(e) g_M(e) = |M cap delta(U)|. So
at rho = 1 the matrix A_n(1) has PSD rank at most C(n,2), which is
polynomial in n. The main theorem is therefore optimal in the sharpest
possible sense: rho = 1 is polynomial, and the moment rho drops below
1 the rank blows up to exponential.
Why does the shift matter? At rho = 0 the entries are even
nonnegative integers; A_n(0) is nonnegative, but not entrywise
positive. Kaniewski, Lee, and de Wolf (2015) show that A_n(0) admits
near-exact PSD factorizations with subexponential rank: for every n
there are matrices of rank 2^{o(n)} that approximate A_n(0)
entrywise to error 2^{-sqrt(n/2)}. So exactness is essential. The
strict positivity at 0 < rho < 1 forces the approximation to work at a
scale that no small-size PSD factorization can reach.
0.6 The main theorem.
----------------------
Theorem 0.1 [Main].
There is a universal constant c > 0 such that, for every fixed
0 < rho < 1, there is n_0 = n_0(rho) with:
rank_psd( A_n(rho) ) >= 2^(c n) for every even n >= n_0.
Corollary 0.2 [Unshifted rank and exact lifts].
There are constants c_0 > 0 and n_1 such that for every even n >= n_1,
both A_n(0) and the augmented matrix
T_n(0) (obtained from A_n(0) by adjoining edge rows e |-> 1_{e in M})
have rank_psd >= 2^(c_0 n). In particular, every exact SDP lift of P_n
has size at least 2^(c_0 n).
The corollary follows from the theorem by a small "add a rho block"
trick. We prove both in Section 7.
0.7 Reading paths.
-------------------
Quick tour: Sections 1 and 2 only. This gives the full proof in
skeletal form, without the technical estimates.
Full tour: Sections 1-7 in order. Each of Sections 3-6 stands alone as
a self-contained lemma or theorem that can be read on its own.
Optional: Appendix A is a side result (a smoothing theorem for
averages over matchings with a prescribed edge-count table across a
fixed number of cells). It is not used in the main proof. You can
skip it entirely and the main argument stays complete.
Appendix B is the reference list.
================================================================================
SECTION 1. BACKGROUND AND NOTATIONAL CONVENTIONS
================================================================================
1.1 Finite sets and probability.
---------------------------------
Every set we work with is finite. For a finite set S, |S| denotes its
cardinality. When S carries the uniform probability, every element has
probability 1/|S|, and expectation is written E_s[ . ], often abbreviated
E when the law is clear.
The constructions we will use:
- Product probability. Given finite sets S_1, ..., S_t each with
uniform law, the product S_1 x ... x S_t carries the product law:
independent uniform coordinates.
- Conditioning. E_{A | B = b}[ . ] means expectation under the
conditional law of A given B = b.
Every probability space here is finite: sums are finite, limits are
attained, and no measure-theoretic pathologies arise.
1.2 Matrices: trace, PSD, norms.
---------------------------------
Every matrix in this document has real entries. For a p x q matrix M:
tr(M) is defined for square M; it equals the sum of its diagonal
entries.
M^T is the transpose.
For a square matrix M:
M is symmetric if M^T = M.
M is positive semidefinite (PSD) if any of the following equivalent
conditions holds:
(a) every eigenvalue of M is a nonnegative real number,
(b) M = V^T V for some rectangular real V,
(c) x^T M x >= 0 for every real vector x,
(d) M = sum_{k=1}^K u_k u_k^T for some vectors u_1,...,u_K.
We write M >= 0, or M in the cone S^+.
For two symmetric matrices A, B: "A >= B" means A - B is PSD.
This is a partial order, not a total one.
The cone of PSD r x r matrices is denoted S^r_+.
The inner products and norms we use:
<A, B>_F = tr(A^T B) Frobenius inner product,
||A||_F = sqrt(<A, A>_F) Frobenius norm,
||A||_op = largest singular value of A operator norm.
For a PSD matrix M:
tr(M) = sum of nonnegative eigenvalues, so tr(M) >= 0, and tr(M) = 0
iff M = 0.
||M||_F = sqrt(sum of squares of eigenvalues) <= tr(M).
||M||_op = largest eigenvalue <= tr(M).
For PSD matrices A, B: tr(AB) >= 0. Because tr(AB) = tr(A^{1/2} B
A^{1/2}) and A^{1/2} B A^{1/2} is PSD (a congruence of PSD B by
symmetric A^{1/2}), so its trace is >= 0.
1.3 A few matrix facts used repeatedly.
----------------------------------------
(i) Cauchy-Schwarz (Frobenius). |<A, B>_F| <= ||A||_F ||B||_F.
(ii) Trace-rank-Frobenius, for PSD C:
tr(C) <= sqrt( rank(C) ) * ||C||_F.
Proof: write C = sum_{k=1}^{rank C} lam_k u_k u_k^T with lam_k > 0
and {u_k} orthonormal. Then tr(C) = sum lam_k, ||C||_F^2 =
sum lam_k^2. Cauchy-Schwarz bounds sum lam_k by sqrt(rank) times
sqrt(sum lam_k^2).
(iii) Two-matrix spectral block bound (used in Lemma 4.1). Let A, B
be PSD matrices on the same space. Let P be the spectral
projection of A - B onto its nonnegative eigenspaces, and put
Q = I - P. Then, splitting into P-blocks and Q-blocks,
A_11 >= B_11 >= 0, A_12 = B_12, B_22 >= A_22 >= 0,
tr(AB) >= ||PBP||_F^2 + ||QAQ||_F^2.
Sketch: since P commutes with A - B, we have P(A-B)Q = 0, so the
cross blocks of A and B agree. Then
tr(AB) = tr(A_11 B_11) + tr(A_22 B_22) + 2 ||A_12||_F^2.
Each of the first two terms dominates a Frobenius squared norm
of the corresponding block of the "smaller" matrix.
1.4 Fourier on the Boolean cube.
---------------------------------
Let Y = (F_2)^a, the a-fold product of the two-element group
F_2 = {0, 1} with addition modulo 2. Give Y the uniform probability.
Its characters are the functions
chi_p( y ) = (-1)^{p_1 y_1 + p_2 y_2 + ... + p_a y_a}, p in Y.
These 2^a functions form an orthonormal basis of real-valued functions
on Y:
E_y[ chi_p(y) chi_q(y) ] = 1 if p = q, 0 otherwise.
Hence every real function f : Y -> R has a unique expansion
f(y) = sum_{p in Y} hat{f}(p) chi_p(y), hat{f}(p) = E_y[ f(y) chi_p(y) ].
Two facts we use constantly:
Plancherel: E_y[ f(y) g(y) ] = sum_{p in Y} hat{f}(p) hat{g}(p).
Parseval: E_y[ f(y)^2 ] = sum_{p in Y} hat{f}(p)^2.
For matrix-valued H : Y -> R^{m x r}, all definitions apply entrywise:
hat{H}(p) = E_y[ chi_p(y) H(y) ], H(y) = sum_p hat{H}(p) chi_p(y),
E_y[ ||H(y)||_F^2 ] = sum_p ||hat{H}(p)||_F^2.
The degree of chi_p is |{ j : p_j != 0 }|. A function has degree at
most D if hat{f}(p) vanishes for every p of degree > D. Such a function
is a polynomial of total degree <= D in the indicator bits of y.
1.5 Products of cubes and block degree.
----------------------------------------
Now let Y_1, ..., Y_t each be a copy of (F_2)^a, and let
Y = Y_1 x ... x Y_t with the uniform product law. Characters of Y are
indexed by tuples p = (p_1, ..., p_t) with p_i in (F_2)^a:
chi_p(y) = chi_{p_1}(y_1) chi_{p_2}(y_2) ... chi_{p_t}(y_t).
The block degree of p counts how many of the t cubes it touches:
|p|_blk = |{ i : p_i != 0 }|.
The block distance is
dist(p, q) = |{ i : p_i != q_i }|.
Two trivial but essential identities:
- dist(p, q) = |p + q|_blk, because p_i != q_i iff p_i + q_i != 0.
- Multiplication by chi_q preserves squares and translates
frequency. Since chi_q(y)^2 = 1 for all y, if H is matrix-valued
then
hat{(chi_q * H)}(p) = hat{H}(p + q).
Each coefficient is moved but not scaled: its Frobenius norm is
preserved exactly.
In particular, if the Fourier support of H_branch is contained in the
ball { p : dist(q, p) <= D }, then multiplying by chi_q yields a
function of block degree <= D, with its squared norm unchanged.
1.6 Matrix-valued functions on a product of cubes.
---------------------------------------------------
Given F : Y -> S^r_+, write hat{F}(p) for its Fourier coefficients.
The L^2 mass of F is
||F||_2^2 = E_y[ ||F(y)||_F^2 ] = sum_p ||hat{F}(p)||_F^2.
For a target function f : Y -> R we will use the usual sup-norm
||f||_inf = max_{y in Y} |f(y)|.
================================================================================
SECTION 2. THE FOUR INGREDIENTS AT A GLANCE
================================================================================
The proof has four separable ideas. Each is a self-contained lemma or
theorem. Only at the very end do we wire them together. This section
describes each idea at the level of mathematics-without-ritual and
explains how they interact.
The whole strategy in one sentence: a small PSD factorization of
A_n(rho) would turn a particular nonnegative parity function f into a
sum of low-degree squares, but a linear functional D that is
nonnegative on every low-degree square yields D(f) < 0. Contradiction.
We spend the rest of this section making that sentence precise.
2.1 Setup: an expanding parity graph and its cells.
----------------------------------------------------
Fix constants d = 100, beta = 1/100, tau = 1/1000 once and for all.
Let H be a bipartite d-regular multigraph on t vertices for an even
integer t. Bipartite: the vertices split into two sides, all edges
between sides. d-regular: every vertex is incident to exactly d edges
(counting multiplicity). We pick H with strong expansion:
|delta_H(W)| >= beta * d * min( |W|, t - |W| ) for all W subset [t].
(Lemma 6.1 constructs such an H by a union bound over random
permutations.) Expansion says: any nontrivial subgraph of H must leak
many edges.
Each vertex i of H has d incidence slots, one per edge. We assign each
incidence a bit y_{i,e} in {0, 1}. The bits at vertex i form a vector
y_i in {0, 1}^d, subject to a parity constraint
sum_{e incident to i} y_{i,e} = b_i (mod 2),
where b_i in {0, 1} are fixed bits with
sum_{i=1}^t b_i = 1 (mod 2).
Consequently, over the whole graph, the total parity of incidence bits
is odd. Summing the bit values on both endpoints of every edge, we
find that the number of edges with disagreeing bits is odd:
sum_{e = uv in E(H)} y_{u,e} + y_{v,e} = sum_{incidence} y_{.,.} = 1 (mod 2).
So for every admissible y there is at least one edge with y_{u,e} !=
y_{v,e}.
The domain of the parity system is
Y = prod_{i=1}^t Y_i, Y_i = { y_i in {0,1}^d : sum_{j} y_{i,j} = b_i (mod 2) }.
Each Y_i is an affine copy of (F_2)^{d-1}, of size L = 2^{d-1}.
Now fix 0 < eps < 1 and define
f_eps(y) = sum_{e = uv in E(H)} 1{ y_{u,e} != y_{v,e} } - eps.
By the parity argument, the sum is an odd positive integer, hence at
least 1. So f_eps(y) >= 1 - eps > 0.
2.2 Ingredient 1 (Section 3): averaging within a cell.
-------------------------------------------------------
To realize the parity system by a matching problem, we replace each
vertex i of H by a "cell" of k vertices of K_n, where k is a large even
integer, FIXED once and for all. A cut U "inside cell i" means a
subset of the cell; its size must match the parity b_i, so its size is
w_i in {k/2, k/2+1} congruent to b_i mod 2.
Local data m_i in the cell consist of:
- one ordered list of d distinct terminal vertices (v_1,...,v_d),
- a perfect matching of the remaining k - d vertices.
For y_i in Y_i, the local restriction pi_y^m is the uniform
distribution on w-subsets a of the cell that (a) agree with y at the
terminals: 1_a(v_l) = y_l; (b) take equal values at both endpoints of
every internal pair.
Averaging over these restrictions is nearly an averaging over all
w-subsets when k grows. The exact statement (proved in Section 3):
Lemma 3.1 (Local averaging). There is a rate theta_d(k) -> 0 as
k -> infinity, uniform in b in {0,1} and y in Y_b, such that:
(a) E_{m}[ pi_y^m(a) ] = 1/|X| for every w-subset a of the cell.
(b) For every real function B on the set of w-subsets,
E_m[ ( sum_a pi_y^m(a) B(a) - E_a B(a) )^2 ]
<= theta_d(k) * E_a[ ( B(a) - E_a B(a) )^2 ].
For matrix-valued B the same inequality holds entrywise with
Frobenius-norm squares replacing scalar squares, and theta_d(k) is
independent of the matrix dimensions.
One may take theta_d(k) = O_d( k^{-1/4} sqrt( log(k + 2) ) ).
In words: averaging a bounded function over the local restriction
pushes it close to its own expectation, at a rate independent of the
dimension of the values being averaged. The "independence of dimension"
property is what lets us feed matrix-valued row factors into this
lemma later.
2.3 Ingredient 2 (Section 4): orthogonal splitting.
----------------------------------------------------
Take L PSD matrices A_1, ..., A_L on the same Euclidean space. We
want L mutually orthogonal projections P_1, ..., P_L with sum_s P_s = I
that "separate" the matrices.
Lemma 4.1 (Orthogonal splitting). Given L PSD matrices A_1, ...,
A_L on a finite-dimensional Euclidean space, there exist mutually
orthogonal projections P_1, ..., P_L with sum_s P_s = I and
sum_s sum_{z != s} || P_s A_z P_s ||_F^2
<= C_L * sum_{z != z'} tr( A_z A_{z'} ),
with C_L = 2^{L-1} depending only on L. Zero projections are
allowed.
The first projection P_1 may be chosen to be the spectral
projection of A_1 - (A_2 + ... + A_L) onto its nonnegative
eigenspaces; the rest comes by induction.
The point: if the "off-diagonal overlaps" tr(A_z A_z') are small for
z != z', then peeling off each A_z into its own summand leaks only a
small amount. The dimension of the ambient space never appears in the
bound.
2.4 Ingredient 3 (Section 5): Fourier smoothing.
------------------------------------------------
Combining 2.2 and 2.3 gives a clean statement about matrix-valued
products of weak averages.
Theorem 5.1 (Fourier smoothing of matrix squares). Let X_i and
M_i be finite sets, let pi_{i,y_i}^{m_i} be probability
distributions on X_i satisfying the marginal and variance
conditions of Lemma 3.1 for some theta >= 0, and let Y_i =
(F_2)^a with L = 2^a. Let F : prod X_i -> S^r_+ be PSD-valued
with tr F(x) <= B for every x.
Fix lambda > 1 with L * lambda^2 * C_L * theta <= 1, where C_L is
from Lemma 4.1.
Then there exist rectangular matrix functions
H_q^m : prod Y_i -> R^{R x r}, q in Lambda^t, Lambda = (F_2)^a,
for some finite R, such that for every m = (m_1,...,m_t),
(i) F_bar_m(y) = sum_{q in Lambda^t} H_q^m(y)^T H_q^m(y) for all
y in prod Y_i, where F_bar_m is the product-restricted
average of F;
(ii) writing U_q^m and C_q^m for the weighted frequency
concatenation and its Gram matrix,
U_q^m = [ lambda^{dist(q,p)/2} hat{H}_{q,p}^m : p in Lambda^t ]
(horizontal concatenation over p),
C_q^m = U_q^m (U_q^m)^T,
the Gram potential has the bound, in expectation over m,
E_m[ sum_q || C_q^m ||_F^2 ] <= 2^t B^2.
Consequently, there exists at least one choice of m satisfying
sum_{q, p} lambda^{dist(q,p)} || hat{H}_{q,p}^m ||_F^2
<= L^t * sqrt(r) * B * 2^{t/2}.
Interpretation: even an arbitrary PSD-valued function F admits a
canonical representation by squares H_q^T H_q in which each branch q's
Fourier coefficients are exponentially damped when the block-distance
from q grows. "Distance" counts blocks, not bits. The proof processes
the t coordinates one by one; at each step a new average is realized by
a fresh stack and Lemma 4.1 splits the stack into branches. Lemma 3.1
keeps the compounding error under control.
2.5 Ingredient 4 (Section 6): the separating functional.
---------------------------------------------------------
The parity function f_eps is nonnegative but not a low-degree square.
We make this concrete with a specific linear functional.
Proposition 6.2. For every sufficiently large even t, with H, Y,
b_i, D = floor(tau t), Lambda, and L as above, there is a real
linear functional D on real functions on Y such that:
(i) D(1) = 1.
(ii) D(g^2) >= 0 for every real g : Y -> R of block degree
at most D.
(iii) D(f_eps) = -eps for every 0 < eps < 1.
(iv) |D(h)| <= L^t * ||h||_inf for every real h on Y.
Property (ii) says D is nonnegative on every low-degree square.
Property (iii) says f_eps is not the sum of any such squares under D.
Properties (i) and (iv) are normalization and boundedness.
Mechanism: the functional is defined on characters p by a sign rule.
For |p|_blk <= 2D, the "incidence map" E(p) subset E(H) picks out the
edges with an odd number of chosen incidences. If E(p) happens to be
a cut delta_H(S), expansion (Lemma 6.1) guarantees that one side S
of the cut is uniquely small (size <= t/5). Define D(chi_p) = the
parity sign (-1)^{sum_{i in S} b_i} of that small side. For all other
characters, set D(chi_p) = 0.
Two facts to check: for any three low-degree characters in the same
"cut coset", the product of three D-signs is one (so each coset block
of D is rank-one PSD); and the disagreement indicators 1{y_{u,e} !=
y_{v,e}} all have D-value zero (because the corresponding character
is the cut of a small side, whose sign cancels against the parity
identity). Doing the sum gives D(f_eps) = -eps.
2.6 Assembly: the contradiction.
---------------------------------
Now suppose A_n(rho) has PSD rank at most 2^t (we will choose t to
scale linearly with n, so this is exponential in n but small enough
to try). Then A_n(rho)_{U,M} = tr(F_U G_M) with PSD factors F_U, G_M
of size r <= 2^t.
Fix constants as in 2.1: d = 100, beta = 1/100, tau = 1/1000, and let
L = 2^{d-1} = 2^{99}. Let C_L = 2^{L-1}. Choose lambda > 1 with
lambda^{tau t} >= 4 L^4 (specific scaling chosen for later error
bookkeeping; any sufficiently large lambda works). Then choose an
even integer k so large that
L * lambda^2 * C_L * theta_d(k) <= 1.
This is possible because theta_d(k) -> 0 as k -> infinity. All these
constants are now fixed and do not depend on n.
Fix 0 < rho < 1 and put eps = 1 - rho. For a large even n, let t be
the largest even integer with kt <= n. Then kt <= n < k(t+2), so
t >= n / (2k) is linear in n.
Take an expanding bipartite d-regular multigraph H on t vertices
(Lemma 6.1), and give each vertex i a bit b_i in {0,1} with
sum b_i = 1 (mod 2). Partition kt vertices of K_n into cells C_1,...,C_t
of size k. Pair the remaining n - kt vertices (an even number) in a
fixed way.
For any y in Y, and any local data m = (m_1,...,m_t) per cell, let
M(m) be the matching of K_n obtained by (a) matching terminals t_{i,e}
and t_{j,e} for each edge e = ij in E(H); (b) matching internal pairs
within each cell; (c) matching the leftover vertices by the fixed
pairing. Let U(a) = union_i a_i for a = (a_1,...,a_t) the chosen
w_i-subsets of the cells.
Now sum: for y in Y and for the corresponding cell-by-cell restrictions,
sum_a pi_y^m(a) tr( F_{U(a)} G_{M(m)} )
= sum_a pi_y^m(a) ( |M(m) cap delta(U(a))| - 1 + rho )
= f_eps(y).
Let F_bar(y) = sum_a pi_y^m(a) F_{U(a)}. Then
tr( F_bar(y) G ) = f_eps(y) for every y in Y.
Apply Fourier smoothing (Theorem 5.1) with average trace bound
B = n (Lemma 7.1 gives tr F_U <= n for all cuts U after normalization).
Get, for some choice of m and G = G_{M(m)},
F_bar(y) = sum_q H_q(y)^T H_q(y),
with weighted Fourier mass bounded by L^t * sqrt(r) * n * 2^{t/2}.
Now truncate. Put D = floor(tau t). For each q, let K_q = sum_{p:
dist(q,p) <= D} hat{H}_{q,p} chi_p, and let
f_*(y) = sum_q || K_q(y) G^{1/2} ||_F^2.
The mass bound gives a uniform estimate:
|| f_eps - f_* ||_inf <= 3 n (4L)^{-t}.
(Because sum_q || hat{H}_{q,p} G^{1/2} ||_F^2 is bounded by n / something,
and Cauchy-Schwarz over <= L^t characters per branch gives the bound.)
Now observe: for each q, multiply K_q by chi_q. By the character
translation property (Section 1.5), chi_q K_q is a function of block
degree at most D (since dist(q,p) <= D means |p+q|_blk <= D).
Multiplication preserves any square (chi_q(y)^2 = 1), so
f_*(y) = sum_q || (chi_q(y) K_q(y)) G^{1/2} ||_F^2,
which is a sum of squares of block-degree-at-most-D functions.
Apply the separating functional D from Proposition 6.2. On one hand,
D(f_*) >= 0 (property (ii): D is nonnegative on low-degree
squares).
On the other hand,
D(f_eps) = -eps < 0 (property (iii)).
And the sup-norm distance gives, via property (iv),
| D(f_*) - D(f_eps) | <= L^t * || f_eps - f_* ||_inf
<= L^t * 3 n (4L)^{-t}
= 3 n * (4)^{-t} * L^t * (L)^{-t}
= 3 n * 4^{-t}
-> 0.
Since t >= n / (2k) grows linearly with n, the RHS is < eps for all
sufficiently large n. Contradiction.
Therefore A_n(rho) has no PSD factorization of size at most 2^t, and
rank_psd( A_n(rho) ) > 2^t >= 2^{n / (2k)}.
Taking c = 1/(2k) proves Theorem 0.1 / Theorem 7.2.
2.7 What each later section must deliver.
------------------------------------------
Section 3: Lemma 3.1 (local averaging), full proof.
Section 4: Lemma 4.1 (orthogonal splitting), full proof.
Section 5: Theorem 5.1 (Fourier smoothing), full proof.
Section 6: Lemma 6.1 (expanding multigraph), Proposition 6.2 (separating
functional), full proofs.
Section 7: Lemma 7.1 (normalization of PSD factors), Theorem 7.2
(Theorem 0.1 restated and proven), Corollary 7.3 (Corollary
0.2 restated and proven), and a final appendix cross
reference.
Each of Sections 3-6 can be read standalone. Section 7 ties them
together.
Now the trees.
================================================================================
SECTION 3. INGREDIENT ONE: LOCAL AVERAGING INSIDE A CELL
================================================================================
This section proves Lemma 3.1, the local averaging lemma. It is the
analytic engine behind Theorem 5.1. The setup is a single cell of k
vertices of K_n; a "local restriction" is a way of choosing which of
the k vertices belong to a cut, subject to a parity constraint and
to a set of "internal pair" equalities. The lemma says: averaging
any function of the cut over the local restriction is, with high
probability over the local data, close to averaging it over all cuts
of the right size. The rate is independent of the dimension of the
function being averaged.
3.1 The cell, the cut space, and the local data.
-------------------------------------------------
Fix an even integer d >= 2 once and for all. In the parity application
we take d = 100, but the proof only uses d's smallness.
Let k be an even integer, sufficiently large (k >= k_0(d)). The "cell"
has vertex set [k] = {1, ..., k}.
For b in {0, 1}, let w be the unique integer in {k/2, k/2 + 1} with
w = b (mod 2). Set
X = C([k], w) (all w-element subsets of the cell, viewed as
BITS: a subset a subset [k] with |a| = w,
identified with its indicator 1_a in {0,1}^k)
Y_b = { y in {0, 1}^d : sum_{l=1}^d y_l = b (mod 2) }
L = |Y_b| = 2^{d-1}.
Both X and Y_b carry uniform probability.
"Local data" m consist of:
- an ordered list of d distinct terminals (v_1, ..., v_d) in [k],
- a perfect matching of the remaining k - d vertices.
Let M = M(k, d) be the set of such data, with uniform law.
For y in Y_b, define the probability distribution pi_y^m on X by:
uniform on w-subsets a subset [k] that satisfy
(a) terminal values: 1_a(v_l) = y_l for l = 1, ..., d;
(b) internal pairs: 1_a(u) = 1_a(v) for every internal pair {u, v} of m.
Equivalently, pi_y^m(a) = 1{T(a) = y and a is constant on internal pairs}
/ Z(y, m), where T(a) = (1_a(v_1), ..., 1_a(v_d))
is the terminal bit vector of a, and Z is the
normalization.
We first check that pi_y^m is well-defined (the support is nonempty).
Write
s = |y| = number of 1s in y
h = (k - d) / 2 = number of internal pairs
g = (w - s) / 2 = number of internal pairs assigned cut value 1.
The parity condition makes g an integer: s = w (mod 2). A subset a
satisfying (a) and (b) is determined by: the s terminals with y_l = 1
(mandatory), the w - s = 2g other vertices, which must be whole pairs.
So the support size is C(h, g).
Let delta = w - k/2 in {0, 1}. Then
g = (w - s)/2 = (k/2 + delta - s)/2 = (k - s)/2 + (delta - s)/2
= (k/2 - s/2 + d/4 - d/4) + ...
= h/2 + d/4 + delta/2 - s/2
= (h/2) + (d/4 + delta/2 - s/2).
With s in {0, ..., d} and delta in {0, 1}, we have
|g - h/2| <= d/4 + 1/2. (*)
Since k is large, 0 <= g <= h, so the support is nonempty.
For a real function B on X, define
(T_y B)(m) = sum_{a in X} pi_y^m(a) B(a).
For matrix-valued B, apply the definition entrywise. Expectations
over m, a, y below use the uniform laws.
3.2 Statement of the local averaging lemma.
--------------------------------------------
Lemma 3.1 (Local averaging).
For each fixed even d >= 2, there exist k_0(d) and a function
theta_d(k) >= 0 defined for even k >= k_0(d), with theta_d(k) -> 0
as k -> infinity, such that the following holds for both b in {0, 1}
and for every y in Y_b.
(a) Marginal: E_m[ pi_y^m(a) ] = 1/|X| for every a in X.
(b) Scalar variance: for every real function B on X,
E_m[ | (T_y B)(m) - E_a B(a) |^2 ]
<= theta_d(k) * E_a[ | B(a) - E_a B(a) |^2 ].
(c) Matrix variance: for every pair of positive integers p, q and
every matrix-valued B : X -> R^{p x q},
E_m[ || (T_y B)(m) - E_a B(a) ||_F^2 ]
<= theta_d(k) * E_a[ || B(a) - E_a B(a) ||_F^2 ].
The same theta_d(k) works, and it does not depend on p or q.
One may take theta_d(k) = O_d( k^{-1/4} sqrt( log(k+2) ) ).
The dimension independence in (c) is the crucial property. Combined
with the fact that theta_d(k) -> 0, it means we can average matrices
of any size with an error that shrinks as the cell grows.
3.3 The marginal (proof of (a)).
---------------------------------
The law of pi_y^m given m, and the uniform law on m, are permutation-
equivariant under the symmetric group S_k acting on the k vertices of
the cell. Specifically, for a permutation sigma in S_k, using the
natural push-forward actions on cells and local data:
pi_{sigma(y)}^{sigma(m)}(sigma(a)) = pi_y^m(a).
When we integrate over the uniform law on m, symmetry gives
Pr[a is uniform from pi_y^m] = 1/|X| for every a in X.
That is: E_m pi_y^m(a) = 1/|X|. Reason: S_k is transitive on w-subsets
of [k], so all a in X are equally likely under the two-step sampling
"m uniform; a ~ pi_y^m". This proves (a). Consequently the
operator K = T_y^* T_y on functions on X has K 1 = 1.
3.4 The kernel K and its trace.
--------------------------------
Fix b and y (we will show the estimates are uniform in both). Write
T = T_y. The adjoint T^* of T (from functions on M to functions on X)
and the composition K = T^* T define an operator on the space of real
functions on X, equipped with the L^2(X) inner product for the uniform
law. K is self-adjoint and PSD.
By 3.3, K 1 = 1, where 1 is the constant function.
We will show:
tr(K^2) = O_d( sqrt(h) * log(h + 2) ), (Trace)
in the operator trace sense (sum of squared eigenvalues of K). And:
every nonzero K-invariant subspace V subset R^X orthogonal to the
constants has dim V >= k / 2. (Mult)
Together, (Trace) and (Mult) give the contraction bound we need; see
3.7 below.
3.5 The two-sample density of K.
---------------------------------
Sample m uniformly, then sample a, a' in X *independently* from
pi_y^m conditional on m. Let J(a, a') be the joint probability that
(a, a') arises this way. Let N = |X|. The joint law is a mixture
over m of independent pi_y^m-samples, so its density with respect to
independent uniform samples a, a' from X is
D(a, a') = N^2 J(a, a').
A direct calculation: for scalar functions B_1, B_2, the pairing
between B_1 and B_2 under K is
<B_1, K B_2>_X = sum_{a, a' in X} J(a, a') B_1(a) B_2(a').
The kernel of K in the standard L^2(X) basis is therefore K(a, a') =
D(a, a')/N. By symmetry (a and a' are symmetric roles), K is a
symmetric operator on the finite space X, and its squared Hilbert-
Schmidt norm equals its squared operator L^2 norm, so:
tr(K^2) = sum_{a in X} sum_{a' in X} K(a, a')^2
= (1/N^2) sum_{a, a' in X} D(a, a')^2. (Density)
This is the standard identity; we use it below to calculate tr(K^2)
by studying the joint law of the two-sample construction.
3.6 The joint law depends only on |a cap a'|.
---------------------------------------------
The joint law of (a, a') under the two-sample construction is
permutation-invariant: it depends only on |a cap a'|, not on the
particular identity of the vertices. Consequences:
- Conditional on m and on the first sample a, the second sample a'
is chosen uniformly from the g-subsets of the h internal pairs that
make |a cap a'| = w - 2j for some j (given m, a, and the constraint
a cap a' = w - 2j is determined by how many of a's g internal "1"
pairs are replaced by "0" pairs).
- Therefore, for m uniform and a, a' two-sample: the probability
that the two samples differ by replacing exactly j of the "1" pairs
of a is
P_j = C(g, j) C(h - g, j) / C(h, g). (P_j formula)
(Choose j of the g "1"-pairs and j of the h-g "0"-pairs; the
intersection size is then s + 2(g - j) = w - 2j.)
- For two independent uniform w-subsets a, a' of [k] (not conditioned
on the local data), the probability that |a cap a'| = w - 2j is
Q_j = C(w, 2j) C(k - w, 2j) / C(k, w). (Q_j formula)
(Choose a, then choose w-2j elements of a and 2j elements of [k]\a
for a'.)
Both laws are uniform within each intersection class. To pass to
the densities, note that the size of class_j is
|class_j| = N * C(w, 2j) * C(k-w, 2j)
(choose a first, then choose a' by picking 2j elements from [k]-a and
w-2j elements from a). Since J is uniform on class_j with total mass
P_j, we have
J(a, a') = P_j / |class_j|
= P_j / (N * C(w, 2j) * C(k-w, 2j)),
D(a, a') = N^2 * J(a, a')
= N * P_j / (C(w, 2j) * C(k-w, 2j)).
Plug into (Density):
tr(K^2) = (1/N^2) sum_{a, a'} D(a, a')^2
= (1/N^2) sum_j |class_j| * (N * P_j / (C(w,2j) C(k-w,2j)))^2
= sum_j C(k, w) * P_j^2 / (C(w,2j) C(k-w,2j))
= sum_j P_j^2 / Q_j.
(The last step uses Q_j = C(w,2j)C(k-w,2j)/C(k,w).) So
tr(K^2) = sum_{j=0}^{g_*} P_j^2 / Q_j, (tr formula)
where g_* = min(g, h - g). Both P_j and Q_j vanish outside
0 <= j <= g_*.
3.7 The trace bound tr(K^2) = O_d( sqrt(h) log(h+2) ).
-------------------------------------------------------
We need a binomial estimate.
Claim (binomial ratio). There is an absolute constant C such that for
integers 0 <= j <= u:
C(u, j)^2 / C(2u, 2j) <= C * sqrt( (u+1) / ((j+1)(u-j+1)) ). (BR)
Proof of (BR). Expand:
C(u,j)^2 / C(2u,2j)
= [u! / (j! (u-j)!)]^2 * (2j)! (2u-2j)! / (2u)!
= [ (2j)! / (j! j!) ] * [ (2(u-j))! / ((u-j)! (u-j)!) ] / [ (2u)! / (u! u!) ]
= C(2j, j) * C(2(u-j), u-j) / C(2u, u).
The identity C(2v, v) ~ 4^v / sqrt(pi v) then gives
C(u,j)^2 / C(2u,2j)
<= C * [4^j / sqrt(j+1)] [4^{u-j} / sqrt(u-j+1)] / [4^u / sqrt(u+1)]
= C * sqrt(u+1) / sqrt((j+1)(u-j+1)).
The bound holds also at the endpoints j = 0 and j = u (up to a constant).
This proves (BR).
Now, the central binomial estimates give, uniformly in b and y,
C(k, w) / C(h, g)^2 = O_d( sqrt(h) ). (CR)
Justification: C(k, w) ~ 2^k / sqrt(pi w / 2) up to a constant, and
C(h, g)^2 ~ (2^h / sqrt(pi g / 2))^2 = 2^{2h} / (pi g / 2). Since
k = 2h + d (from w = k/2 + delta and g = h/2 + O_d(1)), the ratio
reduces to O_d(sqrt h). (We have d fixed, so all the constants
hidden by O_d are allowed to depend on d.)
For j in [0, g_*], since w >= 2g (as w = 2g + s, s >= 0) and
k - w = 2(h - g) + (d - s) >= 2(h-g), we have
C(w, 2j) >= C(2g, 2j), C(k-w, 2j) >= C(2(h-g), 2j).
Hence P_j^2/Q_j is bounded as follows:
P_j^2/Q_j = [C(g,j)C(h-g,j) / C(h,g)]^2 / Q_j
= C(k,w) C(g,j)^2 C(h-g,j)^2 / [C(h,g)^2 C(w,2j) C(k-w,2j)]
<= C(k,w) C(g,j)^2 C(h-g,j)^2 / [C(h,g)^2 C(2g,2j) C(2(h-g),2j)]
<= C(k,w)/C(h,g)^2 * C^2 * sqrt((g+1)(h-g+1) / ((j+1)^2 (g-j+1)(h-g-j+1))).
Using (CR) and the fact that sqrt((g+1)(h-g+1)) = O_d(h):
P_j^2/Q_j <= O_d( sqrt(h) ) * (h/2) * C^2 / [ (j+1) sqrt((g-j+1)(h-g-j+1)) ].
Summing over j from 0 to g_*:
tr(K^2) <= O_d( sqrt(h) ) * C^2 * (h/2) * Sigma_j
where Sigma_j = sum_{j=0}^{g_*} 1 / [ (j+1) sqrt((g-j+1)(h-g-j+1)) ].
Now substitute j' = g_* - j. Since g_* = min(g, h-g), and (from (3.1)
above) g = h/2 + O_d(1), h - g = h/2 + O_d(1), we have (g-j+1) =
(g-g_* + j' + 1) = O_d(1) + j' + 1 and (h-g-j+1) = (h-g-g_* + j' + 1)
= O_d(1) + j' + 1. So
Sigma_j = sum_{j'=0}^{g_*} 1 / [ (g_* - j' + 1) * sqrt((O_d(1) + j')(O_d(1) + j')) ]
<= sum_{j'=1}^{g_*} 1 / [ (g_* - j' + 1) * j' ] * O_d(1)
= (2/(g_* + 1)) * H_{g_*} * O_d(1) (H_n = harmonic number)
= O_d( log(h+2) / h ).
The sum Sigma_{j'=1}^{g_*} 1/[j' (g_*-j'+1)] = (2/(g_*+1)) H_{g_*} is a
standard identity (partial fractions). So:
tr(K^2) <= O_d( sqrt(h) ) * (h/2) * C^2 * O_d( log(h+2)/h )
= O_d( sqrt(h) * log(h+2) ).
This proves (Trace). Note tr(K^2) - 1 = sum_{eigenvalue}^2 - 1 = sum of
squares of nonconstant eigenvalues. Since tr(K) >= 1 (K is PSD with
K1=1, so at least one eigenvalue 1), we get tr(K^2) >= 1 automatically;
the bound tr(K^2) = O_d(sqrt h log(h+2)) is what we will use below.
3.8 The multiplicity bound.
----------------------------
We now prove (Mult): every nonzero permutation-invariant subspace
V subset R^X orthogonal to the constants has dimension >= k/2.
Proof of (Mult). Choose k/2 disjoint transpositions tau_1, ..., tau_{k/2}
of [k] (they exist since k is even). The actions of these
transpositions on V (via permutation) are commuting orthogonal
involutions, so they admit a simultaneous eigendecomposition:
V decomposes as an orthogonal direct sum of subspaces V_eps, indexed
by sign patterns eps in {+1, -1}^{k/2}, such that tau_i acts as
scalar eps_i on V_eps.
Case 1: some V_eps is nonzero with a non-constant sign pattern eps
(that is, with j negative signs where 0 < j < k/2). Then by
conjugating tau_1, ..., tau_{k/2} by any permutation of the vertex
pairs {1,2}, {3,4}, ..., {k-1, k}, we obtain the same V decomposed
with respect to the corresponding conjugated transpositions. The
eigenspaces for different sign patterns are linearly independent, and
there are C(k/2, j) >= k/2 such patterns. So dim V >= C(k/2, j) >=
./pdf/pdf/2.
Case 2: every nonzero V_eps has constant sign pattern (all + or all -).
Then the product tau_i tau_j of any two of the chosen transpositions
acts as the identity on V for every i, j. Since V is S_k-invariant,
this product-of-disjoint-transpositions property extends to all
products of two disjoint transpositions of [k]. Using the identity
[(ab)(ef)] [ (bc)(ef) ] = (ab)(bc),
which holds whenever a, b, c, e, f are distinct, we conclude: every
3-cycle (ab)(bc) acts as the identity on V, hence the alternating
group A_k acts trivially on V. Since A_k is transitive on w-subsets
of [k] for the values of k and w we consider, every function on X
fixed by A_k is constant. So V is contained in the constants, and
since V was orthogonal to the constants, V is the zero space. This
contradicts V nonzero.
Hence Case 2 cannot occur, and (Mult) is proven.
(The transitivity of A_k on w-subsets of [k]: given any w-subset S and
target w-subset T, there exists a bijection [k] -> [k] sending S to T.
If this bijection is odd, multiply it by a transposition inside T
(which has at least 2 elements for our k and w) or inside T's
complement (which also has at least 2 elements). This composes to an
even permutation, and the corrected one is in A_k.)
3.9 From trace and multiplicity to contraction.
-----------------------------------------------
Recall K is PSD, K 1 = 1, and K commutes with vertex permutations
(because both the sum over m and pi_y^m itself are permutation-
invariant). Therefore every eigenspace of K on the orthogonal
complement of the constants is a permutation-invariant subspace.
Let mu denote the largest eigenvalue of K on the orthogonal complement
of the constants. By (Mult), the eigenspace for mu (an invariant
subspace orthogonal to the constants) has dimension at least k/2. By
PSD of K and definition of trace,
k/2 * mu^2 <= tr(K^2) - 1 <= tr(K^2) = O_d( sqrt(h) log(h+2) ).
So
mu <= O_d( sqrt(h) * sqrt(log(h+2)) / sqrt(k) ).
Since h = (k-d)/2 = k/2 + O_d(1), we have h^{1/4} = (k/2)^{1/4} *
(1 + O_d(1/k)) = 2^{-1/4} * k^{1/4} * (1 + O_d(1/k)). Hence
mu <= O_d( h^{1/4} * sqrt(log(h+2)) / k^{1/2} )
= O_d( k^{-1/4} * sqrt(log(h+2)) )
= O_d( k^{-1/4} * sqrt(log(k+2)) ).
Setting
theta_d(k) = A_d * k^{-1/4} * sqrt(log(k+2))
for a large enough constant A_d = O_d(1) completes the scalar bound
(3.1)(b).
3.10 The scalar-to-matrix step (proof of (c)).
-----------------------------------------------
Given matrix-valued B = (B_{uv}) : X -> R^{p x q}, each entry is a
real function on X. Applying (3.1)(b) entrywise gives, for each u, v:
E_m[ | (T_y B_{uv})(m) - E_a B_{uv}(a) |^2 ]
<= theta_d(k) * E_a[ | B_{uv}(a) - E_a B_{uv}(a) |^2 ].
Summing over u, v:
E_m[ || (T_y B)(m) - E_a B(a) ||_F^2 ]
= sum_{u,v} E_m[ | (T_y B_{uv})(m) - E_a B_{uv}(a) |^2 ] (by def. of Frobenius)
<= sum_{u,v} theta_d(k) E_a[ | B_{uv}(a) - E_a B_{uv}(a) |^2 ]
= theta_d(k) E_a[ || B(a) - E_a B(a) ||_F^2 ].
So the same theta_d(k) works for every matrix dimension p x q, with
no extra factor. This proves (c). End of the proof of Lemma 3.1.
3.11 A final note on conditioning.
-----------------------------------
Lemma 3.1 applies uniformly in b and y, and is further uniform in any
"auxiliary conditioning": if we condition on the values of pi_y^m
through a set of linear functionals, the lemma still holds with the
same theta_d(k), as long as the residual law of m given those functionals
is uniform on the appropriate set of m's. This is what we will use
in Section 5 when applying the lemma at each stage of the (weakly)
conditional averaging.
Specifically, the variance bound (3.1)(c) is linear in the outer
expectation, so if we fix some auxiliary data (say a value of B = B(data))
and apply the bound conditionally, we can then uncondition by the
auxiliary data without any loss in the constant. Section 5 makes this
precise in its setup.
That completes the local averaging lemma.
Now the trees continue with the next ingredient.
================================================================================
SECTION 4. INGREDIENT TWO: SPLITTING A STACK OF PSD MATRICES
================================================================================
We need a tool for separating a family of PSD matrices whose "off-
diagonal overlaps" are small into disjoint orthogonal summands. The
separation cost must depend on the number of matrices, not on the
ambient dimension. This is the content of the orthogonal splitting
lemma, which we use in Section 5 to control the Fourier mass
introduced by each averaging step.
4.1 Statement of the splitting lemma.
--------------------------------------
Lemma 4.1 (Orthogonal splitting). Let A_1, ..., A_L be real symmetric
PSD matrices on a finite-dimensional Euclidean space V. Then there
exist mutually orthogonal projections P_1, ..., P_L on V, satisfying
P_s P_{s'} = 0 for s != s', P_s^2 = P_s, sum_{s=1}^L P_s = I,
such that
sum_{s=1}^L sum_{z != s} || P_s A_z P_s ||_F^2
<= C_L * sum_{z != z'} tr( A_z A_{z'} ), (OS)
with C_L = 2^{L-1} depending only on L. Here the right side sums
over ordered pairs of distinct indices z, z', and Zero projections
are allowed.
Note that the left side is a "leaked mass" measure: for each branch s,
we compute how much of the other A_z's survive after compression to
P_s's range. The lemma says this leaked mass is controlled by the
off-diagonal overlaps.
4.2 The two-matrix case.
-------------------------
We first record a base case: L = 2. This is the "binary quantum
discrimination" step that also appears in Helstrom's work on
distinguishing quantum states.
Two-matrix fact (base case). Let A and B be PSD matrices on a
finite-dimensional Euclidean space. There are two orthogonal
projections P, Q with P + Q = I and
|| P B P ||_F^2 + || Q A Q ||_F^2 <= tr( A B ). (2M)
Proof. Let P be the spectral projection of A - B onto its nonnegative
eigenspaces, and Q = I - P. Because P is a spectral projection of a
Hermitian matrix, it commutes with A - B, so the P-blocks and Q-blocks
of A - B have no cross terms:
A - B = P(A - B)P + Q(A - B)Q.
Equivalently, in P-vs-Q block form with A_11 = PAP, A_12 = PAQ, etc.:
A_11 >= B_11, A_12 = B_12, B_22 >= A_22.
Now compute the trace-AB product:
tr(AB) = tr(A_11 B_11) + tr(A_22 B_22) + tr(A_12 B_21) + tr(A_21 B_12).
The last two terms: A_12 = (A_21)^T = (B_21)^T (since A_21 = A_12^T
and A_12 = B_12 = B_21^T), and similarly for the other. So both
equal tr(A_12 A_12^T) = ||A_12||_F^2. Therefore
tr(AB) = tr(A_11 B_11) + tr(A_22 B_22) + 2 || A_12 ||_F^2.
Now: tr(A_11 B_11) >= 0 and A_11 >= B_11 >= 0 implies tr(A_11 B_11)
>= tr(B_11 B_11) = ||B_11||_F^2 = ||PBP||_F^2. (Because B_11 PSD, and
A_11 - B_11 PSD means tr((A_11 - B_11) B_11) >= 0 by trace of
PSD-times-PSD.)
Similarly tr(A_22 B_22) >= tr(A_22 A_22) = ||QAQ||_F^2.
Putting these bounds together:
tr(AB) >= ||PBP||_F^2 + ||QAQ||_F^2.
This proves (2M).
4.3 Induction on L.
--------------------
Now we prove Lemma 4.1 for general L by induction on L. The base
case L = 1 is trivial: take P_1 = I; the sum on the left of (OS) is
empty and equal to zero.
For the inductive step, assume the lemma holds for L - 1 matrices.
Given A_1, ..., A_L, put
B = A_2 + A_3 + ... + A_L.
Apply the two-matrix fact (4.2) to the pair (A_1, B), getting
orthogonal projections P_1, Q with P_1 + Q = I satisfying
|| P_1 B P_1 ||_F^2 + || Q A_1 Q ||_F^2 <= tr( A_1 B ). (+)
Restrict to the range of Q. The compressions Q A_2 Q, ..., Q A_L Q
are PSD matrices on that subspace. Apply the induction hypothesis (to
the L - 1 matrices Q A_2 Q, ..., Q A_L Q on the range of Q), obtaining
orthogonal projections P_2', ..., P_L' on the range of Q with
sum_{s=2}^L P_s' = I_Q (identity on the range of Q). Now extend each
P_s' to a projection P_s on the whole space by declaring P_s = 0 on the
range of P_1. Then P_2, ..., P_L are orthogonal projections on the
whole space, they commute with P_1 (since P_1 * P_s = 0 = P_s * P_1),
and sum_{s=1}^L P_s = P_1 + Q = I.
By the induction hypothesis applied to Q A_2 Q, ..., Q A_L Q:
sum_{s=2}^L sum_{z >= 2, z != s} || P_s (Q A_z Q) P_s ||_F^2
<= C_{L-1} * sum_{z != z' >= 2} tr( (Q A_z Q) (Q A_z' Q) ). (*)
Note ||P_s (Q A_z Q) P_s||_F^2 = ||P_s A_z P_s||_F^2, because P_s is
supported on Q's range so P_s Q = P_s.
4.4 Bounding the individual pieces.
------------------------------------
We decompose the sum in (OS) into three groups.
Group 1: P_1 with z != 1 (so z >= 2). For PSD matrices M_1, ..., M_n
we have
|| sum_k M_k ||_F^2 >= sum_k || M_k ||_F^2,
because || sum M_k ||_F^2 = sum_{k,k'} tr(M_k M_{k'}), all terms are
nonnegative, and the diagonal terms k = k' are exactly || M_k ||_F^2.
Applying this with M_z = P_1 A_z P_1 (each PSD), and using the
definitions of B and of (+):
sum_{z >= 2} || P_1 A_z P_1 ||_F^2
<= || P_1 (sum_{z >= 2} A_z) P_1 ||_F^2
= || P_1 B P_1 ||_F^2
<= tr( A_1 B )
= sum_{z >= 2} tr( A_1 A_z ).
Group 2: A_1 with s != 1 (so s >= 2). The projections P_2, ..., P_L
sum to Q, so by the same inequality:
sum_{s >= 2} || P_s A_1 P_s ||_F^2
<= || (sum_{s >= 2} P_s) A_1 (sum_{s >= 2} P_s) ||_F^2
= || Q A_1 Q ||_F^2
<= tr( A_1 B ) (by (+))
= sum_{z >= 2} tr( A_1 A_z ).
So Group 1 + Group 2:
sum_{z != s, (s,z) in {(1, z >= 2) or (s >= 2, 1)}} || P_s A_z P_s ||_F^2
<= 2 tr( A_1 B ).
Group 3: s, z >= 2 with s != z.
sum_{s, z >= 2, s != z} || P_s A_z P_s ||_F^2
= sum_{s, z >= 2, s != z} || P_s (Q A_z Q) P_s ||_F^2 [P_s Q = P_s]
<= C_{L-1} * sum_{z != z' >= 2} tr( (Q A_z Q) (Q A_z' Q) ). [by (*)]
Now we bound tr((Q A_z Q)(Q A_z' Q)) in terms of the uncompressed
overlaps. Write Q = I - P_1 and expand:
(Q A_z Q)(Q A_z' Q) = A_z^{1/2} (A_z^{1/2} Q A_z' Q A_z'^{1/2}) A_z'^{1/2}
Whose trace, by cyclicity and the positive semidefiniteness structure,
is || A_z^{1/2} Q A_z'^{1/2} ||_F^2. Then:
|| A_z^{1/2} Q A_z'^{1/2} ||_F^2
= || A_z^{1/2} A_z'^{1/2} - A_z^{1/2} P_1 A_z'^{1/2} ||_F^2
<= 2 || A_z^{1/2} A_z'^{1/2} ||_F^2 + 2 || A_z^{1/2} P_1 A_z'^{1/2} ||_F^2
= 2 tr( A_z A_z' ) + 2 tr( P_1 A_z P_1 A_z' P_1 ) [cyclicity]
The second term equals 2 tr((P_1 A_z P_1)(P_1 A_z' P_1)) = 2 <P_1 A_z P_1, P_1 A_z' P_1>_F.
Summing over ordered pairs z != z' with z, z' >= 2:
sum_{z != z' >= 2} 2 tr( P_1 A_z P_1 A_z' P_1 )
= 2 sum_{z != z' >= 2} <P_1 A_z P_1, P_1 A_z' P_1>_F
<= 2 || P_1 B P_1 ||_F^2 (each P_1 A_z P_1 is PSD and the sum
over z != z' is a subset of the
full square, taken nonnegatively).
Combine:
sum_{s, z >= 2, s != z} || P_s A_z P_s ||_F^2
<= C_{L-1} * [2 sum_{z != z' >= 2} tr( A_z A_z' )
+ 2 || P_1 B P_1 ||_F^2 ]
<= C_{L-1} * [2 sum_{z != z' >= 2} tr(A_z A_z') + 2 tr(A_1 B)].
4.5 Assembling the bound and choosing C_L.
-------------------------------------------
Total leaked mass in (OS):
LHS <= (Group1 + Group2) + (Group3)
<= 2 tr(A_1 B) + C_{L-1} [2 sum_{z != z' >= 2} tr(A_z A_z') + 2 tr(A_1 B)].
Note that tr(A_1 B) = sum_{z >= 2} tr(A_1 A_z) is exactly the ordered
overlap sum from z = 1 to z' >= 2. So the total "full ordered pair
overlap" is
S_full = 2 tr(A_1 B) + sum_{z != z' >= 2} tr(A_z A_z')
= sum_{z != z'} tr(A_z A_z').
We can then bound:
LHS <= [2 + 2 C_{L-1}] tr(A_1 B) + 2 C_{L-1} sum_{z != z' >= 2} tr(A_z A_z').
Recall S_full = 2 tr(A_1 B) + sum_{z != z' >= 2} tr(A_z A_z'),
so sum_{z != z' >= 2} tr(A_z A_z') = S_full - 2 tr(A_1 B).
Substituting:
LHS <= [2 + 2 C_{L-1}] tr(A_1 B) + 2 C_{L-1} [S_full - 2 tr(A_1 B)]
= [2 + 2 C_{L-1} - 4 C_{L-1}] tr(A_1 B) + 2 C_{L-1} S_full
= [2 - 2 C_{L-1}] tr(A_1 B) + 2 C_{L-1} S_full.
Since C_{L-1} >= 1, the coefficient 2 - 2 C_{L-1} is at most zero.
Therefore
LHS <= 2 C_{L-1} S_full.
Define C_L = 2 C_{L-1} with base case C_1 = 1 (in which case LHS = 0
trivially). Unwinding gives C_L = 2^{L-1}. This proves (OS).
This completes the proof of Lemma 4.1.
4.6 The splitting lemma at a glance.
-------------------------------------
Two observations about Lemma 4.1 worth carrying into Section 5:
(i) The cost *C_L = 2^{L-1}* is exponential in L, not in the dimension.
We will use this lemma with L = 2^a = |Y_i| = 2^{d-1} in Section 5.
Then C_L = 2^{2^{d-1} - 1}, which is enormous but fixed (d is
fixed). What matters is that the cost does NOT depend on the
dimension of A_z, which is exponential in the number of coordinates
already processed.
(ii) The projections P_1, ..., P_L are deterministic functions of the
PSD matrices A_1, ..., A_L. In Section 5, the matrices A_z will
themselves be deterministic functions of the average parameters
m_{<=i} and the remaining inputs x_{>i}. So P_s = P_s(m_{<=i},
x_{>i}), deterministic given those, with no dependence on any
later randomness (in particular, no dependence on future m's or
on the processed variables y_{<=i}).
We will need both properties in Section 5.
That completes the orthogonal splitting lemma.
================================================================================
SECTION 5. INGREDIENT THREE: FOURIER SMOOTHING
================================================================================
Section 5 proves Theorem 5.1, the Fourier smoothing theorem. It is the
longest technical ingredient. The statement: any PSD-valued function
F on a product space X_1 x ... x X_t, when averaged through a chain of
"weak local averages" that satisfy Lemma 3.1, admits a very special
representation as a sum of squares H_q^T H_q indexed by Fourier
characters q on the product Y_1 x ... x Y_t. Each branch q is
"concentrated near q" in the Fourier sense: its coefficients at
characters p far from q are exponentially damped (in the weighted
sense of the potential below).
The proof processes coordinates one at a time. At each step we add
one more average, realize it as a fresh direct sum of matrices, and use
the orthogonal splitting lemma (Section 4) to sort the new frequency
content into branches. Lemma 3.1 controls the growth of the total
mass. After t steps, the accumulated mass is bounded by 2^t B^2.
5.1 Statement of the theorem.
------------------------------
Theorem 5.1 (Fourier smoothing of matrix squares).
Let t, r >= 1 be integers. For each i in {1, ..., t}, let X_i and M_i
be nonempty finite sets (uniform probability), and let Y_i be a copy
of (F_2)^a, where a >= 1 and L = 2^a. For m in M_i and y in Y_i, let
pi_{i, y}^m be a probability distribution on X_i. Suppose that for
some theta >= 0 the distributions satisfy the marginal law
E_{m in M_i} pi_{i,y}^m(x) = 1/|X_i| (for all x in X_i,
y in Y_i) (5:M)
and the variance bound
E_{m in M_i} ( sum_x pi_{i,y}^m(x) g(x) - E_x g(x) )^2
<= theta * E_x g(x)^2 (for every
real g on X_i,
every y). (5:V)
Let F : prod_{i=1}^t X_i -> S^r_+ be PSD-valued with tr F(x) <= B for
every x in prod X_i. Let Lambda be a second copy of (F_2)^a: the
character group of Y_i. Fix lambda > 1 with
L * lambda^2 * C_L * theta <= 1, (5:lam)
where C_L is the constant of Lemma 4.1 (Section 4).
For m = (m_1, ..., m_t) in prod M_i, define the product average
F_bar_m(y) = sum_{x in prod X_i}
( prod_{i=1}^t pi_{i, y_i}^{m_i}(x_i) ) F(x),
y = (y_1, ..., y_t) in prod Y_i.
Then there exists a finite integer R (depending on the data) and a
family of rectangular matrix-valued functions
H_q^m : prod_{i=1}^t Y_i -> R^{R x r},
indexed by m in prod M_i and q in Lambda^t,
such that
(i) F_bar_m(y) = sum_{q in Lambda^t} H_q^m(y)^T H_q^m(y)
for every y in prod Y_i and every m.
(ii) For each m, q, form the horizontal concatenation U_q^m and
its Gram matrix C_q^m:
U_q^m = [ lambda^{dist(q,p)/2} hat{H}_{q,p}^m :
p in Lambda^t ] (r L^t columns),
C_q^m = U_q^m (U_q^m)^T (R x R PSD),
where hat{H}_{q,p}^m is the Fourier coefficient of H_q^m at
p (Fourier in all of Y = prod Y_i). Then
E_m [ sum_{q in Lambda^t} || C_q^m ||_F^2 ]
<= 2^t B^2. (5:pot)
(iii) Consequently, there exists at least one m in prod M_i for
which
sum_{q, p in Lambda^t}
lambda^{dist(q,p)} || hat{H}_{q,p}^m ||_F^2
<= L^t * sqrt(r) * B * 2^{t/2}. (5:mass)
Remark on constants. With our choices d = 100 and L = 2^{d-1} =
2^{99}, we have C_L = 2^{L-1} = 2^{2^{99}-1}, which is doubly
exponential in d but entirely fixed. Condition (5:lam) then forces
theta < L^{-1} lambda^{-2} C_L^{-1}, a tiny but explicit number.
Lemma 3.1 provides theta_d(k) -> 0, so a suitable k is possible.
Remark on the shape of H_q^m. Each branch q is a "center", and each
H_q^m is a matrix-valued function on the whole Y domain. The content
of the theorem is not just that F_bar has a sum-of-squares
representation --- which is trivial, for instance by taking square
roots --- but that the branches are Fourier-concentrated near their
centers: the weighted quantity in (5:mass) penalizes coefficients that
are far from q, and the total weighted mass does not blow up. This
is what powers the parity contradiction in Section 7.
The rest of this section proves Theorem 5.1.
5.2 Partial averages and the potential.
----------------------------------------
For convenience, abbreviate
m_{<=i} = (m_1, ..., m_i),
m_{>i} = (m_{i+1}, ..., m_t),
and similarly for x, y.
At stage i we will construct matrix-valued functions
H_q^{(i)} = H_q^{(i)}( y_{<=i} ; m_{<=i}, x_{>i} ),
q in Lambda^i,
with a common number R_i of rows and r columns, such that
sum_{q in Lambda^i} (H_q^{(i)})^T H_q^{(i)}
= sum_{x_{<=i}}
( prod_{j=1}^i pi_{j, y_j}^{m_j}(x_j) )
F( x_{<=i}, x_{>i} ). (5:part)
This is the "i-step partial square representation". At i = 0 the
right side is F(x_1, ..., x_t) and we take
R_0 = r, H_\varnothing^{(0) } = F^{1/2}
(the square root of the r x r PSD matrix F). Then
C_\varnothing^{(0)} = F, and the constant weight lambda^0 = 1 is
trivial. We have
sum_p || hat{F}_p ||_F^2 = E_x [ ||F(x)||_F^2 ]
<= E_x [ (tr F(x))^2 ] <= B^2,
so at i = 0:
Phi_0 := sum_{q in Lambda^0} || C_q^{(0)} ||_F^2 = ||F||_F^2 mass
<= B^2. (5:Phi0)
For each i, define the weighted Gram matrix at stage i as
U_q^{(i)} = [ lambda^{dist(q,p)/2} hat{H}_{q,p}^{(i)} : p in Lambda^i ],
C_q^{(i)} = U_q^{(i)} (U_q^{(i)})^T, (R_i x R_i),
where hat{H}_{q,p}^{(i)} is the Fourier coefficient of H_q^{(i)} in
the variable y_{<=i} only (at each fixed m_{<=i}, x_{>i}). Note that
dist(q, p) in this definition refers to block distance in the FIRST i
coordinates (both q, p in Lambda^i). Define the potential
Phi_i = E_{m_{<=i}, x_{>i}}
[ sum_{q in Lambda^i} || C_q^{(i)}(m_{<=i}, x_{>i}) ||_F^2 ].
Our goal is to prove Phi_{i+1} <= 2 Phi_i for all i, so that
Phi_t <= 2^t B^2.
Note that Phi_0 already equals ||F||_F^2 mass by the definition above,
so (5:Phi0) is the base case.
5.3 The one-step analysis.
---------------------------
Assume we have built (H_q^{(i)}) for i < t. We construct
(H_q^{(i+1)}) for q in Lambda^{i+1}, in three moves:
step A. Realize the new average as a "direct sum" stack.
step B. Bound the pairwise Fourier overlap of the stack's
Gram matrices.
step C. Split the stack into branches using Lemma 4.1.
Throughout fix data: m_{<=i}, x_{>i+1}, and a branch center q in
Lambda^i. We will show:
E_{m_{i+1}, x_{i+1}}
[ sum_{s in Lambda} || C_{(q,s)}^{(i+1)} ||_F^2 ]
<= 2 * E_{x_{i+1}} [ || C_q^{(i)} ||_F^2 ].
Averaging over m_{<=i}, x_{>i+1} and summing over q then gives
Phi_{i+1} <= 2 Phi_i.
Actually, to be precise, at stage i+1 we should have m_{<=i+1} and
x_{>i+1} as the outer averaging data (instead of m_{<=i} and x_{>i}).
The equality trace will be: for each fixed (m_{<=i}, x_{>i+1}) and
each q in Lambda^i,
E_{m_{i+1}} E_{x_{i+1}}
[ sum_{s in Lambda} || C_{(q,s)}^{(i+1)}(m_{<=i+1}, x_{>i+1}) ||_F^2 ]
<= 2 E_{x_{i+1}} [ || C_q^{(i)}(m_{<=i}, x_{>i+1}, x_{i+1}) ||_F^2 ].
Note that the right side involves x_{i+1} in an expectation (averaging
over the input in the new coordinate), while the left side does not
(it is a function of m_{<=i+1} and x_{>i+1}).
We now carry out the three steps.
Step A. Realizing one more average by a direct sum.
Fix m_{<=i}, q, and x_{>i+1}. Abbreviate the new coordinate by
writing X = X_{i+1}, M = M_{i+1}, Y = Y_{i+1}, and reserve x for
x_{i+1}, m for m_{i+1}, y for y_{i+1}. Let U(x) denote the matrix
U(x) = U_q^{(i)} ( x ; m_{<=i}, x_{>i+1}, x ). (R_i x rL^i).
This is the "old" concatenated Fourier stack, viewed as a function of
the new coordinate x. The fixed data m_{<=i} and x_{>i+1} together
determine U(.) as a function of x, before the new m is chosen.
Put
Z(x) = U(x)^T U(x) (rL^i x rL^i PSD).
Note Z(x) is PSD (Gram matrix of U(x)) and satisfies
|| Z(x) ||_F = || C_q^{(i)}(x) ||_F (for all x).
For fixed m, construct a matrix-valued function with a larger row
space:
H' : ( prod_{j<=i} Y_j ) x Y -> R^{R' x rL^i}, R' = L |X| R_i,
where for each row-block indexed by (y', x) in Y x X:
H'(y_{<=i}, y)_{(y', x)}
= 1{ y' = y } * sqrt( pi_{y}^m(x) )
* H_q^{(i)}( y_{<=i} ; m_{<=i}, x_{>i+1}, x ). (5:stack)
Then
H'^T H'
= sum_{(y', x)} pi_{y'}^m(x) H^{(i)T} H^{(i)} (that y-block
with y = y')
= sum_{x in X} pi_y^m(x) H_q^{(i)}(...; x)^T H_q^{(i)}(...; x).
This realizes the (i+1)-step partial average for the branch q, in the
sense that summing H'^T H' over q recovers the updated partial-square
relation (5:part) with the (i+1)-coordinates filled in.
Step B. Fourier overlap of the stack.
For z in Lambda, let hat{H}'_{p, z} denote the Fourier coefficient of
H' at the character (p, z) in Lambda^i x Lambda = Lambda^{i+1}, i.e.,
p is the frequency in y_{<=i}, z is the frequency in y. Define
V_z = [ lambda^{dist(q,p)/2} hat{H}'_{p, z} : p in Lambda^i ]
(row-concatenation, R_i rows, r L^i columns).
A_z = V_z V_z^T (R_i x R_i PSD).
Then A_z = (we'll suppress m, m_{<=i}, q, x_{>i+1} in the notation).
Direct calculation gives: for any z, z' in Lambda,
(V_z) below --- the (y', x) row block of V_z is
= L^{-1} chi_z(y') sqrt(pi_{y'}^m(x)) U(x).
(Check: hat{H}'_{(p, z)} averages over y_{<=i} and y. Under the y-average,
the indicator 1{y'=y} converts to L^{-1} chi_z(y') as the coefficient.)
Therefore:
V_z^T V_z'
= sum_{y', x}
[ L^{-1} chi_z(y') sqrt(pi_{y'}^m(x)) U(x) ]^T
[ L^{-1} chi_{z'}(y') sqrt(pi_{y'}^m(x)) U(x) ]
= L^{-2} sum_{y' in Y} chi_z(y') chi_{z'}(y')
sum_{x in X} pi_{y'}^m(x) U(x)^T U(x)
= L^{-2} sum_{y' in Y} chi_z(y') chi_{z'}(y')
T_{i+1, y'}( Z )(m)
= L^{-2} sum_{y' in Y} chi_z(y') chi_{z'}(y')
( T_{i+1, y'}^{m} Z ), (5:overlap)
where T^m_{i+1, y'} Z = sum_x pi_{y'}^m(x) Z(x) is the new-coordinate
application of the i+1 channel. (Renaming y' to y: matches the
statement in 5.1's proof sketch.)
In particular,
tr( A_z A_{z'} ) = || V_z^T V_{z'} ||_F^2. (5:trAz)
Step B': the two overlap estimates. We need to bound E_m of the above
in two cases.
Case z = z'. Then chi_z(y') chi_{z'}(y') = 1 for all y', so (5:overlap)
reduces to
V_z^T V_z = L^{-2} sum_{y in Y} T_y Z(m) = L^{-1} * E_y[ T_y Z(m) ].
The squared Frobenius norm, by Jensen's inequality (convexity of ||.||^2
under averaging over L points):
|| V_z^T V_z ||_F^2 <= L^{-3} sum_{y in Y} || T_y Z(m) ||_F^2.
Taking expectations over m and using the marginal law (5:M):
E_m || T_y Z(m) ||_F^2
= E_m || (T_y Z - mu) + mu ||_F^2 where mu = E_x Z(x)
= E_m || T_y Z - mu ||_F^2 + || mu ||_F^2
(cross term vanishes because E_m T_y Z = mu, by (5:M))
<= theta E_x ||Z - mu||_F^2 + E_x ||Z||_F^2
(by (5:V), (5:M), and ||mu||_F^2 <= E_x ||Z||_F^2)
<= (1 + theta) E_x ||Z||_F^2
(since E_x ||Z - mu||_F^2 <= E_x ||Z||_F^2).
So:
E_m || V_z^T V_z ||_F^2 <= L^{-3} * L * (1 + theta) E_x ||Z||_F^2
= L^{-2} (1 + theta) E_x ||Z||_F^2.
We keep the exact factor (1+theta); the eventual doubling estimate
will use it directly. Record:
E_m tr(A_z A_z) = E_m || V_z^T V_z ||_F^2
<= L^{-2} (1 + theta) E_x || Z ||_F^2. (5:zz)
Case z != z'. Then chi_z chi_{z'} is a nonconstant character of Y,
with mean E_y [chi_z(y) chi_{z'}(y)] = 0. Hence
sum_{y in Y} chi_z(y) chi_{z'}(y) mu = 0, where mu = E_x Z(x).
We may therefore subtract mu from each T_y Z term in (5:overlap)
without changing the sum:
V_z^T V_{z'} = L^{-2} sum_{y in Y} chi_z(y) chi_{z'}(y)
( T_y Z(m) - mu ).
Bounding || ||_F^2 by (sum of || . ||_F)^2, then Cauchy-Schwarz over
L terms:
|| V_z^T V_{z'} ||_F^2
<= L^{-4} ( sum_{y in Y} || T_y Z(m) - mu ||_F )^2
<= L^{-3} sum_{y in Y} || T_y Z(m) - mu ||_F^2.
Taking E_m:
E_m || V_z^T V_{z'} ||_F^2
<= L^{-3} sum_{y in Y} E_m || T_y Z(m) - mu ||_F^2
<= L^{-3} * L * theta * E_x || Z - mu ||_F^2 (by (5:V))
= L^{-2} theta E_x || Z - mu ||_F^2
<= L^{-2} theta E_x || Z ||_F^2.
So:
E_m tr(A_z A_{z'}) <= L^{-2} theta E_x || Z ||_F^2 (z != z'). (5:znotz)
Step C. Splitting the stack.
Let P_1, ..., P_L be the orthogonal projections on the row space of
H' produced by Lemma 4.1 applied to the L PSD matrices
A_z = V_z V_z^T (z in Lambda). Set
H_{(q, s)}^{(i+1)} = P_s H' (for s in Lambda),
and note that each P_s may depend on (m_{<=i}, m, x_{>i+1}, x; but
crucially NOT on y_{<=i} or y, nor on any future randomness). This
is the key property we will use: since P_s does not depend on y, it
commutes with taking Fourier coefficients in y.
The sum-of-squares property of H':
sum_{s in Lambda} (H_{(q,s)}^{(i+1)})^T H_{(q,s)}^{(i+1)}
= H'^T (sum_s P_s) H'
= H'^T H'
= sum_x pi_y^m(x) H_q^{(i)}(...; x)^T H_q^{(i)}(...; x).
So each H'^T H' is exactly the new partial average for branch q,
regardless of how we split.
Now compute the new Gram matrices. Let
C_{(q,s)}^{(i+1)} = [ lambda^{dist((q,s), (p, z))/2}
hat{H}_{(q,s),(p,z)}^{(i+1)} ]_p
* [...]^T,
i.e. the Gram matrix of H_{(q,s)}^{(i+1)} with the (i+1)-coordinate
block weights. Since dist((q,s), (p, z)) = dist(q, p) + 1{s != z}
(block distance is additive across coordinates, and the two-block
contribution is 1{s != z}), we have
(H_{(q,s)}^{(i+1)}) has Fourier coefficient at (p, z) = P_s hat{H}'_{p, z},
so
C_{(q,s)}^{(i+1)}
= sum_{z in Lambda} lambda^{1{s != z}} P_s A_z P_s.
(Each z-summand is P_s A_z P_s with the extra weight lambda if z != s.)
Bounding: For any sum of L matrices, we have || M_1 + ... + M_L ||_F^2
<= L (||M_1||_F^2 + ... + ||M_L||_F^2) [Cauchy-Schwarz on L terms].
Applying with M_z = lambda^{1{s != z}} P_s A_z P_s:
|| C_{(q,s)}^{(i+1)} ||_F^2
<= L * sum_{z in Lambda} lambda^{2 {s != z}} || P_s A_z P_s ||_F^2
= L * [ || P_s A_s P_s ||_F^2
+ lambda^2 sum_{z != s} || P_s A_z P_s ||_F^2 ].
Now use || P_s A_s P_s ||_F <= || A_s ||_F (contraction under
projection). Sum over s:
sum_{s in Lambda} || C_{(q,s)}^{(i+1)} ||_F^2
<= L * [ sum_s || A_s ||_F^2
+ lambda^2 sum_{s != z} || P_s A_z P_s ||_F^2 ]
<= L * [ sum_z || A_z ||_F^2
+ lambda^2 C_L sum_{z != z'} tr( A_z A_{z'} ) ]. (5:onestep)
The last line uses Lemma 4.1 (Lemma 4.1's (OS)) applied to the L
matrices A_z.
Taking expectations over m in (5:onestep):
E_m [ sum_s || C_{(q,s)}^{(i+1)} ||_F^2 ]
<= L * [ sum_z E_m || A_z ||_F^2
+ lambda^2 C_L sum_{z != z'} E_m tr(A_z A_{z'}) ].
Now substitute the overlap estimates (5:zz) and (5:znotz). The
A_z's are identically distributed over z (they only depend on the
common character z, and the estimates (5:zz), (5:znotz) are
independent of z apart from the z vs z' distinction), so:
sum_{z in Lambda} E_m || A_z ||_F^2
= L * E_m || A_1 ||_F^2
<= L * L^{-2} (1 + theta) E_x ||Z||_F^2 [by (5:zz)]
= ((1 + theta) / L) * E_x ||Z||_F^2.
sum_{z != z'} E_m tr( A_z A_{z'} )
<= L(L - 1) * L^{-2} theta * E_x ||Z||_F^2 [by (5:znotz)]
= (theta (L - 1) / L) * E_x ||Z||_F^2.
Substituting into (5:onestep):
E_m [ sum_{s in Lambda} || C_{(q,s)}^{(i+1)} ||_F^2 ]
<= L * [ ((1 + theta)/L) E_x ||Z||_F^2
+ lambda^2 C_L * (theta (L - 1)/L) E_x ||Z||_F^2 ]
= [1 + theta + lambda^2 C_L theta (L - 1)] * E_x ||Z||_F^2.
We now use the standing condition (5:lam), L lambda^2 C_L theta <= 1.
It implies:
theta <= 1 / (L lambda^2 C_L) <= 1/L,
lambda^2 C_L theta (L - 1) <= (L - 1)/L.
Therefore:
1 + theta + lambda^2 C_L theta (L - 1)
<= 1 + 1/L + (L - 1)/L
= 1 + 1 = 2.
Combining, we have proven:
E_m [ sum_{s in Lambda} || C_{(q,s)}^{(i+1)} ||_F^2 ]
<= 2 E_x || Z(x) ||_F^2
= 2 E_x || C_q^{(i)}( x ; m_{<=i}, x_{>i+1} , x ) ||_F^2,
where the last step uses Z(x) = U(x)^T U(x) = C_q^{(i)}(x).
The right side is exactly 2 * E_{x_{i+1}} || C_q^{(i)} ||_F^2 for the
fitted (m_{<=i}, x_{>i+1}). Averaging over m_{<=i} and x_{>i+1} and
summing over q in Lambda^i proves:
Phi_{i+1} <= 2 Phi_i.
Iterating from Phi_0 <= B^2 (see (5:Phi0)) gives Phi_t <= 2^t B^2.
This is (5:pot).
5.4 From potential to weighted Fourier mass.
--------------------------------------------
Choose m* in prod M_i such that sum_q || C_q^m* ||_F^2 <= 2^t B^2
(exists by averaging). Fix this m*. For each q, C_q^{(t)} is the
Gram matrix of U_q^{(t)}, which has R_t rows and r L^t columns.
Therefore
rank C_q^{(t)} <= r L^t.
By (Section 1.3(ii)), for a PSD matrix C,
tr C <= sqrt(rank C) * ||C||_F.
Applied to each C_q^{(t)}:
sum_{q} tr( C_q^{(t)} )
<= sum_q sqrt(r L^t) ||C_q^{(t)}||_F
= sqrt(r L^t) sum_q ||C_q^{(t)}||_F.
By Cauchy-Schwarz over the L^t branches:
sum_q ||C_q^{(t)}||_F
<= sqrt(number of branches) * sqrt(sum_q ||C_q^{(t)}||_F^2)
= sqrt(L^t) * sqrt(2^t B^2)
= L^{t/2} * 2^{t/2} * B.
Combining:
sum_q tr( C_q^{(t)} )
<= sqrt(r L^t) * L^{t/2} * 2^{t/2} * B
= L^t * sqrt(r) * 2^{t/2} * B.
And on the other hand,
sum_q tr( C_q^{(t)} )
= sum_{q, p} lambda^{dist(q, p)} || hat{H}_{q, p}^{(t)} ||_F^2
by definition of the weighted Gram matrix. This is exactly (5:mass).
So the theorem is proven.
5.5 Conditioning remark.
------------------------
The construction uses (5:M) and (5:V) at every stage. When we apply
the construction at coordinate i+1, the "fixed data" are
(m_{<=i}, x_{>i+1}, m_{i+1}, x_{i+1}). We have been careful that
the projections P_s produced by Lemma 4.1 depend on (m_{<=i}, x_{>i+1},
m_{i+1}) but not on any y-coordinate, since the A_z's are Fourier-
Gram matrices (integrated over the y's) and P_s is determined by
the A_z's.
Also, importantly, at each step the residual randomness in the
averaging over x_{i+1} is uniform (unaffected by conditioning on
m_{<=i+1}), and the residual randomness in m_{i+1} is uniform on M_{i+1}
(unaffected by conditioning on x's). So the marginal (5:M) and variance
(5:V) bounds apply conditionally at each step and then uncondition
without any change in the constant theta. This justifies the
two-stage application of the averaging lemma that we implicitly use in
step B' above.
One further technical point: R_0 = r, and at each step R_{i+1} =
L * |X_{i+1}| * R_i, so R_t = r * prod_i (L |X_i|) is a huge but
finite integer. All the matrix constructions above are finite
dimensional.
That completes the proof of Theorem 5.1.
================================================================================
SECTION 6. INGREDIENT FOUR: AN EXPANDING PARITY SYSTEM
================================================================================
This section constructs the object that creates the contradiction. We
build a bipartite d-regular expander graph H, attach parity constraints
to its vertices with an odd total parity, and use the resulting
"disagreement" function f_eps together with a linear functional D that
separates f_eps from low-degree sums of squares. Section 7 will show
that a small PSD factorization of A_n(rho) forces f_eps into a low-
degree sum of squares, contradicting this section's separation.
6.1 The expanding bipartite d-regular multigraph.
--------------------------------------------------
Lemma 6.1 (Expanding multigraph).
For every sufficiently large even integer t, there exists a bipartite
d-regular multigraph H on the vertex set [t] = {1, 2, ..., t} such that
|delta_H(W)| >= beta * d * min( |W|, t - |W| ) for every
W subset [t]. (6:exp)
Here d = 100 and beta = 1/100. "Bipartite d-regular multigraph"
means: the vertices split into two sides of size t/2 each; every edge
is between sides; every vertex is incident to exactly d edges (multiple
edges between the same pair of endpoints are allowed and counted with
multiplicity); cuts and degrees count edges with multiplicity.
In particular, H is connected: any nontrivial connected component has
an empty cut, contradicting positivity of the right side of (6:exp).
Proof. Write t = 2l. Split the vertices into two equal-sized sets
L = {1, ..., l} and R = {l+1, ..., 2l}. Choose d independent uniform
perfect matchings (permutations) between L and R; let H be their
union with all multiplicities.
We will show that with positive probability H satisfies (6:exp), by a
union bound over all subsets W.
Fix a subset W of [t] with 1 <= |W| <= l (the bound is symmetric, so we
only need |W| <= t/2). Write
W_L = W cap L, W_R = W cap R, a = |W_L|, b = |W_R|,
w = a + b = |W|.
Since H is a union of d bipartite perfect matchings, every cut edge of
W is either an edge from W_L to R \ W_R, or an edge from R \ W_L to W_R
(because bipirtite edges can only go between L and R, so an edge between
W_L and W_R is internal to W and contributes 0 to the cut). So
|delta_H(W)| = |{e = (u, v) in E(H) : u in W_L, v in R \ W_R}|
+ |{e = (u, v) in E(H) : u in L \ W_L, v in W_R}|.
We only need the first summand for the lower bound.
Consider the d edges incident to a fixed u in W_L. They are distributed
as d uniform elements of R, one per permutation, but the d elements are
*not* independent across u (they are determined by the d permutations).
If |a - b| is large, we get (6:exp) for free. Specifically:
|delta_H(W)| >= d|a - b|.
(Each permutation sends a elements of W_L into R; the a images land in
R = {l+1, ..., 2l}. Among these, some number land in W_R (of size b)
and some in R \ W_R (of size l - b). If we consider the analogous
"backwards" count from W_R's images in L, at least the difference
|a - b| pairwise-disjoint perfect-matching edges per permutation must
cross from W_L or W_R.) This is easiest verified directly: fix one
perfect matching pi; it contributes a cut edges if pi maps W_L to R and
some element of W_L has image outside W_R, i.e., |pi(W_L) \ W_R|. Summing
over d permutations gives |delta_H(W)| >= sum_j |pi_j(W_L) \ W_R|. Each
pi_j is a bijection L -> R, so |pi_j(W_L) \ W_R| >= |pi_j(W_L)| - |W_R|
= a - b if a > b. Similarly considering pi_j^{-1} applied to W_R gives
a - b if b > a. Summing over d gives d|a - b|.)
So if d|a - b| >= beta d w, we are done. Thus we only need to handle
|a - b| < beta w. With beta = 1/100, this forces
.45 w <= a, b <= .55 w.
Now bound the "bad" event |delta_H(W)| < beta d w. Since the first
summand alone is < beta d w, fewer than beta d w of the da images of
W_L (under the d permutations) lie outside W_R. Let "exceptional" mean
image outside W_R. We have fewer than beta d w exceptional images, so
at least da - beta d w images are in W_R. Since a >= .45 w, we have
at most .05 da exceptional images.
Number of choices for the set of exceptional domain-vertex + permutation
pairs, of size at most .05 da, out of the total da pairs:
sum_{j <= .05 da} C(da, j)
<= exp( da * [-.05 log(.05) - .95 log(.95)] )
<= exp(.21 da).
(Small binomial tail bound by entropy: for p = .05, -p log p - (1-p)
log(1-p) <= .199; we take .21 for slack.)
For a *fixed* choice of nonexceptional images (i.e., a specific set of
forced pairs (u, pi_j) -> pi_j(u) in W_R), we bound the probability that
the d permutations v_j all land their chosen values there. Each v_j is
uniform over bijections L -> R, but within a single permutation the
images of distinct u's in W_L are sampled *without* replacement. For
each individual permutation, the conditional probability that da_j of
its a images hit W_R (where da_j = a - j_j is the number of
nonexceptional images for permutation j, summing over j to >= .95 da)
is at most (b / l)^{.95 da} in the worst case (each image is required
to be in W_R, of size b, out of R of size l).
Combining: for a fixed W with |a - b| < beta w,
Pr[ |delta_H(W)| < beta d w ]
<= exp(.21 da) * (b/l)^{.95 da}
<= exp(.21 da) * (.55 w / l)^{.95 da}.
The exponent log of the second factor is .95 da * log(.55 w/l),
which for w <= l means log(.55 w/l) <= log(.55) < 0. So the total
exponent is
.21 da + .95 da * log(.55 w/l)
= da * [ .21 + .95 * log(.55 w/l) ].
For w = l (the worst case): .21 + .95 * log(.55) ≈ .21 + .95 * (-.598)
= .21 - .568 = -.358. So exponent <= -.358 * da. Using da >= .45 dw
>= .45 d w:
Pr[ |delta_H(W)| < beta d w ] <= exp( -.358 * .45 * d * w )
= exp( -16.11 * w ) [d = 100].
Union bound over all size-w subsets W of [t]:
sum_{|W|=w} Pr[ bad ]
<= C(2l, w) * exp(-16.11 w).
Using C(2l, w) <= (2el / w)^w <= (2e)^w (since w/l <= 1... actually
(2el/w)^w = (2e)^w * (l/w)^w which is <= (2e)^w iff l/w <= ... hmm,
if w >= l/2, then l/w <= 2, and (2e l/w)^w <= (4e)^w. For w small,
use (2el/w)^w where w might be much smaller than l; but then the
exp(-16.11w) crushes it. Let's use C(2l, w) <= (2el/w)^w.)
Then:
C(2l, w) * exp(-16.11 w)
<= (2e l/w)^w * exp(-16.11 w)
= exp( w * [ log(2e l/w) - 16.11 ] ).
For w >= 1, log(2e l/w) <= log(2el) <= log(2e) + log l. So the
bracket is at most log(2e) + log l - 16.11. For l >= 1, log l could
be large (l = t/2 grows). Hmm, so my union bound isn't tight enough
if we only use the crude (2el/w)^w. Let me redo.
For a fixed w <= l, C(2l, w) <= (2el/w)^w. Union bound for size-w:
C(2l, w) * exp(-16.11 w) <= (2el/w)^w * exp(-16.11 w)
At w = l (largest w):
(2e)^w * exp(-16.11 w) = exp(w (log(2e) - 16.11)) = exp(w (1.84 - 16.11)) = exp(-14.27 w).
At w = l/2:
(4e)^w * exp(-16.11 w) = exp(w(2.39 - 16.11)) = exp(-13.72 w).
At smaller w, log(2el/w) grows but bounded by log(2el) = log(2e) + log l.
For l = t/2 growing, this could be large. But then w would be small
relative to l, and we can use a better exponential bound.
Actually, for w <= l/2, C(2l, w) <= (2e l/w)^w is quite loose but we
need to be careful. The paper uses w/l <= 1 so "log(2e l/w)^w" <=
something. Hmm.
Actually the paper says: "C(2l, w) <= (2el/w)^w". Then "log(2e w/l)" ... hmm wait the paper has
exp( w [ log(2e) + 45(.21 + .95 log(.55)) + 41.75 log(w/l) ] )
This has "-16.11 w" type structure and includes log(w/l) terms from the
entropy of C(2l, w). Let me look: 41.75 log(w/l) with w/l <= 1 gives
41.75 w log(w/l), which is negative. So for the paper's bound:
w [ log(2e) + 45(.21 + .95 log(.55)) + 41.75 log(w/l) ]
We need this to be <= -8w, i.e.,
log(2e) + 45(.21 + .95 log(.55)) + 41.75 log(w/l) <= -8.
log(2e) ≈ 1.84. 45 * (.21 + .95*(-.598)) = 45 * (.21 - .568) = 45 * (-.358) = -16.11.
41.75 log(w/l) <= 0 (since w/l <= 1).
So total <= 1.84 - 16.11 + 0 = -14.27 < -8. Good.
Wait but I have "45" as the coefficient of "(.21 + .95 log(.55))" while my earlier bound has "da >= .45 dw = .45 * 100 * w = 45w". So da = 45w. So the exponent is 45w * [.21 + .95 log(.55 w/l)] = 45w * [.21 + .95 log .55 + .95 log(w/l)] = 45w * [.21 - .568 + .95 log(w/l)] = 45w * [-.358 + .95 log(w/l)]. And then log C(2l,w) <= log((2el/w)^w) = w log(2e l/w) = w [log(2e) + log(l/w)] = w [1.84 + log(l/w)] = w [1.84 - log(w/l)].
So total exponent: w * [1.84 - log(w/l) - .358*45 + .95*45*log(w/l)]
= w * [1.84 - 16.11 + log(w/l)*(-1 + 42.75)]
= w * [-14.27 + 41.75 * log(w/l)].
Since w/l <= 1, log(w/l) <= 0, so total <= -14.27w. Good.
For very small w (like w=1), log(w/l) = -log l. That's very negative. So even better.
The paper says <= -8w for all w. Good.
So:
sum_{|W|=w} Pr[bad] <= e^{-8w}.
Sum over w >= 1:
Pr[ H bad for some W ] <= sum_{w=1}^{l} e^{-8w} < sum_{w>=1} e^{-8w}
= e^{-8} / (1 - e^{-8}) < 1.
So some choice of the d permutations produces a good H. This completes
Lemma 6.1.
6.2 The parity construction.
-----------------------------
Fix a graph H as in Lemma 6.1. Order the d incidences at every vertex
i = 1, ..., t. Choose bits b_1, ..., b_t in {0, 1} with
sum_{i=1}^t b_i = 1 (mod 2).
(One simple choice: b_1 = 1 and b_i = 0 for all i > 1.)
For each vertex i, define the "block"
Y_i = { y_i in {0, 1}^d : sum_{j=1}^d y_{i,j} = b_i (mod 2) }.
Let Y = Y_1 x ... x Y_t. Each Y_i is an affine copy of (F_2)^{d-1}
(choose d-1 of the bits freely; the d-th is determined). So
|Y_i| = L = 2^{d-1}, and Y's uniform law is the product of the |Y_i|'s
uniforms. The character group of each Y_i is a copy of Lambda =
{0, 1}^{d-1} acting on the first d-1 coordinates.
For p = (p_1, ..., p_t) in Lambda^t, define the block character
chi_p(y) = (-1)^{ sum_{i=1}^t sum_{j=1}^{d-1} p_{i,j} y_{i,j} },
y in Y.
Its block degree is |p|_blk = |{ i : p_i != 0 }|.
A function has block degree at most D if its Fourier coefficients
vanish at every p with |p|_blk > D.
For an edge e = uv in E(H), denote its terminal bits by y_{u,e} and
y_{v,e} (the bits at the incidences of e at its two ends). For
0 < eps < 1, define
f_eps(y) = sum_{e = uv in E(H)} 1{ y_{u,e} != y_{v,e} } - eps,
y in Y.
Now: what is the parity of the sum of disagreement indicators?
sum_{e = uv} ( y_{u,e} + y_{v,e} ) (mod 2)
Each vertex i has d incidences, one per edge incident to i. Summing
over all edges counts each incidence exactly once (once at each of its
two endpoints... no wait, each edge e has two endpoints, u and v, and
contributes y_{u,e} + y_{v,e}, i.e. one contribution from u's side and
one from v's side). But summing over INCIDENCES at all vertices: each
edge has an incidence at u and an incidence at v, both counted. So:
sum_{e} (y_{u,e} + y_{v,e})
= sum_{all incidences (i,j)} y_{i,j}
= sum_{i=1}^t sum_{j=1}^d y_{i,j}.
But each Y_i has sum_j y_{i,j} = b_i mod 2, so the total sum mod 2 is
sum_{e} (y_{u,e} + y_{v,e}) = sum_{i} b_i = 1 (mod 2).
Mod 2, the sum of "y_u,e + y_v,e" equals the sum of "1{y_u,e != y_v,e}"
(since y_u + y_v is congruent to 1{y_u != y_v} mod 2 for bits). So
sum_{e} 1{ y_{u,e} != y_{v,e} } = 1 (mod 2).
Therefore: the sum of disagreement indicators is an ODD positive
integer, hence at least 1. So
f_eps(y) >= 1 - eps > 0 for every y in Y.
This is the nonnegativity we need. We will construct a functional
that separates f_eps from squares of low-block-degree functions.
6.3 The incidence map and its properties.
-----------------------------------------
We need a bit of linear-algebraic notation over the 2-element field
F_2. For a character index p in Lambda^t (with p_i = (p_{i,1}, ...,
p_{i,d-1}) in {0,1}^{d-1}), define the "incidence map"
E(p) = { e = uv in E(H) : the total number of j in
{i's incidences with p_{i,j}=1 or v's incidences with
p_{v,j}=1} counting all incidences of the edge e
with p_{i,j}=1 is ODD }.
More precisely: each edge e = uv has two incidences, one at u (at some
index j_u(e)) and one at v (at some index j_v(e)). A character index
p "selects" the incidences (i, j) with p_{i,j} = 1. We say e is in
E(p) if an odd number of e's two incidences are selected by p.
Equivalently: E(p) is the set of edges of H whose two chosen-incidence
counts have opposite parities under p.
Properties:
(1) E(p + p') = E(p) triangle E(p') (symmetric difference). This
is because the "odd number of incidences" condition is additive
mod 2 across p and p'.
(2) If p = 0 (all p_i = 0), then E(0) = empty set.
(3) Every E(p) is a subset of E(H).
We will use the following observation: the cut-set delta_H(W) is the
set of edges with exactly one endpoint in W. If E(p) happens to be a
cut delta_H(W) for some W subset [t], then its four "faces" are sets
in F_2^{E(H)}. The cut sets in bipartite graphs form a vector space
(the "cut space"), and a complement delta_H(W^c) = delta_H(W) for every
W (as sets!). So "E(p) is a cut" is well-defined.
6.4 The expansion-side lemma.
------------------------------
We will need the next fact: whenever E(p) is a cut of H and p has small
block degree, expansion forces a unique "small side" of this cut.
Unique-small-side lemma. Suppose t is sufficiently large and H
satisfies (6:exp) of Lemma 6.1. Let D = floor(tau t) where tau = 1/1000.
Let p in Lambda^t satisfy |p|_blk <= 2D and suppose E(p) = delta_H(S)
for some S subset [t]. Then one of the two sides of this cut
(S or its complement) has size at most t/5, and this side is
unique.
Proof. Since |p|_blk <= 2D, the character p "touches" at most 2D
blocks. Each block i has at most d - 1 <= d - 1 incidence bits
"active" (nonzero) inside p_i. So the total number of incidences
where p_{i,j} = 1 is at most 2D * (d-1). Each selected incidence
belongs to an edge e, so
|E(p)| <= |{incidences with p_i != 0}| <= 2D * d. (small cut)
Now, suppose E(p) = delta_H(S) for some S subset [t]. If |S| >= t/5
and |S^c| >= t/5, then by (6:exp):
|delta_H(S)| >= beta * d * min( |S|, |S^c| ) >= beta * d * t/5.
But |delta_H(S)| = |E(p)| <= 2D * d = 2d * floor(tau t) <= 2d tau t
= 2d * t / 1000 = d t / 500.
Combined:
d t / 500 >= |delta_H(S)| >= beta d t / 5 = d t / 500.
Wait, that's an equality, not a contradiction. Let me redo.
beta * d * t/5 = (1/100) * d * t/5 = d t / 500.
And 2d * tau t = 2d * t/1000 = 2d t / 1000 = d t / 500.
Hmm so both are dt/500. Let me check the constants.
Actually |E(p)| <= 2D * (d-1) <= 2 * tau t * (d-1) ≈ 2 * (t/1000) * d = td/500.
And expansion lower bound: beta d * t/5 = (1/100) d * t/5 = dt / 500.
So |delta_H(S)| is simultaneously <= dt/500 (upper from |E(p)|) and >= dt/500 (lower from expansion). These match. What a heartbreaker!
Let me recheck. The paper's constants:
|E(p)| <= 2Dd. D = tau*t = t/1000. So |E(p)| <= 2 * (t/1000) * d = td/500.
beta * d * t/5 = (1/100) * d * t/5 = td/500.
Ah, they're both dt/500. So the contradiction hinges on STRICT inequality. If |E(p)| < 2Dd STRICTLY (i.e., |E(p)| <= 2Dd - 1 < 2Dd), and expansion gives |E(p)| >= beta d min(|S|, |S^c|), then we need min(|S|, |S^c|) <= 2D/beta.
Ah! Right. The paper says: |S(p)| <= 2D / beta. Let me check:
beta d min(|S|, |S^c|) <= |delta_H(S)| = |E(p)| <= 2Dd.
So min(|S|, |S^c|) <= 2D / beta.
With D = floor(tau t) = floor(t/1000), 2D / beta = 2D * 100 = 200D <= 200tau t = 200t/1000 = t/5.
So min(|S|, |S^c|) <= t/5. Good, that's the bound stated.
So the setup is: given a cut S with small E(p), one side of this cut has size <= t/5. That's the "small side". And this is unique because if BOTH S and S^c have size <= t/5, then |S| + |S^c| = t <= 2t/5, contradiction (for t > 0). So exactly one side is small.
Great. Lemma is correct, just I miscalculated earlier.
So the unique-small-side lemma holds with |S(p)| <= 2D/beta <= t/5, using connectivity + uniqueness from the (6:exp) expansion argument.
Actually wait, the paper says "This side is unique: connectivity implies that two vertex sets with the same cut are equal or complementary." So uniqueness of side (up to complement) is from connectivity of H. And then only one of the two is small. Good.
OK let me write this up. Section 6.4 done.
6.5 The separating functional D.
---------------------------------
Let D = floor(tau t) as in Section 6.4. For each p in Lambda^t:
- Case 1: |p|_blk <= 2D and E(p) = delta_H(S(p)) for a cut with
small side S(p) satisfying |S(p)| <= t/5. Then define
D(chi_p) = (-1)^{ sum_{i in S(p)} b_i }.
- Case 2 (all other p): define D(chi_p) = 0.
Extend linearly to all real functions h on Y:
D( sum_p hat{h}(p) chi_p ) = sum_p hat{h}(p) D(chi_p).
Now the four properties of Proposition 6.2:
(i) D(1) = 1. The trivial character p = 0 has E(0) = empty cut,
small side = empty set, so D(chi_0) = (-1)^0 = 1.
(ii) D(g^2) >= 0 for g : Y -> R of block degree at most D.
Proof: consider the matrix M indexed by pairs (p, p') with
|p|, |p'| <= D (in Lambda^t), M_{p,p'} = D(chi_p * chi_p') =
D(chi_{p+p'}). If g = sum_{|p|<=D} hat{g}(p) chi_p, then
g^2 = sum_{p,p'} hat{g}(p)hat{g}(p') chi_{p+p'}, and
D(g^2) = sum_{p,p'} hat{g}(p)hat{g}(p') M_{p,p'}
= hat{g}^T M hat{g}.
We must show M is PSD.
Structure of M: partition the index set {p : |p|_blk <= D} by
coset of the cut space (the vector subspace of F_2^{E(H)} equal to
all cut sets). Two indices p, p' are in the same coset iff E(p+p')
is a cut. If E(p+p') is a cut, then p+p' has |p+p'|_blk <= 2D
(since each has <= D and block degree is subadditive) and
E(p+p') = delta_H(S(p+p')) with small side of size <= t/5, so
D(chi_{p+p'}) = (-1)^{sum_{i in S(p+p')} b_i} = ±1.
If E(p+p') is not a cut, D(chi_{p+p'}) = 0.
So within a coset block, all entries are ±1; between different
cosets, all entries are 0.
Claim: within a coset block, M is rank-one PSD, i.e.,
M_{p,p'} = sigma_p sigma_{p'} for some sigma_p in {±1}.
Proof: it suffices to show the 3-cycle identity
M_{p1, p2} M_{p2, p3} M_{p3, p1} = 1
for any three p_1, p_2, p_3 in the same coset (the same "cut coset"),
and separately M_{p,p} = 1.
M_{p,p} = D(chi_{2p}) = D(chi_0) = 1 (since p + p = 0).
For p_1, p_2, p_3 in the same coset, each pair p_a + p_b has
E(p_a + p_b) = a cut with small side S_{ab}. We know that
E(p_1 + p_2) + E(p_2 + p_3) + E(p_3 + p_1) = 0 (in F_2, since the
three pairwise sums add to 0 and E is linear). And
delta_H(S_{12}) + delta_H(S_{23}) + delta_H(S_{31}) = delta_H(S_{12} triangle S_{23} triangle S_{31}).
So delta_H(S_{12} symdiff S_{23} symdiff S_{31}) = empty,
which by connectivity of H implies S_{12} symdiff S_{23} symdiff S_{31} = empty or [t].
But |S_{ab}| <= t/5 for each, so |S_{12} symdiff S_{23} symdiff S_{31}| <= 3t/5 < t. So it's the empty set, meaning:
S_{31} = S_{12} symdiff S_{23}.
Now compute the signs: D(chi_{p_a+p_b}) = (-1)^{sum_{i in S_{ab}} b_i},
which is multiplicative in symmetric differences:
(-1)^{sum_{i in A symdiff B} b_i} = (-1)^{sum_{i in A} b_i} * (-1)^{sum_{i in B} b_i}
because "sum over symmetric difference" = "sum over A" + "sum over B" - 2 * sum over A cap B, all mod 2.
So D(chi_{p1+p2}) * D(chi_{p2+p3}) * D(chi_{p3+p1})
= (-1)^{sum_{S_{12}} b_i + sum_{S_{23}} b_i + sum_{S_{31}} b_i}
= (-1)^{sum_{S_{12} symdiff S_{23} symdiff S_{31}} b_i} (by multiplicativity)
= (-1)^{sum_{empty} b_i} = 1.
So the 3-cycle identity holds.
Combined with M_{p,p} = 1, this gives M_{p,p'} = sigma_p sigma_{p'} on each coset block for some signs sigma_p in {±1} (choose p_0 = p and sigma_p = M_{p, p_0}). So M restricted to each coset block is a rank-one PSD matrix (outer product of the sign vector). Sum of rank-one PSD blocks (orthogonally supported across cosets) is PSD.
Therefore D(g^2) >= 0.
(iii) D(f_eps) = -eps.
We need to show D(disagreement indicator) = 0 for each edge e.
The disagreement indicator 1{y_{u,e} != y_{v,e}} = (1 - (-1)^{y_{u,e} + y_{v,e}}) / 2.
So D(1{...}) = (1 - D((-1)^{y_{u,e} + y_{v,e}})) / 2.
We need: D((-1)^{y_{u,e} + y_{v,e}}) = 1.
Now: y_{u,e} at vertex u is the incidence bit at index j_u(e) (the slot for edge e). Similarly v. But only the first d-1 bits of y_i are "free" — the d-th bit is determined by the parity constraint.
Let T subset {u,v} be the vertices where j_u(e) = d (the last,
dependent bit). The parity constraint at vertex i gives:
y_{i,d} = b_i + sum_{j=1}^{d-1} y_{i,j} (mod 2).
So:
- If j_i(e) = d for i in T: replace y_{i,d} with b_i + sum_{j<=d-1} y_{i,j}.
- Otherwise, y_{i,j_i(e)} is already a free bit.
Then (-1)^{y_{u,e} + y_{v,e}} = (-1)^{sum_{i in T} b_i} * chi_p for some p in Lambda^t with |p|_blk <= 2 (only blocks u, v are affected).
Specifically, p has:
- For i = u: if u in T, then p_{u,j} = 1 for all j = 1,...,d-1; if u notin T, then p_{u,j} = 1 iff j = j_u(e) (single bit).
- Simiarly for i = v.
- For other i: p_i = 0.
So |p|_blk <= 2.
Now E(p): p selects the incidences (u, j) and (v, j) with p_{u,j}=1
or p_{v,j}=1.
- If u notin T: p_u has 1 bit at j = j_u(e), which is the incidence of e at u. So the incidences selected at u are exactly the one for e ({u, e}). If u in T: p_u = 1 for all j = 1,...,d-1, which selects ALL d-1 incidences at u except the d-th. But that includes all incidences except possibly the one for e (if j_u(e) = d, then the incidence of e is NOT selected at u).
So: if u in T (so j_u(e) = d), the incidence of e at u is not selected by p. If u notin T, it is selected.
For E(p): edges whose two selected incidences have odd total. e itself: reported above. Actually E(p) is defined by "odd number of selected incidences over the edge's two incidence endpoints".
Case: u in T (=e's incidence at u is the d-th), v notin T (e's incidence at v is free). Then e's u-incidence is NOT selected (u's p is 1 on the d-1 free bits, which do NOT include the d-th slot), and e's v-incidence IS selected (v's p is 1 on j_v(e)). Total selected: 1 (odd). So e in E(p).
Case: u notin T, v in T. Symmetric.
Case: u, v notin T. e's u-incidence IS selected, e's v-incidence IS selected. Total 2 (even). So e NOT in E(p).
Case: u, v in T. e's u-incidence NOT selected, e's v-incidence NOT selected. Total 0 (even). So e NOT in E(p).
Wait but E(p) is defined more generally as all edges e' (not just e) with odd # selected incidences.
For e' = u'v' != e:
- If neither u' nor v' is in {u, v}: p_{u'} = p_{v'} = 0, so 0 selected at both ends (assuming e's incidence at u', v' isn't selected at well). Hmm actually "e's" incidences selected depends on p applied to incidences of e', not e. Let me re-read: E(p) is the set of edges e' such that e' has odd number of its two incidences selected by p. So for e' = u'v' with u', v' neither in {u, v}, p_{u'} = p_{v'} = 0 so no incidences at u' or v' are selected by p (except if u', v' both zero). 0 is even, so e' not in E(p).
- If u' = u (i.e., e' = u-v'), then e' has incidence at u (index j_u(e')) and incidence at v'. If u notin T, p_u has 1 at only j_u(e) (the incidence of e). So e's incidence at u IS selected, e''s incidence at u is selected iff j_u(e') = j_u(e), i.e., e' = e. Otherwise not. And e's incidence at v' = selected iff v' = v (so we have e' = e, which is that case) or v' in T with p_{v'} = 1 on all free bits (not the d-th). If v' = v and v notin T, p_v has 1 at j_v(e) which IS e's incidence at v, so e's incidence at v IS selected. Total 2 (even): e' not in E(p). This should match earlier.
# ^C interrupted by user!