Given a boolean function $f:\left\{-1,1\right\}^n\to\left\{-1,1\right\}$, we define its fourier coefficients as $$\hat{f}\left(S\right)=\frac{1}{2^n}\sum_{x\in\left\{-1,1\right\}^n}f\left(x\right)\prod_{i\in S}x_i$$ for any $S\subseteq\left[n\right]=\left\{1,2,\dots,n\right\}$.
I want to prove that if a boolean function $f$ has degree $k$ (that is, $\max\left\{\left|S\right|\middle|\hat{f}\left(S\right)\neq 0\right\}=k$), then $$\sum_{S}\left|\hat{f}\left(S\right)\right|\leq 2^{k-1}$$ (this is from exercise 1.11(c) from Ryan O'donnell's book). Any hints / suggestions?
What I've tried:
- Induction on $n$ doesn't seem to be helpful. If you write $f=f_1+x_nf_2$, where $f_i$ is independent of $x_n$, their degrees may still be $k$, and induction will not help.
- Also induction on $k$ doesn't seem helpful. There is no obvious reduction from $k+1$ to $k$.
- By the context of the exercise, I also tried to use the relation between the fourier expansion of $f$ and its expansion as a multilinear polynomial over $\left\{0,1\right\}^n$, still without success.