Last time, we saw the proof scenario of Corollary 3.2 of Paper S3 in which the double mark lemma on p. 5 plays the key role. It proves that the distribution of marks over l-sets Y are in favor of the extension close to \( {X \choose l} \) due to the given \( \Gamma( 5 \gamma nm / l ) \)-condition.
We’ve seen that it gives some crucial information on the topological properties of \( {\mathcal F} \) in X, if we raise the dimension of \( U \in {\mathcal F} \) from 1 to 2 in set tuples, i.e., from marks (U, Y) to double marks (U, V, Y). Paper 3 on the left above S3 further generalizes this into its Lemma 2.1 on p. 3. It re-increases the dimension from 2 to a sufficiently large constant g to show a claim similar to the double mark lemma. By this we can prove that there are three mutually disjoint sets included in \( {\mathcal F} \subset {X \choose m} \), not just a 3-sunflower, if it satisfies the \( \Gamma(b) \)-condition with b slightly greater than \( \sqrt m \). We’ll discuss this quite interesting topic much later in this blog series.
It takes a couple of preparations before we confirm the double mark lemma. The first one is about number estimation discussed in Section 1 of Paper S3. In this research, we estimate numbers with basic combinatorial identities such as the ones given on the bottom of p.1. Also it could be helpful if we approximate binomial coefficients asymptotically. I use the approximation (1): \( {n – k \choose m} \simeq {n \choose m} \exp \left( – \frac{mk}{n} \right) \) we saw in the 7/20 post all time in my investigations. We need a good approximation of \( {n-m \choose m-j} \) for \( j \le m \ll \sqrt n \) here.
By (1) with \( m^2 \ll n\), $$ {n-m \choose m-j} = {n- j – (m-j) \choose m-j} \simeq {n-j \choose m-j} e^{-\frac{(m-j)^2}{n-j}} \simeq {n-j \choose m-j} \left[ 1- \frac{(m-j)^2}{n-j} \right] \simeq {n-j \choose m-j}, $$ also due to the Taylor series \( e^{-x} = 1- x+ \frac{x^2}{2!} – \frac{x^3}{3!} + \cdots \). The RHS equals $$ \frac{m-j+1}{n-j+1} {n-j+1 \choose m-j+1} = \frac{(m-j+2)(m-j+1)}{(n-j+2)(n-j+1)} {n-j+2 \choose m-j+2} $$ $$ = \frac{m \cdots (m-j+2)(m-j+1)}{n \cdots (n-j+2)(n-j+1)} {n\choose m} \simeq \frac{ \prod_{i=0}^{j-1} (m-i)}{n^j} {n\choose m},$$ seen with the two notes:
- The identity \( {x \choose y} = \frac{x}{y}{x-1 \choose y-1} \) used in the first line is straightforward to see from the definition of \( {x \choose y} \).
- \( \prod_{i=0}^{j-1} (n-i) = j! {n \choose j} \simeq n^j \) by Stirling’s approximation \( j! \simeq \sqrt{2 \pi j} (j/e)^j \) and the standard estimate \( { n \choose j} \simeq \frac{1}{\sqrt{2 \pi j}} (en / j)^j \) of the binomial coefficient that can be derived from Lemma 1.1.
If we further assume \( j \ll \sqrt m \), the product \( \prod_{i=0}^{j-1} (m-i) \) in the numerator approximately equals \( m^j \) by the same reason, so $$ (2) \qquad {n-m \choose m-j} \simeq {n \choose m} \left( \frac{m}{n} \right)^j. $$
If j is not much less than \( \sqrt m \), the standard estimate of \({m \choose j} \) then becomes the inequality \( (m / j)^j \le {m \choose j} < (em / j)^j, \) for which (2) turns into \( {n-m \choose m-j} \simeq {n \choose m} \left[ m/ (cn) \right]^j \) where c is a number in [1, e) depending on \( j / m \). In this case, \( j \gg 1 \) because we always assume \( m \gg 1 \), so \( {n- m \choose m-j} \) is far smaller than \( { n \choose m}, \) whose contribution to \( | {\mathcal D}| \) we’ll find is only trivial. Hence, we just assume (2) in our intuitive understanding of the double mark lemma.
For the exact proof, we use Lemma 1.2 saying for \( 0 \le j \le m \ll \sqrt n, \) $$ (3) \qquad \ln {n-m \choose m-j} = \ln {n \choose m} – j \left( \ln \frac{m}{n} + 1 \right) – \left( m- j – \frac{1}{2} \right) \ln \left( 1 – \frac{j}{m} \right) + O(1), $$ for a number O(1) denoted asymptotically whose absolute value doesn’t exceed \( \frac{1}{4} + \frac{1}{2} \ln \frac{3}{2} = 0.4527 \ldots. \) This approximates \( {n -m \choose m-j} \) quite well in its logarithmic scale for all \( j \in [0, m] \).
Links for mobile devices