# Sparsity of a Boolean function and its Fourier depth [closed]

For a function $f : \{-1,1\}^n \rightarrow \mathbb{R}$ one can ask for its $l_0$ norm in the indicator basis i.e the number of vertices on which the function is non-zero. Does this sparsity parameter have any bearing (or the otherway) on how large can the largest non-zero term be in its Fourier expansion?

• Of course it does not..$f$ and $2^{2^{n}}f$ have the same sparsity in any basis. Feb 11, 2017 at 22:20
• Your questions should demonstrate some minimal understanding of the subject matter. A question of this type is more appropriate at Math.SE if anywhere. Feb 11, 2017 at 22:22
• @SashoNikolov I did not understand your objection to the question I asked. Maybe my wording isn't clear. Can you please check the comment I made below Areyh's answer. Just in case my clarification helps! Feb 12, 2017 at 1:35
• Your wording indeed seems unclear. "[L]argest non-zero term" to me means largest in absolute value. This clearly has no connection to sparsity. Are you asking about a relationship between sparsity and degree? Feb 12, 2017 at 3:46
• There are only slightly less trivial examples that show you cannot say much: large degree functions can be both very sparse or very dense. Something you can say is the uncertainty principle: $\|f\|_0 \|\hat{f}\|_0 \ge 2^n$. Feb 12, 2017 at 4:03

The Fourier transform is a linear operation. In particular, for $f:\{-1,1\}\to\mathbb{R}$ and $S\subseteq[n]$, the Fourier coefficient $\hat f(S)$ is a linear functional of $f$. If $\hat f(S)\neq 0$, its magnitude can be made arbitrarily large or small by multiplying $f$ by an appropriate scalar -- without affecting $||f||_0$. So the answer to your question is negative.
• Yes. But I think my question was the other way round. If one fixes the sparsity of $f$ then does that still allow for large Fourier degrees to be non-zero? Like see the "parity" function. I will call it highly non-sparse because on half the vertices it is non-zero. And "correspondingly" its non-zero Fourier coefficient is the largest it could be. Is there any underlying phenomenon here? Feb 12, 2017 at 1:24
• Exercise: what is the Fourier transform of the indicator function of the singleton set $\{1\}$, where $1$ is the all-ones vector? I.e. the function $f(1, \ldots, 1) = 1$ and $f(x) = 0$ for any other $x$. Feb 12, 2017 at 3:59