6
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ What is $d$? For the Inner Product function that quantity is $2^{n/2}$, which is the largest possible value. $\endgroup$ – Manu Mar 4 '13 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 Mar 4 '13 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 Mar 4 '13 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$ – MCH Mar 5 '13 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$ – Sasho Nikolov Mar 13 '13 at 14:06
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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