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?

Improve this question
$\endgroup$
13
  • 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, 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
    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
    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$
    – Mahdi Cheraghchi
    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$
    – Sasho Nikolov
    Mar 13, 2013 at 14:06

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
1
$\begingroup$

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

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

Your Answer

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

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