Let’s finish proving the conversion lemma in this post. We’re confirming (22) given last time. Assume true for g-1 and prove for g. By induction hypothesis:
The second line is justified by (1′) and the figure: the induction hypothesis considers \( {\boldsymbol U}=(U_1, U_2, \ldots, U_{g-1} ) \in {\mathcal P}_{k, g-1} \), so \( Union ({\boldsymbol U} ) = (g-1)m-k \) by definition. Add the last element \( U_g \in {\mathcal F} \) to \( {\boldsymbol U}\) such that \( |Union({\boldsymbol U}) \cap U_g| = j-k \). There are \( {(g-1)m – k \choose j-k}\) or less choices of such (j-k)-intersection, each producing the weight at most \( h b^{j-k} \| {\mathcal F} \|_* \) by the primitive \( \Gamma(b, h) \)-condition of \({\mathcal F} \). So we get the second line.
The third line is due to \( b_g=2^{g-2} b \) and the note below it.
We have proven the conversion lemma.
Links for mobile devices