Caracterización de Boolean funciones con valores en la discreta cubo basado en sus coeficientes de Fourier.

Question

Considerar las funciones en el discretos cube $\{-1,1\}^n$.

Consideramos que la transformada de Fourier Discreta de tales funciones. Supongamos que denotan la función de paridad en un subconjunto $S \subseteq [n]$ de co-ordenadas por $\Pi_S(x)=\pi_{i \in S}(x_i)$, entonces el coeficiente de Fourier $\hat{f}_S$ es simplemente la expectativa: $\hat{f}_S=\mathbb{E}_x[f(x)\Pi_S(x)]$; y por orthonormality de la paridad de las funciones, de cualquier $f$ puede ser representado como $f(x)=\sum_{S \subseteq [n]}\hat{f}_S \Pi_S(x)$ (la suma de estar en $\mathbb{R}$.)

Estoy interesado en saber la diferencia entre boolean valores de ($\{-1,1\}^n \rightarrow \{-1,1\}$) y el valor real de las funciones de ($\{-1,1\}^n \rightarrow \mathbb{R}$). Más específicamente, me gustaría saber la diferencia entre los espectros de Fourier de cualquiera de las clases de funciones.

¿Qué propiedades de los espectros de Fourier de retener para una clase, pero no para el otro?

(Como ejemplo: se puede demostrar que para funciones con valores Booleanos, si todo el peso se concentra en los coeficientes de Fourier de tamaño en la mayoría de los 1, entonces la función es una constante o un dictador. Esto no es cierto para el valor real de las funciones.)

Answer 1

Esta es una buena pregunta que es objeto de intensa investigación en las matemáticas y la informática teórica. El blog (que es la serialización de un libro en proceso) "Análisis de Funciones Booleanas" por Ryan O'Donnell es una buena fuente, y así es el Libro: Conferencias sobre la sensibilidad al ruido y la percolación por Garban y Steif.

Aquí hay alguna información

1) por supuesto, los coeficientes de Fourier de funciones reales sobre la discreta cubo puede ser arbitraria. La pregunta es, por tanto, qué restricciones se aplican para las funciones Booleanas.

Funciones booleanas se caracterizan por $f^2(x)=1$ y ya que el producto se traduce a la convolución de la transformada de Fourier, siendo Booleano se caracteriza por una propiedad de la transformada de Fourier convoluciona con la misma. Sin embargo, esta caracterización de por sí no es muy útil.

La fórmula de Parseval afirma que para funciones Booleanas la suma del cuadrado de la transformada de Fourier los coeficientes es 1. También dar la siguiente fórmula para la varianza de $f$, $$\operatorname{var}(f) = \sum \{ \hat f^2(S): S \ne \emptyset \} $$

2) Una importante herramienta que da mucha información es Bonami (o Bonami–Bruto–Beckner) de la desigualdad. Se afirma que para cada función $f$, $$\|T_\epsilon (f) \|_2 \le \|f\| _{1+\epsilon^2}.$$ Esto implica que si $f$ tiene valores $0$, $1$, y $-1$ y el apoyo de $f$ tiene una medida de $t$, entonces la mayoría del espectro de Fourier de $f$ $S$ $|A|> \log n/10$ (por ejemplo).

3) Un razonamiento similar da el llamado KKL del teorema. Se afirma que para una función Booleana $f$ hay un índice $k$, de modo que $$\sum \{ \hat f^2(S): S \subset [n], i \in S \} \ge \operatorname{var}(f) \log n/n.$$

4) Un teorema de Friedgut afirma que para una función Booleana $f$ si $\sum \hat f^2(S) |S|$ está acotada arriba por una constante $c$ $f$ "$\epsilon$- cerca" de una "Junta. "Una Junta es una función Booleana dependiendo de un acotado número de $C$ de las variables. ($C$ es una función de $c$$\epsilon$.)

5) Un teorema de Green y Sanders desde el papel de funciones Booleanas con pequeñas espectral de la norma, afirma que una función Booleana que todos los coeficientes de Fourier están delimitadas por $M$ es una combinación lineal de limitada número de $(\le 2^{2^{O(M^4)}}$) de las funciones características de los subespacios.

6) resultado por Talagrand afirma que para funciones Booleanas $f_n$ si $\sum_i^n\hat f_n^2(\{i\})$ es o(1) también lo es $\sum_i^n\hat f_n^2(\{i\})$. Una extensión de este resultado a niveles más altos, fue dado por Benjamini, Kalai y Schramm, y un fuerte cuantitativa versión por Keller y Kindler.

7) Un teorema de Bourgain afirma que para una función Booleana si el decaimiento de los coeficientes de Fourier cuadrado es más grande que la de segundo grado en $|S|$, luego de nuevo a $f$ es de aproximadamente una Junta.

8) No es una conjetura llamado la Entropía influencia conjetura que afirma que $\sum \hat f^2 (S)|S|$ está delimitada desde abajo por una absoluta constante de veces $\sum \hat f^2(S) \log (\hat f^2(S))$.