Let $f: \{-1,1\}^n \rightarrow \{-1,1\}$ be a Boolean function.The Fourier expansion of $f$ is$$f(T) = \sum_{S \subseteq [n]} \widehat{f}(S)\ \chi_S(T)$$ where $\widehat{f}(S)$ are real numbers and $\chi_S(T)=\Pi_{i \in S} T_i$ is a parity function.Let $d$ be the degree of the the Fourier expansion of $f$, i.e. $d= \max_{\widehat{f}(S)\neq 0} |S|$. By Parseval's identity we have $$\sum_{S \subseteq [n]} \widehat{f}(S)^2=1$$I am looking for a bound on$$\sum_{S \subseteq [n]} |\widehat{f}(S)|$$I think it is bounded by $d$.But I have neither a proof nor a counterexample for this claim. Can someone provide a proof or give a counterexample?
Is the the spectral norm of a Boolean function bounded by the degree of its Fourier expansion?
co.combinatorics;boolean functions;fourier analysis
It is a standard fact that if $f:\{-,1,1\}^n \to \{-1,1\}$ is a function of Fourier degree $d$, then its Fourier coefficients are multiples of $2^{-d+1}$. In particular, every non-zero coefficient must be at least $2^{-d+1}$ in absolute value. Therefore, by Parseval, there are at most $2^{2(d-1)}$ non-zero coefficients, and so the spectral norm of $f$ is at most$$\sum_{S}|\hat{f}(S)| \leq \sqrt{2^{2(d-1)}}\sqrt{\sum_{S}\hat{f}(S)^2} = 2^{d-1}$$.This bound is tight. For example the complete binary decision tree of depth $d$ has spectral norm $2^{d-1}$. This can be shown, e.g., by induction on $d$.The address function has also maximal possible spectral norm.