# Is the the spectral norm of a Boolean function bounded by the degree of its Fourier expansion?

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?

• What is $d$? For the Inner Product function that quantity is $2^{n/2}$, which is the largest possible value. – Manu Mar 4 '13 at 13:23
• where $d$ is the degree of $f$ in the Fourier expansion of $f$. i.e., d= max {$|S| / \widehat{f}(S)$ $\neq 0$ } – Kumar Mar 4 '13 at 13:49
• Inner product function has very large spectral norm, $2^{n/2}$, as Emanuele already said. The much more interesting question is to come up with Boolean functions with small spectral norm. For a characterization of Boolean functions of spectral norm $\leq M$, see the very nice paper by Green and Sanders (arxiv.org/pdf/math/0605524v2.pdf). – arnab Mar 4 '13 at 20:00
• $d$ is a number between $0$ and $n$, so obviously it can never be as large as $2^{n/2}$. – MCH Mar 5 '13 at 20:11
• @arnab but we could give a bound in terms of $d$, right? For example, per Thm 4 here, degree $d$ boolean functions are $d2^{d-1}$ juntas, which implies roughly a $2^{d2^{d-2}}$ bound on the spectral norm. is this tight for small $d$? or did i misunderstand something? – Sasho Nikolov Mar 13 '13 at 14:06

## 2 Answers

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.

For the Inner Product function that quantity is $2^{n/2}$, which is the largest possible value.

• Is that easy to prove? – Thomas Ahle May 9 '16 at 20:59
• Are you asking why that is the largest possible value? It follows by Cauchy Schwarz: $\sum_i a_i \cdot b_i \le \sqrt{\sum_i a_i^2} \sqrt{\sum_i b_i^2}$. Let $b_i = 1$ and $a_i$ be the Fourier coefficients. – Manu May 17 '16 at 10:35
• Sorry, I meant that the inner product function achieves the bound. – Thomas Ahle May 17 '16 at 11:15