buchholz_evenq_trace_pairbound
ProvedBuchholz even-moment trace pairbound (the combinatorial core of the noncommutative Khintchine inequality). Let be the symmetrized coordinate Rademacher series (rademacherSampledMatrix), where and are independent signs. For every integer , the sign-averaged even trace moment is dominated by the pair-partition count times the larger diagonal-Gram trace:
Here and are diagonal, so their -th-power traces are exactly and likewise for columns; the right-hand side is stated in this Schatten form. The constant is the number of perfect matchings (pair-partitions) of a -element set; combined with it yields Buchholz's optimal factor with constant .
This is the genuinely deep estimate of the moment method: the K-expand bricks (trace_pow_eq_walk, E_sign_monomial) reduce the left side to a sum over matched closed bipartite walks (every coordinate-edge multiplicity even), and this lemma bounds that matched sum by the pair-partition count times the Gram traces. Source: Buchholz, Operator Khintchine inequality in non-commutative probability, Math. Ann. 319 (2001) 1–16, §2–3; CR2009 (arXiv:0805.4471) §6.1 Lemma 6.1.
import Definitions.Def_matrix_completion_gram_schatten open MatrixCompletion open scoped BigOperators
theorem buchholz_evenq_trace_pairbound
(n : Nat) (hn : 1 ≤ n)
{n1 n2 : Nat} (Omega : Finset (Fin n1 × Fin n2)) (p : ℝ) (hp : 0 < p)
(X : RealMatrix n1 n2) :
rademacherExpectation
(fun eps =>
Matrix.trace
((rademacherSampledMatrix Omega eps p X *
(rademacherSampledMatrix Omega eps p X).transpose) ^ n))
≤ ((Nat.factorial (2 * n) : ℝ) / ((2 ^ n : ℝ) * (Nat.factorial n : ℝ))) *
max ((sampledRowGramSchatten Omega p X (2 * n : ℝ)) ^ (2 * n))
((sampledColumnGramSchatten Omega p X (2 * n : ℝ)) ^ (2 * n)) := by sorry