Coefficients de Fourier linéairement indépendants

19

Une propriété de base des espaces vectoriels est qu'un espace vectoriel VF2n de dimension nd peut être caractérisé par d contraintes linéaires linéairement indépendantes - c'est-à-dire qu'il existe d vecteurs linéairement indépendants w1,,wdF2n qui sont orthogonales à V .

Du point de vue de Fourier, cela revient à dire que la fonction d'indicateur 1V de V a coefficients de Fourier d linéairement indépendants non nuls. Notez que 1V a 2d coefficients de Fourier non nuls au total, mais seuls d d'entre eux sont linéairement indépendants.

Je recherche une version approximative de cette propriété des espaces vectoriels. Plus précisément, je recherche un relevé sous la forme suivante:

Soit de taille 2 n - d . Ensuite, la fonction d'indicateur 1 S a au plus d log ( 1 / ε ) des coefficients de Fourier linéairement indépendants dont la valeur absolue est au moins ε .SF2n2nd1Sdlog(1/ε) ε

Cette question peut être considérée du point de vue de la "structure par rapport à l'aléatoire". Intuitivement, une telle affirmation dit que chaque grand ensemble peut être décomposé en une somme d'un espace vectoriel et d'un petit ensemble biaisé. Il est bien connu que chaque fonction peut être décomposée en une "partie linéaire" dont les coefficients de Fourier p o l y ( 1 / ε ) sont importants, et une "partie pseudo-aléatoire" qui a un faible biais . Ma question demande si la partie linéaire n'a qu'un nombre logarithmique de coefficients de Fourier linéairement indépendants .f:F2nF2poly(1/ε)

Ou Meir
la source
3
Bonjour Ou pourriez-vous faire référence à votre dernière affirmation selon laquelle chaque fonction peut être décomposée en une partie linéaire + une partie pseudo-aléatoire? Merci!
Henry Yuen
2
Je ne sais pas où il est apparu pour la première fois. C'est un corollaire direct de l'inégalité de Parseval: De Parseval, vous obtenez que chaque fonction booléenne a au plus caractères dont les coefficients de Fourier ont une valeur absolue au moins ε . Maintenant, prenez la partie "linéaire" pour être la somme de ces derniers caractères (avec les mêmes coefficients), et la "partie pseudo-aléatoire" pour être la somme de tous les autres caractères (avec les mêmes coefficients). 1/ε2ε
Ou Meir

Réponses:

12

Ce qui suit n'est-il pas un contre-exemple?

Soit la majorité de x 1 , , x 1 / ϵ 2 , qui est un indicateur d'un ensemble de taille 2 n / 2 , donc d = 1 . Cependant, f ( { i } ) = Θ ( ε ) pour 1 i 1 / ε 2 , vous avez 1 / ε 2f(x)x1,,x1/ϵ22n/2d=1f^({i})=Θ(ϵ)1i1/ϵ21/ϵ2 grands coefficients de Fourier linéairement indépendants.

Per Austrin
la source
9

Peut-être voulez-vous ce que l'on appelle parfois le «lemme de Chang» ou le «lemme de Talagrand» ... appelé ici «l'inégalité de niveau 1»: http://analysisofbooleanfunctions.org/?p=885

Cela implique que si a une moyenne de 2 - d, alors le nombre de coefficients de Fourier linéairement indépendants dont le carré est au moins γ 2 - d est au plus O ( d / γ 2 ) . (En effet, une transformation linéaire F 2 sur l'entrée ne modifie pas la moyenne, vous pouvez donc toujours déplacer des caractères de Fourier linéairement indépendants au degré -1.)1S2dγ2dO(d/γ2)F2

Ryan O'Donnell
la source
ϵγ