Having finished our proof of Lemma A.1 of Paper S4 last time, the bound (4) given on 6/17/24 is now available to help resolve our initial core growth problem. First, let’s find a general good \( r\)-split following the same style as Theorem 4 on 6/3/24.
To prove Theorem 5 from (5), we again count the pairs \( (U, \boldsymbol{X} )\) using the same technique as 5/13/24, 11/6/23 and the extra notes of the 2/23 post: among the \( |{\mathcal F}| \prod_{i=1}^r {n-(i-1)n/r \choose n/r} \) such pairs, less than \( m \exp \left( – \frac{m}{12 r} \right) \) of them fail to meet \( \frac{m}{2r} < |U \cap X_1| < \frac{2m}{r} \) due to (5); count them the same way as 5/13/24 fixing each \( U \). By symmetry, less than \( m \exp \left( – \frac{m}{12 r} \right) \) of them fail to meet \( \frac{m}{2r} < |U \cap X_i| < \frac{2m}{r} \) for any particular \( X_i \).
So, all the other \( (U, \boldsymbol{X} )\) that amount to \( \left[ 1- r m \exp \left( – \frac{m}{12 r} \right) \right] |{\mathcal F}| \prod_{i=1}^r {n-(i-1)n/r \choose n/r} \) or more meet the double inequality for every strip \( X_i \). Hence, there must be an \( \boldsymbol{X} \) and subfamily \( {\mathcal F’ } \subset {\mathcal F} \) meeting the two conditions given by Theorem 5, completing its proof.
The theorem helps us justify the simultaneous core growth presented on 6/17/24 for \( k=3 \) completely. Given an \( {\mathcal F} \) satisfying \( \Gamma (b) \) where \( b=m^{\frac{1}{2} + \epsilon} \), find a good \( \boldsymbol{X} \) and \( {\mathcal F}’ \) by the theorem. For \( j=1, 2, \ldots, r \), we recursively prove the existence of:
mutually disjoint three sets \( C_i \) with \( |C_i | = O( j r \ln m ) \),
and subfamilies \( {\mathcal F}_i \subset {\mathcal F}'[C_i] \) for \( i \in [3] \),
satisfying the \( \Gamma (b_j, 2) \)-condition in \( X – C_i \), i.e., \( | {\mathcal F}_i [S] | < 2 b_j^{-|S|} | {\mathcal F}_i| \) for every nonempty \( S \subset X – C_i \), where \( b_j = b( 1- 1/r)^j \),
and \( |U \cap X_{j’}| = q_{j’} \) for each \( j’ \le j \) and \( i \in [3]\), some \( q_{j’} \in \left( \frac{m}{2r}, \frac{2m}{r} \right) \), and all \( U \in {\mathcal F}_i \).
You can check the truth for each \( j \) by performing the process described there. Next time, we’ll generalize this to any given \( k \) to pose our final solution to the initial core growth problem.
In our proof of Lemma A.1 of Paper S4, we figured out last time that (A.3): \( u \le – \alpha \Delta \) suffices for the \( u \) expressed as (A.4) in the two cases of \( \alpha \).
In Case 2 where \[ \frac{y’}{x’} \ge \frac{2x}{y}, \qquad p \ge 1, \qquad \textrm{and} \qquad \alpha = \ln 4 -1> 0.386, \] we see that \( \left( \frac{1}{p} + 1 \right) \ln (1+p) \ge 2 \ln 2 \): put the LHS in \( f (p) \) to find \( f'(p) = p^{-2} [p – \ln (1+p) ] >0 \), due to \( p – \ln (1+p) >0 \) if \( p \ge 1 \). So \( f(p) \) takes minimum \( f(1) = 2 \ln 2 \) at \( p=1 \).
\( |q| \) is always less than 1 so we can still use the above upper bound. Consequently, \[ u \le -\Delta (2 \ln 2 – 1) = – \alpha \Delta, \] confirming (A.3) in Case 2 as well. We’ve completed the proof of Lemma A.1 now.
We now show (A.3): \( u \le – \alpha \Delta \) to prove Lemma A.1 of Paper S4 that is also posed on 6/25/24. We figured out last time that (A.3) implies the lemma.
We’ll use the Taylor series of \( \ln (1+x) \) in (A.4) to show \( u \le -\alpha \Delta \). But we need to check if \( |p| < 1 \) and \( |q|<1 \) before it.
We’ll continue the arguments to finish proving (A.3) next time.
We now start proving Lemma A.1 of Paper S4. To devise an upper bound on \( \ln \frac{{x-x’ \choose y-y’}{x’ \choose y’}}{{x \choose y}} \), we rely on Lemma 1.1 of Paper S3 again like 5/27/24 and 6/10/24:
Please check this to get convinced, where \( u \) is from the \( y \left( \ln \frac{x}{y} + 1 \right)\) terms of (A.1) for the three binomial coefficients, \( v_j \) are from the \( y s \left( \frac{y}{x} \right) \) terms, and \( – 2^{-1} \ln 2 \pi \beta \) is from the \( \frac{1}{2} \ln \frac{x}{2 \pi y (x-y)} \) terms.
This simplifies the situation a lot allowing us to focus on just two relations: \[ \textrm{(A.2)} \qquad v_j \ge 0, \quad \textrm{for all}~ j>0, \qquad \qquad \textrm{and} \qquad \qquad \textrm{(A.3)} \qquad u \le – \alpha \Delta. \] It’s clear in the above figure that the two imply our target bound.
Let’s focus on Lemma A.1 of Paper S4 that shows the number bound indicating the chart we made last time. To show (4) there, the formulation of Lemma A.2 in Appendix of Paper 3 is not quite relevant although it is ok for Lemma 4.1 on p. 12 to refer to. It’s good if it’s changed into the formulation of Lemma A.1, covering a broader range of applications such as showing (4) to resolve our initial core growth problem.
Before breaking down its proof, let’s get convinced that \( {m \choose q}{n-m \choose d-q} \) regarded as a function of \( q \in [0, m] \) takes maximum around \( q \simeq \frac{md}{n} = \frac{m}{r} \) given that \( m \ll d \ll n \). This is because \[ {m \choose q+1} = \frac{m-q}{q+1} {m \choose q}, \quad \textrm{and} \quad {n-m \choose d-q-1} =\frac{d-q}{n-m+q+1}{n-m \choose d-q}, \] so \( {m \choose q+1}{n-m \choose d-q-1} = t {m \choose q} {n-m \choose d-q} \) where \[ t= \frac{(m-q)(d-q)}{(q+1)(n-m+q+1)} = \frac{md}{qn} \frac{\left[1-O(q/m) \right]\left[1-O(q/d) \right]}{\left[1 + O(1/q) \right] \left[1 – O(m/n) \right]} \simeq \frac{md}{qn}, \] Here the approximate equality is due to the extra condition \( 1 \ll q \ll m \) added to \( m \ll d \ll n \). So, if \( q > m/r + o(1) \), then \( {m \choose q}{n-m \choose d-q} \) increases when \( q\) is incremented, and decreases if \( q < m/r – o(1) \). (Asymptotic notations here work just as well as 8/11/23. )
If \( q = O(1) \), the value of \(t \) is \( \frac{m}{O(r)} \) so it has the same asymptotic behavior upon the incrementation. If \( q \ge \epsilon m \), then \( {m \choose q} \) increases by less than \( \epsilon^{-1} \), and \( {n-m \choose d-q} \) reduces by an approximate factor \( r^{-1} \) not affecting the asymptotic decrease rate. Therefore, we conclude that \( {m \choose q}{n-m \choose d-q} \) takes maximum at either \( \lfloor m/r \rfloor \) or \( \lceil m/r \rceil \) when \( m \ll d \ll n \): if \(q \le \lfloor m/r \rfloor -1 \) the function still increases, and if \(q \ge \lceil m/r \rceil +1 \), it decreases. There’s a subtlety at \( q= \lceil m/r \rceil \), but you can check that \( q= \lceil m/r \rceil~ \Rightarrow~ t<1 \) by a bit more involved argument, so you know it can’t take maximum at \( q \ge \lceil m/r \rceil +1 \).
As said before, we are analyzing the distribution of the summand \( {m \choose q}{n-m \choose d-q} \) of the Vandermode’s identity \( \sum_{q=0}^m {m \choose q}{n-m \choose d-q} = {n \choose d} \). This is equivalent to the following visualization involving random \(d \)-sets:
It’s good to know that random \( d \)-sets are distributed in \( X \) in the above sense. Each element of \( U \) is chosen almost independently so it gets in \( X’ \) with probability \( \simeq m/n \), and in \( X- X’ \) with probability \( \simeq (n-m)/n \). (Element placements are not completely independent because you can’t place one where it’s already taken. But \(n \) is much larger than \( d \) giving a small difference from \(d \) independent trials.) So a typical \(U \) must have \( \frac{|U \cap X’|}{|U- X’|} \) around \( \frac{m}{n-m} \). This insight allows us to derive (2) on 5/27/24 and Remark 4 on 6/10/24, where we can just consider typical \(U \) with \( m_*/2 < q < 2m_* \) because all others have a negligible occurrence probability.
A lot of statistical distributions, not just combinatorial ones, have a similar tendency that event occurrence probabilities are concentrated in a small range of a random variable. This is often due to the nature of some binomial coefficients.
Here is our formulation of the lemma:
So if the lemma is true, we have (4) last time stepping forward to resolve our problem. We’ll start seeing its proof next time.
We’ve finished reviewing the \(r\)-split lemma presented on 5/13/24, outlining last time how we can resolve the initial core growth problem with its proof technique. However, our plan for the fix is not quite complete. We can see the shortcoming this way: consider \( k=3 \) for simplicity. As said in the last post, we can grow the core \( C_1 \) up to \( |C_1|= O (r \log m) \) for the first family \( {\mathcal F}_1 \subset {\mathcal F} \) to maintain its \( \Gamma(b_1) \)-condition for some \(b_1\simeq b\). This works for many \( d\)-sets \( X_1 \) but may not for all of them. Keep \( C_1 \) for each good \(X_1 \) deleting \( {\mathcal F}[C_1] \) from \({\mathcal F} \). When we try the core growth for the second family \( {\mathcal F}_2 \), we notice the remaining \( {\mathcal F} \) depends on both \(X_1 \) and \(C_1 \). Try finding \(C_2 \) but the already fixed \(X_1 \) for each \( C_1 \) may not work for \( C_2 \).
This kind of big subtleties happen very often in this study almost as a default, which can be both interesting and frustrating. Fortunately, there’s a good repair for this particular case. Instead of fixing the target \( q \), you allow all \( U \in {\mathcal F}_i \) such that \[ (3) \qquad \frac{1}{2} m_* < q < 2m_*, \quad \textrm{where} \quad q = |X_{j+1} \cap U|, \quad m_* = \frac{m}{r} \simeq m^{\frac{1}{2} +\epsilon^2}, \] and \( j=0 \). It can be shown that a vast majority of \( U \) meet the double inequality, so we can a priori eliminate all \( X_{j+1} \) undesired for any \( {\mathcal F}_i \) with trivial sparsity increases.
Now let’s consider the general \( j^{th} \) induction step where we are given three \( {\mathcal F}_i \subset {\mathcal F}[C_i] \) with a \( \Gamma(b_j) \)-condition. After the \( (X_{j+1}, U) \)-arguments in \( X’ \) as 5/20/24, fix any remaining good \( X_{j+1} \) to eliminate all \( U \) such that \( \neg \) (3) anywhere. Then \( {\mathcal F}_i\) satisfy the \( \Gamma(b_j) \)-condition approximately because \( |{\mathcal F}_i| \) didn’t change too much.
Do the simultaneous core growth we mentioned last time: let \( {\mathcal F}_{1, q} \) be the family of \( U \in {\mathcal F}_1 \) such that (3) with the \(q \). Choose a \( q \) with the largest \( {\mathcal F}_{1, q} \). Find a maximal \( S \subset X- C_1 \) such that \( |{\mathcal F}_{1, q}[S]| \ge b_{j+1}^{-|S|} |{\mathcal F}_{1, q}| \) for some \( b_{j+1} \) slightly smaller than \( b_j \). After it, perform the updates \( C_1 \leftarrow C_1 \cup S \) and \( {\mathcal F}_1 \leftarrow {\mathcal F}_{1, q}[S] \) that satisfies the \( \Gamma (b_{j+1}) \)-condition. Because \( |S|=O(r \log m) \), we can delete \( {\mathcal F}[C_1] \) from the other two \( {\mathcal F}_i \) keeping the \( \Gamma(b_j) \)-condition approximately true.
Now that the \( X_{j+1} \) is fixed, we can grow the second core \( C_2 \) without worrying about errors. Perform the same core growth for \( i=2\), after which eliminate \( {\mathcal F}[C_2] \) from both \( {\mathcal F}_1 \) and \( {\mathcal F}_3 \); it doesn’t disturb the approximate \( \Gamma \)-conditions since \( |C_2| \ll b_{j+1} \). Do the same for \( {\mathcal F}_3 \), and do it recursively for \( j=0, 1, \ldots, r\) to complete the construction. On the obtained \( r \)-split, the \( m\)-sets \( U \) just meet (3) rather than \( q= m_* \) exactly, but a constant factor on \( m_* \) isn’t an issue for the rank \( g \)-construction. The final \( {\mathcal F}_i \) satisfy the \( \Gamma(b_r) \)-condition for some \( b_r > \epsilon b \), and the three \( C_i \) are mutually disjoint.
This description of the construction process is almost complete to find our final \( {\boldsymbol X} \), \( C_i \), and \( {\mathcal F}_i \), except for the justifications of some number bounds. Especially, we need to be sure that the first step \( j=0 \) reduces less than \( \exp ( -\sqrt m ) \) of \( {\mathcal F} \) to eliminate \( U \) such that \( \neg \) (3).
In other words, we want to show \[ (4) \qquad \sum_{2^{-1} m_* < q < 2 m_* } \frac{{m \choose q}{n-m \choose d-q}}{{n \choose d}} > 1 – e^{-\sqrt m}. \] Graphically, it should look like:
It’s about the distribution of the summand \( {m \choose q}{n-m \choose d-q} \) of the Vandermode’s identity \( \sum_{q=0}^m {m \choose q}{n-m \choose d-q} = {n \choose d} \); we used it on 6/6/23 to prove the complement sparsity lemma. We see in the chart that \( f(q) \) is maximized when \( q=\frac{dm}{n}=\frac{m}{r} =m_* \), much larger than the values with \( q>20=2m_* \) or \( q<5=m_*/2 \). The function decreases quicker when \( q> 2 m_* \).
Lemma A.1 in Appendix of Paper S4 proves it quantitatively implying (4). When arranging materials for the next posts, I noticed that its formulation copied from Paper 3 was not quite relevant in order to confirm (4). So I fixed it with the same proof to meet our need. Also, the parameter of the \( \Gamma \)-condition in Proposition 3 on 11/13/23 should read \( c m^{\frac{1}{2} +\epsilon} k \ln^2 k \) changing \( \ln k \) into \( \ln^2 k = (\ln k)^2 \). This works although it may not be the optimal bound.
Lemma A.1 is useful in this research. We’ll need it later when we discuss the circuit complexity of the clique function. In the next couple of posts, we’ll break down the proof for complete understanding.
Here’s our last remark on the \(r\)-split lemma we’ve been discussing in the last few posts.
Remark 4: the first proof step we found on 5/13/24 is useful for our initial core growth problem. We argued on 4/29/24 that we want an \( r \)-split \( {\boldsymbol X} \), \( k \) mutually disjoint sets \( C_i \) and subfamilies \( {\mathcal F}_i \subset {\mathcal F}[C_i] \) on \( {\boldsymbol X} \) satisfying necessary \( \Gamma \)-conditions to prove Proposition 3 on 11/13/23. To start its proof, we are just given an \( {\mathcal F} \) with \( \Gamma (b ) \) where \( b= c m^{\frac{1}{2} + \epsilon} k \ln^2 k \). To apply the rank \(g \)-construction, we want \( {\mathcal F} \) on a good split with a \( \Gamma \)-condition, but we can’t just use the split lemma or grow the core because we’re trying to find \( k \) mutually disjoint sets in \( {\mathcal F} \). The initial core growth problem asks how to construct such \( {\boldsymbol X} \), \( C_i \) and \( {\mathcal F}_i \).
Our solution to the problem finds pairs \( (U, X_1) \) of \( U \in {\mathcal F} \) and \( d\)-sets \(X_1 \) the same way as the 5/13/24 post, so there are \( {m \choose q} {n-m \choose d-q} |{\mathcal F}|\) of them such that \( |U \cap X_1|=q \). It means there are \( {m \choose q} {n-m \choose d-q} {n \choose d}^{-1} |{\mathcal F}|\) sets \( U \in {\mathcal F} \) with \( |U \cap X_1|= q \) for some \(X_1 \). Put them in \( {\mathcal F}_1 \) fixing the \(X_1 \).
We choose \( r= m^{\frac{1}{2} – \epsilon^2} \) as before, so \[ d = \frac{n}{r} = \frac{n}{m^{\frac{1}{2} – \epsilon^2} } , \qquad \textrm{and} \qquad q= \frac{m}{r} = m^{\frac{1}{2} + \epsilon^2}. \] Assume \( r \) divides both \( n \) and \( m \), and \( n \gg m^2 \) for simplicity here. We notice something similar to our finding on 5/27/24:
In other words, the sparsity increase \( \kappa ({\mathcal F}_1) – \kappa({\mathcal F }) \) is no more than \( \ln q + O(1) = O (\ln m) \). By this we can grow the core \( C_1=\emptyset \) for the first step: let \( b_1 \) be slightly smaller than \( b \), say \( b_1= (1 – \epsilon/r ) b \). Find a maximal set \( C_1 \) such that \[ |{\mathcal F}_1[C_1] | \ge b_1^{-|C_1|} |{\mathcal F}|. \] It’s not too hard to see \( |C_1| = O ( r \ln m ) \ll b \) by the given \( \Gamma(b) \)-condition of \( {\mathcal F} \). After it, \( {\mathcal F}_1[C_1] \) satisfies the \( \Gamma(b_1) \)-condition in \( X-C_1 \).
Because \( |C_1| \) is asymptotically smaller than \(b \), we can delete the whole \( {\mathcal F}[C_1] \) from \( {\mathcal F} \) without much disturbing its \(\Gamma(b) \)-condition, since it just reduces less than \( k^{-1} m^{-\epsilon} \) of \( {\mathcal F} \). We can similarly detect \( {\mathcal F}_2[C_2], {\mathcal F}_3[C_3], \ldots, {\mathcal F}_k[C_k] \) with the same \(X_1\), besides the \( {\mathcal F}_1[C_1] \) we just found. We will clarify more about this process of simultaneous core growth later.
The process can continue for \( X_2, X_3, \ldots, X_r \) like the induction steps for the \( r \)-split lemma on 5/20/24 to construct \( {\boldsymbol X} \), \( C_i \) and \( {\mathcal F}_i \) we need. In the next while, we will see its details to resolve the initial core growth problem eventually. Section 4.1 on p. 12-14 of Paper 3 deals with it in a different way. We’ll break it down as well.
We see the other two remarks on the \(r\)-split lemma given on 4/29/24 in this and the next posts.
Remark 3. \( d = n/r \) and \( q = m/q \) can be changed into variables whose sums are \( n \) and \( m\), respectively: instead of the fixed \( d \) and \(q \), we can consider positive integer tuples \( {\boldsymbol d} = (d_1, d_2, \ldots, d_r ) \) and \( {\boldsymbol q} = (q_1, q_2, \ldots, q_r ) \) such that \( \sum_{i=1}^r d_i =n \), and \( \sum_{i=1}^r q_i=m \). Then \( {\boldsymbol X} = (X_1, X_2, \ldots X_r) \) with \( |X_i|=d_i \) is an \( {\boldsymbol r} \)-split where \( {\boldsymbol r} = ({\boldsymbol d}, {\boldsymbol q} ) \), for which an \( m \)-set \( U \) is on \( {\boldsymbol X} \) if \( |U \cap X_i| = q_i \) for all \( X_i \). By the same approach, we can show \[ \left\| {\mathcal F} \cap {{\boldsymbol X} \choose m} \right\| \ge \frac{\| {\mathcal F} \|}{{n \choose m}} \prod_{i=1}^r {d_i \choose q_i}, \] for some \( {\boldsymbol X} \).
In the \(j^{th}\) induction step of its proof as on 5/20/24, we can set \[ X’= X – \bigcup_{i=1}^j X_i, \quad n’ = |X’| = n- \sum_{i=1}^j d_i, \quad m’= m- \sum_{i=1}^j q_i, \quad \textrm{and} \quad \gamma_{\boldsymbol X} = \frac{\| {\mathcal F}_{{\boldsymbol X}} \|}{{n’ \choose m’} \prod_{i=1}^j {d_i \choose q_i}}. \] Its keypoint is that there are new pairs \( (U, X_{j+1}) \) whose weight sum equals \( {m’ \choose q_{j+1}} {n’ -m’ \choose m’-q_{j+1}} \| {\mathcal F}_{{\boldsymbol X}} \| \), instead of the original proof saying there are \( {m’ \choose q} {n’ -m’ \choose m’-q} | {\mathcal F}_{{\boldsymbol X}} | \) new pairs \( (U, X_{j+1}) \).
Similar inductive arguments with this note can show \[ \# ~\textrm{of}~ (U, {\boldsymbol X} )~\textrm{with Condition}~ j~=~ {n – \sum_{i=1}^j d_i \choose m- \sum_{i=1}^j q_i } e^{-\kappa ({\mathcal F} )} \prod_{i=1}^j {d_i \choose q_i} {n- \sum_{i’=1}^{i-1} d_{i’} \choose d_i},\] for all \( j \in [0, r] \), where Condition \(j \) of \( U \in {\mathcal F}_{\boldsymbol X} \) here means \( |U \cap X_i| = q_i \) for all \( X_i \) with \( i \in [j] \). In the end, there are \( (U, {\boldsymbol X}) \) of total weight sum \( \| {\mathcal F} \| {n \choose m}^{-1} \prod_{j=1}^r {d_i \choose q_i} {n- \sum_{i’=1}^{i-1} d_{i’} \choose d_i} \) found. So there must be an \( {\boldsymbol X} \) with \( \| {\mathcal F}_{{\boldsymbol X}} \| \ge \| {\mathcal F} \| {n \choose m}^{-1} \prod_{i=1}^r {d_i \choose q_i}. \)
This generalization particularly allows us to handle \( r \) that divides neither \(n \) nor \( m \), that is:
Corollary 3.3: in an \( X \) primitively weighted with \( \| \cdot \| \), a family \( {\mathcal F} \subset {X \choose m} \) meets \[ \left \| {\mathcal F} \cap {{\boldsymbol X} \choose m} \right \| \ge {\lfloor n/r \rfloor \choose \lfloor m/r \rfloor}^{r-1} {n ~\textrm{mod}~ r \choose m ~\textrm{mod}~ r} \frac{ \| {\mathcal F} \|}{{n \choose m}}, \] for any \( r \in [n] \) that divides neither \( n \) nor \( r \), and some \(r \)-split \( {\boldsymbol X} \).
An \( r \)-split here is an \( {\boldsymbol X} =(X_1, X_2, \ldots, X_r ) \) such that \( X_i = n/r \) for \( i<r \), and \( X_r = n ~\textrm{mod}~ r \) that expresses the remainder of \( n \) when divided by \(r \). It is not too difficult to check the truth of the generalization following the arguments on 5/20/24. Here’s its formal description:
We’ve finished the proof of Lemma 1 posed on 5/13/24. Let’s call it \(r\)-split lemma in this blog. As said, a set \( S \) is on an \(r\)-split \( {\boldsymbol X} \) if it satisfies Condition \( r \) given last time. Denoting the family of all \( m \)-sets on \( {\boldsymbol X} \) by \( {{\boldsymbol X} \choose m } \), let’s see some additional facts related to it.
Remark 1. The lemma can be weighted with primitive norm \( \| \cdot \| \): as on 5/13/24 and 1/15/24, primitive norm is the simplest norm defined by a one-parameter weight function \(w_* : 2^X \rightarrow {\mathbb R}_{\ge 0} \) we dealt with a lot discussing collective \( \Gamma \)-conditions. In Paper 3, the \(r\)-split lemma with such weight is stated as Corollary 3.2 on p. 11, which is rephrased into:
Corollary 3.2: in an \( X \) primitively weighted with \( \| \cdot \| \), a family \( {\mathcal F} \subset {X \choose m} \) meets \[ \left \| {\mathcal F} \cap {{\boldsymbol X} \choose m} \right \| \ge {n/r \choose m/r}^ r \frac{ \| {\mathcal F} \|}{{n \choose m}}, \] for any \( r \in [n] \) that divides both \( n \) and \(m \), and some \(r \)-split \( {\boldsymbol X} \).
We did the same generalization for the EGT on 10/8/23 and after. By the update \( | \cdot | \rightarrow \| \cdot \| \), it changed the sparsity into \( \kappa ({\mathcal F} ) = \ln {n \choose m} – \ln \| {\mathcal F} \| \) that worked for the proof steps for the weighted EGT as well. Almost nothing else was necessary to change.
The update \( | \cdot | \rightarrow \| \cdot \| \) also works for the \(r\)-split lemma to prove the corollary. It is straightforward to check this in our proof last time.
Remark 2. The lower bound on the RHS can be further bounded by \( \|{\mathcal F} \| \exp \left[ – \frac{r}{2} \ln 2 \pi \frac{m}{r} – O\left( \frac{r^2}{m} \right) \right] \): the original split lemma says \( \left| {\mathcal F} \cap {{\boldsymbol X} \choose m} \right| \ge \left( \frac{n}{m} \right)^m |{\mathcal F}| {n \choose m}^{-1} > |{\mathcal F}| e^{-m} \), or \( \kappa \left[ {\mathcal F} \cap {{\boldsymbol X} \choose m} \right] < m \). We can find a similar sparsity bound for an \(r\)-split \( {\boldsymbol X} \) by Lemma 1.1 of Paper S3: we used it on 9/9/23 to prove the inequality (3) on 8/4/23.
We’ll see other remarks in the next couple of posts.
We continue our proof of Lemma 1 to show the existence of an \(r\)-split \( {\boldsymbol X} =(X_1, X_2, \ldots, X_r) \) and an \( {\mathcal F}’ \subset {\mathcal F} \) on \( {\boldsymbol X} \) meeting \( |{\mathcal F}’| \ge {n/r \choose m/r}^r |{\mathcal F}| \Big/ {n \choose m} \). We saw its first inductive step \( j=0 \) demonstrating there are many \( X_1 \) and \( U \in {\mathcal F} \) such that \( |X_1 \cap U|=q = m/r \).
The general induction step \( j \rightarrow j+1 \) works like \( j=0 \). After Step \(j \), we found some \( {\boldsymbol X}=(X_1, X_2, \ldots, X_j) \) and \( U \in {\mathcal F} \) satisfying \[ \textrm{Condition \( j \) of \(U \) for \( {\boldsymbol X} \):} \quad \textrm{\( |U \cap X_i| = q \) for \(X_1, X_2, \ldots, X_j \)}. \] Assume \[ (1) \qquad \# ~\textrm{of}~ (U, {\boldsymbol X} )~\textrm{with Condition}~ j~=~ {d \choose q}^j {n – dj \choose m- qj} e^{-\kappa({\mathcal F})} \prod_{i=0}^{j-1} {n-di \choose d},\] as the induction hypothesis. This is the main claim we want to verify.
To extend the current splits \( {\boldsymbol X} \) to the next ones \( {\boldsymbol X}’=(X_1, X_2, \ldots, X_j, X_{j+1}) \), fix each \( {\boldsymbol X} \) adding an \( X_{j+1} \) to the bottom. Write \[ X’ = X- \bigcup_{i=1}^j X_i, \quad n’=|X’|=n- jd, \quad \textrm{and} \quad m’=m-jq \] to see:
With (1) confirmed now for \( j=r \), we have completed our proof of Lemma 1: as said last time, \( \prod_{i=0}^{r-1} {n-di \choose d } \) is the number of \({\boldsymbol X} \), so there must be an \( {\mathcal F}’ = {\mathcal F}_{\boldsymbol X} \) with the desired cardinality bound.
