5
$\begingroup$

I have been reading 'Improved bounds for the sunflower lemma' by Alweiss, Lovett, Wu and Zhang (Ann. of Math., Vol. 194(3), 2021), and have some gaps in my understanding of the paper. They are as follows:

  1. In Lemma: 2.8 (pg. 802), the authors bound the number of bad pairs $(W,S_{i})$ by a product of four bounds obtained earlier- (i) the bound on the number of sets of the form $W \cup S_{i}$, (ii) the number of sets of the form $A = S_{i} \cap S_{j}$ (once $S_{j}$ is chosen and fixed in a certain manner), (iii) the number of sets in $\mathcal{F}^{'}$ that contain the set $A$, and (iv) the number of sets of the form $S_{i} \cap W$. Each of the bounds in i)-iv) are clear to me, but I am unable to understand how the product is indeed a bound for the number of bad pairs, both heuristically and in terms of constructing an injection from the set of bad pairs into the set encoded as above.
  2. In Lemma 2.10 (pg. 803), a new weighting $\sigma^{'}$ is defined on $\mathcal{F}^{'}$. Am I right in thinking that $\forall \, S \, \in F^{'}: \sigma^{'}(S) = 1$? In this case, the spreadness criteria seems to go through. If not, how is $\sigma^{'}$ defined explicitly?
  3. On pg. 804, the authors construct a recursively-defined, strictly-decreasing sequence of integers, $(w_{i})_{i =1}^{r}$, with $w_{i+1} = \lfloor (1 - \varepsilon)w_{i} \rfloor + 1$ for some small, fixed $\varepsilon$, uniformly bounded below by $w^{*}.$ It can be shown that $w^{*} \geq \frac{1}{\varepsilon}$. The authors claim that $\exists K > 0: r \leq \frac{K \, \log(w)}{\varepsilon}.$ I am unable to prove this remark, and would prefer, if possible, a constructive proof.
    My Attempt: Here are some observations, which don't seem to lead to a proof of what is required. We have that $w_{i} \geq (1 - \varepsilon)^{i}w.$ Moreover, we have that $w_{i} - w_{i+1} \geq \varepsilon w_{i} - 1,$ and hence, we also have that $$w_{i} - w_{i + 1} \geq \varepsilon w_{r} - 1 \geq \varepsilon w^{*} - 1.$$ Thus, the distance between each pair of successive terms is at least $\varepsilon w^{*} - 1$, and so, assuming that this is positive, the number of integers in the sequence, i.e., $r$ is bounded above by $$\frac{w - w^{*} + 1}{\varepsilon w^{*} - 1}.$$ We also observe that $$1 \leq w_{i} - w_{i + 1} \leq \varepsilon w_{i} \leq \varepsilon w_{0} = \varepsilon w,$$ and hence, a lower bound for $r$ is $$\frac{w - w^{*} + 1}{\varepsilon w}.$$
  4. On pg. 808, the proof of Theorem: 4.2 concludes by stating that $\mathcal{F}$ cannot be $C \, \log(w)$ spread for large enough $C$. This apparently follows from the improved version of Theorem 2.5 from Rao's paper (also proved independently by Tao). Below is my argument- I am not certain that it is correct.

Any help on any or all of these questions is appreciated.

Edit: I would especially appreciate any insights regarding the first question, even if you don't have the time to answer the others.

$\endgroup$
7
  • 3
    $\begingroup$ Have you tried to contact the authors? If not, don't be shy, just contact them. $\endgroup$
    – GH from MO
    Dec 5, 2021 at 20:41
  • 2
    $\begingroup$ @GHfromMO In this particular journal, authors are generally expected to leave a lot to the reader. Most the omitted stuff should be "trivial" to some but definitely not to all. MathOverflow is a perfectly reasonable place to ask about such details. That said, it's usually better to ask one question at a time but since they are evidently related there isn't much harm asking them all at once. $\endgroup$ Dec 5, 2021 at 23:36
  • 2
    $\begingroup$ @FrançoisG.Dorais: I did not mean that it was unreasonable to ask these questions here. I just tried to help the OP by giving another reasonable way: ask the authors. BTW I don't think that the authors of the Annals are expected to exercise different standards in terms of detail and clarity. $\endgroup$
    – GH from MO
    Dec 6, 2021 at 0:34
  • 1
    $\begingroup$ This should be linked: mathoverflow.net/questions/409526/… $\endgroup$
    – domotorp
    Dec 6, 2021 at 7:59
  • 3
    $\begingroup$ @GHfromMO Posting on MO turned out to be an efficient way of contacting the authors, it seems. $\endgroup$ Dec 7, 2021 at 9:25

1 Answer 1

6
$\begingroup$

Let me try to answer your questions.

  1. We can recover the pair $(W, S_i)$ from the four quantities you mentioned. So the number of their combinations upper bounds the number of pairs $(W, S_{i})$, which is why we multiply the number of options for each one.

  2. Indeed, we switch from a set system with not necessarily uniform weights to a multi set system with uniform weights to simplify the proof.

  3. You are asking for a constructive proof. Assume that $w_{i} \geq \frac{2}{\varepsilon}$. Then $w_{i+1} \leq (1 - \varepsilon) w_{i} + 1 \leq (1-\frac{\varepsilon}{2}) w_{i}$. So you reach $w_{i} < \frac{2}{\varepsilon}$ after at most $O\left(\frac{\log w}{\varepsilon}\right)$ steps.

  4. I don't understand your question. If you replace our Theorem 2.5 with Rao's result it removes all the $\log\log$ terms we have, which is the point we are making.

$\endgroup$
2
  • $\begingroup$ Thank you for your response. I still have the following questions: (1) The recovery of the pair $(W,S_i)$ from the sets is the part of the proof I am unable to get the intuition for. More concretely, I am unable to construct an injective map from $(W,S_i)$ into $\{(A,B,C,D):A−D \textrm{ are sets as in i)−iv respectively})\}$. (2) I understand that $\sigma'$ is a uniform weight function, but wanted to confirm that the specific weight function you use in the paper is indeed the constant $1$ function. $\endgroup$
    – user469866
    Dec 7, 2021 at 12:18
  • 1
    $\begingroup$ 1. The quantities A,B,C,D are functions of (W,S_i), and we give in the paper a (simple) algorithm to reconstruct (W,S_i) from A,B,C,D. This shows that the natural map from (W,S_i) to (A,B,C,D) is injective. 2. Yes, uniform means all equal to 1 in this case $\endgroup$
    – Shachar
    Dec 8, 2021 at 3:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.