19
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Hi Or, could you give a reference to your last claim that every function can be decomposed into a linear part + pseudorandom part? Thanks! $\endgroup$ – Henry Yuen Jul 11 '12 at 4:59
  • 2
    $\begingroup$ 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). $\endgroup$ – Or Meir Jul 11 '12 at 23:47
12
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Or Meir Jul 13 '12 at 2:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.