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?

  • 4
    $\begingroup$ What is $d$? For the Inner Product function that quantity is $2^{n/2}$, which is the largest possible value. $\endgroup$
    – Manu
    Commented Mar 4, 2013 at 13:23
  • 1
    $\begingroup$ where $d$ is the degree of $f$ in the Fourier expansion of $f$. i.e., d= max {$|S| / \widehat{f}(S)$ $\neq 0$ } $\endgroup$
    – Kumar
    Commented Mar 4, 2013 at 13:49
  • 3
    $\begingroup$ 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). $\endgroup$
    – arnab
    Commented Mar 4, 2013 at 20:00
  • 3
    $\begingroup$ $d$ is a number between $0$ and $n$, so obviously it can never be as large as $2^{n/2}$. $\endgroup$ Commented Mar 5, 2013 at 20:11
  • 2
    $\begingroup$ @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? $\endgroup$ Commented Mar 13, 2013 at 14:06

2 Answers 2


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.

  • $\begingroup$ Is that easy to prove? $\endgroup$ Commented May 9, 2016 at 20:59
  • $\begingroup$ 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. $\endgroup$
    – Manu
    Commented May 17, 2016 at 10:35
  • $\begingroup$ Sorry, I meant that the inner product function achieves the bound. $\endgroup$ Commented May 17, 2016 at 11:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.