Please recall t, t’, u, v, v’ and the relation (11) given last time, and \( |{\mathcal M} | = A \) and \( |{\mathcal D} | \le B \) in the 9/17 post. It’s seen that (11) implies Corollary 3.2 of Paper S3 we’ve been trying to figure out since the 7/27 post. Let’s finish proving it in today’s post.
We check the truth of the upper bound \( \alpha = v {l \choose m} e^{-\kappa({\mathcal F}) } \) in (11) first. Among all in \( {X \choose l} = \left\{ Y_1, Y_2, \ldots, Y_{{n \choose l}} \right\} \), call an l-set \( Y_i \) good if it meets the upper bound, i.e., \( x_i = \left| {\mathcal F} \cap {Y_i \choose m} \right| < \alpha \). We want to prove there are \( (1 – u) {n \choose l} \) good \( Y_i \) as Lemma 2.3 a) says on p. 7 of Paper S3.
Suppose for a contradiction that this is not the case. Noting that \( u {n \choose l} = \left \lfloor \epsilon {n \choose l} \Big/ 2 \right \rfloor \) is an integer, let the first \( u {n \choose l} \) sets \( Y_i \) be bad without loss of generality. We’ll show this would violate \( |{\mathcal D}| < t’ \) of (11) coming from the double mark lemma \( |{\mathcal D}| < B \).
We have $$ (12) \qquad x_1+x_2+ \cdots + x_{{n \choose l}} = z{n \choose l}{l \choose m}, \quad \textrm{where} \quad z= e^{-\kappa({\mathcal F}) }, $$ from \( |{\mathcal M}| = A \), and $$ (13) \qquad \qquad x_1+x_2+ \cdots + x_{ u {n \choose l}} = y z{n \choose l}{l \choose m}, $$ where \(y \in (0, 1) \) is the ratio of the fraction of \( {\mathcal M} \) accumulated over the bad \( Y_i \).
To (13), apply the same optimization problem (10) in the 7/17 post to get $$ x_1^2+x_2^2+ \cdots + x^2_{ u {n \choose l}}\ge \frac{\left( x_1+x_2+ \cdots + x_{ u {n \choose l}}\right)^2}{u {n \choose l}} =\frac{\left[ y z{n \choose l}{l \choose m} \right]^2}{u {n \choose l}}= \frac{y^2 z^2}{u} {n \choose l} {l \choose m}^2, $$ as Solution to (10) = \( A^2 / N \) found in the post. Likewise, by applying (10) to (12)-(13), $$ x_{u{n \choose l}+1}^2+x_{u{n \choose l}+2}^2+ \cdots + x_{{n \choose l}}^2 \ge \frac{(1-y)^2 z^2}{1-u} {n \choose l} {l \choose m}^2.$$ So $$(14) \qquad |{\mathcal D}| \ge f {n \choose l}{l \choose m}^2, \qquad \textrm{where} \quad f= \frac{y^2}{u} + \frac{(1-y)^2}{1-u} = \frac{y^2 – 2uy + u}{u(1-u)} .$$
Now all we need here is \( f \ge t’ \) because it would produce a contradiction against \( |{\mathcal D}| < t’ {n \choose l} {l \choose m}^2 \) of (11). To see it, observe:
Hence, $$ f \ge f(uv) = \frac{u(v-1)^2}{1-u} + 1 = t’,$$ proving our desired upper bound in (11) and also Lemma 2.3 a): there are \( (1-u) {n \choose l} \) sets \( Y_i \) such that \( x_i < \alpha \).
Lemma 2.3 b) can be seen similarly. We want to show there are the same number of \( Y_i \) meeting the lower bound \( x_i > v’ {l \choose m} e^{-\kappa({\mathcal F}) } \) using the same y and f. The only differences from the upper bound arguments are: i) \( y \le uv’ \) this time because the first \( u {n \choose l} \) bad \(Y_i \) don’t meet the lower bound; ii) v'<1 from the last time; iii) so we consider the left half of the parabola f(y) where the minimum occurs at y=uv’.
We have now confirmed Corollary 3.2. Next time, we’ll generalize the arguments to the weighted cases to check the truth of Theorem 2.1 on p. 4.
Links for mobile devices