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

CC BY-SA 3.0
2017-02-12T01:24:28.567Z
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?
gradstudent
CC BY-SA 3.0
2017-02-12T03:59:52.507Z
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$.
Sasho Nikolov
CC BY-SA 3.0
2017-02-12T06:52:55.610Z
Yes. Since the examples do seem to go both ways, it raises the question if there is any implication at all. Maybe atleast a one-way implication exists?
gradstudent
CC BY-SA 3.0
2017-02-17T00:54:14.340Z
I think the answer is nope
ivmihajlin
CC BY-SA 3.0
2017-02-11T22:19:02.460Z
2017-02-11T22:19:02.460Z
Aryeh
<p>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? </p>

CC BY-SA 3.0
2017-02-11T22:20:39.730Z
Of course it does not..$f$ and $2^{2^{n}}f$ have the same sparsity in any basis.
Sasho Nikolov
CC BY-SA 3.0
2017-02-11T22:22:07.433Z
Your questions should demonstrate some minimal understanding of the subject matter. A question of this type is more appropriate at Math.SE if anywhere.
Sasho Nikolov
CC BY-SA 3.0
2017-02-12T01:35:08.110Z
@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!
gradstudent
CC BY-SA 3.0
2017-02-12T03:46:13.160Z
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?
Sasho Nikolov
CC BY-SA 3.0
2017-02-12T03:56:29.063Z
Yes. By "largest non-zero term" I meant, the non-zero term with the largest degree.
gradstudent
CC BY-SA 3.0
2017-02-12T04:03:49.650Z
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$.
Sasho Nikolov
CC BY-SA 3.0
2017-02-12T22:12:32.813Z
To follow up on the above (uncertainty principle): maybe going through Exercise 3.15 of Ryan O'Donnell's *Analysis of Boolean Functions* (Exercise 3.14 of [the online version](http://www.contrib.andrew.cmu.edu/~ryanod/?p=602#exuncertainty)) would bring some insight.
Clement C.
<boolean-functions><fourier-analysis><boolean-matrix>
Sparsity of a Boolean function and its Fourier depth
gradstudent
# Sparsity of a Boolean function and its Fourier depth

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

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?

**Tags:** boolean-functions, fourier-analysis, boolean-matrix

> **Comments:**
> **username_1**: Of course it does not..$f$ and $2^{2^{n}}f$ have the same sparsity in any basis.  
> **username_1**: Your questions should demonstrate some minimal understanding of the subject matter. A question of this type is more appropriate at Math.SE if anywhere.  
> **username_0**: @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!  
> **username_1**: 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?  
> **username_0**: Yes. By "largest non-zero term" I meant, the non-zero term with the largest degree.  
> **username_1**: 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$.  
> **username_2**: To follow up on the above (uncertainty principle): maybe going through Exercise 3.15 of Ryan O'Donnell's *Analysis of Boolean Functions* (Exercise 3.14 of [the online version](http://www.contrib.andrew.cmu.edu/~ryanod/?p=602#exuncertainty)) would bring some insight.  

---

## 1 answers

### Answer by username_3 on 2017-02-11. Score: 1

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.

> **Comments:**
> **username_0**: 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?  
> **username_1**: 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$.  
> **username_0**: Yes. Since the examples do seem to go both ways, it raises the question if there is any implication at all. Maybe atleast a one-way implication exists?  
> **username_4**: I think the answer is nope  

---

