En un trabajo reciente con Alex Arkhipov en "La Complejidad Computacional Lineal Óptica," necesitamos asumir una razonable sonido probabilística de la conjetura: a saber, que la permanente de una matriz de yo.yo.d. Gauss entradas es "demasiado concentrada alrededor de 0." He aquí una declaración formal de nuestra conjetura:
Existe un polinomio $p$ tal que para todos los $n$ e $\delta>0$, $\Pr_{X\sim\mathcal{N}\left( 0,1\right) _{\mathbb{C}}^{n\times n}}\left[\left\vert \operatorname*{Per}\left( X\right) \right\vert \leq \frac{\sqrt{n!}}{p\left( n/\delta\right) }\right] \leq \delta. $
Esta conjetura parece muy interesante, incluso fuera de nuestra aplicación, así que me quiso llevar a la atención de la gente-tal vez hay una sencilla/conocido prueba de que estamos perdiendo!
Aquí es lo que sabemos:
- La expectativa de Per(X) es de curso 0 (por simetría), mientras que la desviación estándar es $\sqrt{n!}$. Por lo tanto, nuestra conjetura, básicamente, dice que "Por(X) es exponencialmente más pequeño que su desviación estándar sólo un 1/poli(n) de la fracción del tiempo."
- Recientemente, Terry Tao y Van Vu resultó ser un maravilloso anti-concentración obligado para los permanentes de Bernoulli matrices, que puede ser enunciada de la siguiente manera: para todos los $\varepsilon > 0$ y suficientemente grande n, $\Pr_{X\in\left\{ -1,1\right\} ^{n\times n}}\left[ \left\vert \operatorname*{Por}\left( X\right) \right\vert \leq \frac{\sqrt{n!}% }{n^{\varepsilon n}}\right] \leq \frac{1}{n^{0.1}}.$ Por desgracia, su resultado se queda corto de lo que necesitamos en tres aspectos. En primer lugar, es de Bernoulli matrices en lugar de Gauss de las matrices. (Aunque, por supuesto, el de Gauss caso bien podría ser más fácil que en el caso de Bernoulli, que es nuestra principal razón para el optimismo!) Segundo, y más importante, el Tao y el Vu solo demostrar que Por(X) es de al menos 1/nes la fracción de su desviación estándar, con alta probabilidad, mientras que necesitamos que al menos un 1/poli(n) de la fracción. Tercero, ellos-límite superior de la probabilidad de un "evento malo" por 1/n0.1, mientras que nos gustaría-límite superior es por 1/p(n) para cualquier polinomio p.
- La evidencia numérica que hemos obtenido es muy consistente con nuestra conjetura de ser verdad (ver figura de abajo).
- Podemos demostrar que nuestra conjetura tiene el factor determinante en el lugar de la permanente. Para ello, utilizamos el hecho de que si X es Gaussiana, entonces, debido a la rotación de la invariancia de la Gaussiana de la medida, no hay una fórmula explícita para todos los momentos de Det(X) -- incluso las fracciones y la inversa momentos.
- Uno podría preguntarse si también podemos calcular los momentos de orden superior de Per(X), y el uso que para probar nuestra conjetura. De hecho, se puede demostrar que $\operatorname*{E}_{X\sim\mathcal{N}\left( 0,1\right) _{\mathbb{C}}^{n\times n}}\left[ \left\vert \operatorname*{Per}\left( X\right)\right\vert ^{4}\right] =\left( n!\right) ^{2}\left( n+1\right)$, lo que implica entonces la siguiente débil contra la concentración de la envolvente: para todos β<1, $\Pr_{X\sim\mathcal{N}\left( 0,1\right) _{\mathbb{C}}^{n\times n}}\left[ \left\vert \operatorname*{Por}\left( X\right) \right\vert \geq \beta\sqrt{n!}\right] \geq\frac{\left( 1-\beta^{2}\right) ^{2}}{n+1}$. Por desgracia, la informática, la 6ª, 8ª, y más momentos parece difícil.
Consulte la sección 8 de nuestro papel para las pruebas 4 y 5.
Corto de probar nuestros anti-concentración de conjeturas, aquí hay dos más fáciles de preguntas cuyas respuestas también sería de mucho interés:
- Podemos, al menos, redarguye Tao y Vu enlazado Gaussiana matrices en lugar de Bernoulli matrices? En su artículo, Tao y Vu decir que el resultado se mantiene para "prácticamente ninguna (no degenerado) distribución discreta." Yo no creo que la distribución Gaussiana presente graves dificultades, pero no estoy seguro.
- ¿El pdf de Per(X) difieren en el origen? (No sabemos la respuesta a esa pregunta en el caso de Det(X).) No sé de ningún formal implicaciones entre esta pregunta y la anti-concentración pregunta, pero sería de gran respuesta de todos modos.