Last time we finished proving the double mark lemma on p. 5 of Paper S3 in the unweighted case. Please open the 7/27 post to recall why we are doing this, and what marks and double marks mean. At this point, we’ve confirmed $$ |{\mathcal M}| = x_1 + x_2 + \ldots + x_{{n \choose l}} = {n \choose l}{l \choose m} e^{-\kappa({\mathcal F})},$$ $$ \textrm{and} \qquad |{\mathcal D}| = x_1^2 + x_2^2 + \ldots + x_{{n \choose l}}^2 < \frac{1}{1 – \frac{1}{2 \gamma}} {n \choose l}{l \choose m}^2 e^{-2\kappa({\mathcal F})}, $$
where:
- \( {X \choose l} = \left\{ Y_1, Y_2, \ldots, Y_{{n \choose l}} \right\} \),
- \( x_i = \left| {\mathcal F} \cap {Y_i \choose m} \right| \) is the number of marks \( (U, Y_i) \) of the \( i\)th \( l\)-set \(Y_i \),
- and \( x_i^2 \) counts double marks \( (U, V, Y_i) \) of \( Y_i \).
Because \( \gamma>0 \) is sufficiently large, we now know \( {\mathcal F} \) is in something close to Situation 1 given in the 7/27 post. It remains to confirm \( |Ext({\mathcal F}, l )| \), the number of \( Y_i \) with \( x_i>0 \), is actually at least \( {n \choose l} ( 1 – 2 \gamma^{-1/3} ) \) to prove the EGT. For Collorary 3.2 on p. 9, we need the same number of \( Y_i \) such that $$ (8) \qquad \qquad \frac{{l \choose m} |{\mathcal F}|}{{n \choose m}} \left( 1- \frac{1}{\sqrt[3]{\gamma}} \right)< x_i < \frac{{l \choose m} |{\mathcal F}|}{{n \choose m}} \left( 1+ \frac{1}{\sqrt[3]{\gamma}} \right). $$ These are shown with Lemma 2.3 on p. 7.
Let’s just confirm the EGT in the rest of today’s post. (You can check in the arguments on p. 7 that it suffices to just count \( Y_i \) with \(x_i >0 \).) It is now not difficult by solving this optimization problem with calculus: $$ (9) \qquad \qquad \textrm{minimize}~ \sum_{i=1}^{{n \choose l}} \textrm{sgn}(x_i), \qquad \textrm{subject to}~ \quad \sum_{i=1}^{{n \choose l}} x_i = A, \quad \textrm{and} \quad \sum_{i=1}^{{n \choose l}} x_i^2 \le B, $$ $$ \qquad \qquad \textrm{where}~ \quad A= {n \choose l}{l \choose m} e^{-\kappa({\mathcal F})}, \qquad \textrm{and} \qquad B= \frac{1}{1 – \frac{1}{2 \gamma}} {n \choose l}{l \choose m}^2 e^{-2\kappa({\mathcal F})}, $$ regarding \( x_i \) as nonnegative integer variables. Here \( \textrm{sgn}(x_i) \) expresses the sign of \(x_i \) returning 1 if it is positive and zero otherwize. Therefore, $$ N= \sum_{i=1}^{{n \choose l}} \textrm{sgn}(x_i) = |Ext({\mathcal F}, l)|, $$ which needs to be at least \( N_{min} = {n \choose l} ( 1 – 2 \gamma^{-1/3} ) \).
To prove \( N \ge N_{min} \), give any value to N and solve: $$ (10) \qquad \qquad \textrm{minimize}~ \sum_{i=1}^N x_i^2, \qquad \textrm{subject to} \quad x_i \ge 0, \quad \textrm{and} \quad \sum_{i=1}^N x_i = A. $$ Then it suffices to show \( N < N_{min} \) \( \Rightarrow \) Solution to (10) \( > B\), that is, such an N cannot be the solution to (9), finishing the proof.
We can try small N first to see it true. For N=2, we minimize \( x_1^2 + x_2^2 \) subject to \( x_1+x_2= A \) with the real variables \(x_i \ge 0 \). The solution occurs at \( x_1 =x_2 = \frac{A}{2} \): draw the circle \( x_1^1 + x_2^2 = R^2 \) in the 2-dimensional Euclidian plane \( \{ (x_1, x_2) \} \) as the figure below. Varying the radius R, we see R must be at least \( \frac{A}{\sqrt 2} \) occurring at \( x_1 =x_2 = \frac{A}{2} \) for the circle to meet with the straight line \( x_1+ x_2 =A \). The solution to (10) in this case is \(R^2 = A^2/2 \) that is way bigger than B, impossible to be that of (9).
It’s the same for N=3 in the 3-dimensional Euclidian space, where the sphere \( x_1^1 + x_2^2 +x_3^2 = R^2 \) must meet with the plane \( x_1+x_2 + x_3 = A \), producing the solution \(R^2 = A^2/3\), which cannot be that of (9).
For any N, we can use a Lagrange multiplier to find the solution: minimize \( f(x_1, x_2, \ldots, x_N; \lambda)= \sum_{i=1}^N x_i^2 + \lambda \left( A – \sum_{i=1}^N x_i \right) \) subject to \( x_i \ge 0 \) and \( \sum_{i=1}^N x_i = A \). By \( \partial f / \partial x_i = 0 \) and \( \partial f / \partial \lambda = 0 \), we see there’s only one local min/max \( A^2 / N \) at \( x_1= x_2= \cdots = x_N = A/N \). It’s smaller than the \( R^2 \) at the boundary \( x_1= A \) and \(x_2=x_3= \cdots = x_N=0 \), so \( A^2 / N \) is the global minimum being the solution to (10).
If \( N< N_{min}\), the solution is greater than $$ \frac{A^2}{N_{min}} \ge \frac{{n \choose l}^2 {l \choose m}^2 e^{-2 \kappa({\mathcal F})} }{{n \choose l} ( 1 – 2 \gamma^{-1/3} )} > \frac{1}{1 – \frac{1}{2 \gamma}} {n \choose l}{l \choose m}^2 e^{-2\kappa({\mathcal F})} = B, $$ since \( 1 – 2 \gamma^{-1/3} < 1 – (2 \gamma)^{-1} \).
So the solution to (9) indeed satisfies \( N \ge N_{min} \), leading to our confirmation of the EGT, and all the statements in the 2/16, and 2/23 posts.
Links for mobile devices