Results on PSD factorizations, averaging, splitting, Fourier smoothing and parity functionals, with their assumptions

The course proves the statements below; each link leads to the statement with its assumptions and its proof. The lessons are self-checked by the writing AI; independent mathematical review is not complete.

• Normalization of PSD factorizations — Lemma 2.3. A nonzero nonnegative matrix with entries at most B and a PSD factorization of size r_0 has a PSD factorization of some size r <= r_0 with tr F_i <= B and tr G_j <= r. No hypothesis.
• Affine certificates — Lemma 3.3. If an affine subspace L of symmetric w x w matrices contains a positive definite matrix and an affine function is nonnegative on the positive semidefinite part of L, it equals <F, Y> + mu on L with F positive semidefinite and mu >= 0. No hypothesis.
• Semidefinite lifts give PSD factorizations — Proposition 3.4. If a convex set with at least two points has a semidefinite lift of size r, every matrix of values of affine functions nonnegative on the set at points of the set has PSD rank at most r + 1. No hypothesis.
• Exponential PSD rank of the shifted matching matrices (OpenAI) — Theorem 4.3. There is c > 0 such that for every 0 < rho < 1 the matrix with entries |M ∩ δ(U)| − 1 + rho, on odd sets U and perfect matchings M of K_n, has PSD rank at least 2^(cn) for all large even n; proved in the sixth lesson. No hypothesis.
• Semidefinite lifts of the perfect matching polytope (OpenAI) — Corollary 4.4. For all large even n, every semidefinite lift of the perfect matching polytope of K_n has size at least 2^(c_0 n); proved in the sixth lesson. No hypothesis.
• Large invariant subspaces — Lemma 4.1. For even k >= 6 and w in {k/2, k/2+1}, every nonzero S_k-invariant space of functions on the w-subsets of [k] orthogonal to the constants has dimension at least k/2. No hypothesis.
• Local averaging — Theorem 5.1. Averages over the restrictions of a cut to a cell, with random terminals and internal matching, have uniform marginal and variance at most theta_d(k) = 2^((d+10)/2) k^(-1/4) (1 + log k)^(1/2) times the variance, in every matrix dimension. No hypothesis.
• Two positive semidefinite matrices — Lemma 1.2. For positive semidefinite A, B and the projection P onto the nonnegative eigenspaces of A - B, tr(AB) >= ||PBP||^2 + ||QAQ||^2 with Q = I - P. No hypothesis.
• Orthogonal splitting — Theorem 2.1. Positive semidefinite A_1, ..., A_L admit mutually orthogonal projections P_s with sum I such that the sum over s != z of ||P_s A_z P_s||^2 is at most 2^(L-1) times the sum of the overlaps tr(A_z A_z'), in every dimension. No hypothesis.
• Translation by a character — Lemma 1.2. Multiplying a function whose Fourier coefficients vanish beyond block distance D from q by the character chi_q gives block degree at most D and keeps its square. No hypothesis.
• Fourier smoothing of matrix squares — Theorem 2.1. A product average of a positive semidefinite matrix function through channels with uniform marginals and variance factor theta is a sum of squares whose Fourier coefficients satisfy a bound weighted by lambda^dist, when L lambda^2 2^(L-1) theta <= 1. No hypothesis.
• Expanding multigraphs — Lemma 1.2. For every even t there is a bipartite 100-regular multigraph on t vertices in which every vertex set W has at least min(|W|, t - |W|) edges leaving it. No hypothesis.
• A functional separating low-degree squares — Proposition 3.1. On an odd parity system on such a multigraph there is a linear functional D with D(1) = 1, nonnegative on squares of block degree at most t/1000, equal to -epsilon on the disagreement count minus epsilon, and bounded by L^t times the sup norm. No hypothesis.
• Realization by odd cuts and matchings — Lemma 2.1. For cells with terminals joined along the parity graph, every odd cut in the support of the product restriction crosses the matching exactly at the disagreeing edges. No hypothesis.
• Uniform smoothing of matching averages (OpenAI) — Theorem 1.1. For a fixed number of cells and K > 0 there is d with ||T_t(I - Pi_d)|| <= N^(-K) for all cell sizes and admissible tables, and T_t Pi_d f is one polynomial of degree at most d in the counts between the cells. No hypothesis.
• The fourth moment — Proposition 3.4. tr((T_t^* T_t)^2) <= e^(2a) (N+1)^b with a = l(l+1) + 1 and b = 2a + l^2, uniformly in the table. No hypothesis.
• Dimensions outside the edge-product span — Lemma 4.2. For N >= 4d^2, every irreducible subrepresentation of the complexified orthogonal complement of the products of at most d edge indicators has dimension at least N^(d/2)/(2^d d!). No hypothesis.
• Containment probabilities — Lemma 5.1. A uniform matching with a given table contains a given set of disjoint edges with probability 2^(sum m_uu) prod (t_uv)_(m_uv) / prod (s_u)_(a_u). No hypothesis.

Reading order

Seven lessons. The first sets up PSD factorizations, semidefinite lifts and the matching matrices and states the main theorem; the second to fifth prove its four ingredients (local averaging, orthogonal splitting, Fourier smoothing, the parity functional), each independently of the others; the sixth proves the theorem and its corollary on lifts; the seventh proves a further smoothing theorem for averages over perfect matchings and can be read after the second. Everything used is proved in the course, apart from the spectral theorem for real symmetric matrices and, in the seventh lesson, the representation theory of the symmetric group from the programme course on finite groups.