Koefisien Fourier yang bebas linear

Sifat dasar ruang vektor adalah ruang vektor dari dimensi n - d dapat dikarakteristikkan dengan d kendala linear bebas linear - yaitu, terdapat d vektor bebas linear dengan w 1 , … , w d ∈ F n 2 yang ortogonal terhadap V .$V \subseteq \mathbb{F}_2^n$$n-d$$d$$d$$w_1, \ldots, w_d \in \mathbb{F}_2^n$$V$

Dari perspektif Fourier, ini setara dengan mengatakan bahwa fungsi indikator dari V memiliki d koefisien Fourier yang tidak bebas secara linear . Perhatikan bahwa 1 V memiliki total koefisien Fourier 2 d bukan nol, tetapi hanya d dari mereka yang bebas linear.$1_V$$V$$d$ $1_V$$2^d$$d$

Saya mencari versi perkiraan properti ruang vektor ini. Secara khusus, saya mencari pernyataan dalam bentuk berikut:

Biarkan berukuran 2 n - d . Kemudian, fungsi indikator 1 S memiliki paling banyak d ⋅ log ( 1 / ε ) koefisien Fourier yang bebas linear yang nilai absolutnya setidaknya ε .$S \subseteq \mathbb{F}_2^n$$2^{n-d}$$1_S$$d\cdot\log(1/\varepsilon)$ $\varepsilon$

Pertanyaan ini dapat dilihat dari perspektif "Struktur vs. Keacakan" - Secara intuitif, klaim seperti itu mengatakan bahwa setiap set besar dapat didekomposisi menjadi jumlah ruang vektor dan set bias kecil. Diketahui bahwa setiap fungsi dapat didekomposisi menjadi "bagian linier" yang memiliki p o l y ( 1 / ε ) koefisien Fourier besar, dan "bagian pseudorandom" yang memiliki bias kecil. . Pertanyaan saya menanyakan apakah bagian linier hanya memiliki jumlah logaritmik koefisien Fourier yang bebas linear .$f:\mathbb{F}_2^n \to \mathbb{F}_2$$\mathrm{poly}(1/\varepsilon)$

Bukankah ini contoh yang berlawanan?

Misalkan menjadi mayoritas x 1 , … , x 1 / ϵ 2 , yang merupakan indikator dari serangkaian ukuran 2 n / 2 , jadi d = 1 . Namun, f ( { i } ) = Θ ( ε ) untuk 1 ≤ i ≤ 1 / ε 2 , sehingga Anda memiliki 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$ koefisien Fourier besar yang bebas linear.

Mungkin Anda menginginkan apa yang kadang-kadang disebut "Chang's Lemma" atau "Talagrand's Lemma" ... disebut "Level-1 Ketimpangan" di sini: http://analysisofbooleanfunctions.org/?p=885

$1_S$$2^{-d}$$\gamma 2^{-d}$$O(d/\gamma^2)$$F_2$