MathLabs

Worked solution: Marcus–Spielman–Srivastava proof via interlacing families (2013)

Step 7 of 8: Assembling the pieces: Weaver's KS2KS_2 is a theorem
In plain words

Every piece is now in place: the mixed characteristic polynomial is real-rooted (step 4), an interlacing family selects a concrete random-vector outcome no worse than its average (step 5), and the barrier computation bounds that average root (step 6). The standard r=2r=2 direct-sum lift from the paper then gives two complementary groups, each satisfying the displayed norm bound. This is Weaver's KS2KS_2 theorem.

∃ S1,S2:∥∑i∈Sjvivi∗∥≤(1+2δ)22,j=1,2\exists\, S_1,S_2: \left\|\sum_{i\in S_j} v_iv_i^*\right\| \le \frac{(1+\sqrt{2\delta})^2}{2}, \qquad j=1,2
Detailed analysis

Putting the last three steps together: (1) the mixed characteristic polynomial μ[A1,…,Am](x)\mu[A_1,\ldots,A_m](x) equals the expected characteristic polynomial of the independent random sum and is real-rooted (step 4); (2) interlacing selects an outcome whose largest root is no larger than the average's largest root (step 5); (3) the barrier computation bounds that average root by u∗=(1+2δ)2/2u^*=(1+\sqrt{2\delta})^2/2 (step 6). Applying the paper's r=2r=2 direct-sum lift to these random vectors yields complementary sets S1,S2S_1,S_2 with ∥∑i∈Sjvivi∗∥≤u∗\left\|\sum_{i\in S_j}v_iv_i^*\right\|\le u^* for both jj, proving KS2KS_2.

Knowledge used in this step