<p>Perhaps you want what's sometimes called "Chang's Lemma" or "Talagrand's Lemma"... called the "Level-1 Inequality" here:
<a href="http://analysisofbooleanfunctions.org/?p=885">http://analysisofbooleanfunctions.org/?p=885</a></p>

<p>It implies that if $1_S$ has mean $2^{-d}$ then the number of linearly independent Fourier coefficients whose square is at least $\gamma 2^{-d}$ is at most $O(d/\gamma^2)$.  (This is because an $F_2$-linear transformation on the input does not change the mean, so you can always move linearly independent Fourier characters to degree-1.)</p>

CC BY-SA 3.0
2012-07-13T02:00:15.287Z
Thanks a lot! It is definitely close to what I looked for,  but for the application I had in mind it was crucial to have logarithmic dependence on $\epsilon$ (which in your notation would also imply logarithmic dependence on $\gamma$). Alas, Per's example shows that this is not possible.
Or Meir
CC BY-SA 3.0
2012-07-12T20:05:34.887Z
2012-07-12T20:05:34.887Z
Ryan O'Donnell
<p>Isn't the following a counter-example?</p>

<p>Let $f(x)$ be the majority of $x_1, \ldots, x_{1/\epsilon^2}$, which is an indicator of a set of size $2^n/2$, so $d = 1$.  However, $\hat{f}(\{i\}) = \Theta(\epsilon)$ for $1 \le i \le 1/\epsilon^2$, so you have $1/\epsilon^2$ linearly independent large Fourier coefficients.</p>

CC BY-SA 3.0
2012-07-11T15:45:12.333Z
2012-07-11T15:45:12.333Z
Per Austrin
<p>A basic property of vector spaces is that a vector space $V \subseteq \mathbb{F}_2^n$ of dimension $n-d$ can be characterized by $d$ linearly independent linear constraints - that is, there exist $d$ linearly independent vectors $w_1, \ldots, w_d \in \mathbb{F}_2^n$ that are orthogonal to $V$.</p>

<p>From a Fourier perspective, this is equivalent to saying that the indicator function $1_V$ of $V$ has $d$ <i>linearly independent</i> non-zero Fourier coefficients. Note that $1_V$ has $2^d$ non-zero Fourier coefficients in total, but only $d$ of them are linearly independent.</p>

<p>I am looking for an approximate version of this property of vector spaces. Specifically, I am looking for a statement of the following form:</p>

<p>Let $S \subseteq \mathbb{F}_2^n$ be of size $2^{n-d}$. Then, the indicator function $1_S$ has at most $d\cdot\log(1/\varepsilon)$ <i>linearly independent</i> Fourier coefficients whose absolute value is at least $\varepsilon$.</p>

<p>This question can be viewed from a "Structure vs. Randomness" perspective - Intuitively, such a claim says that every large set can be decomposed to a sum of a vector space and a small biased set. It is well known that every function $f:\mathbb{F}_2^n \to \mathbb{F}_2$ can be decomposed into a "linear part" of which has $\mathrm{poly}(1/\varepsilon)$ large Fourier coefficients, and a "pseudorandom part" that has small bias. My question asks whether the linear part has only a logarithmic number of <i>linearly independent</i> Fourier coefficients.</p>

CC BY-SA 3.0
2012-07-11T04:59:41.407Z
Hi Or, could you give a reference to your last claim that every function can be decomposed into a linear part + pseudorandom part? Thanks!
Henry Yuen
CC BY-SA 3.0
2012-07-11T23:47:06.093Z
I am not sure about where it first appeared. It is a direct corollary of Parseval inequality: From Parseval, you get that every Boolean function has at most $1/\varepsilon^2$ characters whose Fourier coefficients have absolute value at least $\varepsilon$. Now, take the "linear" part to be the sum of the latter characters (with the same coefficients), and the "pseudorandom part" to be the sum of all the other characters (with the same coefficients).
Or Meir
<co.combinatorics><linear-algebra><boolean-functions><fourier-analysis>
Linearly independent Fourier coefficients
Or Meir
# Linearly independent Fourier coefficients

(Asked by: username_0 on 2012-07-10)

A basic property of vector spaces is that a vector space $V \subseteq \mathbb{F}\_2^n$ of dimension $n-d$ can be characterized by $d$ linearly independent linear constraints - that is, there exist $d$ linearly independent vectors $w\_1, \ldots, w\_d \in \mathbb{F}\_2^n$ that are orthogonal to $V$.

From a Fourier perspective, this is equivalent to saying that the indicator function $1\_V$ of $V$ has $d$ *linearly independent* non-zero Fourier coefficients. Note that $1\_V$ has $2^d$ non-zero Fourier coefficients in total, but only $d$ of them are linearly independent.

I am looking for an approximate version of this property of vector spaces. Specifically, I am looking for a statement of the following form:

Let $S \subseteq \mathbb{F}\_2^n$ be of size $2^{n-d}$. Then, the indicator function $1\_S$ has at most $d\cdot\log(1/\varepsilon)$ *linearly independent* Fourier coefficients whose absolute value is at least $\varepsilon$.

This question can be viewed from a "Structure vs. Randomness" perspective - Intuitively, such a claim says that every large set can be decomposed to a sum of a vector space and a small biased set. It is well known that every function $f:\mathbb{F}\_2^n \to \mathbb{F}\_2$ can be decomposed into a "linear part" of which has $\mathrm{poly}(1/\varepsilon)$ large Fourier coefficients, and a "pseudorandom part" that has small bias. My question asks whether the linear part has only a logarithmic number of *linearly independent* Fourier coefficients.

**Tags:** co.combinatorics, linear-algebra, boolean-functions, fourier-analysis
> **Comments:**
> **username_1**: Hi Or, could you give a reference to your last claim that every function can be decomposed into a linear part + pseudorandom part? Thanks!  
> **username_0**: I am not sure about where it first appeared. It is a direct corollary of Parseval inequality: From Parseval, you get that every Boolean function has at most $1/\varepsilon^2$ characters whose Fourier coefficients have absolute value at least $\varepsilon$. Now, take the "linear" part to be the sum of the latter characters (with the same coefficients), and the "pseudorandom part" to be the sum of all the other characters (with the same coefficients).  

---

## 2 answers

### Answer by username_3 on 2012-07-11. Score: 12 | Accepted answer

Isn't the following a counter-example?

Let $f(x)$ be the majority of $x\_1, \ldots, x\_{1/\epsilon^2}$, which is an indicator of a set of size $2^n/2$, so $d = 1$. However, $\hat{f}(\{i\}) = \Theta(\epsilon)$ for $1 \le i \le 1/\epsilon^2$, so you have $1/\epsilon^2$ linearly independent large Fourier coefficients.


---

### Answer by username_2 on 2012-07-12. Score: 9

Perhaps you want what's sometimes called "Chang's Lemma" or "Talagrand's Lemma"... called the "Level-1 Inequality" here:
<http://analysisofbooleanfunctions.org/?p=885>

It implies that if $1\_S$ has mean $2^{-d}$ then the number of linearly independent Fourier coefficients whose square is at least $\gamma 2^{-d}$ is at most $O(d/\gamma^2)$. (This is because an $F\_2$-linear transformation on the input does not change the mean, so you can always move linearly independent Fourier characters to degree-1.)

> **Comments:**
> **username_0**: Thanks a lot! It is definitely close to what I looked for,  but for the application I had in mind it was crucial to have logarithmic dependence on $\epsilon$ (which in your notation would also imply logarithmic dependence on $\gamma$). Alas, Per's example shows that this is not possible.  

---

