# About counting the “total size” of non-zero Fourier coefficients of a Boolean function

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.

• 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 Feb 20 '17 at 19:06
• 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 Feb 20 '17 at 20:03
• 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 Feb 20 '17 at 22:55