<p>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}$$.</p>

<p>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.</p>

CC BY-SA 3.0
2013-09-28T19:14:45.520Z
2013-09-28T19:34:04.537Z
2013-09-28T19:34:04.537Z
Igor Shinkar
<p>For the Inner Product function that quantity is $2^{n/2}$, which is the largest possible value.</p>

CC BY-SA 3.0
2016-05-09T20:59:48.133Z
Is that easy to prove?
Thomas Ahle
CC BY-SA 3.0
2016-05-17T10:35:55.027Z
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
CC BY-SA 3.0
2016-05-17T11:15:17.620Z
Sorry, I meant that the inner product function achieves the bound.
Thomas Ahle
CC BY-SA 3.0
2013-03-20T12:59:42.133Z
2013-03-20T12:59:42.133Z
Manu
<p>Let $f: \{-1,1\}^n \rightarrow \{-1,1\}$ be a Boolean function.</p>

<p>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.</p>

<p>Let $d$ be the degree of the the Fourier expansion of $f$, i.e. 
$d= \max_{\widehat{f}(S)\neq 0} |S|$. </p>

<p>By Parseval's identity we have 
$$\sum_{S \subseteq [n]} \widehat{f}(S)^2=1$$</p>

<p>I am looking for a bound on<br>
$$\sum_{S \subseteq [n]} |\widehat{f}(S)|$$</p>

<p>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?</p>

CC BY-SA 3.0
2013-03-04T11:21:46.353Z
atleast an idea is great for me
Kumar
CC BY-SA 3.0
2013-03-04T13:23:52.870Z
What is $d$?  For the Inner Product function that quantity is $2^{n/2}$, which is the largest possible value.
Manu
CC BY-SA 3.0
2013-03-04T13:49:37.507Z
where $d$ is the degree of $f$ in the Fourier expansion of $f$. i.e., 
d= max {$|S| / \widehat{f}(S)$ $\neq 0$ }
Kumar
CC BY-SA 3.0
2013-03-04T13:58:44.690Z
for example $f: \{-1,1\}^3 \rightarrow \{-1,1\}$. $f=Majority$ 

then 

$f(x)= \frac{1}{2}x_1+\frac{1}{2}x_2+\frac{1}{2}x_3+\frac{1}{2}x_1x_2x_3$ 

Here degree of $f$ is $3$.
Kumar
CC BY-SA 3.0
2013-03-04T20:00:18.153Z
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 (http://arxiv.org/pdf/math/0605524v2.pdf).
arnab
CC BY-SA 3.0
2013-03-04T22:33:35.987Z
This quantity can be as large as $\sqrt{2^n}$ (as others point out), or as small as $1$ (e.g., any parity). Does that close the question?
Mahdi Cheraghchi
CC BY-SA 3.0
2013-03-05T01:21:45.593Z
@arnab: my understanding is that we are interested in the inverse question, i.e. given a Boolean function, is there some property of it that allows us to bound the spectral norm?
usul
CC BY-SA 3.0
2013-03-05T04:51:37.987Z
By using Cauchy-Schwarz inequality I got the upper bound $2^{n/2}$. My question is whether it is bounded by degree $d$ of the Fourier expansion of $f$. I had tried with many examples and for all of those I got  $\sum_{S \subseteq[n]} |\widehat{f}(S)| \leq d$, I am trying to prove this, but I have no idea.
Kumar
CC BY-SA 3.0
2013-03-05T20:11:36.340Z
$d$ is a number between $0$ and $n$, so obviously it can never be as large as $2^{n/2}$.
Mahdi Cheraghchi
CC BY-SA 3.0
2013-03-12T23:24:03.083Z
@Emanuele, could you please post your comment as an answer so the question becomes answered?
Kaveh
CC BY-SA 3.0
2013-03-13T00:28:13.703Z
@EmanueleViola yes please post your comment as an answer.
Suresh Venkat
CC BY-SA 3.0
2013-03-13T14:06:37.100Z
@arnab but we could give a bound in terms of $d$, right? For example, per Thm 4 [here](http://www.contrib.andrew.cmu.edu/~ryanod/?p=535), 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
CC BY-SA 3.0
2013-03-14T05:20:38.490Z
@SashoNikolov: You are right. Bounding the spectral norm in terms of $d$ is an interesting question (though the questioner was asking if $d$ itself is a bound).
arnab
<co.combinatorics><boolean-functions><fourier-analysis>
Is the the spectral norm of a Boolean function bounded by the degree of its Fourier expansion?
Kumar
# Is the the spectral norm of a Boolean function bounded by the degree of its Fourier expansion?

(Asked by: username_0 on 2013-03-04)

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?

**Tags:** co.combinatorics, boolean-functions, fourier-analysis
> **Comments:**
> **username_0**: atleast an idea is great for me  
> **username_1**: What is $d$?  For the Inner Product function that quantity is $2^{n/2}$, which is the largest possible value.  
> **username_0**: where $d$ is the degree of $f$ in the Fourier expansion of $f$. i.e.,  d= max {$|S| / \widehat{f}(S)$ $\neq 0$ }  
> **username_0**: for example $f: \{-1,1\}^3 \rightarrow \{-1,1\}$. $f=Majority$   then   $f(x)= \frac{1}{2}x_1+\frac{1}{2}x_2+\frac{1}{2}x_3+\frac{1}{2}x_1x_2x_3$   Here degree of $f$ is $3$.  
> **username_2**: 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 (http://arxiv.org/pdf/math/0605524v2.pdf).  
> **username_3**: This quantity can be as large as $\sqrt{2^n}$ (as others point out), or as small as $1$ (e.g., any parity). Does that close the question?  
> **username_4**: @arnab: my understanding is that we are interested in the inverse question, i.e. given a Boolean function, is there some property of it that allows us to bound the spectral norm?  
> **username_0**: By using Cauchy-Schwarz inequality I got the upper bound $2^{n/2}$. My question is whether it is bounded by degree $d$ of the Fourier expansion of $f$. I had tried with many examples and for all of those I got  $\sum_{S \subseteq[n]} |\widehat{f}(S)| \leq d$, I am trying to prove this, but I have no idea.  
> **username_3**: $d$ is a number between $0$ and $n$, so obviously it can never be as large as $2^{n/2}$.  
> **username_5**: @Emanuele, could you please post your comment as an answer so the question becomes answered?  
> **username_6**: @EmanueleViola yes please post your comment as an answer.  
> **username_7**: @arnab but we could give a bound in terms of $d$, right? For example, per Thm 4 [here](http://www.contrib.andrew.cmu.edu/~ryanod/?p=535), 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?  
> **username_2**: @SashoNikolov: You are right. Bounding the spectral norm in terms of $d$ is an interesting question (though the questioner was asking if $d$ itself is a bound).  

---

## 2 answers

### Answer by username_8 on 2013-09-28. Score: 3 | Accepted answer

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.


---

### Answer by username_1 on 2013-03-20. Score: 2

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

> **Comments:**
> **username_9**: Is that easy to prove?  
> **username_1**: 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.  
> **username_9**: Sorry, I meant that the inner product function achieves the bound.  

---

