In this post, we start exploring our new topic, the collective \( \Gamma \)-conditions. On the weighted domain \( 2^X \) with the induced norm \( \| \cdot \| \), the simple one states $$ (16) \qquad \sum_{T \in {X \choose j}} \|{\mathcal F}[T] \|^2 < b^{-j} \| {\mathcal F} \|^2, \quad \textrm{for all}~ j \in [m], $$ which is equivalent to its unweighted version (5) given in the 8/18 post if \( b=5 \gamma n/ l \). It implicitly assumes the 2nd condition \( U \not \in {\mathcal F} \) \( \Rightarrow \) \( w(U)=0 \) whenever necessary.
The rank of the \( \Gamma \)-condition is 2 because it takes the 2nd power inside. The primary benefit of considering a collective \( \Gamma \)-condition is that we can raise the rank to a sufficiently large constant g to enhance the depth of arguments significantly. As we noted this in the 8/4 post, Paper 3 posted on the left uses the rank g to prove \( \Gamma( m^{\frac{1}{2}+\epsilon}) \) of \( {\mathcal F} \) means there are three mutually disjoint sets in \( {\mathcal F} \), not just a 3-sunflower, for any given small constant \( \epsilon>0 \) and sufficiently large m.
For the next while, we’ll see the essence of the Paper 3 construction: what the \(g^{th} \) mark lemma, Lemma 2.1 on p. 3 does and how it’s proven, also how it is connected to our previous discussions and is used in the proof the 3-disjoint-sets claim. We’ll focus on the intrinsic ideas behind dismissing some details, in order to convince us that the rank-g argument works. It’ll take some time for it.
To use a collective \( \Gamma \)-condition in the proof in Section 4.2, it’d be most useful if provided as a single inequality. Rather than the form of (16), we define the \(g^{th} \) collective \( \Gamma(b, h) \)-condition of \( {\mathcal F} \subset {X \choose m} \) as $$ (17) \qquad \sum_{u \in [m],~T \in {X \choose u}} \frac{\| {\mathcal F} [T]\|^g}{b^{-u(g-1)} {m \choose u}} <h \| {\mathcal F} \|^g, $$ where b>0 is typically \( \gamma n m / l \) as before, and h>0 is a sufficiently large constant given for proof convenience. A variant of this form is used as the condition \( \Pi_j\)-ii)-a) on p. 14 to be maintained recursively by the main proof.
First off, let’s show that the plain \( \Gamma (\gamma m n / l) \)-condition we’ve been investigating for the proof of EGT is roughly the same as (16) and (17), with proper choices of b, h and sufficiently large \( \gamma \). (Please recall n=|X| and l is the target extension length, i.e., the 2nd parameter of \( Ext ({\mathcal F}, l) \).) We check the three statements.
Proposition 1.
- If \({\mathcal F} \) satisfies the \( \Gamma(b) \)-condition on the norm \( \| \cdot \| \), then both (16) with \( b \leftarrow b / m \), and (17) with \( b \leftarrow b/2 \) and h=1 hold true.
- If (16), there exists a subfamily \( {\mathcal F}’ \subset {\mathcal F} \) satisfying \( \| {\mathcal F}’ \| > 2^{-1} \| {\mathcal F} \| \) and the \( \Gamma \left( b / 6 \right) \)-condition on \( \| \cdot \| \).
- If (17) for a given \( g>1 \), \( b< m^2\), and \( h=1 \), the family \( {\mathcal F} \) satisfies the \( \Gamma \left( b m^{-3/g} \right) \)-condition on \( \| \cdot \| \).
By Prop. 1-1, we are given \({\mathcal F} \) such that \( \| {\mathcal F}[T] \| < b^{-|T|} \| {\mathcal F} \|\) for every nonempty set T. So $$ (18) \qquad \sum_{T \in {X \choose u}} \| {\mathcal F}[T] \|^g < b^{-u(g-1)} {m \choose u} \| {\mathcal F} \|^g, \qquad \textrm{for all}~ u \in [m], $$ for the integer g given by (17). Think of it this way: if \( \| \cdot \| \) is just the cardinality \( | \cdot | \) and g=2, the sum \( \sum_{T \in {X \choose u}} \| {\mathcal F}[T] \|^2 \) counts set pairs \( (U_1, U_2) \) with \( U_i \in {\mathcal F}[T] \), so the RHS should be \( b^{-u} {m \choose u} |{\mathcal F}|^2 \) as correctly given there.
For any norm and \( g \ge 2 \), the LHS considers all the set tuples \( (U_1, U_2, \ldots, U_g) \) with \( U_i \in {\mathcal F}[T] \), finding the product of \( \| {\mathcal F}[U_i] \| \). To upper-bound \( \sum_{(U_1, U_2, \ldots, U_G)} \prod_{i \in [g]} \| {\mathcal F}[U_i] \| \), fix any \(U_1\) so the first factor is \( \|{\mathcal F}\| \). There are \( {m \choose u} \) choices of \( T \in {U_1 \choose u} \), for each of which all \( U_2 \in {\mathcal F} [T] \) produces the factor \( \| {\mathcal F}[T] \| < b^{-u} \| {\mathcal F} \| \). So we multiply \( \|{\mathcal F}\| {m \choose u} \) by \( b^{-u} \| {\mathcal F} \| \). Do the same for \( U_2, U_3, \ldots, U_g \) to get (18).
This means $$ \sum_{T \in {X \choose u}} \frac{\| {\mathcal F}[T] \|^g}{(b/2)^{-u(g-1)} {m \choose u}} < 2^{-u} \| {\mathcal F} \|^g, \qquad \textrm{for}~ u \in [m]. $$ Summing this up for all u, we see \( \Gamma(b) \) of \( {\mathcal F} \) \( \Rightarrow \) (18) with \( b \leftarrow b/2 \) and \( h \leftarrow 1 \), confirming the second statement of Proposition 1-1.
The first statement of P 1-1 is simpler to see: with \( g \leftarrow 2 \) in (18), $$ \sum_{T \in {X \choose u}} \| {\mathcal F}[T] \|^2 < b^{-u} {m \choose u} \| {\mathcal F} \|^2 < \left( \frac{b}{m} \right)^u \| {\mathcal F} \|^2, $$ justifying (16) with \( b \leftarrow b/m \).
We’ll continue on the proof next time.
Links for mobile devices