# What is $\mathbb{E} [\max_{\sigma \in \{ \pm 1\}^n} \sigma^T Z \sigma]$ for a random Gaussian matrix $Z$?

Given an $$n \times n$$ random matrix $$\mathbf{Z}$$ with each entry i.i.d. $$\mathcal{N} (0,1)$$, what is $$\mathbb{E} [\max_{\sigma \in \{ \pm 1\}^n} \sigma^T Z \sigma]$$ as $$n \to \infty$$? If this is too much to ask, are there any good known upper or lower bounds?

This gives a lower bound of $$\frac{4}{3\sqrt{\pi}}n^{3/2}+O(\sqrt{n})$$ and an upper bound of $$2n^{3/2}+O(\sqrt{n})$$. Note: in the arguments below, I messed up the constants somewhere, so I'm not sure what the correct constants they should give is. The arguments should still work.
To get a lower bound, we can try to build $$\sigma$$ greedily. Choose $$\sigma_1$$ arbitrarily, and choose $$\sigma_j$$ depending on $$\{\sigma_i,Z_{ij},Z_{ji}\mid i. When we are choosing $$\sigma_j$$, we are trying to maximize $$\sigma_j\sum_{i Since all the $$Z_{ij}$$ and $$Z_{ji}$$ are iid $$\mathcal N(0,1)$$ independent of $$\{\sigma_i\mid i, we get that $$\sum_{i, so by the right choice of $$\sigma_j$$, we can get $$\mathbb E\left[\sigma_j\sum_{i where $$\sqrt{2/\pi}=\mathbb E|x|$$ for $$x\sim \mathcal N(0,1)$$. Finally, we get $$\mathbb E[ \sigma^TZ\sigma]=E\left[\sum_{i=1}^n Z_{ii}\sigma_i^2+\sum_{j=1}^n \sigma_j\sum_{i I'm sure there are more precise ways to evaluate the last sum, but just comparing it to Riemann sums from above and below, we can get $$\sum_{j=1}^n \sqrt{j-1}=n^{3/2}\int_0^1\sqrt{x} dx+O(\sqrt{n})=\frac{2}{3}n^{3/2}+O(\sqrt{n})$$ putting it all together, this greedy construction yields a lower bound of $$\mathbb E[ \sigma^TZ\sigma]\ge \frac{4}{3\sqrt{\pi}}n^{3/2}+O(\sqrt{n})$$ for well-chosen $$\sigma$$ (hopefully I didn't mess up the coefficient in front).
To get the upper bound, we note that for any fixed $$\sigma$$, we have that $$\sigma^TZ\sigma\sim \mathcal N(0,n^2)$$, so (this is not using optimal bounds on erf) $$\mathbb P\left[\sigma^TZ\sigma>Cn^{3/2}\right]<\exp\left(-\frac{C^2}{2}n\right)$$ so, since there are only $$2^n$$ choices for $$\sigma$$, we have $$\mathbb P\left[\max_\sigma \sigma^TZ\sigma>Cn^{3/2}\right]<\exp\left(\left(2-\frac{C^2}{2}\right)n\right)$$ Then we use $$\mathbb E(\max_\sigma \sigma^TZ\sigma>Cn^{3/2})\le 2n^{3/2}+n^{3/2}\int_{2n^{3/2}}^\infty \mathbb P(\max_\sigma \sigma^TZ\sigma>s) ds\le n^{3/2}\left(2+\int_{2}^\infty \exp\left(\left(2-\frac{t^2}{2}\right)n\right) dtdt\right)=2n^{3/2}+O(\sqrt{n}).$$
• @Sandeep Silwal Where does the polylog come from? If you're taking the sum of $n^2$ variables, each of which is the absolute value of a Gaussian and thus has positive constant expectation, the expected value will go like $n^2$ – Sam Zbarsky Nov 14 '19 at 2:57
• @SamZbarsky did you mean $\sum \limits_{i<j}\sigma_i(Z_{ij}+Z_{ji})\sim N(0,\sqrt{2(j-1)})$ instead of $\sigma_{i<j}(Z_{ij}+Z_{ji})\sim N(0,\sqrt{2(j-1)})$? Also, could you clarify on how you get the square root in the variance? Its not clear to me. Thank you for your help. – sigmatau Nov 14 '19 at 14:35
• @sigmatau Thank you, I fixed that. I messed up my notation. I thought for some reason that in $\mathcal N(0,b)$, the $b$ was supposed to be standard deviation, not variance. It's fixed now. – Sam Zbarsky Nov 14 '19 at 21:23
This is related to the Sherrington-Kirkpatrick Spin Glass model. In arxiv.org/pdf/1412.0170.pdf, Dmitry Panchenko writes that $$\lim_{N\to\infty} \frac{1}{N} \mathbb{E}\big[\max_\sigma \frac{1}{\sqrt{N}} \sum_{i with $$g_{ij}$$ iid standard normals. This is a consequence of the Parisi formula. I believe your desired asymptotic should then be $$0.7633\sqrt{2}N^{3/2}+ o(N^{3/2})$$.