Coeficientes de Fourier linealmente independientes

Una propiedad básica de los espacios vectoriales es que un espacio vectorial de dimensión n - d puede caracterizarse por d restricciones lineales linealmente independientes, es decir, existen d vectores linealmente independientes w 1 , ... , w d ∈ F n 2 que son ortogonales a V .$V \subseteq \mathbb{F}_2^n$$n-d$$d$$d$$w_1, \ldots, w_d \in \mathbb{F}_2^n$$V$

Desde una perspectiva de Fourier, esto es equivalente a decir que la función del indicador de V tiene d coeficientes de Fourier linealmente independientes distintos de cero. Tenga en cuenta que 1 V tiene 2 d coeficientes de Fourier distintos de cero en total, pero solo d de ellos son linealmente independientes.$1_V$$V$$d$ $1_V$$2^d$$d$

Estoy buscando una versión aproximada de esta propiedad de espacios vectoriales. Específicamente, estoy buscando una declaración de la siguiente forma:

Sea de tamaño 2 n - d . Entonces, la función del indicador 1 S tiene como máximo d ⋅ log ( 1 / ε ) coeficientes de Fourier linealmente independientes cuyo valor absoluto es al menos ε .$S \subseteq \mathbb{F}_2^n$$2^{n-d}$$1_S$$d\cdot\log(1/\varepsilon)$ $\varepsilon$

Esta pregunta se puede ver desde una perspectiva de "Estructura vs. Aleatoriedad". Intuitivamente, tal afirmación dice que cada conjunto grande puede descomponerse en una suma de un espacio vectorial y un pequeño conjunto sesgado. Es bien conocido que cada función se puede descomponer en una "parte lineal" de los cuales tiene p o l y ( 1 / varepsilon ) grandes coeficientes de Fourier, y una "parte pseudoaleatorio" que tiene pequeño sesgo . Mi pregunta es si la parte lineal solo tiene un número logarítmico de coeficientes de Fourier linealmente independientes .$f:\mathbb{F}_2^n \to \mathbb{F}_2$$\mathrm{poly}(1/\varepsilon)$

¿No es el siguiente un contraejemplo?

Sea la mayoría de x 1 , ... , x 1 / ϵ 2 , que es un indicador de un conjunto de tamaño 2 n / 2 , entonces d = 1 . Sin embargo, f ( { i } ) = Θ ( ε ) para 1 ≤ i ≤ 1 / ε 2 , por lo que tiene 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 linealmente independientes.

Quizás quiera lo que a veces se llama "Lema de Chang" o "Lema de Talagrand" ... llamado "Desigualdad de nivel 1" aquí: http://analysisofbooleanfunctions.org/?p=885

Implica que si tiene una media de 2 - d, entonces el número de coeficientes de Fourier linealmente independientes cuyo cuadrado es al menos γ 2 - d es como máximo O ( d / γ 2 ) . (Esto se debe a que una transformación lineal F 2 en la entrada no cambia la media, por lo que siempre puede mover caracteres de Fourier linealmente independientes al grado 1).$1_S$$2^{-d}$$\gamma 2^{-d}$$O(d/\gamma^2)$$F_2$