Esta pregunta está relacionada con esta pregunta anterior donde preguntaba sobre los coeficientes ordinarios de Fourier.
Caso especial: ¿es Möbius casi ortogonal a Morse?
August Ferdinand Möbius (17 de noviembre de 1790 - 26 de septiembre de 1868), Harold Calvin Marston Morse (24 de marzo de 1892 - 22 de junio de 1977)
Considera la secuencia de valores de las funciones Möbius en enteros no negativos. (Comenzando con 0 para 0.)
0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, ...
Y la secuencia de Morse
1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1
¿Estas dos secuencias son casi ortogonales?
Observación: Este caso del problema general sigue de la solución de Mauduit y Rivat de una conjetura de 1968 de Gelfond. Ellos demuestran que los números primos tienen la misma probabilidad de tener una suma de dígitos par o impar en base 2. Ver el comentario de Ben Green a continuación.)
Los Problemas
Comienza con la función Möbius $\mu (m)$. (Entonces $\mu(m)=0$ a menos que todos los factores primos de $m$ aparezcan una vez y $\mu (m)=(-1)^r$ si $m$ tiene $r$ factores primos distintos.) Ahora, para un número positivo de n dígitos $m$ considera la función de Möbius como una función booleana $\mu(x_1,x_2,\dots,x_n)$ donde $x_1,x_2,\dots,x_n$ son los dígitos binarios de $m$.
Por ejemplo $\mu (0,1,0,1)=\mu(2+8)=\mu(10)=1$. Escribimos $\Omega_n$ como el conjunto de vectores 0-1 $x=(x_1,x_2,x_m)$ de longitud $n$. También escribimos $[n]=\{1,2,\dots,n\}$, y $N=2^n$.
A continuación, considera para cierto número natural $n$ la transformada de Walsh-Fourier
$$\hat \mu (S)= \frac{1}{2^n} \sum _{x\in \Omega_n} \mu(x_1,x_2,\dots,x_n)(-1)^{\sum\{x_i:i\in S\}}.$$
Entonces $\sum_{S \subset [n]}|\hat \mu (S)|^2$ es aproximadamente $6/\pi ^2$; y el teorema de los números primos asegura que $\hat \mu(\emptyset)=o(1)$; De hecho, la forma fuerte conocida del teorema de los números primos asegura que
$$|\hat \mu (\emptyset )| \lt n^{-A} =(\log N)^{-A},$$
para cada $A>0$. (Ten en cuenta que $|\hat \mu (\emptyset)=\sum_{k=0}^{N-1}\mu(k)$.)
Mis preguntas son:
-
¿Es cierto que los coeficientes individuales tienden a 0? ¿Se sabe incluso que $|\hat \mu (S)| \le n^{-A}$ para cada $A>0$.
Resuelto positivamente por Jean Bourgain (12 de Abril de 2011): Límites de correlación Moebius-Walsh y una estimación de Mauduit y Rivat; (Dic, 2011) Para resultados aún más fuertes, ve el paper de Bourgain En el espectro de Fourier-Walsh de la función Moebius.
-
¿Es el caso que $$\tag{$*$} \sum \{ \hat \mu ^2(S)~:~|S|<(\log n)^A \} =o(1), \label{*}$$ para cada $A>0$.
(Esto no parece seguir de los límites que podemos esperar incondicionalmente sobre los coeficientes individuales.) Resuelto positivamente por Ben Green (12 de Marzo de 2011): Sobre (no) calcular la función de Möbius usando circuitos de profundidad acotada. (Ver la respuesta de Green a continuación.)
-
La Hipótesis de Riemann asegura que $$|\hat \mu (\emptyset )| < N^{-1/2+\epsilon}.$$
¿Se deduce del GRH que para algún $c>0$, $$| \hat \mu (S)| < N^{-c},$$ para cada $S$?
Un límite superior de $(\log N)^{-{\log \log N}^A}$ es suficiente para obtener la aplicación deseada.
La motivación
La motivación para estas preguntas proviene de una cierta extensión de complejidad computacional del teorema de los números primos. Asegura que cada función en los enteros positivos que puede ser representada por un circuito booleano de profundidad acotada en términos de la expansión binaria tiene una correlación decreciente con la función Möbius. Esta conjetura a la que podemos referirnos como la conjetura de los números primos AC^0 se discute aquí, en mi blog y aquí, en el blog de Dick Lipton. La conjetura sigue de la fórmula \eqref{*} por un resultado de Linial Mansour y Nisan sobre los coeficientes de Walsh-Fourier de funciones AC^0.
La pregunta 3 sugiere que quizás podemos deducir la conjetura de los números primos AC^0 del GRH, lo que sería de interés. Por supuesto, será mejor demostrarlo incondicionalmente. (Ben Green lo demostró incondicionalmente).
Para fórmulas de tamaño polinómico, es decir, para funciones expresables por circuitos de tamaño polinómico de profundidad 2, podemos necesitar incluso menos. Un resultado de Mansour muestra que la desigualdad $|\hat \mu (S)| \le n^{-(\log \log n)^A}$ para cada $A>0$, ¡suficiente! Además, una conjetura de Mansour (que también se sigue de una conjetura más general llamada la conjetura de influencia/entropía, ver esta entrada de blog para una descripción de ambas conjeturas) implica que será suficiente demostrar que
$$|\hat \mu (S)| \le n^{-A}$$
para cada $A>0$, para deducir el PNT para fórmulas.)
Algo de trasfondo
Permíteme mencionar que la pregunta sigue en gran medida una línea de investigación que asocia fórmulas $AC^0$ con preguntas de teoría de números. Ver los artículos de Anna Bernasconi e Igor Shparlinski y el artículo de Eric Allender Mike Saks Igor Shparlinski, y el artículo Complejidad de algunos problemas aritméticos para polinomios binarios de Eric Allender, Anna Bernasconi, Carsten Damm, Joachim von zur Gathen, Michael Saks e Igor Shparlinski.
Pregunta relacionada en MO: Proporción de números primos de bits impares
