For the exact proof of the double mark lemma, p. 6 of Paper S3 proves $$ (7) \qquad \Gamma(b) ~\textrm{of}~{\mathcal F} ~\textrm{where}~ b= \frac{5 \gamma mn}{l}, \quad \Rightarrow \quad |{\mathcal D}|<{n \choose l} {l \choose m}^2 e^{-2 \kappa({\mathcal F})} \sum_{j=0}^m (2 \gamma)^{-j}, $$ considering the three cases.
1. For \( 1 \le j < m \):
Remark E) on p. 5 shows the two bounds with Lemma 1.2 on p. 3, or (3) in the 8/4 post, involving \( u_j \). This argument works for \( 1 \le j < m \) only, because we can’t use the \( \Gamma \)-condition for j=0, and \( \ln \left( 1 – \frac{j}{m} \right) \) for j=m.
2. j=m.
Here \( {n \choose m} \Big/ {l \choose m} = \prod_{i=0}^{m-1} \frac{n-i}{l-i} < (2n/l)^m \) because $$ \frac{n-i}{l-i} < \frac{2n}{l}, \quad \Leftrightarrow \quad (n-l) i < nl, $$ which is true for every \( i \in [0, m) \). Also with the 8/18 post considered, the argument holds even with the collective \( \Gamma \) condition (5) given there: we only need \( {m \choose m} \le m^m \) because \( \frac{m^m {n \choose m}}{b^m {l \choose m}} < (2 \gamma)^{-m}. \)
3. j=0.
As the note says, the last inequality holds universally for any m, l and n such that \( 2 m \le l \le n \): the RHS counts all the (U, V, Y) as before, and the LHS doesn’t exceed it: count (U, V) first, for each of which there are at least \( {n-2m \choose l-2m} \) l-sets Y including U and V that is the minimum value not exceeding the real value \( {n – |U \cup V| \choose l – |U \cup V| } \).
This confirms (7) finishing our proof of the double mark lemma in the unweighted case, having also shown that the upper bound is implied by the collective \( \Gamma \)-condition \( \sum_{T \in {X \choose j}} |{\mathcal F}[T]|^2 < \left( \frac{\gamma n}{l} \right)^{-j} |{\mathcal F}|^2 \) for all \( j \in [m] \).
Links for mobile devices