# 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.

• Is there a nice "analytic" form for this quantity? Anything is known about this?
• 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
• @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 Feb 20 '17 at 20:14
• 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
• 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 Feb 21 '17 at 14:10