In Ryan O'Donnell's book Analysis of Boolean functions, following Corollary 9.25 the following appears:

If $f\colon \{-1,1\}^n \to \{0,1\}$, and we have $\mathbb{E}[f] = \alpha$, then for any integer $k$ at most $2\ln \frac{1}{\alpha}$, we have $W^{\leq k}[f] \leq \rho^{-k}\alpha^{2(1-\rho)}$. He then deduces the following corollary:

If $\epsilon > 0$ and $k_\epsilon = 2(1-\epsilon)\ln \frac{1}{\alpha}$, then $W^{\leq k_\epsilon}[f] \leq \alpha^{\epsilon^2}$

My question is isn't this bound meaningless?

Indeed, we have

$W^{\leq k_\epsilon}[f] \leq \lVert f\rVert_2^2 = \alpha \ll \alpha^{\epsilon^2}$

  • $\begingroup$ For $0 < \epsilon < 1$, we have $a^{\epsilon^2} \ll a$, not the other way around. $\endgroup$ Commented Oct 18, 2019 at 20:41
  • $\begingroup$ @RobertAndrews But $a<1$... $\endgroup$
    – Andy
    Commented Oct 18, 2019 at 21:12
  • $\begingroup$ My mistake, I completely missed that. $\endgroup$ Commented Oct 18, 2019 at 21:32
  • 1
    $\begingroup$ @Andy Well, there is some magic number $c$ (roughly, $c\approx 1.582$) such that, setting $$k_\varepsilon = \frac{1}{c\ln(2e)}\cdot (1-\varepsilon)\ln\frac{1}{\alpha}$$ you get $$W^{\leq k_\varepsilon}[f] \leq \alpha^{1+\varepsilon-O(\varepsilon^2)}$$ $\endgroup$
    – Clement C.
    Commented Oct 19, 2019 at 0:05
  • 2
    $\begingroup$ The level $k$ inequality has been improved by Chin Ho Lee, Fourier Bounds and Pseudorandom Generators for Product Tests. See Lemma 10 here. $\endgroup$ Commented Oct 19, 2019 at 8:13

2 Answers 2


Just posting an answer in order to close the question.

See the helpful comments to the question which contain all the info;

  1. Yes it is vacuous, but if you use the stronger bound you get something nontrivial for large $\epsilon$, of course for fixed $k$ you also have interesting things, it's just the estimates in the book lose too much.

  2. Better bounds are known (thanks ot Yuval) : http://drops.dagstuhl.de/opus/volltexte/2019/10829/pdf/LIPIcs-CCC-2019-7.pdf

  • $\begingroup$ I'm not sure I agree with 2. As shown in my comment, the issue is not so much the tightness of the bounds used (although, of course, it cannot hurt to use the improved bound of Chin Ho Lee) as much as a bad choice of $k_\varepsilon$. Replace the leading constant $2$ in the current setting by some constant less than 1, you will get something non-vacuous. $\endgroup$
    – Clement C.
    Commented Oct 19, 2019 at 9:56
  • $\begingroup$ @ClementC. Yeah sure I wasn't phrasing myself well $\endgroup$
    – Andy
    Commented Oct 19, 2019 at 16:53

This statement has been removed from the latest version of the textbook and the referenced problem (9.19) has been updated to prove a weaker result instead.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.