<p>Just posting an answer in order to close the question.</p>

<p>See the helpful comments to the question which contain all the info;</p>

<ol>
<li><p>Yes it is vacuous, but if you use the stronger bound you get something nontrivial for large <span class="math-container">$\epsilon$</span>, of course for fixed <span class="math-container">$k$</span> you also have interesting things, it's just the estimates in the book lose too much.</p></li>
<li><p>Better bounds are known (thanks ot Yuval) : <a href="http://drops.dagstuhl.de/opus/volltexte/2019/10829/pdf/LIPIcs-CCC-2019-7.pdf" rel="nofollow noreferrer">http://drops.dagstuhl.de/opus/volltexte/2019/10829/pdf/LIPIcs-CCC-2019-7.pdf</a></p></li>
</ol>

CC BY-SA 4.0
2019-10-19T09:56:48.693Z
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.
CC BY-SA 4.0
2019-10-19T16:53:38.143Z
@ClementC. Yeah sure I wasn't phrasing myself well
Andy
CC BY-SA 4.0
2019-10-19T09:29:10.137Z
2019-10-23T09:14:22.997Z
2019-10-23T09:14:22.997Z
Andy
<p>This statement has been removed from the <a href="https://arxiv.org/pdf/2105.10386.pdf" rel="nofollow noreferrer">latest version of the textbook</a> and the referenced problem (9.19) has been updated to prove a weaker result instead.</p>

CC BY-SA 4.0
2023-12-20T23:26:39.503Z
2023-12-27T11:21:51.557Z
2023-12-27T11:21:51.557Z
user3919899
<p>In Ryan O'Donnell's book <em>Analysis of Boolean functions</em>, following Corollary 9.25 the following appears:</p>

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

<blockquote>
  <p>If <span class="math-container">$\epsilon &gt; 0$</span> and <span class="math-container">$k_\epsilon = 2(1-\epsilon)\ln \frac{1}{\alpha}$</span>, then 
  <span class="math-container">$W^{\leq k_\epsilon}[f] \leq \alpha^{\epsilon^2}$</span></p>
</blockquote>

<p>My question is isn't this bound meaningless?</p>

<p>Indeed, we have</p>

<p><span class="math-container">$W^{\leq k_\epsilon}[f] \leq \lVert f\rVert_2^2 = \alpha \ll \alpha^{\epsilon^2}$</span></p>

CC BY-SA 4.0
2019-10-18T20:41:11.020Z
For $0 < \epsilon < 1$, we have $a^{\epsilon^2} \ll a$, not the other way around.
Robert Andrews
CC BY-SA 4.0
2019-10-18T21:12:26.323Z
@RobertAndrews But $a<1$...
Andy
CC BY-SA 4.0
2019-10-18T21:32:31.653Z
My mistake, I completely missed that.
Robert Andrews
CC BY-SA 4.0
2019-10-18T23:16:12.410Z
I may be very confused, but that seems right — the bound looks vacuous, unless I am missing something as well. If you're right, however, the actual bound obtained (see Exercise 9.19) is $$2(\varepsilon+(1-\varepsilon)\ln(1-\varepsilon))$$which is non-vacuous (greater than $1$) when $\varepsilon\geq 0.81$.
Clement C.
CC BY-SA 4.0
2019-10-18T23:22:39.707Z
@ClementC. I agree, but it kinda of suck we don't have a workable estimate for the full range of $\epsilon$, i.e you get interesting stuff both for $\epsilon$ close to $1$, and for constant $k$. I guess if I'm not missing something someone should answer so we can close the question
Andy
CC BY-SA 4.0
2019-10-19T00:05:06.267Z
@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.
CC BY-SA 4.0
2019-10-19T08:13:17.970Z
The level $k$ inequality has been improved by Chin Ho Lee, Fourier Bounds and Pseudorandom Generators for
Product Tests. See Lemma 10 [here](http://drops.dagstuhl.de/opus/volltexte/2019/10829/pdf/LIPIcs-CCC-2019-7.pdf).
Yuval Filmus
<co.combinatorics><boolean-functions><fourier-analysis>
Level $k$ bounds in Analysis of Boolean functions
Andy
# Level $k$ bounds in Analysis of Boolean functions

(Asked by: username_0 on 2019-10-18)

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

**Tags:** co.combinatorics, boolean-functions, fourier-analysis

> **Comments:**
> **username_1**: For $0 < \epsilon < 1$, we have $a^{\epsilon^2} \ll a$, not the other way around.  
> **username_0**: @RobertAndrews But $a<1$...  
> **username_1**: My mistake, I completely missed that.  
> **username_2**: I may be very confused, but that seems right — the bound looks vacuous, unless I am missing something as well. If you're right, however, the actual bound obtained (see Exercise 9.19) is $$2(\varepsilon+(1-\varepsilon)\ln(1-\varepsilon))$$which is non-vacuous (greater than $1$) when $\varepsilon\geq 0.81$.  
> **username_0**: @ClementC. I agree, but it kinda of suck we don't have a workable estimate for the full range of $\epsilon$, i.e you get interesting stuff both for $\epsilon$ close to $1$, and for constant $k$. I guess if I'm not missing something someone should answer so we can close the question  
> **username_2**: @username_0 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)}$$  
> **username_3**: The level $k$ inequality has been improved by Chin Ho Lee, Fourier Bounds and Pseudorandom Generators for Product Tests. See Lemma 10 [here](http://drops.dagstuhl.de/opus/volltexte/2019/10829/pdf/LIPIcs-CCC-2019-7.pdf).  

---

## 2 answers

### Answer by username_0 on 2019-10-19. Score: 2 | Accepted answer

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>

> **Comments:**
> **username_2**: 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.  
> **username_0**: @ClementC. Yeah sure I wasn't phrasing myself well  

---

### Answer by username_4 on 2023-12-20. Score: 1

This statement has been removed from the [latest version of the textbook](https://arxiv.org/pdf/2105.10386.pdf) and the referenced problem (9.19) has been updated to prove a weaker result instead.


---

