Coeficientes de Fourier linearmente independentes

Uma propriedade básica de espaço vectorial é que um espaço vectorial $V \subseteq \mathbb{F}_2^n$ de dimensão pode ser caracterizado por restrições lineares linearmente independentes - isto é, existem vectores linearmente independentes$n-d$$d$$d$$w_1, \ldots, w_d \in \mathbb{F}_2^n$ que são ortogonais para .$V$

De uma perspectiva de Fourier, isso equivale a dizer que a função indicadora de possui coeficientes de Fourier linearmente independentes, diferentes de zero. Observe que possui coeficientes de Fourier diferentes de zero no total, mas apenas deles são linearmente independentes.$1_V$$V$$d$ $1_V$$2^d$$d$

Estou procurando uma versão aproximada dessa propriedade de espaços vetoriais. Especificamente, estou procurando uma declaração do seguinte formulário:

Seja do tamanho . Então, a função indicadora tem no máximo coeficientes de Fourier linearmente independentes , cujo valor absoluto é pelo menos$S \subseteq \mathbb{F}_2^n$$2^{n-d}$$1_S$$d\cdot\log(1/\varepsilon)$ $\varepsilon$ .

Essa questão pode ser vista da perspectiva "Estrutura versus aleatoriedade" - intuitivamente, essa afirmação diz que todo conjunto grande pode ser decomposto em uma soma de um espaço vetorial e em um pequeno conjunto tendencioso. É sabido que toda função pode ser decomposta em uma "parte linear" da qual tem Fourier grande coeficientes e uma "parte pseudo-aleatória" com pequeno viés. Minha pergunta pergunta se a parte linear tem apenas um número logarítmico de coeficientes de Fourier linearmente independentes .$f:\mathbb{F}_2^n \to \mathbb{F}_2$$\mathrm{poly}(1/\varepsilon)$

O exemplo a seguir não é um contra-exemplo?

Seja a maioria de x 1 , … , x 1 / ϵ 2 , que é um indicador de um conjunto de tamanho 2 n / 2 , então d = 1 . No entanto, f ( { i } ) = Θ ( ε ) para 1 ≤ i ≤ 1 / ε 2 , então você tem 1 / ε $f(x)$$x_1, \ldots, x_{1/\epsilon^2}$$2^n/2$$d = 1$$\hat{f}(\{i\}) = \Theta(\epsilon)$$1 \le i \le 1/\epsilon^2$$1/\epsilon^2$ coeficientes de Fourier grandes linearmente independentes.

Talvez você queira o que às vezes é chamado "Lema de Chang" ou "Lema de Talagrand" ... chamado de "Desigualdade de Nível 1" aqui: http://analysisofbooleanfunctions.org/?p=885

Isso implica que se tiver média 2 - d, então o número de coeficientes de Fourier linearmente independentes cujo quadrado é pelo menos γ 2 - d é no máximo O ( d / γ 2 ) . (Isto acontece porque um F 2 transformação -linear na entrada não altera a média, para que possa sempre mover caracteres de Fourier linearmente independentes de grau-1).$1_S$$2^{-d}$$\gamma 2^{-d}$$O(d/\gamma^2)$$F_2$