# Finding an $\epsilon$-concentrated collection with size in terms of spectral $1$-norm

$$\newcommand{\R}{\mathbb{R}}$$ This question is about Problem 3.16 in Ryan O'Donnell's Analysis of Boolean Functions book. The problem is stated as follows:

Let $$f : \{-1,1\}^n\to\R$$ and let $$\epsilon>0$$. Show that $$f$$ is $$\epsilon$$-concentrated on a collection $$F\subseteq 2^{[n]}$$ with $$|F|\leq \hat{||}f\hat{||}_1^2/\epsilon$$.

Here, $$\hat{||}f\hat{||}_1 := \sum_{S\subseteq [n]} |\widehat{f}(S)|$$, and $$f$$ being $$\epsilon$$-concentrated on $$F$$ means $$\sum_{S\notin F} \widehat{f}(S)^2 \leq \epsilon$$. I have tried several approaches for this problem, and all seem to run into the pitfall of relating $$\hat{||}f\hat{||}_1^2$$ to $$||f||_2$$ (equivalently $$\hat{||}f\hat{||}_2$$ by Parseval's) in any nontrivial way. The most fruitful approach was using a probabilistic method: randomly sampling $$|\widehat{f}(S)|$$ uniformly over $$S$$, bounding the variance of this random variable, and applying Chebyshev's. But since $$\mathbf{E}[|\widehat{f}(S)|]$$ might be large and Chebyshev's only dictates deviation from the expectation, I don't think this approach yields the desired concentration bound. Would appreciate any hints or insight!

Edit: I was eventually able to find a solution. As a hint, start by constructing a reasonable set $$F$$ which trivially satisfies $$|F|\leq \hat{||}f\hat{||}_1^2/\epsilon$$. To prove $$\epsilon$$-concentration, recall the fairly simple technique used to bound $$\sum \widehat{g}(S)^3$$ in the analysis for the BLR test (Section 1.6 in Analysis of Boolean Functions).

Hint: find a random variable $$X=X(S)$$ such that $$\mathbf{E}[X]=\hat{||}f\hat{||}_1$$ where the expectation is under the spectral sample. Use this to apply Markov to find an appropriate set with Fourier mass at least $$1-\epsilon$$, and then argue that the size of the set must be at most the claimed cardinality.
• Thanks for responding, just have a quick question. This approach seems to be assuming that the function is Boolean valued (so that total Fourier mass is equal to 1). Does scaling by $||f||_2^2$ give the same result for real-valued functions?
Here is a direct construction: $$F = \left\{S:|\hat{f}(S)|\ge \frac{\epsilon}{\hat{\|}f\hat{\|}_1}\right\}$$ And you can verify the two conditions.