Liniowo niezależne współczynniki Fouriera

Podstawową właściwością przestrzeni wektorowych jest to, że przestrzeń wektorowa $V \subseteq \mathbb{F}_2^n$ o wymiarze $n-d$ można scharakteryzować $d$ liniowo niezależnymi wiązaniami liniowymi - to znaczy istnieją $d$ liniowo niezależne wektory $w_1, \ldots, w_d \in \mathbb{F}_2^n$ , które są prostopadłe do $V$ .

Z punktu widzenia Fouriera jest to równoważne ze stwierdzeniem, że funkcja wskaźnik $1_V$ o $V$ został $d$ liniowo niezależne niezerowe współczynniki Fouriera. Należy zauważyć, że $1_V$ ma w sumie $2^d$ niezerowe współczynniki Fouriera, ale tylko $d$ z nich jest liniowo niezależne.

Szukam przybliżonej wersji tej właściwości przestrzeni wektorowych. W szczególności szukam oświadczenia o następującej formie:

Niech $S \subseteq \mathbb{F}_2^n$ będzie rozmiaru $2^{n-d}$ . Następnie funkcja wskaźnika $1_S$ ma co najwyżej $d\cdot\log(1/\varepsilon)$ liniowo niezależne współczynniki Fouriera, których wartość bezwzględna wynosi co najmniej $\varepsilon$ .

To pytanie można rozpatrywać z perspektywy „Struktura vs. losowość” - takie stwierdzenie intuicyjnie mówi, że każdy duży zestaw można rozłożyć na sumę przestrzeni wektorowej i małego zbioru stronniczego. Jest dobrze znane, że każda funkcja można rozłożyć w „liniowej części”, które ma p o, l r ( 1 / ε ) duże współczynniki Fouriera oraz „części pseudolosowego”, który ma małe odchylenie . Moje pytanie dotyczy tego, czy część liniowa ma tylko logarytmiczną liczbę liniowo niezależnych współczynników Fouriera.$f:\mathbb{F}_2^n \to \mathbb{F}_2$$\mathrm{poly}(1/\varepsilon)$

Czy podany poniżej nie jest przykładem?

Niech będzie większością x 1 , … , x 1 / ϵ 2 , co jest wskaźnikiem zbioru wielkości 2 n / 2 , więc d = 1 . Jednakże, f ( { i } ) = Θ ( ε ) dla 1 ≤ i ≤ 1 / ε 2 , więc trzeba 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$ liniowo niezależne duże współczynniki Fouriera.

Być może chcesz czegoś, co czasami nazywa się „Lemą Changa” lub „Lememą Talagranda” ... zwaną tutaj „Nierównością poziomu 1”: http://analysisofbooleanfunctions.org/?p=885

Oznacza to, że jeśli ma średnią 2 - d, to liczba liniowo niezależnych współczynników Fouriera, których kwadrat wynosi co najmniej γ 2 - d, wynosi co najwyżej O ( d / γ 2 ) . (Jest tak, ponieważ transformacja liniowa F 2 na wejściu nie zmienia średniej, więc zawsze możesz przesunąć liniowo niezależne znaki Fouriera do stopnia-1.)$1_S$$2^{-d}$$\gamma 2^{-d}$$O(d/\gamma^2)$$F_2$