<p>Given a $f: \{-1,1\}^n \rightarrow \mathbb{R}$, I want to compute this quantity, </p>

<p>$\sum_{ \hat{f}(S) \neq 0, S \subseteq 2^{[n]}} \vert S \vert $</p>

<p>i.e the sum of the sizes of the subsets of $[n]$ corresponding to the non-zero Fourier coefficients of the function. </p>

<ul>
<li>Is there a nice "analytic" form for this quantity? Anything is known about this? </li>
</ul>

CC BY-SA 3.0
2017-02-20T19:06:36.717Z
This is a very "discontinuous" quantity, as you can switch from zero to nonzero with an arbitrarily small change, so I doubt you will get a nice expression. What about something like $\sum_S \hat f(S)^2 |S|$? This is a continuous version of what you want. It is called the total influence and has a variety of properties.
Thomas Steinke
CC BY-SA 3.0
2017-02-20T20:03:04.517Z
Yeah. Your quantity is more standard. I want to somehow analyze this sum without that Fourier weighting. Any "nice" way to set all the $\hat{f}(S)$ to $1$ whenever $\hat{f}(S) \neq 0$?
gradstudent
CC BY-SA 3.0
2017-02-20T20:14:38.550Z
@Thomas The point you raise is interesting - do we know any characterization of what kind of small changes will turn on a specific Fourier mode?
gradstudent
CC BY-SA 3.0
2017-02-20T22:55:02.460Z
Another commonly studied property is Fourier sparsity, which is $\sum_{\hat{f}(S) \neq \emptyset} 1$. Perhaps you can somehow relate the two.
Yuval Filmus
CC BY-SA 3.0
2017-02-21T14:10:08.587Z
Well, since the Fourier basis is a linear basis, the condition for a coefficient to be zero is a linear condition. So although your quantity is discontinuous, it is still lower semi-continuous (analogous to the rank of a matrix). If you want to know what changes to a circuit will "turn on" a given Fourier mode, however, that sounds quite tricky and probably doesn't have a clean characterization.
Joshua Grochow
CC BY-SA 3.0
2017-02-21T20:07:29.013Z
@YuvalFilmus That has been one of my ideas. If the notion of Fourier sparsity helps here. But I don't see a "nice" way to implement something like "set to $1$ all the non-zero Fourier coefficients". If this could be done then one could take the corresponding Fourier indicator like you write and compute its $p-$stability and take its derivative at $p=1$ and that would give my sum. No idea if this can be analyzed! Are there bounds on the Fourier sparsity based on properties of the function?
gradstudent
CC BY-SA 3.0
2017-02-21T20:09:38.953Z
@JoshuaGrochow Thanks for the comment! This is something I was thinking of only today! Do we have any relationship between how many or which Fourier coefficients are active and the circuit topology?
gradstudent
<cc.complexity-theory><boolean-functions><fourier-analysis>
About counting the "total size" of non-zero Fourier coefficients of a Boolean function
gradstudent
# About counting the "total size" of non-zero Fourier coefficients of a Boolean function

(Asked by: username_0 on 2017-02-20)

Given a $f: \{-1,1\}^n \rightarrow \mathbb{R}$, I want to compute this quantity,

$\sum\_{ \hat{f}(S) \neq 0, S \subseteq 2^{[n]}} \vert S \vert $

i.e the sum of the sizes of the subsets of $[n]$ corresponding to the non-zero Fourier coefficients of the function.

* Is there a nice "analytic" form for this quantity? Anything is known about this?

**Tags:** cc.complexity-theory, boolean-functions, fourier-analysis
> **Comments:**
> **username_1**: This is a very "discontinuous" quantity, as you can switch from zero to nonzero with an arbitrarily small change, so I doubt you will get a nice expression. What about something like $\sum_S \hat f(S)^2 |S|$? This is a continuous version of what you want. It is called the total influence and has a variety of properties.  
> **username_0**: Yeah. Your quantity is more standard. I want to somehow analyze this sum without that Fourier weighting. Any "nice" way to set all the $\hat{f}(S)$ to $1$ whenever $\hat{f}(S) \neq 0$?  
> **username_0**: @Thomas The point you raise is interesting - do we know any characterization of what kind of small changes will turn on a specific Fourier mode?  
> **username_2**: Another commonly studied property is Fourier sparsity, which is $\sum_{\hat{f}(S) \neq \emptyset} 1$. Perhaps you can somehow relate the two.  
> **username_3**: Well, since the Fourier basis is a linear basis, the condition for a coefficient to be zero is a linear condition. So although your quantity is discontinuous, it is still lower semi-continuous (analogous to the rank of a matrix). If you want to know what changes to a circuit will "turn on" a given Fourier mode, however, that sounds quite tricky and probably doesn't have a clean characterization.  
> **username_0**: @YuvalFilmus That has been one of my ideas. If the notion of Fourier sparsity helps here. But I don't see a "nice" way to implement something like "set to $1$ all the non-zero Fourier coefficients". If this could be done then one could take the corresponding Fourier indicator like you write and compute its $p-$stability and take its derivative at $p=1$ and that would give my sum. No idea if this can be analyzed! Are there bounds on the Fourier sparsity based on properties of the function?  
> **username_0**: @JoshuaGrochow Thanks for the comment! This is something I was thinking of only today! Do we have any relationship between how many or which Fourier coefficients are active and the circuit topology?  

---

## 0 answers

