In a <a href="http://www.scottaaronson.com/papers/optics.pdf">recent paper with Alex Arkhipov</a> on "The Computational Complexity of Linear Optics," we needed to assume a reasonable-sounding probabilistic conjecture: namely, that the permanent of a matrix of i.i.d. Gaussian entries is "not too concentrated around 0."  Here's a formal statement of our conjecture:

<blockquote>
There exists a polynomial $p$ such that for all $n$ and $\delta>0$,

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\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. $

</blockquote>

This conjecture seems interesting even apart from our application, so I wanted to bring it to people's attention -- maybe there's a simple/known proof that we're missing!

Here's what we do know:

<ol>
<li>The expectation of Per(X) is of course 0 (by symmetry), while the standard deviation is $\sqrt{n!}$.  Thus, our conjecture basically says that "Per(X) is polynomially smaller than its standard deviation only a 1/poly(n) fraction of the time."

<li>Recently, Terry Tao and Van Vu proved a <a href="http://arxiv.org/PS_cache/arxiv/pdf/0804/0804.2362v3.pdf">wonderful anti-concentration bound</a> for the permanents of Bernoulli matrices, which can be stated as follows: for all $\varepsilon > 0$ and sufficiently large n,

$\Pr_{X\in\left\{  -1,1\right\}  ^{n\times n}}\left[  \left\vert
\operatorname*{Per}\left(  X\right)  \right\vert \leq \frac{\sqrt{n!}%
}{n^{\varepsilon n}}\right]  \leq \frac{1}{n^{0.1}}.$

Unfortunately, their result falls short of what we need in three respects.  First, it's for Bernoulli matrices rather than Gaussian matrices.  (Though of course, the Gaussian case might well be <i>easier</i> than the Bernoulli case, which is our main reason for optimism!)  Second, and most important, Tao and Vu only prove that Per(X) is at least a 1/n<sup>&epsilon;n</sup> fraction of its standard deviation with high probability, whereas we need that it's at least a 1/poly(n) fraction.  Third, they upper-bound the probability of a "bad event" by 1/n<sup>0.1</sup>, whereas we'd like to upper-bound it by 1/p(n) for any polynomial p.

<li>The numerical evidence that we've obtained is strongly consistent with our conjecture being true (see figure below).

<li>We can prove that our conjecture holds with the determinant in place of the permanent.  To do so, we use the fact that if X is Gaussian, then because of the rotational invariance of the Gaussian measure, there's an explicit formula for all the moments of Det(X) -- even the fractional and inverse moments.

<li>One might wonder if we can also calculate the higher moments of Per(X), and use that to prove our conjecture.  Indeed, we can show that $\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)$, which then implies the following weak anti-concentration bound: for all &beta;&lt;1, $\Pr_{X\sim\mathcal{N}\left(  0,1\right)  _{\mathbb{C}}^{n\times n}}\left[  \left\vert \operatorname*{Per}\left(  X\right)  \right\vert \geq
\beta\sqrt{n!}\right]  \geq\frac{\left(  1-\beta^{2}\right)  ^{2}}{n+1}$.  Unfortunately, computing the 6th, 8th, and higher moments seems difficult.
</ol>

See section 8 of <a href="http://www.scottaaronson.com/papers/optics.pdf">our paper</a> for the proofs of 4 and 5.

Short of proving our anti-concentration conjecture, here are two easier questions whose answers would also greatly interest us:

<ul>
<li>Can we at least reprove Tao and Vu's bound for Gaussian matrices rather than Bernoulli matrices?  In their paper, Tao and Vu say their result holds for "virtually any (not too degenerate) discrete distribution."  I don't <i>think</i> the Gaussian distribution would present serious new difficulties, but I'm not sure.
<li>Does the pdf of Per(X) diverge at the origin?  (We don't even know the answer to that question in the case of Det(X).)  I don't know of any formal implications between this question and the anti-concentration question, but it would be great to answer anyway.
</ul>

![alt text][2] [(source: Wayback Machine)][1]


  [1]: https://web.archive.org/web/20141229100424im_/http://www.scottaaronson.com/perdet.jpg
  [2]: https://i.sstatic.net/XDYvN.jpg