1

I am trying to solve exercise 1.29(a) from Ryan ODonell's Analysis of Boolean Functions which says that given $ f:\mathbb{F}_{2}^{n} \rightarrow\{-1,1\} $ such that $ dist(f,\chi_{S^{*}})=\delta $ for some $ S^{*} \subseteq \{1,2,...,n\}$where $ dist(f,g)=\mathbb{Pr}_{x}(f(x) \neq g(x) ) $ and $ \chi_{S}(x)=\prod_{i \in S}x_{i} \, \forall x \in \mathbb{F}_{2}^{n} $ , prove that $ |\widehat{f}(S)| \leq 2 \delta $ for all $ S \subseteq \{1,2,...,n \}, S \neq S^{*} $.

Here $ \widehat{f}(S) $ denotes the Fourier coefficient of $ f $ on $ S $ given by $\widehat{f}(S)=<f,\chi_{S}>=\frac{1}{2^{n}}\sum_{x \in\mathbb{F}_{2}^{n}}f(x)\chi_{S}(x) $.

So suppose that $ \exists S \neq S^{*} $ such that $ |\widehat{f}(S)| > 2 \delta $. We know that $ \widehat{f}(S^{*})=<f,\chi_{S^{*}}>=1-2dist(f,\chi_{S^{*}}) =1-2\delta $. How can I then use the union bound to prove the claim?

I would appreciate any ideas and suggestions. Thank you!

Andrei
  • 1,073

1 Answers1

1

By the Reverse Triangle inequality, for all $S\neq S^*$, $$ \text{dist}(f,\chi_S)\geq \text{dist}(\chi_{S^*},\chi_S)-\text{dist}(\chi_{S^*},f)=\frac{1}{2}-\delta. $$ Using the expression for Fourier coefficients that you wrote: $$ \vert \hat{f}(S^*)\vert=1-2\text{dist}(f,\chi_{S^*})\leq 1-2(1/2-\delta)=2\delta. $$

J.G
  • 5,084