# Riemann theta function inequality for a class of large random matrices

The following is essentially the same question as in this previous post, but since I have completely re-formulated it (hopefully for the better ;-), I decided to post a new question instead of an edit.

I would be very grateful for any suggestion how to approach a proof of the conjecture below, or for any reference to a relevant publication.

The Riemann theta function is usually defined as follows, for a symmetric $n{\times}n$ matrix $\Omega$ with ${\rm Im}\, \Omega > 0$, and for any $z \in \mathbb C^n$ : \begin{align*} \theta_{\small\rm R}(z,\Omega) = \sum_{k \in \mathbb Z^n} {\rm e}^{{\rm i}\pi \big( k^{\rm T} \Omega\, k + 2 k^{\rm T} z \big)} \ . \tag*{(1)} \end{align*}

Now let $M$ be a $m{\times}n$ ($m<n$) Toeplitz or circulant matrix with random entries $\pm1$, and let $\gamma>0$ be some constant. Set $z=0$ and $\Omega = {\small\frac{\rm i}\pi} \big( I_n + \gamma\, M^{\rm T}M \big)$ (where $I_n$ is the $n{\times}n$ unit matrix), and consider the following $n$-dimensional "gaussian sum": \begin{align*} \theta_{\small\rm R}(0,\Omega) = \sum_{k \in \mathbb Z^n} {\rm e}^{-k^{\rm T}\big(I_n+\gamma M^{\rm T}M\big)k} \ . \tag*{(2)} \end{align*}

I want to bound this sum by its average over the orthogonal group ${\rm O}(n)$, multiplied with some factor which is exponential in $n$. More precisely, I would like to prove the conjecture below. Before stating the conjecture, let me define a normalization constant ($\theta_3$ denotes the Jacobi theta function) \begin{align*} a_0 = \theta_3(0,{\rm e}^{-1}) = \sum_{k=-\infty}^\infty {\rm e}^{-k^2} \quad (\approx \sqrt\pi) \ , \tag*{(3)} \end{align*} so that for instance $\theta_{\small\rm R}(0,\Omega)\big|_{\gamma=0} = a_0^n$.

Conjecture 1:

Let $\eta$, $\xi$ be real constants with $0<\eta<\xi$. Consider a sequence of $m{\times}n$ random $\pm1$ matrices $M$ of circulant, Toeplitz, or general form, with $n$ monotonically increasing and $m$ obeying the inequalities $\eta \leq m\frac{\ln n}{n} \leq \xi$. Then there exist constants $\gamma,\, C > 0$ (with $C < a_0$) and $p \in\, ]0,1[$, all independent of $m$ and $n$, such that for large enough $n$ the following inequality holds with probability $\geq\!p$ (in the $M$ ensemble): \begin{align*} \theta_{\small\rm R}(0,\Omega) &\leq C^n \Big\langle \theta_{\small\rm R}\big(0,R^{\rm T}\Omega R\big) \Big\rangle_{R\in {\rm O}(n)} \ , \tag*{(4)} \\ \text{where }\hspace{2cm} \Omega &= {\small\frac{\rm i}\pi} \big( I_n + \gamma\, M^{\rm T}M \big) \tag*{(5)} \ . \end{align*} Here $\big\langle {\cdot} \big\rangle_{R\in {\rm O}(n)}$ denotes the average over a uniformly (i.e., Haar) distributed orthogonal random matrix $R$.

Background:

I need this (or something like this) proposition in an attempt to prove an entropy conjecture for large random Bernoulli-Toeplitz matrices (Conjecture 1 on p. 16 of this preprint by Clifford et al. 2015), which is essentially equivalent to Conjecture 2 in this previous question.

Motivation of the conjecture:

Here I'll give a heuristic motivation of the specific form of the conjectured bound (4). Consider the spectral decomposition of the (symmetric) $n{\times}n$ matrix $M^{\rm T}M$. All eigenvectors are real and non-negative, and the eigenbasis is a family of orthonormal vectors in $\mathbb R^n$. It can be shown that for large $m$, $n$ (and $m/n$ small), the eigenvalues are concentrated in an interval of width $\sim \sqrt{mn}$ around the value $n$; more precisely, their asymptotic distribution turns out to be sub-gaussian with mean $n$ and variance $mn$. In contrast, very little seems to be known about the distribution of the eigenvectors in this special case of random matrices of Toeplitz form (they are much more difficult to handle than random matrices with independent entries). However, we may argue heuristically as follows. Since $M^{\rm T}M$ is a random matrix, its basis of eigenvectors should be in some sense "randomly" oriented relative to the canonical basis of $\mathbb R^n$, and so one might expect that the sum behaves asymptotically (for large $m$ and $n$) like its average over all orientations of the basis in $\mathbb R^n$: \begin{align*} \theta_{\small\rm R}(0,\Omega) \sim \Big\langle \theta_{\small\rm R}\big(0,R^{\rm T}\Omega R\big) \Big\rangle_{R\in {\rm O}(n)} \ . \tag*{(6)} \end{align*} The right hand side of (6) now has the interesting property that it does not depend on the eigenvectors of $M^{\rm T}M$ anymore, only on the eigenvalue spectrum, and therefore it is much easier to estimate than the left hand side. For my purposes I only need the weaker inequality (4) to hold with nonzero probability.

Further remarks:

1. For (4) to be non-trivial, the definition (1) of the Riemann theta function by a discrete sum is essential. For instance, if the gaussian sum were replaced by a gaussian integral with the same exponent ${\rm i}\pi k^{\rm T} \Omega_\gamma k$, then the averaging $\big\langle {\cdot} \big\rangle_{R\in {\rm O}(n)}$ in (4) would have no effect at all on this integral.

2. Also the assumption $C < a_0$ in Conjecture 1 is essential for (4) to be non-trivial. The reason is the following. For any fixed $M$, the value of $\theta_{\small\rm R}(0,\Omega_\gamma)$ in (4) is monotonically increasing with decreasing $\gamma>0$, and so (for the definition of $a_0$, see (¤1.2)) \begin{align*} 1 \leq \theta_{\small\rm R}(0,\Omega_\gamma) \leq \theta_{\small\rm R}(0,\Omega)\big|_{\gamma=0} = \theta_3(0,{\rm e}^{-1})^n = a_0^n \ . \tag*{(7)} \end{align*} As a consequence, inequality (4) is trivially true for any $C \geq a_0$.

3. The probabilistic formulation of Conjecture 1 is essential as well, since (4) does not hold for all $M$ in the stochastic ensemble. The simplest counterexample --- in fact the only one I have found so far --- is $M=(1)_{m\times n}$ (the $m{\times}n$ matrix whose entries are all equal to $1$), which trivially is both Toeplitz and circulant. This particular choice implies $M^{\rm T}\!M = m\, (1)_{n\times n}$ (the $n{\times}n$ matrix with all entries equal to $m$), which has one large eigenvalue $\lambda = mn$, with corresponding eigenvector $v = (1)_{n\times1}$, and all remaining eigenvalues are equal to $0$. One can then show that, in this case, as $n\to \infty$ the left hand side of (6) is asymptotically equal to $a_0^n$, whereas the right hand side becomes, for $m \geq \eta\frac{n}{\ln n}$ (with any fixed $\eta>2\ln a_0$), eventually smaller than $(1+\epsilon)^n$ for any given $\epsilon>0$. As a consequence, (4) is not valid for $C<a_0$.

4. Since the matrix $M$ has $m$ rows, the rank of $M^{\rm T}\!M$ is at most $m$. It can be shown that for large $m$, $n$ (and $m/n$ small), the eigenvalues of $M^{\rm T}\!M$ are concentrated in a region of width $\sim\! \sqrt{mn}$ around their mean value $n$; more precisely, their asymptotic distribution turns out to be sub-gaussian with mean $n$ and variance $mn$ (see Lemma 8). Therefore, we have approximately $M^{\rm T}\!M \approx n\,\Pi$, where $\Pi$ is some $n{\times}n$ projection matrix of rank $m$. One may then be tempted to conjecture that (4) holds for all matrices $\Omega$ of the form $\Omega = \frac{\rm i}\pi \big( I_n + \gamma\,n\,\Pi \big)$, where $\Pi$ is any $n{\times}n$ projection matrix of rank $m$ (i.e., with ${\rm Tr}\,\Pi = m$). This is, however, not true, as the following simple counterexample shows (again the only one I have found so far). Consider a diagonal projection matrix $\Pi$ (so that $\Pi$ has $m$ diagonal entries equal to $1$, and the remaining $n{-}m$ equal to $0$). Then obviously $\theta_{\small\rm R}(0,\Omega)$ $= \theta_3(0,{\rm e}^{-1-\gamma n})^m a_0^{n-m}$ $\geq a_0^{n-m}$, and thus $\theta_{\small\rm R}(0,\Omega_\gamma)^{1/n}$ $\geq a_0^{1-m/n}$ $\to a_0$ as $n\to\infty$, since $\frac mn \to 0$ by assumption. Together with (7) this in turn implies that $\theta_{\small\rm R}(0,\Omega_\gamma)^{1/n}$ $\to a_0$. Like in remark 3.\ above, it follows that (4) cannot hold for $C<a_0$.

5. For our purposes it would actually be sufficient in Conjecture 1 to assume $p>c/n$ with some positive constant $c$ (instead of a fixed $p>0$), since for $n\to\infty$ this already insures the existence of an arbitrary large number of matrices $M$ within the ensemble which satisfy (4). (However, I doubt that it would make the conjecture any easier to prove.)

6. Apart from the specific application I have in mind here, it may be interesting to investigate bounds of the kind (4) for other (or more general) random matrix ensembles. Does anybody know if that has been done? I believe that in cases where so-called "quantum unique ergodicity" (meaning, roughly speaking, "asymptotically uniform" distribution of eigenvectors with respect to ${\rm O}(n)$, as $n\to\infty$) has been proved, presumably any $C>1$ in (4) should do. This would then include, for instance, the cases of matrices $\Omega = f(H)$ with $H$ belonging to ${\rm GOE}(n)$, ${\rm GUE}(n)$, or ${\rm GSE}(n)$, or to the Wigner matrices ($f$ being any analytic function with ${\rm Im}f >0$ on $\mathbb R$, in order to insure convergence of the sum (2)), but probably also more general ensembles [Knowles and Yin 2011, Tao and Vu 2012, Bourgade and Yau 2013, Bloemendal et al. 2014]. The question would then be whether an inequality like (4) can be established in a case where the detailed eigenvector distribution is not known.