Proof of Theorem 2.23 (final)

We proved that the support of any homogeneous c-Rayleigh polynomial is \(M\)-convex (Thm 2.23). Instead of sticking strictly to the proof in the paper, we first introduced a slightly modified concept, \(M^\#\)-convexity, motivated by the independent sets of matroids, which provides a different perspective of the theorem:

Definition ( \(M^\#\)-convexity): A set \(J\subseteq \mathbb{N}_{\geq 0}^n\) is \(M^\#\)-convex if it satisfies the following conditions:

1. \(0 \in J^\#\).
2. If \(\beta \in j^\#\), \(\alpha \subset \beta\), then \(\alpha \in J^\#\).
3. If \(\alpha, \beta \in J^\#\) and \(|\alpha|_1 < |\beta|_1\), then there exists \(i\) such that \(\alpha_i < \beta_i\) and \(\alpha + e_i \in J^\#\).

Note that if we view an \(M\)-convex set as a direct generalization of the bases of matroids, then \(M^\#\)-convex set is a direct generalization of the independent sets.We know that bases are exactly the collection of the "largest" independent sets, and this generalizes perfectly: \(M\)-convex set is exactly the collection of the "largest" elements of an \(M^\#\)-convex set (in the sense of L1-norm).

We then proved that if the support of any c-Rayleigh polynomial (not necessarily homogeneous) satisfies the 1st condition of \(M^\#\)-convex set, then it also satisfies the 2nd and 3rd conditions, making the support \(M^\#\)-convex. We established this through an elegant minimal counterexample argument.

Finally, we concluded the proof of the main theorem by considering the support of \(g(w) := f(w₁+1,...,wₙ+1)\). If f is c-Rayleigh then g is also \(c\)-Rayleigh by definition, meaning \(supp(g)\) is \(M^\#\)-convex by the theorem above. Since \(supp(f)\) is exactly the collection of the "largest" elements of \(supp(g)\), \(supp(f)\) is \(M\)-convex.

By combining this with our results of week 5, we conclude that \(L^d_n\) is closed, which completes the proof that \(\overline{\mathring{L_n^d}} = L_n^d\) (Thm 2.25).