[Edición: añadidos detalles sobre los códigos Reed-Muller].
¿Existen construcciones explícitas (no aleatorias) de medidas de probabilidad sobre $D_N = \{0,1\}^N$ con soporte de tamaño $O(N)$ y con todos los coeficientes de Fourier no triviales menores que $\frac 1 2$ ¿es el valor absoluto?
Me imagino que este tipo de preguntas se entienden muy bien, pero al ser de un entorno diferente probablemente carezco de los conocimientos comunes. Agradecería que se me indicara la bibliografía pertinente.
A continuación encontrará algunas explicaciones sobre la terminología y sobre la $O(N)$ . Estoy contento con cualquier respuesta con $\frac 1 2$ sustituido por $c<1$ (pero independiente de $N$ ).
Cuando escribo eso $\mu$ tiene todos los coeficientes de Fourier no triviales menores que $\frac 1 2$ en valor absoluto Quiero decir que $|\hat \mu(A)| \leq \frac 1 2$ para cada subconjunto no vacío $A$ de $\{1,\dots,N\}$ donde $\hat \mu(A)$ es el coeficiente de Fourier (o Fourier-Walsh): $$ \hat \mu(A) = \int (-1)^{\sum_{i \in A} \varepsilon_i} d\mu(\varepsilon).$$ El coeficiente de Fourier trivial, correspondiente a $A=\emptyset$ siempre es $1$ . La medida de probabilidad uniforme sobre $D_N$ tiene todos los coeficientes de Fourier no triviales iguales a $0$ pero es totalmente compatible con el tamaño $2^N$ . Así que estoy buscando una medida de probabilidad que se parezca a la probabilidad uniforme en el lado de Fourier, pero que esté muy lejos en el otro lado, teniendo un soporte muy pequeño.
¿Por qué la $O(N)$ ? Porque es la tasa óptima para la mera existencia de $\mu$ .
En efecto, al ver $D_N$ como un espacio vectorial de dimensión $N$ sobre el campo con dos elementos, la pregunta puede traducirse en términos de álgebra lineal. En particular, vemos que para todos los coeficientes de Fourier no triviales de $\mu$ ser $\neq 1$ necesitamos el apoyo de $\mu$ contiene al menos una base de $D_N$ y por lo tanto tiene que tener una cardinalidad de al menos $N$ .
Por el contrario, tomar por $\mu$ la medida uniforme en un subconjunto de cardinalidad $K N$ elegidos uniformemente al azar, una aplicación básica de los argumentos de límites de unión y grandes desviaciones (desigualdad de Hoeffding) da que $\mu$ funciona con alta probabilidad, siempre que $K$ es lo suficientemente grande. Lo que busco son construcciones explícitas no aleatorias.
Utilizando Códigos Reed-Muller un cálculo a partir de la envolvente parece proporcionar una solución explícita. $\mu$ con apoyo $N^{K \log \log N}$ .
[Añadido después de la solicitud en los comentarios] Aquí está la construcción. No sé qué tan estándar es ; Lo aprendí de el documento PIP*=RE . Existe un parámetro entero $a$ y utilizamos el código de las funciones multilineales sobre el campo $\mathbf{F}_q$ con $q=2^{a}$ elementos en $m = 2^{a-1}$ variables.
Denote $\mathcal{P}(m)$ el conjunto de todos los subconjuntos de $\{1,\dots,m\}$ y definir un mapa $\alpha:\mathbf{F}_q^{m+1} \to \mathbf{F}_q^{\mathcal{P}(m)}$ estableciendo $$\alpha(u_1,\dots,u_m,a) = (a \prod_{i \in A} u_i \prod_{i \notin A} (1-u_i))_{A \in \mathcal{P}(m)}.$$ Podemos identificar $\mathbf{F}_q^{\mathcal{P}(m)}$ como grupo aditivo con $D_N$ para $N=a 2^m = a 2^{2^{a-1}}$ y afirmo que $\mu$ la imagen por $\alpha$ de la medida uniforme en $\mathbf{F}_q^{m+1}$ hace el trabajo.
$\mu$ tiene claramente apoyo de tamaño $q^{m+1} = 2^{a +a2^{a-1}} = 2^{O(\log N \log\log N)}$ así que estamos bien en lo que respecta al apoyo.
Permítanme demostrar que $|\hat\mu(\chi)|\leq \frac 1 2$ para cada carácter no trivial $\chi$ . Fijemos un carácter distinto de cero $\eta$ de $\mathbf{F_q}$ . Entonces, por recuento, cada carácter de $\mathbf{F_q}^{\mathcal P(m)}$ es de la forma $\eta \circ T$ para un $\mathbf{F}_q$ -mapa lineal $T:\mathbf{F}_q^{\mathcal{P}(m)} \to \mathbf{F}_q$ . Además, para cada $x \in \mathbf{F}_q$ tenemos $\mathbf{E}_{a \in \mathbf{F_q}} \eta(ax)=1_{x=0}$ por lo que podemos calcular
\begin{align*}\hat \mu(\chi) &= \mathbf{E}_{u \in \mathbf{F}_q^m} \mathbf{E}_{a \in \mathbf{F}_q} \eta(a T(\alpha(u,1)))\\ &= \mathbf{E}_{u \in \mathbf{F}_q^m} 1_{T(\alpha(u,1))}=0\\ & = \mathbf{P}_{u \in\mathbf{F}_q^m}( T(\alpha(u,1))). \end{align*}
Pero si $T$ es un mapa lineal distinto de cero, entonces $T(\alpha(u,1))$ es un polinomio distinto de cero en $m$ variables de grado individual $\leq 1$ por lo que la última probabilidad es $\leq\frac{m}{q} = \frac 1 2$ . QED
