Last time, we proved the \( g^{th} \) mark lemma on p. 2 of Paper S4. It is the generalization of the double mark lemma for the rank-g construction. By this we completed the second task of the four listed in the 12/11/23 post.
The \( g^{th} \) mark lemma is stronger implying the whole statement of the double mark lemma for g=2. It is shown by the inequality \( {n \choose m}^g {n-gm \choose l-gm} \le {n \choose l}{l \choose m}^g \) tautologically true for every possible l, m, n and g. The proof is simple not counting \( g^{th} \)-marks along a combinatorial identity like we did for the double mark lemma. The equation given in Remark C) on p.3 might lead to something else that is interesting.
Despite the simplicity of the new proof, it is interesting to find the identity (6) in the 8/25/23 post to count double marks along its algebraic proof, with the accurate approximation of \( {x-y \choose y-j} \) shown in the 9/9/23 post. I think both ways are equally good to know.
Before moving to the third task to prove the conversion lemma, let’s look at Section 1.3. It’s to connect the rank-g weight \( w: (2^X)^g \rightarrow {\mathbb R}_{\ge 0} \) to the g=1 weight \( 2^X \rightarrow {\mathbb R}_{\ge 0} \) we dealt with in Paper S3. We say that \( w \) is primitive if it is defined by \[ (U_1, U_2, \ldots, U_g ) \mapsto \prod_{i=1}^g w_*(U_i), \qquad \textrm{for some}~~ w_* :~2^X \rightarrow {\mathbb R}_{\ge 0}. \]
If so, \( w \) is essentially the same as \( w_* \) because for any family \( {\mathcal G} \subset 2^X \), \[ \| {\mathcal G} \|^g = \sum_{\boldsymbol{U} \in {\mathcal G}^g } w( \boldsymbol{U} ) = \sum_{(U_1, U_2, \ldots, U_g) \in {\mathcal G}^g } ~~\prod_{i=1}^q w_*( U_i) = \left[ \sum_{U \in {\mathcal G}} w_*(U) \right]^g = \| {\mathcal G} \|_*^g, \] meaning \( \| {\mathcal G} \| = \| {\mathcal G} \|_* \) where \( \| \cdot \|_* \) is the norm induced by \( w_* \).
Then we can define the weight of a mark \( (U, Y) \) to be \( w_*(U) \), so the family \( {\mathcal M} \) of marks has the norm \[ \| {\mathcal M} \| = \sum_{{Y \choose l}} \left\| {Y \choose m} \right \| = \| {\mathcal F} \| {n-m \choose l-m} = {n \choose m}{n-m \choose l-m} e^{-\kappa({\mathcal F})} = {n \choose m}{l \choose m} e^{-\kappa({\mathcal F})} \] as before and G) on p. 5 due to \( \| \cdot \| = \| \cdot \|_* \).
By this we can make the same quadratic optimization arguments for g=2 started at the 9/17/23 post. So we have Theorem 1.3 on p. 4 that is almost the same as Theorem 2.1 of Paper S3 we proved before. It says that if \( {\mathcal F} \) satisfies the \( \Gamma_2( \frac{4 \gamma n}{l}, 1 ) \)-condition, almost all \( l \)-sets Y have approximate norm \( {l \choose m} \| {\mathcal F} \| \Big/ {n \choose m} \).
We’ll do the next task to prove Lemma 1.4 on primitive weight. Although such weight is similar to the \( w_* \), we can accumulate them to make a non-primitive weight. That’s what we did for g=2: in the the 11/20/23 post , we designed the 2-parameter weight \(w \) such that \( w ( {\mathcal F}_Y ) = \sum_{T \subset X – X_,~T \ne \emptyset} ~~ \frac{|{\mathcal F}_Y[T]|^2}{b^{-|T|} {m \choose |T|}} \). You can see that the summand for each T is primitive, but the total weight may not be. We’ll covert the given plain \( \Gamma \)-condition to a \( \Gamma_g \)-condition for each primitive part of the total weight by the lemma. Step 2 on p. 8 accumulates them to show the \( \Gamma_g \)-condition as a whole. Then apply it to the \( g^{th} \) mark lemma to export the collective \( \Gamma \)-condition.
Links for mobile devices