Linear unabhängige Fourier-Koeffizienten

19

Eine grundlegende Eigenschaft von Vektorräumen ist, dass ein Vektorraum der Dimension durch linear unabhängige lineare Nebenbedingungen charakterisiert werden kann - das heißt, es gibt linear unabhängige Vektoren , die zu orthogonal sind .VF2nndddw1,,wdF2nV

Aus einer Fourier Sicht ist dies äquivalent zu der Aussage , dass die Indikatorfunktion von ist linear unabhängige Nicht-Null - Fourier - Koeffizienten. Man beachte , dass hat ungleich Null Fourierkoeffizienten insgesamt, aber nur von ihnen sind linear unabhängig.1VVd 1V2dd

Ich suche eine ungefähre Version dieser Eigenschaft von Vektorräumen. Konkret suche ich eine Stellungnahme in folgender Form:

Sei SF2n von der Größe . Dann hat die Indikatorfunktion höchstens linear unabhängige Fourier-Koeffizienten , deren Absolutwert mindestens beträgt .2nd1Sdlog(1/ε) ε

Diese Frage kann aus der Perspektive "Struktur vs. Zufälligkeit" betrachtet werden. Intuitiv besagt eine solche Behauptung, dass jede große Menge in eine Summe aus einem Vektorraum und einer kleinen voreingenommenen Menge zerlegt werden kann. Es ist bekannt, dass jede Funktion in einen "linearen Teil" zerlegt werden kann, von dem großes Fourier hat Koeffizienten und ein "Pseudozufallsteil", der eine geringe Vorspannung aufweist. Meine Frage lautet, ob der lineare Teil nur eine logarithmische Anzahl linear unabhängiger Fourier-Koeffizienten hat.f:F2nF2poly(1/ε)

Oder Meir
quelle
3
Hallo Oder, könnten Sie auf Ihre letzte Behauptung verweisen, dass jede Funktion in einen linearen Teil + einen Pseudozufallsteil zerlegt werden kann? Vielen Dank!
Henry Yuen
2
Ich bin mir nicht sicher, wo es zuerst auftauchte. Dies ist eine direkte Folge der Parseval-Ungleichung: Aus Parseval geht hervor, dass jede Boolesche Funktion höchstens Zeichen hat, deren Fourier-Koeffizienten einen absoluten Wert von mindestens ε haben . Nehmen wir nun den "linearen" Teil als die Summe der letzteren Zeichen (mit den gleichen Koeffizienten) und den "pseudozufälligen Teil" als die Summe aller anderen Zeichen (mit den gleichen Koeffizienten). 1/ε2ε
Oder Meir

Antworten:

12

Ist das Folgende nicht ein Gegenbeispiel?

Sei die Mehrheit von x 1 , , x 1 / ϵ 2 , was ein Indikator für eine Menge von 2 n / 2 ist , also ist d = 1 . Allerdings f ( { i } ) = Θ ( ε ) für 1 i 1 / ε 2 , so haben Sie 1 / ε 2f(x)x1,,x1/ϵ22n/2d=1f^({i})=Θ(ϵ)1i1/ϵ21/ϵ2 linear unabhängige große Fourier-Koeffizienten.

Per Austrin
quelle
9

Vielleicht möchten Sie, was manchmal "Chang's Lemma" oder "Talagrand's Lemma" genannt wird ... hier als "Level-1-Ungleichung" bezeichnet werden: http://analysisofbooleanfunctions.org/?p=885

Dies impliziert, dass, wenn einen Mittelwert von 2 - d hat, die Anzahl der linear unabhängigen Fourier-Koeffizienten, deren Quadrat mindestens γ 2 - d ist, höchstens O ( d / γ 2 ) beträgt . (Dies liegt daran, dass eine F 2 -lineare Transformation am Eingang den Mittelwert nicht ändert. Sie können also immer linear unabhängige Fourier-Zeichen auf Grad 1 verschieben.)1S2dγ2dO(d/γ2)F2

Ryan O'Donnell
quelle
Vielen Dank! Es ist definitiv in der Nähe von dem, wonach ich gesucht habe, aber für die Anwendung, an die ich gedacht habe, war es entscheidend, eine logarithmische Abhängigkeit von (was in Ihrer Notation auch eine logarithmische Abhängigkeit von γ implizieren würde ). Leider zeigt Per's Beispiel, dass dies nicht möglich ist. ϵγ
Oder Meir