# Level $k$ bounds in Analysis of Boolean functions

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}$$

• For $0 < \epsilon < 1$, we have $a^{\epsilon^2} \ll a$, not the other way around. – Robert Andrews Oct 18 '19 at 20:41
• @RobertAndrews But $a<1$... – Andy Oct 18 '19 at 21:12
• My mistake, I completely missed that. – Robert Andrews Oct 18 '19 at 21:32
• @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)}$$ – Clement C. Oct 19 '19 at 0:05
• The level $k$ inequality has been improved by Chin Ho Lee, Fourier Bounds and Pseudorandom Generators for Product Tests. See Lemma 10 here. – Yuval Filmus Oct 19 '19 at 8:13

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.
• 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. – Clement C. Oct 19 '19 at 9:56