Category Archive

You are currently browsing the category archive for the ‘math.SP’ category.

The effective potential of an M-matrix

6 January, 2021 in math.AP, math.SP, paper | Tags: effective potential, eigenvectors, landscape theory, localisation, Marcel Filoche, Svitlana Mayboroda | by Terence Tao | 7 comments

Marcel Filoche, Svitlana Mayboroda, and I have just uploaded to the arXiv our preprint “The effective potential of an ${M}$ -matrix“. This paper explores the analogue of the effective potential of Schrödinger operators ${-\Delta + V}$ provided by the “landscape function” ${u}$ , when one works with a certain type of self-adjoint matrix known as an ${M}$ -matrix instead of a Schrödinger operator.

Suppose one has an eigenfunction

$\displaystyle (-\Delta + V) \phi = E \phi$

of a Schrödinger operator ${-\Delta+V}$ , where ${\Delta}$ is the Laplacian on ${{\bf R}^d}$ , ${V: {\bf R}^d \rightarrow {\bf R}}$ is a potential, and ${E}$ is an energy. Where would one expect the eigenfunction ${\phi}$ to be concentrated? If the potential ${V}$ is smooth and slowly varying, the correspondence principle suggests that the eigenfunction ${\phi}$ should be mostly concentrated in the potential energy wells ${\{ x: V(x) \leq E \}}$ , with an exponentially decaying amount of tunnelling between the wells. One way to rigorously establish such an exponential decay is through an argument of Agmon, which we will sketch later in this post, which gives an exponentially decaying upper bound (in an ${L^2}$ sense) of eigenfunctions ${\phi}$ in terms of the distance to the wells ${\{ V \leq E \}}$ in terms of a certain “Agmon metric” on ${{\bf R}^d}$ determined by the potential ${V}$ and energy level ${E}$ (or any upper bound ${\overline{E}}$ on this energy). Similar exponential decay results can also be obtained for discrete Schrödinger matrix models, in which the domain ${{\bf R}^d}$ is replaced with a discrete set such as the lattice ${{\bf Z}^d}$ , and the Laplacian ${\Delta}$ is replaced by a discrete analogue such as a graph Laplacian.

When the potential ${V}$ is very “rough”, as occurs for instance in the random potentials arising in the theory of Anderson localisation, the Agmon bounds, while still true, become very weak because the wells ${\{ V \leq E \}}$ are dispersed in a fairly dense fashion throughout the domain ${{\bf R}^d}$ , and the eigenfunction can tunnel relatively easily between different wells. However, as was first discovered in 2012 by my two coauthors, in these situations one can replace the rough potential ${V}$ by a smoother effective potential ${1/u}$ , with the eigenfunctions typically localised to a single connected component of the effective wells ${\{ 1/u \leq E \}}$ . In fact, a good choice of effective potential comes from locating the landscape function ${u}$ , which is the solution to the equation ${(-\Delta + V) u = 1}$ with reasonable behavior at infinity, and which is non-negative from the maximum principle, and then the reciprocal ${1/u}$ of this landscape function serves as an effective potential.

There are now several explanations for why this particular choice ${1/u}$ is a good effective potential. Perhaps the simplest (as found for instance in this recent paper of Arnold, David, Jerison, and my two coauthors) is the following observation: if ${\phi}$ is an eigenvector for ${-\Delta+V}$ with energy ${E}$ , then ${\phi/u}$ is an eigenvector for ${-\frac{1}{u^2} \mathrm{div}(u^2 \nabla \cdot) + \frac{1}{u}}$ with the same energy ${E}$ , thus the original Schrödinger operator ${-\Delta+V}$ is conjugate to a (variable coefficient, but still in divergence form) Schrödinger operator with potential ${1/u}$ instead of ${V}$ . Closely related to this, we have the integration by parts identity

$\displaystyle \int_{{\bf R}^d} |\nabla f|^2 + V |f|^2\ dx = \int_{{\bf R}^d} u^2 |\nabla(f/u)|^2 + \frac{1}{u} |f|^2\ dx \ \ \ \ \ (1)$

for any reasonable function ${f}$ , thus again highlighting the emergence of the effective potential ${1/u}$ .

These particular explanations seem rather specific to the Schrödinger equation (continuous or discrete); we have for instance not been able to find similar identities to explain an effective potential for the bi-Schrödinger operator ${\Delta^2 + V}$ .

In this paper, we demonstrate the (perhaps surprising) fact that effective potentials continue to exist for operators that bear very little resemblance to Schrödinger operators. Our chosen model is that of an ${M}$ -matrix: self-adjoint positive definite matrices ${A}$ whose off-diagonal entries are negative. This model includes discrete Schrödinger operators (with non-negative potentials) but can allow for significantly more non-local interactions. The analogue of the landscape function would then be the vector ${u := A^{-1} 1}$ , where ${1}$ denotes the vector with all entries ${1}$ . Our main result, roughly speaking, asserts that an eigenvector ${A \phi = E \phi}$ of ${A}$ will then be exponentially localised to the “potential wells” ${K := \{ j: \frac{1}{u_j} \leq E \}}$ , where ${u_j}$ denotes the coordinates of the landscape function ${u}$ . In particular, we establish the inequality

$\displaystyle \sum_k \phi_k^2 e^{2 \rho(k,K) / \sqrt{W}} ( \frac{1}{u_k} - E )_+ \leq W \max_{i,j} |a_{ij}|$

if ${\phi}$ is normalised in ${\ell^2}$ , where the connectivity ${W}$ is the maximum number of non-zero entries of ${A}$ in any row or column, ${a_{ij}}$ are the coefficients of ${A}$ , and ${\rho}$ is a certain moderately complicated but explicit metric function on the spatial domain. Informally, this inequality asserts that the eigenfunction ${\phi_k}$ should decay like ${e^{-\rho(k,K) / \sqrt{W}}}$ or faster. Indeed, our numerics show a very strong log-linear relationship between ${\phi_k}$ and ${\rho(k,K)}$ , although it appears that our exponent ${1/\sqrt{W}}$ is not quite optimal. We also provide an associated localisation result which is technical to state but very roughly asserts that a given eigenvector will in fact be localised to a single connected component of ${K}$ unless there is a resonance between two wells (by which we mean that an eigenvalue for a localisation of ${A}$ associated to one well is extremely close to an eigenvalue for a localisation of ${A}$ associated to another well); such localisation is also strongly supported by numerics. (Analogous results for Schrödinger operators had been previously obtained by the previously mentioned paper of Arnold, David, Jerison, and my two coauthors, and to quantum graphs in a very recent paper of Harrell and Maltsev.)

Our approach is based on Agmon’s methods, which we interpret as a double commutator method, and in particular relying on exploiting the negative definiteness of certain double commutator operators. In the case of Schrödinger operators ${-\Delta+V}$ , this negative definiteness is provided by the identity

$\displaystyle \langle [[-\Delta+V,g],g] u, u \rangle = -2\int_{{\bf R}^d} |\nabla g|^2 |u|^2\ dx \leq 0 \ \ \ \ \ (2)$

for any sufficiently reasonable functions ${u, g: {\bf R}^d \rightarrow {\bf R}}$ , where we view ${g}$ (like ${V}$ ) as a multiplier operator. To exploit this, we use the commutator identity

$\displaystyle \langle g [\psi, -\Delta+V] u, g \psi u \rangle = \frac{1}{2} \langle [[-\Delta+V, g \psi],g\psi] u, u \rangle$

$\displaystyle -\frac{1}{2} \langle [[-\Delta+V, g],g] \psi u, \psi u \rangle$

valid for any ${g,\psi,u: {\bf R}^d \rightarrow {\bf R}}$ after a brief calculation. The double commutator identity then tells us that

$\displaystyle \langle g [\psi, -\Delta+V] u, g \psi u \rangle \leq \int_{{\bf R}^d} |\nabla g|^2 |\psi u|^2\ dx.$

If we choose ${u}$ to be a non-negative weight and let ${\psi := \phi/u}$ for an eigenfunction ${\phi}$ , then we can write

$\displaystyle [\psi, -\Delta+V] u = [\psi, -\Delta+V - E] u = \psi (-\Delta+V - E) u$

and we conclude that

$\displaystyle \int_{{\bf R}^d} \frac{(-\Delta+V-E)u}{u} |g|^2 |\phi|^2\ dx \leq \int_{{\bf R}^d} |\nabla g|^2 |\phi|^2\ dx. \ \ \ \ \ (3)$

We have considerable freedom in this inequality to select the functions ${u,g}$ . If we select ${u=1}$ , we obtain the clean inequality

$\displaystyle \int_{{\bf R}^d} (V-E) |g|^2 |\phi|^2\ dx \leq \int_{{\bf R}^d} |\nabla g|^2 |\phi|^2\ dx.$

If we take ${g}$ to be a function which equals ${1}$ on the wells ${\{ V \leq E \}}$ but increases exponentially away from these wells, in such a way that

$\displaystyle |\nabla g|^2 \leq \frac{1}{2} (V-E) |g|^2$

outside of the wells, we can obtain the estimate

$\displaystyle \int_{V > E} (V-E) |g|^2 |\phi|^2\ dx \leq 2 \int_{V < E} (E-V) |\phi|^2\ dx,$

which then gives an exponential type decay of ${\phi}$ away from the wells. This is basically the classic exponential decay estimate of Agmon; one can basically take ${g}$ to be the distance to the wells ${\{ V \leq E \}}$ with respect to the Euclidean metric conformally weighted by a suitably normalised version of ${V-E}$ . If we instead select ${u}$ to be the landscape function ${u = (-\Delta+V)^{-1} 1}$ , (3) then gives

$\displaystyle \int_{{\bf R}^d} (\frac{1}{u} - E) |g|^2 |\phi|^2\ dx \leq \int_{{\bf R}^d} |\nabla g|^2 |\phi|^2\ dx,$

and by selecting ${g}$ appropriately this gives an exponential decay estimate away from the effective wells ${\{ \frac{1}{u} \leq E \}}$ , using a metric weighted by ${\frac{1}{u}-E}$ .

It turns out that this argument extends without much difficulty to the ${M}$ -matrix setting. The analogue of the crucial double commutator identity (2) is

$\displaystyle \langle [[A,D],D] u, u \rangle = \sum_{i \neq j} a_{ij} u_i u_j (d_{ii} - d_{jj})^2 \leq 0$

for any diagonal matrix ${D = \mathrm{diag}(d_{11},\dots,d_{NN})}$ . The remainder of the Agmon type arguments go through after making the natural modifications.

Numerically we have also found some aspects of the landscape theory to persist beyond the ${M}$ -matrix setting, even though the double commutators cease being negative definite, so this may not yet be the end of the story, but it does at least demonstrate that utility the landscape does not purely rely on identities such as (1).

Inverting the Schur complement, and large-dimensional Gelfand-Tsetlin patterns

16 September, 2017 in expository, math.PR, math.RA, math.SP | Tags: free probability, Gelfand-Tsetlin patterns, Schur complement | by Terence Tao | 7 comments

Suppose we have an ${n \times n}$ matrix ${M}$ that is expressed in block-matrix form as

$\displaystyle M = \begin{pmatrix} A & B \\ C & D \end{pmatrix}$

where ${A}$ is an ${(n-k) \times (n-k)}$ matrix, ${B}$ is an ${(n-k) \times k}$ matrix, ${C}$ is an ${k \times (n-k)}$ matrix, and ${D}$ is a ${k \times k}$ matrix for some ${1 < k < n}$ . If ${A}$ is invertible, we can use the technique of Schur complementation to express the inverse of ${M}$ (if it exists) in terms of the inverse of ${A}$ , and the other components ${B,C,D}$ of course. Indeed, to solve the equation

$\displaystyle M \begin{pmatrix} x & y \end{pmatrix} = \begin{pmatrix} a & b \end{pmatrix},$

where ${x, a}$ are ${(n-k) \times 1}$ column vectors and ${y,b}$ are ${k \times 1}$ column vectors, we can expand this out as a system

$\displaystyle Ax + By = a$

$\displaystyle Cx + Dy = b.$

Using the invertibility of ${A}$ , we can write the first equation as

$\displaystyle x = A^{-1} a - A^{-1} B y \ \ \ \ \ (1)$

and substituting this into the second equation yields

$\displaystyle (D - C A^{-1} B) y = b - C A^{-1} a$

and thus (assuming that ${D - CA^{-1} B}$ is invertible)

$\displaystyle y = - (D - CA^{-1} B)^{-1} CA^{-1} a + (D - CA^{-1} B)^{-1} b$

and then inserting this back into (1) gives

$\displaystyle x = (A^{-1} + A^{-1} B (D - CA^{-1} B)^{-1} C A^{-1}) a - A^{-1} B (D - CA^{-1} B)^{-1} b.$

Comparing this with

$\displaystyle \begin{pmatrix} x & y \end{pmatrix} = M^{-1} \begin{pmatrix} a & b \end{pmatrix},$

we have managed to express the inverse of ${M}$ as

$\displaystyle M^{-1} =$

$\displaystyle \begin{pmatrix} A^{-1} + A^{-1} B (D - CA^{-1} B)^{-1} C A^{-1} & - A^{-1} B (D - CA^{-1} B)^{-1} \\ - (D - CA^{-1} B)^{-1} CA^{-1} & (D - CA^{-1} B)^{-1} \end{pmatrix}. \ \ \ \ \ (2)$

One can consider the inverse problem: given the inverse ${M^{-1}}$ of ${M}$ , does one have a nice formula for the inverse ${A^{-1}}$ of the minor ${A}$ ? Trying to recover this directly from (2) looks somewhat messy. However, one can proceed as follows. Let ${U}$ denote the ${n \times k}$ matrix

$\displaystyle U := \begin{pmatrix} 0 \\ I_k \end{pmatrix}$

(with ${I_k}$ the ${k \times k}$ identity matrix), and let ${V}$ be its transpose:

$\displaystyle V := \begin{pmatrix} 0 & I_k \end{pmatrix}.$

Then for any scalar ${t}$ (which we identify with ${t}$ times the identity matrix), one has

$\displaystyle M + UtV = \begin{pmatrix} A & B \\ C & D+t \end{pmatrix},$

and hence by (2)

$\displaystyle (M+UtV)^{-1} =$

$\displaystyle \begin{pmatrix} A^{-1} + A^{-1} B (D + t - CA^{-1} B)^{-1} C A^{-1} & - A^{-1} B (D + t- CA^{-1} B)^{-1} \\ - (D + t - CA^{-1} B)^{-1} CA^{-1} & (D + t - CA^{-1} B)^{-1} \end{pmatrix}.$

noting that the inverses here will exist for ${t}$ large enough. Taking limits as ${t \rightarrow \infty}$ , we conclude that

$\displaystyle \lim_{t \rightarrow \infty} (M+UtV)^{-1} = \begin{pmatrix} A^{-1} & 0 \\ 0 & 0 \end{pmatrix}.$

On the other hand, by the Woodbury matrix identity (discussed in this previous blog post), we have

$\displaystyle (M+UtV)^{-1} = M^{-1} - M^{-1} U (t^{-1} + V M^{-1} U)^{-1} V M^{-1}$

and hence on taking limits and comparing with the preceding identity, one has

$\displaystyle \begin{pmatrix} A^{-1} & 0 \\ 0 & 0 \end{pmatrix} = M^{-1} - M^{-1} U (V M^{-1} U)^{-1} V M^{-1}.$

This achieves the aim of expressing the inverse ${A^{-1}}$ of the minor in terms of the inverse of the full matrix. Taking traces and rearranging, we conclude in particular that

$\displaystyle \mathrm{tr} A^{-1} = \mathrm{tr} M^{-1} - \mathrm{tr} (V M^{-2} U) (V M^{-1} U)^{-1}. \ \ \ \ \ (3)$

In the ${k=1}$ case, this can be simplified to

$\displaystyle \mathrm{tr} A^{-1} = \mathrm{tr} M^{-1} - \frac{e_n^T M^{-2} e_n}{e_n^T M^{-1} e_n} \ \ \ \ \ (4)$

where ${e_n}$ is the ${n^{th}}$ basis column vector.

We can apply this identity to understand how the spectrum of an ${n \times n}$ random matrix ${M}$ relates to that of its top left ${n-1 \times n-1}$ minor ${A}$ . Subtracting any complex multiple ${z}$ of the identity from ${M}$ (and hence from ${A}$ ), we can relate the Stieltjes transform ${s_M(z) := \frac{1}{n} \mathrm{tr}(M-z)^{-1}}$ of ${M}$ with the Stieltjes transform ${s_A(z) := \frac{1}{n-1} \mathrm{tr}(A-z)^{-1}}$ of ${A}$ :

$\displaystyle s_A(z) = \frac{n}{n-1} s_M(z) - \frac{1}{n-1} \frac{e_n^T (M-z)^{-2} e_n}{e_n^T (M-z)^{-1} e_n} \ \ \ \ \ (5)$

At this point we begin to proceed informally. Assume for sake of argument that the random matrix ${M}$ is Hermitian, with distribution that is invariant under conjugation by the unitary group ${U(n)}$ ; for instance, ${M}$ could be drawn from the Gaussian Unitary Ensemble (GUE), or alternatively ${M}$ could be of the form ${M = U D U^*}$ for some real diagonal matrix ${D}$ and ${U}$ a unitary matrix drawn randomly from ${U(n)}$ using Haar measure. To fix normalisations we will assume that the eigenvalues of ${M}$ are typically of size ${O(1)}$ . Then ${A}$ is also Hermitian and ${U(n)}$ -invariant. Furthermore, the law of ${e_n^T (M-z)^{-1} e_n}$ will be the same as the law of ${u^* (M-z)^{-1} u}$ , where ${u}$ is now drawn uniformly from the unit sphere (independently of ${M}$ ). Diagonalising ${M}$ into eigenvalues ${\lambda_j}$ and eigenvectors ${v_j}$ , we have

$\displaystyle u^* (M-z)^{-1} u = \sum_{j=1}^n \frac{|u^* v_j|^2}{\lambda_j - z}.$

One can think of ${u}$ as a random (complex) Gaussian vector, divided by the magnitude of that vector (which, by the Chernoff inequality, will concentrate to ${\sqrt{n}}$ ). Thus the coefficients ${u^* v_j}$ with respect to the orthonormal basis ${v_1,\dots,v_j}$ can be thought of as independent (complex) Gaussian vectors, divided by that magnitude. Using this and the Chernoff inequality again, we see (for ${z}$ distance ${\sim 1}$ away from the real axis at least) that one has the concentration of measure

$\displaystyle u^* (M-z)^{-1} u \approx \frac{1}{n} \sum_{j=1}^n \frac{1}{\lambda_j - z}$

and thus

$\displaystyle e_n^T (M-z)^{-1} e_n \approx \frac{1}{n} \mathrm{tr} (M-z)^{-1} = s_M(z)$

(that is to say, the diagonal entries of ${(M-z)^{-1}}$ are roughly constant). Similarly we have

$\displaystyle e_n^T (M-z)^{-2} e_n \approx \frac{1}{n} \mathrm{tr} (M-z)^{-2} = \frac{d}{dz} s_M(z).$

Inserting this into (5) and discarding terms of size ${O(1/n^2)}$ , we thus conclude the approximate relationship

$\displaystyle s_A(z) \approx s_M(z) + \frac{1}{n} ( s_M(z) - s_M(z)^{-1} \frac{d}{dz} s_M(z) ).$

This can be viewed as a difference equation for the Stieltjes transform of top left minors of ${M}$ . Iterating this equation, and formally replacing the difference equation by a differential equation in the large ${n}$ limit, we see that when ${n}$ is large and ${k \approx e^{-t} n}$ for some ${t \geq 0}$ , one expects the top left ${k \times k}$ minor ${A_k}$ of ${M}$ to have Stieltjes transform

$\displaystyle s_{A_k}(z) \approx s( t, z ) \ \ \ \ \ (6)$

where ${s(t,z)}$ solves the Burgers-type equation

$\displaystyle \partial_t s(t,z) = s(t,z) - s(t,z)^{-1} \frac{d}{dz} s(t,z) \ \ \ \ \ (7)$

with initial data ${s(0,z) = s_M(z)}$ .

Example 1 If ${M}$ is a constant multiple ${M = cI_n}$ of the identity, then ${s_M(z) = \frac{1}{c-z}}$ . One checks that ${s(t,z) = \frac{1}{c-z}}$ is a steady state solution to (7), which is unsurprising given that all minors of ${M}$ are also ${c}$ times the identity.

Example 2 If ${M}$ is GUE normalised so that each entry has variance ${\sigma^2/n}$ , then by the semi-circular law (see previous notes) one has ${s_M(z) \approx \frac{-z + \sqrt{z^2-4\sigma^2}}{2\sigma^2} = -\frac{2}{z + \sqrt{z^2-4\sigma^2}}}$ (using an appropriate branch of the square root). One can then verify the self-similar solution

$\displaystyle s(t,z) = \frac{-z + \sqrt{z^2 - 4\sigma^2 e^{-t}}}{2\sigma^2 e^{-t}} = -\frac{2}{z + \sqrt{z^2 - 4\sigma^2 e^{-t}}}$

to (7), which is consistent with the fact that a top ${k \times k}$ minor of ${M}$ also has the law of GUE, with each entry having variance ${\sigma^2 / n \approx \sigma^2 e^{-t} / k}$ when ${k \approx e^{-t} n}$ .

One can justify the approximation (6) given a sufficiently good well-posedness theory for the equation (7). We will not do so here, but will note that (as with the classical inviscid Burgers equation) the equation can be solved exactly (formally, at least) by the method of characteristics. For any initial position ${z_0}$ , we consider the characteristic flow ${t \mapsto z(t)}$ formed by solving the ODE

$\displaystyle \frac{d}{dt} z(t) = s(t,z(t))^{-1} \ \ \ \ \ (8)$

with initial data ${z(0) = z_0}$ , ignoring for this discussion the problems of existence and uniqueness. Then from the chain rule, the equation (7) implies that

$\displaystyle \frac{d}{dt} s( t, z(t) ) = s(t,z(t))$

and thus ${s(t,z(t)) = e^t s(0,z_0)}$ . Inserting this back into (8) we see that

$\displaystyle z(t) = z_0 + s(0,z_0)^{-1} (1-e^{-t})$

and thus (7) may be solved implicitly via the equation

$\displaystyle s(t, z_0 + s(0,z_0)^{-1} (1-e^{-t}) ) = e^t s(0, z_0) \ \ \ \ \ (9)$

for all ${t}$ and ${z_0}$ .

Remark 3 In practice, the equation (9) may stop working when ${z_0 + s(0,z_0)^{-1} (1-e^{-t})}$ crosses the real axis, as (7) does not necessarily hold in this region. It is a cute exercise (ultimately coming from the Cauchy-Schwarz inequality) to show that this crossing always happens, for instance if ${z_0}$ has positive imaginary part then ${z_0 + s(0,z_0)^{-1}}$ necessarily has negative or zero imaginary part.

Example 4 Suppose we have ${s(0,z) = \frac{1}{c-z}}$ as in Example 1. Then (9) becomes

$\displaystyle s( t, z_0 + (c-z_0) (1-e^{-t}) ) = \frac{e^t}{c-z_0}$

for any ${t,z_0}$ , which after making the change of variables ${z = z_0 + (c-z_0) (1-e^{-t}) = c - e^{-t} (c - z_0)}$ becomes

$\displaystyle s(t, z ) = \frac{1}{c-z}$

as in Example 1.

Example 5 Suppose we have

$\displaystyle s(0,z) = \frac{-z + \sqrt{z^2-4\sigma^2}}{2\sigma^2} = -\frac{2}{z + \sqrt{z^2-4\sigma^2}}.$

as in Example 2. Then (9) becomes

$\displaystyle s(t, z_0 - \frac{z_0 + \sqrt{z_0^2-4\sigma^2}}{2} (1-e^{-t}) ) = e^t \frac{-z_0 + \sqrt{z_0^2-4\sigma^2}}{2\sigma^2}.$

If we write

$\displaystyle z := z_0 - \frac{z_0 + \sqrt{z_0^2-4\sigma^2}}{2} (1-e^{-t})$

$\displaystyle = \frac{(1+e^{-t}) z_0 - (1-e^{-t}) \sqrt{z_0^2-4\sigma^2}}{2}$

one can calculate that

$\displaystyle z^2 - 4 \sigma^2 e^{-t} = (\frac{(1-e^{-t}) z_0 - (1+e^{-t}) \sqrt{z_0^2-4\sigma^2}}{2})^2$

and hence

$\displaystyle \frac{-z + \sqrt{z^2 - 4\sigma^2 e^{-t}}}{2\sigma^2 e^{-t}} = e^t \frac{-z_0 + \sqrt{z_0^2-4\sigma^2}}{2\sigma^2}$

which gives

$\displaystyle s(t,z) = \frac{-z + \sqrt{z^2 - 4\sigma^2 e^{-t}}}{2\sigma^2 e^{-t}}. \ \ \ \ \ (10)$

One can recover the spectral measure ${\mu}$ from the Stieltjes transform ${s(z)}$ as the weak limit of ${x \mapsto \frac{1}{\pi} \mathrm{Im} s(x+i\varepsilon)}$ as ${\varepsilon \rightarrow 0}$ ; we write this informally as

$\displaystyle d\mu(x) = \frac{1}{\pi} \mathrm{Im} s(x+i0^+)\ dx.$

In this informal notation, we have for instance that

$\displaystyle \delta_c(x) = \frac{1}{\pi} \mathrm{Im} \frac{1}{c-x-i0^+}\ dx$

which can be interpreted as the fact that the Cauchy distributions ${\frac{1}{\pi} \frac{\varepsilon}{(c-x)^2+\varepsilon^2}}$ converge weakly to the Dirac mass at ${c}$ as ${\varepsilon \rightarrow 0}$ . Similarly, the spectral measure associated to (10) is the semicircular measure ${\frac{1}{2\pi \sigma^2 e^{-t}} (4 \sigma^2 e^{-t}-x^2)_+^{1/2}}$ .

If we let ${\mu_t}$ be the spectral measure associated to ${s(t,\cdot)}$ , then the curve ${e^{-t} \mapsto \mu_t}$ from ${(0,1]}$ to the space of measures is the high-dimensional limit ${n \rightarrow \infty}$ of a Gelfand-Tsetlin pattern (discussed in this previous post), if the pattern is randomly generated amongst all matrices ${M}$ with spectrum asymptotic to ${\mu_0}$ as ${n \rightarrow \infty}$ . For instance, if ${\mu_0 = \delta_c}$ , then the curve is ${\alpha \mapsto \delta_c}$ , corresponding to a pattern that is entirely filled with ${c}$ ‘s. If instead ${\mu_0 = \frac{1}{2\pi \sigma^2} (4\sigma^2-x^2)_+^{1/2}}$ is a semicircular distribution, then the pattern is

$\displaystyle \alpha \mapsto \frac{1}{2\pi \sigma^2 \alpha} (4\sigma^2 \alpha -x^2)_+^{1/2},$

thus at height ${\alpha}$ from the top, the pattern is semicircular on the interval ${[-2\sigma \sqrt{\alpha}, 2\sigma \sqrt{\alpha}]}$ . The interlacing property of Gelfand-Tsetlin patterns translates to the claim that ${\alpha \mu_\alpha(-\infty,\lambda)}$ (resp. ${\alpha \mu_\alpha(\lambda,\infty)}$ ) is non-decreasing (resp. non-increasing) in ${\alpha}$ for any fixed ${\lambda}$ . In principle one should be able to establish these monotonicity claims directly from the PDE (7) or from the implicit solution (9), but it was not clear to me how to do so.

An interesting example of such a limiting Gelfand-Tsetlin pattern occurs when ${\mu_0 = \frac{1}{2} \delta_{-1} + \frac{1}{2} \delta_1}$ , which corresponds to ${M}$ being ${2P-I}$ , where ${P}$ is an orthogonal projection to a random ${n/2}$ -dimensional subspace of ${{\bf C}^n}$ . Here we have

$\displaystyle s(0,z) = \frac{1}{2} \frac{1}{-1-z} + \frac{1}{2} \frac{1}{1-z} = \frac{z}{1-z^2}$

and so (9) in this case becomes

$\displaystyle s(t, z_0 + \frac{1-z_0^2}{z_0} (1-e^{-t}) ) = \frac{e^t z_0}{1-z_0^2}$

A tedious calculation then gives the solution

$\displaystyle s(t,z) = \frac{(2e^{-t}-1)z + \sqrt{z^2 - 4e^{-t}(1-e^{-t})}}{2e^{-t}(1-z^2)}. \ \ \ \ \ (11)$

For ${\alpha = e^{-t} > 1/2}$ , there are simple poles at ${z=-1,+1}$ , and the associated measure is

$\displaystyle \mu_\alpha = \frac{2\alpha-1}{2\alpha} \delta_{-1} + \frac{2\alpha-1}{2\alpha} \delta_1 + \frac{1}{2\pi \alpha(1-x^2)} (4\alpha(1-\alpha)-x^2)_+^{1/2}\ dx.$

This reflects the interlacing property, which forces ${\frac{2\alpha-1}{2\alpha} \alpha n}$ of the ${\alpha n}$ eigenvalues of the ${\alpha n \times \alpha n}$ minor to be equal to ${-1}$ (resp. ${+1}$ ). For ${\alpha = e^{-t} \leq 1/2}$ , the poles disappear and one just has

$\displaystyle \mu_\alpha = \frac{1}{2\pi \alpha(1-x^2)} (4\alpha(1-\alpha)-x^2)_+^{1/2}\ dx.$

For ${\alpha=1/2}$ , one has an inverse semicircle distribution

$\displaystyle \mu_{1/2} = \frac{1}{\pi} (1-x^2)_+^{-1/2}.$

There is presumably a direct geometric explanation of this fact (basically describing the singular values of the product of two random orthogonal projections to half-dimensional subspaces of ${{\bf C}^n}$ ), but I do not know of one off-hand.

The evolution of ${s(t,z)}$ can also be understood using the ${R}$ -transform and ${S}$ -transform from free probability. Formally, letlet ${z(t,s)}$ be the inverse of ${s(t,z)}$ , thus

$\displaystyle s(t,z(t,s)) = s$

for all ${t,s}$ , and then define the ${R}$ -transform

$\displaystyle R(t,s) := z(t,-s) - \frac{1}{s}.$

The equation (9) may be rewritten as

$\displaystyle z( t, e^t s ) = z(0,s) + s^{-1} (1-e^{-t})$

and hence

$\displaystyle R(t, -e^t s) = R(0, -s)$

or equivalently

$\displaystyle R(t,s) = R(0, e^{-t} s). \ \ \ \ \ (12)$

See these previous notes for a discussion of free probability topics such as the ${R}$ -transform.

Example 6 If ${s(t,z) = \frac{1}{c-z}}$ then the ${R}$ transform is ${R(t,s) = c}$ .

Example 7 If ${s(t,z)}$ is given by (10), then the ${R}$ transform is

$\displaystyle R(t,s) = \sigma^2 e^{-t} s.$

Example 8 If ${s(t,z)}$ is given by (11), then the ${R}$ transform is

$\displaystyle R(t,s) = \frac{-1 + \sqrt{1 + 4 s^2 e^{-2t}}}{2 s e^{-t}}.$

This simple relationship (12) is essentially due to Nica and Speicher (thanks to Dima Shylakhtenko for this reference). It has the remarkable consequence that when ${\alpha = 1/m}$ is the reciprocal of a natural number ${m}$ , then ${\mu_{1/m}}$ is the free arithmetic mean of ${m}$ copies of ${\mu}$ , that is to say ${\mu_{1/m}}$ is the free convolution ${\mu \boxplus \dots \boxplus \mu}$ of ${m}$ copies of ${\mu}$ , pushed forward by the map ${\lambda \rightarrow \lambda/m}$ . In terms of random matrices, this is asserting that the top ${n/m \times n/m}$ minor of a random matrix ${M}$ has spectral measure approximately equal to that of an arithmetic mean ${\frac{1}{m} (M_1 + \dots + M_m)}$ of ${m}$ independent copies of ${M}$ , so that the process of taking top left minors is in some sense a continuous analogue of the process of taking freely independent arithmetic means. There ought to be a geometric proof of this assertion, but I do not know of one. In the limit ${m \rightarrow \infty}$ (or ${\alpha \rightarrow 0}$ ), the ${R}$ -transform becomes linear and the spectral measure becomes semicircular, which is of course consistent with the free central limit theorem.

In a similar vein, if one defines the function

$\displaystyle \omega(t,z) := \alpha \int_{\bf R} \frac{zx}{1-zx}\ d\mu_\alpha(x) = e^{-t} (- 1 - z^{-1} s(t, z^{-1}))$

and inverts it to obtain a function ${z(t,\omega)}$ with

$\displaystyle \omega(t, z(t,\omega)) = \omega$

for all ${t, \omega}$ , then the ${S}$ -transform ${S(t,\omega)}$ is defined by

$\displaystyle S(t,\omega) := \frac{1+\omega}{\omega} z(t,\omega).$

Writing

$\displaystyle s(t,z) = - z^{-1} ( 1 + e^t \omega(t, z^{-1}) )$

for any ${t}$ , ${z}$ , we have

$\displaystyle z_0 + s(0,z_0)^{-1} (1-e^{-t}) = z_0 \frac{\omega(0,z_0^{-1})+e^{-t}}{\omega(0,z_0^{-1})+1}$

and so (9) becomes

$\displaystyle - z_0^{-1} \frac{\omega(0,z_0^{-1})+1}{\omega(0,z_0^{-1})+e^{-t}} (1 + e^{t} \omega(t, z_0^{-1} \frac{\omega(0,z_0^{-1})+1}{\omega(0,z_0^{-1})+e^{-t}}))$

$\displaystyle = - e^t z_0^{-1} (1 + \omega(0, z_0^{-1}))$

which simplifies to

$\displaystyle \omega(t, z_0^{-1} \frac{\omega(0,z_0^{-1})+1}{\omega(0,z_0^{-1})+e^{-t}})) = \omega(0, z_0^{-1});$

replacing ${z_0}$ by ${z(0,\omega)^{-1}}$ we obtain

$\displaystyle \omega(t, z(0,\omega) \frac{\omega+1}{\omega+e^{-t}}) = \omega$

and thus

$\displaystyle z(0,\omega)\frac{\omega+1}{\omega+e^{-t}} = z(t, \omega)$

and hence

$\displaystyle S(0, \omega) = \frac{\omega+e^{-t}}{\omega+1} S(t, \omega).$

One can compute ${\frac{\omega+e^{-t}}{\omega+1}}$ to be the ${S}$ -transform of the measure ${(1-\alpha) \delta_0 + \alpha \delta_1}$ ; from the link between ${S}$ -transforms and free products (see e.g. these notes of Guionnet), we conclude that ${(1-\alpha)\delta_0 + \alpha \mu_\alpha}$ is the free product of ${\mu_1}$ and ${(1-\alpha) \delta_0 + \alpha \delta_1}$ . This is consistent with the random matrix theory interpretation, since ${(1-\alpha)\delta_0 + \alpha \mu_\alpha}$ is also the spectral measure of ${PMP}$ , where ${P}$ is the orthogonal projection to the span of the first ${\alpha n}$ basis elements, so in particular ${P}$ has spectral measure ${(1-\alpha) \delta_0 + \alpha \delta_1}$ . If ${M}$ is unitarily invariant then (by a fundamental result of Voiculescu) it is asymptotically freely independent of ${P}$ , so the spectral measure of ${PMP = P^{1/2} M P^{1/2}}$ is asymptotically the free product of that of ${M}$ and of ${P}$ .

On the sign patterns of entrywise positivity preservers in fixed dimension

17 August, 2017 in math.CA, math.SP, paper | Tags: Apoorva Khare, Hadamard product, Harish-Chandra-Itzykson-Zuber formula, positive definite matrices, Schur polynomials | by Terence Tao | 10 comments

Apoorva Khare and I have just uploaded to the arXiv our paper “On the sign patterns of entrywise positivity preservers in fixed dimension“. This paper explores the relationship between positive definiteness of Hermitian matrices, and entrywise operations on these matrices. The starting point for this theory is the Schur product theorem, which asserts that if ${A = (a_{ij})_{1 \leq i,j \leq N}}$ and ${B = (b_{ij})_{1 \leq i,j \leq N}}$ are two ${N \times N}$ Hermitian matrices that are positive semi-definite, then their Hadamard product

$\displaystyle A \circ B := (a_{ij} b_{ij})_{1 \leq i,j \leq N}$

is also positive semi-definite. (One should caution that the Hadamard product is not the same as the usual matrix product.) To prove this theorem, first observe that the claim is easy when ${A = {\bf u} {\bf u}^*}$ and ${B = {\bf v} {\bf v}^*}$ are rank one positive semi-definite matrices, since in this case ${A \circ B = ({\bf u} \circ {\bf v}) ({\bf u} \circ {\bf v})^*}$ is also a rank one positive semi-definite matrix. The general case then follows by noting from the spectral theorem that a general positive semi-definite matrix can be expressed as a non-negative linear combination of rank one positive semi-definite matrices, and using the bilinearity of the Hadamard product and the fact that the set of positive semi-definite matrices form a convex cone. A modification of this argument also lets one replace “positive semi-definite” by “positive definite” in the statement of the Schur product theorem.

One corollary of the Schur product theorem is that any polynomial ${P(z) = c_0 + c_1 z + \dots + c_d z^d}$ with non-negative coefficients ${c_n \geq 0}$ is entrywise positivity preserving on the space ${{\mathbb P}_N({\bf C})}$ of ${N \times N}$ positive semi-definite Hermitian matrices, in the sense that for any matrix ${A = (a_{ij})_{1 \leq i,j \leq N}}$ in ${{\mathbb P}_N({\bf C})}$ , the entrywise application

$\displaystyle P[A] := (P(a_{ij}))_{1 \leq i,j \leq N}$

of ${P}$ to ${A}$ is also positive semi-definite. (As before, one should caution that ${P[A]}$ is not the application ${P(A)}$ of ${P}$ to ${A}$ by the usual functional calculus.) Indeed, one can expand

$\displaystyle P[A] = c_0 A^{\circ 0} + c_1 A^{\circ 1} + \dots + c_d A^{\circ d},$

where ${A^{\circ i}}$ is the Hadamard product of ${i}$ copies of ${A}$ , and the claim now follows from the Schur product theorem and the fact that ${{\mathbb P}_N({\bf C})}$ is a convex cone.

A slight variant of this argument, already observed by Pólya and Szegö in 1925, shows that if ${I}$ is any subset of ${{\bf C}}$ and

$\displaystyle f(z) = \sum_{n=0}^\infty c_n z^n \ \ \ \ \ (1)$

is a power series with non-negative coefficients ${c_n \geq 0}$ that is absolutely and uniformly convergent on ${I}$ , then ${f}$ will be entrywise positivity preserving on the set ${{\mathbb P}_N(I)}$ of positive definite matrices with entries in ${I}$ . (In the case that ${I}$ is of the form ${I = [0,\rho]}$ , such functions are precisely the absolutely monotonic functions on ${I}$ .)

In the work of Schoenberg and of Rudin, we have a converse: if ${f: (-1,1) \rightarrow {\bf C}}$ is a function that is entrywise positivity preserving on ${{\mathbb P}_N((-1,1))}$ for all ${N}$ , then it must be of the form (1) with ${c_n \geq 0}$ . Variants of this result, with ${(-1,1)}$ replaced by other domains, appear in the work of Horn, Vasudeva, and Guillot-Khare-Rajaratnam.

This gives a satisfactory classification of functions ${f}$ that are entrywise positivity preservers in all dimensions ${N}$ simultaneously. However, the question remains as to what happens if one fixes the dimension ${N}$ , in which case one may have a larger class of entrywise positivity preservers. For instance, in the trivial case ${N=1}$ , a function would be entrywise positivity preserving on ${{\mathbb P}_1((0,\rho))}$ if and only if ${f}$ is non-negative on ${I}$ . For higher ${N}$ , there is a necessary condition of Horn (refined slightly by Guillot-Khare-Rajaratnam) which asserts (at least in the case of smooth ${f}$ ) that all derivatives of ${f}$ at zero up to ${(N-1)^{th}}$ order must be non-negative in order for ${f}$ to be entrywise positivity preserving on ${{\mathbb P}_N((0,\rho))}$ for some ${0 < \rho < \infty}$ . In particular, if ${f}$ is of the form (1), then ${c_0,\dots,c_{N-1}}$ must be non-negative. In fact, a stronger assertion can be made, namely that the first ${N}$ non-zero coefficients in (1) (if they exist) must be positive, or equivalently any negative term in (1) must be preceded (though not necessarily immediately) by at least ${N}$ positive terms. If ${f}$ is of the form (1) is entrywise positivity preserving on the larger set ${{\mathbb P}_N((0,+\infty))}$ , one can furthermore show that any negative term in (1) must also be followed (though not necessarily immediately) by at least ${N}$ positive terms.

The main result of this paper is that these sign conditions are the only constraints for entrywise positivity preserving power series. More precisely:

Theorem 1 For each ${n}$ , let ${\epsilon_n \in \{-1,0,+1\}}$ be a sign.

Suppose that any negative sign ${\epsilon_M = -1}$ is preceded by at least ${N}$ positive signs (thus there exists ${0 \leq n_0 < \dots < n_{N-1}< M}$ with ${\epsilon_{n_0} = \dots = \epsilon_{n_{N-1}} = +1}$ ). Then, for any ${0 < \rho < \infty}$ , there exists a convergent power series (1) on ${(0,\rho)}$ , with each ${c_n}$ having the sign of ${\epsilon_n}$ , which is entrywise positivity preserving on ${{\bf P}_N((0,\rho))}$ .

Suppose in addition that any negative sign ${\epsilon_M = -1}$ is followed by at least ${N}$ positive signs (thus there exists ${M < n_N < \dots < n_{2N-1}}$ with ${\epsilon_{n_N} = \dots = \epsilon_{n_{2N-1}} = +1}$ ). Then there exists a convergent power series (1) on ${(0,+\infty)}$ , with each ${c_n}$ having the sign of ${\epsilon_n}$ , which is entrywise positivity preserving on ${{\bf P}_N((0,+\infty))}$ .

One can ask the same question with ${(0,\rho)}$ or ${(0,+\infty)}$ replaced by other domains such as ${(-\rho,\rho)}$ , or the complex disk ${D(0,\rho)}$ , but it turns out that there are far fewer entrywise positivity preserving functions in those cases basically because of the non-trivial zeroes of Schur polynomials in these ranges; see the paper for further discussion. We also have some quantitative bounds on how negative some of the coefficients can be compared to the positive coefficients, but they are a bit technical to state here.

The heart of the proofs of these results is an analysis of the determinants ${\mathrm{det} P[ {\bf u} {\bf u}^* ]}$ of polynomials ${P}$ applied entrywise to rank one matrices ${uu^*}$ ; the positivity of these determinants can be used (together with a continuity argument) to establish the positive definiteness of ${P[uu^*]}$ for various ranges of ${P}$ and ${u}$ . Using the Cauchy-Binet formula, one can rewrite such determinants as linear combinations of squares of magnitudes of generalised Vandermonde determinants

$\displaystyle \mathrm{det}( u_i^{n_j} )_{1 \leq i,j \leq N},$

where ${{\bf u} = (u_1,\dots,u_N)}$ and the signs of the coefficients in the linear combination are determined by the signs of the coefficients of ${P}$ . The task is then to find upper and lower bounds for the magnitudes of such generalised Vandermonde determinants. These determinants oscillate in sign, which makes the problem look difficult; however, an algebraic miracle intervenes, namely the factorisation

$\displaystyle \mathrm{det}( u_i^{n_j} )_{1 \leq i,j \leq N} = \pm V({\bf u}) s_\lambda({\bf u})$

of the generalised Vandermonde determinant into the ordinary Vandermonde determinant

$\displaystyle V({\bf u}) = \prod_{1 \leq i < j \leq N} (u_j - u_i)$

and a Schur polynomial ${s_\lambda}$ applied to ${{\bf u}}$ , where the weight ${\lambda}$ of the Schur polynomial is determined by ${n_1,\dots,n_N}$ in a simple fashion. The problem then boils down to obtaining upper and lower bounds for these Schur polynomials. Because we are restricting attention to matrices taking values in ${(0,\rho)}$ or ${(0,+\infty)}$ , the entries of ${{\bf u}}$ can be taken to be non-negative. One can then take advantage of the total positivity of the Schur polynomials to compare these polynomials with a monomial, at which point one can obtain good criteria for ${P[A]}$ to be positive definite when ${A}$ is a rank one positive definite matrix ${A = {\bf u} {\bf u}^*}$ .

If we allow the exponents ${n_1,\dots,n_N}$ to be real numbers rather than integers (thus replacing polynomials or power series by Pusieux series or Hahn series), then we lose the above algebraic miracle, but we can replace it with a geometric miracle, namely the Harish-Chandra-Itzykson-Zuber identity, which I discussed in this previous blog post. This factors the above generalised Vandermonde determinant as the product of the ordinary Vandermonde determinant and an integral of a positive quantity over the orthogonal group, which one can again compare with a monomial after some fairly elementary estimates.

It remains to understand what happens for more general positive semi-definite matrices ${A}$ . Here we use a trick of FitzGerald and Horn to amplify the rank one case to the general case, by expressing a general positive semi-definite matrix ${A}$ as a linear combination of a rank one matrix ${{\bf u} {\bf u}^*}$ and another positive semi-definite matrix ${B}$ that vanishes on the last row and column (and is thus effectively a positive definite ${N-1 \times N-1}$ matrix). Using the fundamental theorem of calculus to continuously deform the rank one matrix ${{\bf u} {\bf u}^*}$ to ${A}$ in the direction ${B}$ , one can then obtain positivity results for ${P[A]}$ from positivity results for ${P[{\bf u} {\bf u}^*]}$ combined with an induction hypothesis on ${N}$ .

A wave equation approach to automorphic forms in analytic number theory

15 August, 2015 in expository, math.AP, math.NT, math.SP | Tags: automorphic forms, Poincare series, wave equation | by Terence Tao | 19 comments

The Poincaré upper half-plane ${{\mathbf H} := \{ z: \hbox{Im}(z) > 0 \}}$ (with a boundary consisting of the real line ${{\bf R}}$ together with the point at infinity ${\infty}$ ) carries an action of the projective special linear group

$\displaystyle \hbox{PSL}_2({\bf R}) := \{ \begin{pmatrix} a & b \\ c & d \end{pmatrix}: a,b,c,d \in {\bf R}: ad-bc = 1 \} / \{\pm 1\}$

via fractional linear transformations:

$\displaystyle \begin{pmatrix} a & b \\ c & d \end{pmatrix} z := \frac{az+b}{cz+d}. \ \ \ \ \ (1)$

Here and in the rest of the post we will abuse notation by identifying elements ${\begin{pmatrix} a & b \\ c & d \end{pmatrix}}$ of the special linear group ${\hbox{SL}_2({\bf R})}$ with their equivalence class ${\{ \pm \begin{pmatrix} a & b \\ c & d \end{pmatrix} \}}$ in ${\hbox{PSL}_2({\bf R})}$ ; this will occasionally create or remove a factor of two in our formulae, but otherwise has very little effect, though one has to check that various definitions and expressions (such as (1)) are unaffected if one replaces a matrix ${\begin{pmatrix} a & b \\ c & d \end{pmatrix}}$ by its negation ${\begin{pmatrix} -a & -b \\ -c & -d \end{pmatrix}}$ . In particular, we recommend that the reader ignore the signs ${\pm}$ that appear from time to time in the discussion below.

As the action of ${\hbox{PSL}_2({\bf R})}$ on ${{\mathbf H}}$ is transitive, and any given point in ${{\mathbf H}}$ (e.g. ${i}$ ) has a stabiliser isomorphic to the projective rotation group ${\hbox{PSO}_2({\bf R})}$ , we can view the Poincaré upper half-plane ${{\mathbf H}}$ as a homogeneous space for ${\hbox{PSL}_2({\bf R})}$ , and more specifically the quotient space of ${\hbox{PSL}_2({\bf R})}$ of a maximal compact subgroup ${\hbox{PSO}_2({\bf R})}$ . In fact, we can make the half-plane a symmetric space for ${\hbox{PSL}_2({\bf R})}$ , by endowing ${{\mathbf H}}$ with the Riemannian metric

$\displaystyle dg^2 := \frac{dx^2 + dy^2}{y^2}$

(using Cartesian coordinates ${z=x+iy}$ ), which is invariant with respect to the ${\hbox{PSL}_2({\bf R})}$ action. Like any other Riemannian metric, the metric on ${{\mathbf H}}$ generates a number of other important geometric objects on ${{\mathbf H}}$ , such as the distance function ${d(z,w)}$ which can be computed to be given by the formula

$\displaystyle 2(\cosh(d(z_1,z_2))-1) = \frac{|z_1-z_2|^2}{\hbox{Im}(z_1) \hbox{Im}(z_2)}, \ \ \ \ \ (2)$

the volume measure ${\mu = \mu_{\mathbf H}}$ , which can be computed to be

$\displaystyle d\mu = \frac{dx dy}{y^2},$

and the Laplace-Beltrami operator, which can be computed to be ${\Delta = y^2 (\frac{\partial^2}{\partial x^2} + \frac{\partial^2}{\partial y^2})}$ (here we use the negative definite sign convention for ${\Delta}$ ). As the metric ${dg}$ was ${\hbox{PSL}_2({\bf R})}$ -invariant, all of these quantities arising from the metric are similarly ${\hbox{PSL}_2({\bf R})}$ -invariant in the appropriate sense.

The Gauss curvature of the Poincaré half-plane can be computed to be the constant ${-1}$ , thus ${{\mathbf H}}$ is a model for two-dimensional hyperbolic geometry, in much the same way that the unit sphere ${S^2}$ in ${{\bf R}^3}$ is a model for two-dimensional spherical geometry (or ${{\bf R}^2}$ is a model for two-dimensional Euclidean geometry). (Indeed, ${{\mathbf H}}$ is isomorphic (via projection to a null hyperplane) to the upper unit hyperboloid ${\{ (x,t) \in {\bf R}^{2+1}: t = \sqrt{1+|x|^2}\}}$ in the Minkowski spacetime ${{\bf R}^{2+1}}$ , which is the direct analogue of the unit sphere in Euclidean spacetime ${{\bf R}^3}$ or the plane ${{\bf R}^2}$ in Galilean spacetime ${{\bf R}^2 \times {\bf R}}$ .)

One can inject arithmetic into this geometric structure by passing from the Lie group ${\hbox{PSL}_2({\bf R})}$ to the full modular group

$\displaystyle \hbox{PSL}_2({\bf Z}) := \{ \begin{pmatrix} a & b \\ c & d \end{pmatrix}: a,b,c,d \in {\bf Z}: ad-bc = 1 \} / \{\pm 1\}$

or congruence subgroups such as

$\displaystyle \Gamma_0(q) := \{ \begin{pmatrix} a & b \\ c & d \end{pmatrix} \in \hbox{PSL}_2({\bf Z}): c = 0\ (q) \} / \{ \pm 1 \} \ \ \ \ \ (3)$

for natural number ${q}$ , or to the discrete stabiliser ${\Gamma_\infty}$ of the point at infinity:

$\displaystyle \Gamma_\infty := \{ \pm \begin{pmatrix} 1 & b \\ 0 & 1 \end{pmatrix}: b \in {\bf Z} \} / \{\pm 1\}. \ \ \ \ \ (4)$

These are discrete subgroups of ${\hbox{PSL}_2({\bf R})}$ , nested by the subgroup inclusions

$\displaystyle \Gamma_\infty \leq \Gamma_0(q) \leq \Gamma_0(1)=\hbox{PSL}_2({\bf Z}) \leq \hbox{PSL}_2({\bf R}).$

There are many further discrete subgroups of ${\hbox{PSL}_2({\bf R})}$ (known collectively as Fuchsian groups) that one could consider, but we will focus attention on these three groups in this post.

Any discrete subgroup ${\Gamma}$ of ${\hbox{PSL}_2({\bf R})}$ generates a quotient space ${\Gamma \backslash {\mathbf H}}$ , which in general will be a non-compact two-dimensional orbifold. One can understand such a quotient space by working with a fundamental domain ${\hbox{Fund}( \Gamma \backslash {\mathbf H})}$ – a set consisting of a single representative of each of the orbits ${\Gamma z}$ of ${\Gamma}$ in ${{\mathbf H}}$ . This fundamental domain is by no means uniquely defined, but if the fundamental domain is chosen with some reasonable amount of regularity, one can view ${\Gamma \backslash {\mathbf H}}$ as the fundamental domain with the boundaries glued together in an appropriate sense. Among other things, fundamental domains can be used to induce a volume measure ${\mu = \mu_{\Gamma \backslash {\mathbf H}}}$ on ${\Gamma \backslash {\mathbf H}}$ from the volume measure ${\mu = \mu_{\mathbf H}}$ on ${{\mathbf H}}$ (restricted to a fundamental domain). By abuse of notation we will refer to both measures simply as ${\mu}$ when there is no chance of confusion.

For instance, a fundamental domain for ${\Gamma_\infty \backslash {\mathbf H}}$ is given (up to null sets) by the strip ${\{ z \in {\mathbf H}: |\hbox{Re}(z)| < \frac{1}{2} \}}$ , with ${\Gamma_\infty \backslash {\mathbf H}}$ identifiable with the cylinder formed by gluing together the two sides of the strip. A fundamental domain for ${\hbox{PSL}_2({\bf Z}) \backslash {\mathbf H}}$ is famously given (again up to null sets) by an upper portion ${\{ z \in {\mathbf H}: |\hbox{Re}(z)| < \frac{1}{2}; |z| > 1 \}}$ , with the left and right sides again glued to each other, and the left and right halves of the circular boundary glued to itself. A fundamental domain for ${\Gamma_0(q) \backslash {\mathbf H}}$ can be formed by gluing together

$\displaystyle [\hbox{PSL}_2({\bf Z}) : \Gamma_0(q)] = q \prod_{p|q} (1 + \frac{1}{p}) = q^{1+o(1)}$

copies of a fundamental domain for ${\hbox{PSL}_2({\bf Z}) \backslash {\mathbf H}}$ in a rather complicated but interesting fashion.

While fundamental domains can be a convenient choice of coordinates to work with for some computations (as well as for drawing appropriate pictures), it is geometrically more natural to avoid working explicitly on such domains, and instead work directly on the quotient spaces ${\Gamma \backslash {\mathbf H}}$ . In order to analyse functions ${f: \Gamma \backslash {\mathbf H} \rightarrow {\bf C}}$ on such orbifolds, it is convenient to lift such functions back up to ${{\mathbf H}}$ and identify them with functions ${f: {\mathbf H} \rightarrow {\bf C}}$ which are ${\Gamma}$ -automorphic in the sense that ${f( \gamma z ) = f(z)}$ for all ${z \in {\mathbf H}}$ and ${\gamma \in \Gamma}$ . Such functions will be referred to as ${\Gamma}$ -automorphic forms, or automorphic forms for short (we always implicitly assume all such functions to be measurable). (Strictly speaking, these are the automorphic forms with trivial factor of automorphy; one can certainly consider other factors of automorphy, particularly when working with holomorphic modular forms, which corresponds to sections of a more non-trivial line bundle over ${\Gamma \backslash {\mathbf H}}$ than the trivial bundle ${(\Gamma \backslash {\mathbf H}) \times {\bf C}}$ that is implicitly present when analysing scalar functions ${f: {\mathbf H} \rightarrow {\bf C}}$ . However, we will not discuss this (important) more general situation here.)

An important way to create a ${\Gamma}$ -automorphic form is to start with a non-automorphic function ${f: {\mathbf H} \rightarrow {\bf C}}$ obeying suitable decay conditions (e.g. bounded with compact support will suffice) and form the Poincaré series ${P_\Gamma[f]: {\mathbf H} \rightarrow {\bf C}}$ defined by

$\displaystyle P_{\Gamma}[f](z) = \sum_{\gamma \in \Gamma} f(\gamma z),$

which is clearly ${\Gamma}$ -automorphic. (One could equivalently write ${f(\gamma^{-1} z)}$ in place of ${f(\gamma z)}$ here; there are good argument for both conventions, but I have ultimately decided to use the ${f(\gamma z)}$ convention, which makes explicit computations a little neater at the cost of making the group actions work in the opposite order.) Thus we naturally see sums over ${\Gamma}$ associated with ${\Gamma}$ -automorphic forms. A little more generally, given a subgroup ${\Gamma_\infty}$ of ${\Gamma}$ and a ${\Gamma_\infty}$ -automorphic function ${f: {\mathbf H} \rightarrow {\bf C}}$ of suitable decay, we can form a relative Poincaré series ${P_{\Gamma_\infty \backslash \Gamma}[f]: {\mathbf H} \rightarrow {\bf C}}$ by

$\displaystyle P_{\Gamma_\infty \backslash \Gamma}[f](z) = \sum_{\gamma \in \hbox{Fund}(\Gamma_\infty \backslash \Gamma)} f(\gamma z)$

where ${\hbox{Fund}(\Gamma_\infty \backslash \Gamma)}$ is any fundamental domain for ${\Gamma_\infty \backslash \Gamma}$ , that is to say a subset of ${\Gamma}$ consisting of exactly one representative for each right coset of ${\Gamma_\infty}$ . As ${f}$ is ${\Gamma_\infty}$ -automorphic, we see (if ${f}$ has suitable decay) that ${P_{\Gamma_\infty \backslash \Gamma}[f]}$ does not depend on the precise choice of fundamental domain, and is ${\Gamma}$ -automorphic. These operations are all compatible with each other, for instance ${P_\Gamma = P_{\Gamma_\infty \backslash \Gamma} \circ P_{\Gamma_\infty}}$ . A key example of Poincaré series are the Eisenstein series, although there are of course many other Poincaré series one can consider by varying the test function ${f}$ .

For future reference we record the basic but fundamental unfolding identities

$\displaystyle \int_{\Gamma \backslash {\mathbf H}} P_\Gamma[f] g\ d\mu_{\Gamma \backslash {\mathbf H}} = \int_{\mathbf H} f g\ d\mu_{\mathbf H} \ \ \ \ \ (5)$

for any function ${f: {\mathbf H} \rightarrow {\bf C}}$ with sufficient decay, and any ${\Gamma}$ -automorphic function ${g}$ of reasonable growth (e.g. ${f}$ bounded and compact support, and ${g}$ bounded, will suffice). Note that ${g}$ is viewed as a function on ${\Gamma \backslash {\mathbf H}}$ on the left-hand side, and as a ${\Gamma}$ -automorphic function on ${{\mathbf H}}$ on the right-hand side. More generally, one has

$\displaystyle \int_{\Gamma \backslash {\mathbf H}} P_{\Gamma_\infty \backslash \Gamma}[f] g\ d\mu_{\Gamma \backslash {\mathbf H}} = \int_{\Gamma_\infty \backslash {\mathbf H}} f g\ d\mu_{\Gamma_\infty \backslash {\mathbf H}} \ \ \ \ \ (6)$

whenever ${\Gamma_\infty \leq \Gamma}$ are discrete subgroups of ${\hbox{PSL}_2({\bf R})}$ , ${f}$ is a ${\Gamma_\infty}$ -automorphic function with sufficient decay on ${\Gamma_\infty \backslash {\mathbf H}}$ , and ${g}$ is a ${\Gamma}$ -automorphic (and thus also ${\Gamma_\infty}$ -automorphic) function of reasonable growth. These identities will allow us to move fairly freely between the three domains ${{\mathbf H}}$ , ${\Gamma_\infty \backslash {\mathbf H}}$ , and ${\Gamma \backslash {\mathbf H}}$ in our analysis.

When computing various statistics of a Poincaré series ${P_\Gamma[f]}$ , such as its values ${P_\Gamma[f](z)}$ at special points ${z}$ , or the ${L^2}$ quantity ${\int_{\Gamma \backslash {\mathbf H}} |P_\Gamma[f]|^2\ d\mu}$ , expressions of interest to analytic number theory naturally emerge. We list three basic examples of this below, discussed somewhat informally in order to highlight the main ideas rather than the technical details.

The first example we will give concerns the problem of estimating the sum

$\displaystyle \sum_{n \leq x} \tau(n) \tau(n+1), \ \ \ \ \ (7)$

where ${\tau(n) := \sum_{d|n} 1}$ is the divisor function. This can be rewritten (by factoring ${n=bc}$ and ${n+1=ad}$ ) as

$\displaystyle \sum_{ a,b,c,d \in {\bf N}: ad-bc = 1} 1_{bc \leq x} \ \ \ \ \ (8)$

which is basically a sum over the full modular group ${\hbox{PSL}_2({\bf Z})}$ . At this point we will “cheat” a little by moving to the related, but different, sum

$\displaystyle \sum_{a,b,c,d \in {\bf Z}: ad-bc = 1} 1_{a^2+b^2+c^2+d^2 \leq x}. \ \ \ \ \ (9)$

This sum is not exactly the same as (8), but will be a little easier to handle, and it is plausible that the methods used to handle this sum can be modified to handle (8). Observe from (2) and some calculation that the distance between ${i}$ and ${\begin{pmatrix} a & b \\ c & d \end{pmatrix} i = \frac{ai+b}{ci+d}}$ is given by the formula

$\displaystyle 2(\cosh(d(i,\begin{pmatrix} a & b \\ c & d \end{pmatrix} i))-1) = a^2+b^2+c^2+d^2 - 2$

and so one can express the above sum as

$\displaystyle 2 \sum_{\gamma \in \hbox{PSL}_2({\bf Z})} 1_{d(i,\gamma i) \leq \hbox{cosh}^{-1}(x/2)}$

(the factor of ${2}$ coming from the quotient by ${\{\pm 1\}}$ in the projective special linear group); one can express this as ${P_\Gamma[f](i)}$ , where ${\Gamma = \hbox{PSL}_2({\bf Z})}$ and ${f}$ is the indicator function of the ball ${B(i, \hbox{cosh}^{-1}(x/2))}$ . Thus we see that expressions such as (7) are related to evaluations of Poincaré series. (In practice, it is much better to use smoothed out versions of indicator functions in order to obtain good control on sums such as (7) or (9), but we gloss over this technical detail here.)

The second example concerns the relative

$\displaystyle \sum_{n \leq x} \tau(n^2+1) \ \ \ \ \ (10)$

of the sum (7). Note from multiplicativity that (7) can be written as ${\sum_{n \leq x} \tau(n^2+n)}$ , which is superficially very similar to (10), but with the key difference that the polynomial ${n^2+1}$ is irreducible over the integers.

As with (7), we may expand (10) as

$\displaystyle \sum_{A,B,C \in {\bf N}: B^2 - AC = -1} 1_{B \leq x}.$

At first glance this does not look like a sum over a modular group, but one can manipulate this expression into such a form in one of two (closely related) ways. First, observe that any factorisation ${B + i = (a-bi) (c+di)}$ of ${B+i}$ into Gaussian integers ${a-bi, c+di}$ gives rise (upon taking norms) to an identity of the form ${B^2 - AC = -1}$ , where ${A = a^2+b^2}$ and ${C = c^2+d^2}$ . Conversely, by using the unique factorisation of the Gaussian integers, every identity of the form ${B^2-AC=-1}$ gives rise to a factorisation of the form ${B+i = (a-bi) (c+di)}$ , essentially uniquely up to units. Now note that ${(a-bi)(c+di)}$ is of the form ${B+i}$ if and only if ${ad-bc=1}$ , in which case ${B = ac+bd}$ . Thus we can essentially write the above sum as something like

$\displaystyle \sum_{a,b,c,d: ad-bc = 1} 1_{|ac+bd| \leq x} \ \ \ \ \ (11)$

and one the modular group ${\hbox{PSL}_2({\bf Z})}$ is now manifest. An equivalent way to see these manipulations is as follows. A triple ${A,B,C}$ of natural numbers with ${B^2-AC=1}$ gives rise to a positive quadratic form ${Ax^2+2Bxy+Cy^2}$ of normalised discriminant ${B^2-AC}$ equal to ${-1}$ with integer coefficients (it is natural here to allow ${B}$ to take integer values rather than just natural number values by essentially doubling the sum). The group ${\hbox{PSL}_2({\bf Z})}$ acts on the space of such quadratic forms in a natural fashion (by composing the quadratic form with the inverse ${\begin{pmatrix} d & -b \\ -c & a \end{pmatrix}}$ of an element ${\begin{pmatrix} a & b \\ c & d \end{pmatrix}}$ of ${\hbox{SL}_2({\bf Z})}$ ). Because the discriminant ${-1}$ has class number one (this fact is equivalent to the unique factorisation of the gaussian integers, as discussed in this previous post), every form ${Ax^2 + 2Bxy + Cy^2}$ in this space is equivalent (under the action of some element of ${\hbox{PSL}_2({\bf Z})}$ ) with the standard quadratic form ${x^2+y^2}$ . In other words, one has

$\displaystyle Ax^2 + 2Bxy + Cy^2 = (dx-by)^2 + (-cx+ay)^2$

which (up to a harmless sign) is exactly the representation ${B = ac+bd}$ , ${A = c^2+d^2}$ , ${C = a^2+b^2}$ introduced earlier, and leads to the same reformulation of the sum (10) in terms of expressions like (11). Similar considerations also apply if the quadratic polynomial ${n^2+1}$ is replaced by another quadratic, although one has to account for the fact that the class number may now exceed one (so that unique factorisation in the associated quadratic ring of integers breaks down), and in the positive discriminant case the fact that the group of units might be infinite presents another significant technical problem.

Note that ${\begin{pmatrix} a & b \\ c & d \end{pmatrix} i = \frac{ai+b}{ci+d}}$ has real part ${\frac{ac+bd}{c^2+d^2}}$ and imaginary part ${\frac{1}{c^2+d^2}}$ . Thus (11) is (up to a factor of two) the Poincaré series ${P_\Gamma[f](i)}$ as in the preceding example, except that ${f}$ is now the indicator of the sector ${\{ z: |\hbox{Re} z| \leq x |\hbox{Im} z| \}}$ .

Sums involving subgroups of the full modular group, such as ${\Gamma_0(q)}$ , often arise when imposing congruence conditions on sums such as (10), for instance when trying to estimate the expression ${\sum_{n \leq x: q|n} \tau(n^2+1)}$ when ${q}$ and ${x}$ are large. As before, one then soon arrives at the problem of evaluating a Poincaré series at one or more special points, where the series is now over ${\Gamma_0(q)}$ rather than ${\hbox{PSL}_2({\bf Z})}$ .

The third and final example concerns averages of Kloosterman sums

$\displaystyle S(m,n;c) := \sum_{x \in ({\bf Z}/c{\bf Z})^\times} e( \frac{mx + n\overline{x}}{c} ) \ \ \ \ \ (12)$

where ${e(\theta) := e^{2p\i i\theta}}$ and ${\overline{x}}$ is the inverse of ${x}$ in the multiplicative group ${({\bf Z}/c{\bf Z})^\times}$ . It turns out that the ${L^2}$ norms of Poincaré series ${P_\Gamma[f]}$ or ${P_{\Gamma_\infty \backslash \Gamma}[f]}$ are closely tied to such averages. Consider for instance the quantity

$\displaystyle \int_{\Gamma_0(q) \backslash {\mathbf H}} |P_{\Gamma_\infty \backslash \Gamma_0(q)}[f]|^2\ d\mu_{\Gamma \backslash {\mathbf H}} \ \ \ \ \ (13)$

where ${q}$ is a natural number and ${f}$ is a ${\Gamma_\infty}$ -automorphic form that is of the form

$\displaystyle f(x+iy) = F(my) e(m x)$

for some integer ${m}$ and some test function ${f: (0,+\infty) \rightarrow {\bf C}}$ , which for sake of discussion we will take to be smooth and compactly supported. Using the unfolding formula (6), we may rewrite (13) as

$\displaystyle \int_{\Gamma_\infty \backslash {\mathbf H}} \overline{f} P_{\Gamma_\infty \backslash \Gamma_0(q)}[f]\ d\mu_{\Gamma_\infty \backslash {\mathbf H}}.$

To compute this, we use the double coset decomposition

$\displaystyle \Gamma_0(q) = \Gamma_\infty \cup \bigcup_{c \in {\mathbf N}: q|c} \bigcup_{1 \leq d \leq c: (d,c)=1} \Gamma_\infty \begin{pmatrix} a & b \\ c & d \end{pmatrix} \Gamma_\infty,$

where for each ${c,d}$ , ${a,b}$ are arbitrarily chosen integers such that ${ad-bc=1}$ . To see this decomposition, observe that every element ${\begin{pmatrix} a & b \\ c & d \end{pmatrix}}$ in ${\Gamma_0(q)}$ outside of ${\Gamma_\infty}$ can be assumed to have ${c>0}$ by applying a sign ${\pm}$ , and then using the row and column operations coming from left and right multiplication by ${\Gamma_\infty}$ (that is, shifting the top row by an integer multiple of the bottom row, and shifting the right column by an integer multiple of the left column) one can place ${d}$ in the interval ${[1,c]}$ and ${(a,b)}$ to be any specified integer pair with ${ad-bc=1}$ . From this we see that

$\displaystyle P_{\Gamma_\infty \backslash \Gamma_0(q)}[f] = f + \sum_{c \in {\mathbf N}: q|c} \sum_{1 \leq d \leq c: (d,c)=1} P_{\Gamma_\infty}[ f( \begin{pmatrix} a & b \\ c & d \end{pmatrix} \cdot ) ]$

and so from further use of the unfolding formula (5) we may expand (13) as

$\displaystyle \int_{\Gamma_\infty \backslash {\mathbf H}} |f|^2\ d\mu_{\Gamma_\infty \backslash {\mathbf H}}$

$\displaystyle + \sum_{c \in {\mathbf N}} \sum_{1 \leq d \leq c: (d,c)=1} \int_{\mathbf H} \overline{f}(z) f( \begin{pmatrix} a & b \\ c & d \end{pmatrix} z)\ d\mu_{\mathbf H}.$

The first integral is just ${m \int_0^\infty |F(y)|^2 \frac{dy}{y^2}}$ . The second expression is more interesting. We have

$\displaystyle \begin{pmatrix} a & b \\ c & d \end{pmatrix} z = \frac{az+b}{cz+d} = \frac{a}{c} - \frac{1}{c(cz+d)}$

$\displaystyle = \frac{a}{c} - \frac{cx+d}{c((cx+d)^2+c^2y^2)} + \frac{iy}{(cx+d)^2 + c^2y^2}$

so we can write

$\displaystyle \int_{\mathbf H} \overline{f}(z) f( \begin{pmatrix} a & b \\ c & d \end{pmatrix} z)\ d\mu_{\mathbf H}$

$\displaystyle \int_0^\infty \int_{\bf R} \overline{F}(my) F(\frac{imy}{(cx+d)^2 + c^2y^2}) e( -mx + \frac{ma}{c} - m \frac{cx+d}{c((cx+d)^2+c^2y^2)} )$

$\displaystyle \frac{dx dy}{y^2}$

which on shifting ${x}$ by ${d/c}$ simplifies a little to

$\displaystyle e( \frac{ma}{c} + \frac{md}{c} ) \int_0^\infty \int_{\bf R} F(my) \bar{F}(\frac{imy}{c^2(x^2 + y^2)}) e(- mx - m \frac{x}{c^2(x^2+y^2)} )$

$\displaystyle \frac{dx dy}{y^2}$

and then on scaling ${x,y}$ by ${m}$ simplifies a little further to

$\displaystyle e( \frac{ma}{c} + \frac{md}{c} ) \int_0^\infty \int_{\bf R} F(y) \bar{F}(\frac{m^2}{c^2} \frac{iy}{x^2 + y^2}) e(- x - \frac{m^2}{c^2} \frac{x}{x^2+y^2} )\ \frac{dx dy}{y^2}.$

Note that as ${ad-bc=1}$ , we have ${a = \overline{d}}$ modulo ${c}$ . Comparing the above calculations with (12), we can thus write (13) as

$\displaystyle m (\int_0^\infty |F(y)|^2 \frac{dy}{y^2} + \sum_{q|c} \frac{S(m,m;c)}{c} V(\frac{m}{c})) \ \ \ \ \ (14)$

where

$\displaystyle V(u) := \frac{1}{u} \int_0^\infty \int_{\bf R} F(y) \bar{F}(u^2 \frac{y}{x^2 + y^2}) e(- x - u^2 \frac{x}{x^2+y^2} )\ \frac{dx dy}{y^2}$

is a certain integral involving ${F}$ and a parameter ${u}$ , but which does not depend explicitly on parameters such as ${m,c,d}$ . Thus we have indeed expressed the ${L^2}$ expression (13) in terms of Kloosterman sums. It is possible to invert this analysis and express varius weighted sums of Kloosterman sums in terms of ${L^2}$ expressions (possibly involving inner products instead of norms) of Poincaré series, but we will not do so here; see Chapter 16 of Iwaniec and Kowalski for further details.

Traditionally, automorphic forms have been analysed using the spectral theory of the Laplace-Beltrami operator ${-\Delta}$ on spaces such as ${\Gamma\backslash {\mathbf H}}$ or ${\Gamma_\infty \backslash {\mathbf H}}$ , so that a Poincaré series such as ${P_\Gamma[f]}$ might be expanded out using inner products of ${P_\Gamma[f]}$ (or, by the unfolding identities, ${f}$ ) with various generalised eigenfunctions of ${-\Delta}$ (such as cuspidal eigenforms, or Eisenstein series). With this approach, special functions, and specifically the modified Bessel functions ${K_{it}}$ of the second kind, play a prominent role, basically because the ${\Gamma_\infty}$ -automorphic functions

$\displaystyle x+iy \mapsto y^{1/2} K_{it}(2\pi |m| y) e(mx)$

for ${t \in {\bf R}}$ and ${m \in {\bf Z}}$ non-zero are generalised eigenfunctions of ${-\Delta}$ (with eigenvalue ${\frac{1}{4}+t^2}$ ), and are almost square-integrable on ${\Gamma_\infty \backslash {\mathbf H}}$ (the ${L^2}$ norm diverges only logarithmically at one end ${y \rightarrow 0^+}$ of the cylinder ${\Gamma_\infty \backslash {\mathbf H}}$ , while decaying exponentially fast at the other end ${y \rightarrow +\infty}$ ).

However, as discussed in this previous post, the spectral theory of an essentially self-adjoint operator such as ${-\Delta}$ is basically equivalent to the theory of various solution operators associated to partial differential equations involving that operator, such as the Helmholtz equation ${(-\Delta + k^2) u = f}$ , the heat equation ${\partial_t u = \Delta u}$ , the Schrödinger equation ${i\partial_t u + \Delta u = 0}$ , or the wave equation ${\partial_{tt} u = \Delta u}$ . Thus, one can hope to rephrase many arguments that involve spectral data of ${-\Delta}$ into arguments that instead involve resolvents ${(-\Delta + k^2)^{-1}}$ , heat kernels ${e^{t\Delta}}$ , Schrödinger propagators ${e^{it\Delta}}$ , or wave propagators ${e^{\pm it\sqrt{-\Delta}}}$ , or involve the PDE more directly (e.g. applying integration by parts and energy methods to solutions of such PDE). This is certainly done to some extent in the existing literature; resolvents and heat kernels, for instance, are often utilised. In this post, I would like to explore the possibility of reformulating spectral arguments instead using the inhomogeneous wave equation

$\displaystyle \partial_{tt} u - \Delta u = F.$

Actually it will be a bit more convenient to normalise the Laplacian by ${\frac{1}{4}}$ , and look instead at the automorphic wave equation

$\displaystyle \partial_{tt} u + (-\Delta - \frac{1}{4}) u = F. \ \ \ \ \ (15)$

This equation somewhat resembles a “Klein-Gordon” type equation, except that the mass is imaginary! This would lead to pathological behaviour were it not for the negative curvature, which in principle creates a spectral gap of ${\frac{1}{4}}$ that cancels out this factor.

The point is that the wave equation approach gives access to some nice PDE techniques, such as energy methods, Sobolev inequalities and finite speed of propagation, which are somewhat submerged in the spectral framework. The wave equation also interacts well with Poincaré series; if for instance ${u}$ and ${F}$ are ${\Gamma_\infty}$ -automorphic solutions to (15) obeying suitable decay conditions, then their Poincaré series ${P_{\Gamma_\infty \backslash \Gamma}[u]}$ and ${P_{\Gamma_\infty \backslash \Gamma}[F]}$ will be ${\Gamma}$ -automorphic solutions to the same equation (15), basically because the Laplace-Beltrami operator commutes with translations. Because of these facts, it is possible to replicate several standard spectral theory arguments in the wave equation framework, without having to deal directly with things like the asymptotics of modified Bessel functions. The wave equation approach to automorphic theory was introduced by Faddeev and Pavlov (using the Lax-Phillips scattering theory), and developed further by by Lax and Phillips, to recover many spectral facts about the Laplacian on modular curves, such as the Weyl law and the Selberg trace formula. Here, I will illustrate this by deriving three basic applications of automorphic methods in a wave equation framework, namely

Using the Weil bound on Kloosterman sums to derive Selberg’s 3/16 theorem on the least non-trivial eigenvalue for ${-\Delta}$ on ${\Gamma_0(q) \backslash {\mathbf H}}$ (discussed previously here);
Conversely, showing that Selberg’s eigenvalue conjecture (improving Selberg’s ${3/16}$ bound to the optimal ${1/4}$ ) implies an optimal bound on (smoothed) sums of Kloosterman sums; and
Using the same bound to obtain pointwise bounds on Poincaré series similar to the ones discussed above. (Actually, the argument here does not use the wave equation, instead it just uses the Sobolev inequality.)

This post originated from an attempt to finally learn this part of analytic number theory properly, and to see if I could use a PDE-based perspective to understand it better. Ultimately, this is not that dramatic a depature from the standard approach to this subject, but I found it useful to think of things in this fashion, probably due to my existing background in PDE.

I thank Bill Duke and Ben Green for helpful discussions. My primary reference for this theory was Chapters 15, 16, and 21 of Iwaniec and Kowalski.

Read the rest of this entry »

The standard branch of the matrix logarithm

3 May, 2015 in expository, math.GR, math.RA, math.SP | Tags: branch cuts, Lie groups, matrix logarithm, split orthogonal group | by Terence Tao | 24 comments

Because of Euler’s identity ${e^{\pi i} + 1 = 0}$ , the complex exponential is not injective: ${e^{z + 2\pi i k} = e^z}$ for any complex ${z}$ and integer ${k}$ . As such, the complex logarithm ${z \mapsto \log z}$ is not well-defined as a single-valued function from ${{\bf C} \backslash \{0\}}$ to ${{\bf C}}$ . However, after making a branch cut, one can create a branch of the logarithm which is single-valued. For instance, after removing the negative real axis ${(-\infty,0]}$ , one has the standard branch ${\hbox{Log}: {\bf C} \backslash (-\infty,0] \rightarrow \{ z \in {\bf C}: |\hbox{Im} z| < \pi \}}$ of the logarithm, with ${\hbox{Log}(z)}$ defined as the unique choice of the complex logarithm of ${z}$ whose imaginary part has magnitude strictly less than ${\pi}$ . This particular branch has a number of useful additional properties:

The standard branch ${\hbox{Log}}$ is holomorphic on its domain ${{\bf C} \backslash (-\infty,0]}$ .
One has ${\hbox{Log}( \overline{z} ) = \overline{ \hbox{Log}(z) }}$ for all ${z}$ in the domain ${{\bf C} \backslash (-\infty,0]}$ . In particular, if ${z \in {\bf C} \backslash (-\infty,0]}$ is real, then ${\hbox{Log} z}$ is real.
One has ${\hbox{Log}( z^{-1} ) = - \hbox{Log}(z)}$ for all ${z}$ in the domain ${{\bf C} \backslash (-\infty,0]}$ .

One can then also use the standard branch of the logarithm to create standard branches of other multi-valued functions, for instance creating a standard branch ${z \mapsto \exp( \frac{1}{2} \hbox{Log} z )}$ of the square root function. We caution however that the identity ${\hbox{Log}(zw) = \hbox{Log}(z) + \hbox{Log}(w)}$ can fail for the standard branch (or indeed for any branch of the logarithm).

One can extend this standard branch of the logarithm to ${n \times n}$ complex matrices, or (equivalently) to linear transformations ${T: V \rightarrow V}$ on an ${n}$ -dimensional complex vector space ${V}$ , provided that the spectrum of that matrix or transformation avoids the branch cut ${(-\infty,0]}$ . Indeed, from the spectral theorem one can decompose any such ${T: V \rightarrow V}$ as the direct sum of operators ${T_\lambda: V_\lambda \rightarrow V_\lambda}$ on the non-trivial generalised eigenspaces ${V_\lambda}$ of ${T}$ , where ${\lambda \in {\bf C} \backslash (-\infty,0]}$ ranges in the spectrum of ${T}$ . For each component ${T_\lambda}$ of ${T}$ , we define

$\displaystyle \hbox{Log}( T_\lambda ) = P_\lambda( T_\lambda )$

where ${P_\lambda}$ is the Taylor expansion of ${\hbox{Log}}$ at ${\lambda}$ ; as ${T_\lambda-\lambda}$ is nilpotent, only finitely many terms in this Taylor expansion are required. The logarithm ${\hbox{Log} T}$ is then defined as the direct sum of the ${\hbox{Log} T_\lambda}$ .

The matrix standard branch of the logarithm has many pleasant and easily verified properties (often inherited from their scalar counterparts), whenever ${T: V \rightarrow V}$ has no spectrum in ${(-\infty,0]}$ :

(i) We have ${\exp( \hbox{Log} T ) = T}$ .
(ii) If ${T_1: V_1 \rightarrow V_1}$ and ${T_2: V_2 \rightarrow V_2}$ have no spectrum in ${(-\infty,0]}$ , then ${\hbox{Log}( T_1 \oplus T_2 ) = \hbox{Log}(T_1) \oplus \hbox{Log}(T_2)}$ .
(iii) If ${T}$ has spectrum in a closed disk ${B(z,r)}$ in ${{\bf C} \backslash (-\infty,0]}$ , then ${\hbox{Log}(T) = P_z(T)}$ , where ${P_z}$ is the Taylor series of ${\hbox{Log}}$ around ${z}$ (which is absolutely convergent in ${B(z,r)}$ ).
(iv) ${\hbox{Log}(T)}$ depends holomorphically on ${T}$ . (Easily established from (ii), (iii), after covering the spectrum of ${T}$ by disjoint disks; alternatively, one can use the Cauchy integral representation ${\hbox{Log}(T) = \frac{1}{2\pi i} \int_\gamma \hbox{Log}(z)(z-T)^{-1}\ dz}$ for a contour ${\gamma}$ in the domain enclosing the spectrum of ${T}$ .) In particular, the standard branch of the matrix logarithm is smooth.
(v) If ${S: V \rightarrow W}$ is any invertible linear or antilinear map, then ${\hbox{Log}( STS^{-1} ) = S \hbox{Log}(T) S^{-1}}$ . In particular, the standard branch of the logarithm commutes with matrix conjugations; and if ${T}$ is real with respect to a complex conjugation operation on ${V}$ (that is to say, an antilinear involution), then ${\hbox{Log}(T)}$ is real also.
(vi) If ${T^*: V^* \rightarrow V^*}$ denotes the transpose of ${T}$ (with ${V^*}$ the complex dual of ${V}$ ), then ${\hbox{Log}(T^*) = \hbox{Log}(T)^*}$ . Similarly, if ${T^\dagger: V^\dagger \rightarrow V^\dagger}$ denotes the adjoint of ${T}$ (with ${V^\dagger}$ the complex conjugate of ${V^*}$ , i.e. ${V^*}$ with the conjugated multiplication map ${(c,z) \mapsto \overline{c} z}$ ), then ${\hbox{Log}(T^\dagger) = \hbox{Log}(T)^\dagger}$ .
(vii) One has ${\hbox{Log}(T^{-1}) = - \hbox{Log}( T )}$ .
(viii) If ${\sigma(T)}$ denotes the spectrum of ${T}$ , then ${\sigma(\hbox{Log} T) = \hbox{Log} \sigma(T)}$ .

As a quick application of the standard branch of the matrix logarithm, we have

Proposition 1 Let ${G}$ be one of the following matrix groups: ${GL_n({\bf C})}$ , ${GL_n({\bf R})}$ , ${U_n({\bf C})}$ , ${O(Q)}$ , ${Sp_{2n}({\bf C})}$ , or ${Sp_{2n}({\bf R})}$ , where ${Q: {\bf R}^n \rightarrow {\bf R}}$ is a non-degenerate real quadratic form (so ${O(Q)}$ is isomorphic to a (possibly indefinite) orthogonal group ${O(k,n-k)}$ for some ${0 \leq k \leq n}$ . Then any element ${T}$ of ${G}$ whose spectrum avoids ${(-\infty,0]}$ is exponential, that is to say ${T = \exp(X)}$ for some ${X}$ in the Lie algebra ${{\mathfrak g}}$ of ${G}$ .

Proof: We just prove this for ${G=O(Q)}$ , as the other cases are similar (or a bit simpler). If ${T \in O(Q)}$ , then (viewing ${T}$ as a complex-linear map on ${{\bf C}^n}$ , and using the complex bilinear form associated to ${Q}$ to identify ${{\bf C}^n}$ with its complex dual ${({\bf C}^n)^*}$ , then ${T}$ is real and ${T^{*-1} = T}$ . By the properties (v), (vi), (vii) of the standard branch of the matrix logarithm, we conclude that ${\hbox{Log} T}$ is real and ${- \hbox{Log}(T)^* = \hbox{Log}(T)}$ , and so ${\hbox{Log}(T)}$ lies in the Lie algebra ${{\mathfrak g} = {\mathfrak o}(Q)}$ , and the claim now follows from (i). $\Box$

Exercise 2 Show that ${\hbox{diag}(-\lambda, -1/\lambda)}$ is not exponential in ${GL_2({\bf R})}$ if ${-\lambda \in (-\infty,0) \backslash \{-1\}}$ . Thus we see that the branch cut in the above proposition is largely necessary. See this paper of Djokovic for a more complete description of the image of the exponential map in classical groups, as well as this previous blog post for some more discussion of the surjectivity (or lack thereof) of the exponential map in Lie groups.

For a slightly less quick application of the standard branch, we have the following result (recently worked out in the answers to this MathOverflow question):

Proposition 3 Let ${T}$ be an element of the split orthogonal group ${O(n,n)}$ which lies in the connected component of the identity. Then ${\hbox{det}(1+T) \geq 0}$ .

The requirement that ${T}$ lie in the identity component is necessary, as the counterexample ${T = \hbox{diag}(-\lambda, -1/\lambda )}$ for ${\lambda \in (-\infty,-1) \cup (-1,0)}$ shows.

Proof: We think of ${T}$ as a (real) linear transformation on ${{\bf C}^{2n}}$ , and write ${Q}$ for the quadratic form associated to ${O(n,n)}$ , so that ${O(n,n) \equiv O(Q)}$ . We can split ${{\bf C}^{2n} = V_1 \oplus V_2}$ , where ${V_1}$ is the sum of all the generalised eigenspaces corresponding to eigenvalues in ${(-\infty,0]}$ , and ${V_2}$ is the sum of all the remaining eigenspaces. Since ${T}$ and ${(-\infty,0]}$ are real, ${V_1,V_2}$ are real (i.e. complex-conjugation invariant) also. For ${i=1,2}$ , the restriction ${T_i: V_i \rightarrow V_i}$ of ${T}$ to ${V_i}$ then lies in ${O(Q_i)}$ , where ${Q_i}$ is the restriction of ${Q}$ to ${V_i}$ , and

$\displaystyle \hbox{det}(1+T) = \hbox{det}(1+T_1) \hbox{det}(1+T_2).$

The spectrum of ${T_2}$ consists of positive reals, as well as complex pairs ${\lambda, \overline{\lambda}}$ (with equal multiplicity), so ${\hbox{det}(1+T_2) > 0}$ . From the preceding proposition we have ${T_2 = \exp( X_2 )}$ for some ${X_2 \in {\mathfrak o}(Q_2)}$ ; this will be important later.

It remains to show that ${\hbox{det}(1+T_1) \geq 0}$ . If ${T_1}$ has spectrum at ${-1}$ then we are done, so we may assume that ${T_1}$ has spectrum only at ${(-\infty,-1) \cup (-1,0)}$ (being invertible, ${T}$ has no spectrum at ${0}$ ). We split ${V_1 = V_3 \oplus V_4}$ , where ${V_3,V_4}$ correspond to the portions of the spectrum in ${(-\infty,-1)}$ , ${(-1,0)}$ ; these are real, ${T}$ -invariant spaces. We observe that if ${V_\lambda, V_\mu}$ are generalised eigenspaces of ${T}$ with ${\lambda \mu \neq 1}$ , then ${V_\lambda, V_\mu}$ are orthogonal with respect to the (complex-bilinear) inner product ${\cdot}$ associated with ${Q}$ ; this is easiest to see first for the actual eigenspaces (since ${ \lambda \mu u \cdot v = Tu \cdot Tv = u \cdot v}$ for all ${u \in V_\lambda, v \in V_\mu}$ ), and the extension to generalised eigenvectors then follows from a routine induction. From this we see that ${V_1}$ is orthogonal to ${V_2}$ , and ${V_3}$ and ${V_4}$ are null spaces, which by the non-degeneracy of ${Q}$ (and hence of the restriction ${Q_1}$ of ${Q}$ to ${V_1}$ ) forces ${V_3}$ to have the same dimension as ${V_4}$ , indeed ${Q}$ now gives an identification of ${V_3^*}$ with ${V_4}$ . If we let ${T_3, T_4}$ be the restrictions of ${T}$ to ${V_3,V_4}$ , we thus identify ${T_4}$ with ${T_3^{*-1}}$ , since ${T}$ lies in ${O(Q)}$ ; in particular ${T_3}$ is invertible. Thus

$\displaystyle \hbox{det}(1+T_1) = \hbox{det}(1 + T_3) \hbox{det}( 1 + T_3^{*-1} ) = \hbox{det}(T_3)^{-1} \hbox{det}(1+T_3)^2$

and so it suffices to show that ${\hbox{det}(T_3) > 0}$ .

At this point we need to use the hypothesis that ${T}$ lies in the identity component of ${O(n,n)}$ . This implies (by a continuity argument) that the restriction of ${T}$ to any maximal-dimensional positive subspace has positive determinant (since such a restriction cannot be singular, as this would mean that ${T}$ positive norm vector would map to a non-positive norm vector). Now, as ${V_3,V_4}$ have equal dimension, ${Q_1}$ has a balanced signature, so ${Q_2}$ does also. Since ${T_2 = \exp(X_2)}$ , ${T_2}$ already lies in the identity component of ${O(Q_2)}$ , and so has positive determinant on any maximal-dimensional positive subspace of ${V_2}$ . We conclude that ${T_1}$ has positive determinant on any maximal-dimensional positive subspace of ${V_1}$ .

We choose a complex basis of ${V_3}$ , to identify ${V_3}$ with ${V_3^*}$ , which has already been identified with ${V_4}$ . (In coordinates, ${V_3,V_4}$ are now both of the form ${{\bf C}^m}$ , and ${Q( v \oplus w ) = v \cdot w}$ for ${v,w \in {\bf C}^m}$ .) Then ${\{ v \oplus v: v \in V_3 \}}$ becomes a maximal positive subspace of ${V_1}$ , and the restriction of ${T_1}$ to this subspace is conjugate to ${T_3 + T_3^{*-1}}$ , so that

$\displaystyle \hbox{det}( T_3 + T_3^{*-1} ) > 0.$

But since ${\hbox{det}( T_3 + T_3^{*-1} ) = \hbox{det}(T_3) \hbox{det}( 1 + T_3^{-1} T_3^{*-1} )}$ and ${ 1 + T_3^{-1} T_3^{*-1}}$ is positive definite, so ${\hbox{det}(T_3)>0}$ as required. $\Box$

Random matrices: tail bounds for gaps between eigenvalues

3 April, 2015 in math.PR, math.SP, paper | Tags: eigenvalues, Hoi Nguyen, Littlewood-Offord problem, Van Vu | by Terence Tao | 21 comments

Hoi Nguyen, Van Vu, and myself have just uploaded to the arXiv our paper “Random matrices: tail bounds for gaps between eigenvalues“. This is a followup paper to my recent paper with Van in which we showed that random matrices ${M_n}$ of Wigner type (such as the adjacency matrix of an Erdös-Renyi graph) asymptotically almost surely had simple spectrum. In the current paper, we push the method further to show that the eigenvalues are not only distinct, but are (with high probability) separated from each other by some negative power ${n^{-A}}$ of ${n}$ . This follows the now standard technique of replacing any appearance of discrete Littlewood-Offord theory (a key ingredient in our previous paper) with its continuous analogue (inverse theorems for small ball probability). For general Wigner-type matrices ${M_n}$ (in which the matrix entries are not normalised to have mean zero), we can use the inverse Littlewood-Offord theorem of Nguyen and Vu to obtain (under mild conditions on ${M_n}$ ) a result of the form

$\displaystyle {\bf P} (\lambda_{i+1}(M_n) - \lambda_i(M_n) \leq n^{-A} ) \leq n^{-B}$

for any ${B}$ and ${i}$ , if ${A}$ is sufficiently large depending on ${B}$ (in a linear fashion), and ${n}$ is sufficiently large depending on ${B}$ . The point here is that ${B}$ can be made arbitrarily large, and also that no continuity or smoothness hypothesis is made on the distribution of the entries. (In the continuous case, one can use the machinery of Wegner estimates to obtain results of this type, as was done in a paper of Erdös, Schlein, and Yau.)

In the mean zero case, it becomes more efficient to use an inverse Littlewood-Offord theorem of Rudelson and Vershynin to obtain (with the normalisation that the entries of ${M_n}$ have unit variance, so that the eigenvalues of ${M_n}$ are ${O(\sqrt{n})}$ with high probability), giving the bound

$\displaystyle {\bf P} (\lambda_{i+1}(M_n) - \lambda_i(M_n) \leq \delta / \sqrt{n} ) \ll \delta \ \ \ \ \ (1)$

for ${\delta \geq n^{-O(1)}}$ (one also has good results of this type for smaller values of ${\delta}$ ). This is only optimal in the regime ${\delta \sim 1}$ ; we expect to establish some eigenvalue repulsion, improving the RHS to ${\delta^2}$ for real matrices and ${\delta^3}$ for complex matrices, but this appears to be a more difficult task (possibly requiring some quadratic inverse Littlewood-Offord theory, rather than just linear inverse Littlewood-Offord theory). However, we can get some repulsion if one works with larger gaps, getting a result roughly of the form

$\displaystyle {\bf P} (\lambda_{i+k}(M_n) - \lambda_i(M_n) \leq \delta / \sqrt{n} ) \ll \delta^{ck^2}$

for any fixed ${k \geq 1}$ and some absolute constant ${c>0}$ (which we can asymptotically make to be ${1/3}$ for large ${k}$ , though it ought to be as large as ${1}$ ), by using a higher-dimensional version of the Rudelson-Vershynin inverse Littlewood-Offord theorem.

In the case of Erdös-Renyi graphs, we don’t have mean zero and the Rudelson-Vershynin Littlewood-Offord theorem isn’t quite applicable, but by working carefully through the approach based on the Nguyen-Vu theorem we can almost recover (1), except for a loss of ${n^{o(1)}}$ on the RHS.

As a sample applications of the eigenvalue separation results, we can now obtain some information about eigenvectors; for instance, we can show that the components of the eigenvectors all have magnitude at least ${n^{-A}}$ for some ${A}$ with high probability. (Eigenvectors become much more stable, and able to be studied in isolation, once their associated eigenvalue is well separated from the other eigenvalues; see this previous blog post for more discussion.)

Random matrices have simple spectrum

4 December, 2014 in math.CO, math.PR, math.SP, paper | Tags: eigenvalues, Littlewood-Offord problem, random matrices, Van Vu | by Terence Tao | 22 comments

Van Vu and I have just uploaded to the arXiv our paper “Random matrices have simple spectrum“. Recall that an ${n \times n}$ Hermitian matrix is said to have simple eigenvalues if all of its ${n}$ eigenvalues are distinct. This is a very typical property of matrices to have: for instance, as discussed in this previous post, in the space of all ${n \times n}$ Hermitian matrices, the space of matrices without all eigenvalues simple has codimension three, and for real symmetric cases this space has codimension two. In particular, given any random matrix ensemble of Hermitian or real symmetric matrices with an absolutely continuous distribution, we conclude that random matrices drawn from this ensemble will almost surely have simple eigenvalues.

For discrete random matrix ensembles, though, the above argument breaks down, even though general universality heuristics predict that the statistics of discrete ensembles should behave similarly to those of continuous ensembles. A model case here is the adjacency matrix ${M_n}$ of an Erdös-Rényi graph – a graph on ${n}$ vertices in which any pair of vertices has an independent probability ${p}$ of being in the graph. For the purposes of this paper one should view ${p}$ as fixed, e.g. ${p=1/2}$ , while ${n}$ is an asymptotic parameter going to infinity. In this context, our main result is the following (answering a question of Babai):

Theorem 1 With probability ${1-o(1)}$ , ${M_n}$ has simple eigenvalues.

Our argument works for more general Wigner-type matrix ensembles, but for sake of illustration we will stick with the Erdös-Renyi case. Previous work on local universality for such matrix models (e.g. the work of Erdos, Knowles, Yau, and Yin) was able to show that any individual eigenvalue gap ${\lambda_{i+1}(M)-\lambda_i(M)}$ did not vanish with probability ${1-o(1)}$ (in fact ${1-O(n^{-c})}$ for some absolute constant ${c>0}$ ), but because there are ${n}$ different gaps that one has to simultaneously ensure to be non-zero, this did not give Theorem 1 as one is forced to apply the union bound.

Our argument in fact gives simplicity of the spectrum with probability ${1-O(n^{-A})}$ for any fixed ${A}$ ; in a subsequent paper we also show that it gives a quantitative lower bound on the eigenvalue gaps (analogous to how many results on the singularity probability of random matrices can be upgraded to a bound on the least singular value).

The basic idea of argument can be sketched as follows. Suppose that ${M_n}$ has a repeated eigenvalue ${\lambda}$ . We split

$\displaystyle M_n = \begin{pmatrix} M_{n-1} & X \\ X^T & 0 \end{pmatrix}$

for a random ${n-1 \times n-1}$ minor ${M_{n-1}}$ and a random sign vector ${X}$ ; crucially, ${X}$ and ${M_{n-1}}$ are independent. If ${M_n}$ has a repeated eigenvalue ${\lambda}$ , then by the Cauchy interlacing law, ${M_{n-1}}$ also has an eigenvalue ${\lambda}$ . We now write down the eigenvector equation for ${M_n}$ at ${\lambda}$ :

$\displaystyle \begin{pmatrix} M_{n-1} & X \\ X^T & 0 \end{pmatrix} \begin{pmatrix} v \\ a \end{pmatrix} = \lambda \begin{pmatrix} v \\ a \end{pmatrix}.$

Extracting the top ${n-1}$ coefficients, we obtain

$\displaystyle (M_{n-1} - \lambda) v + a X = 0.$

If we let ${w}$ be the ${\lambda}$ -eigenvector of ${M_{n-1}}$ , then by taking inner products with ${w}$ we conclude that

$\displaystyle a (w \cdot X) = 0;$

we typically expect ${a}$ to be non-zero, in which case we arrive at

$\displaystyle w \cdot X = 0.$

In other words, in order for ${M_n}$ to have a repeated eigenvalue, the top right column ${X}$ of ${M_n}$ has to be orthogonal to an eigenvector ${w}$ of the minor ${M_{n-1}}$ . Note that ${X}$ and ${w}$ are going to be independent (once we specify which eigenvector of ${M_{n-1}}$ to take as ${w}$ ). On the other hand, thanks to inverse Littlewood-Offord theory (specifically, we use an inverse Littlewood-Offord theorem of Nguyen and Vu), we know that the vector ${X}$ is unlikely to be orthogonal to any given vector ${w}$ independent of ${X}$ , unless the coefficients of ${w}$ are extremely special (specifically, that most of them lie in a generalised arithmetic progression). The main remaining difficulty is then to show that eigenvectors of a random matrix are typically not of this special form, and this relies on a conditioning argument originally used by Komlós to bound the singularity probability of a random sign matrix. (Basically, if an eigenvector has this special form, then one can use a fraction of the rows and columns of the random matrix to determine the eigenvector completely, while still preserving enough randomness in the remaining portion of the matrix so that this vector will in fact not be an eigenvector with high probability.)

A Banach algebra proof of the prime number theorem

25 October, 2014 in expository, math.NT, math.OA, math.SP | Tags: Banach algebra, prime number theorem, spectral theorem | by Terence Tao | 11 comments

The prime number theorem can be expressed as the assertion

$\displaystyle \sum_{n \leq x} \Lambda(n) = x + o(x) \ \ \ \ \ (1)$

as ${x \rightarrow \infty}$ , where

$\displaystyle \Lambda(n) := \sum_{d|n} \mu(d) \log \frac{n}{d}$

is the von Mangoldt function. It is a basic result in analytic number theory, but requires a bit of effort to prove. One “elementary” proof of this theorem proceeds through the Selberg symmetry formula

$\displaystyle \sum_{n \leq x} \Lambda_2(n) = 2 x \log x + O(x) \ \ \ \ \ (2)$

where the second von Mangoldt function ${\Lambda_2}$ is defined by the formula

$\displaystyle \Lambda_2(n) := \sum_{d|n} \mu(d) \log^2 \frac{n}{d} \ \ \ \ \ (3)$

or equivalently

$\displaystyle \Lambda_2(n) = \Lambda(n) \log n + \sum_{d|n} \Lambda(d) \Lambda(\frac{n}{d}). \ \ \ \ \ (4)$

(We are avoiding the use of the ${*}$ symbol here to denote Dirichlet convolution, as we will need this symbol to denote ordinary convolution shortly.) For the convenience of the reader, we give a proof of the Selberg symmetry formula below the fold. Actually, for the purposes of proving the prime number theorem, the weaker estimate

$\displaystyle \sum_{n \leq x} \Lambda_2(n) = 2 x \log x + o(x \log x) \ \ \ \ \ (5)$

suffices.

In this post I would like to record a somewhat “soft analysis” reformulation of the elementary proof of the prime number theorem in terms of Banach algebras, and specifically in Banach algebra structures on (completions of) the space ${C_c({\bf R})}$ of compactly supported continuous functions ${f: {\bf R} \rightarrow {\bf C}}$ equipped with the convolution operation

$\displaystyle f*g(t) := \int_{\bf R} f(u) g(t-u)\ du.$

This soft argument does not easily give any quantitative decay rate in the prime number theorem, but by the same token it avoids many of the quantitative calculations in the traditional proofs of this theorem. Ultimately, the key “soft analysis” fact used is the spectral radius formula

$\displaystyle \lim_{n \rightarrow \infty} \|f^n\|^{1/n} = \sup_{\lambda \in \hat B} |\lambda(f)| \ \ \ \ \ (6)$

for any element ${f}$ of a unital commutative Banach algebra ${B}$ , where ${\hat B}$ is the space of characters (i.e., continuous unital algebra homomorphisms from ${B}$ to ${{\bf C}}$ ) of ${B}$ . This formula is due to Gelfand and may be found in any text on Banach algebras; for sake of completeness we prove it below the fold.

The connection between prime numbers and Banach algebras is given by the following consequence of the Selberg symmetry formula.

Theorem 1 (Construction of a Banach algebra norm) For any ${G \in C_c({\bf R})}$ , let ${\|G\|}$ denote the quantity

$\displaystyle \|G\| := \limsup_{x \rightarrow \infty} |\sum_n \frac{\Lambda(n)}{n} G( \log \frac{x}{n} ) - \int_{\bf R} G(t)\ dt|.$

Then ${\| \|}$ is a seminorm on ${C_c({\bf R})}$ with the bound

$\displaystyle \|G\| \leq \|G\|_{L^1({\bf R})} := \int_{\bf R} |G(t)|\ dt \ \ \ \ \ (7)$

for all ${G \in C_c({\bf R})}$ . Furthermore, we have the Banach algebra bound

$\displaystyle \| G * H \| \leq \|G\| \|H\| \ \ \ \ \ (8)$

for all ${G,H \in C_c({\bf R})}$ .

We prove this theorem below the fold. The prime number theorem then follows from Theorem 1 and the following two assertions. The first is an application of the spectral radius formula (6) and some basic Fourier analysis (in particular, the observation that ${C_c({\bf R})}$ contains a plentiful supply of local units):

Theorem 2 (Non-trivial Banach algebras with many local units have non-trivial spectrum) Let ${\| \|}$ be a seminorm on ${C_c({\bf R})}$ obeying (7), (8). Suppose that ${\| \|}$ is not identically zero. Then there exists ${\xi \in {\bf R}}$ such that

$\displaystyle |\int_{\bf R} G(t) e^{-it\xi}\ dt| \leq \|G\|$

for all ${G \in C_c}$ . In particular, by (7), one has

$\displaystyle \|G\| = \| G \|_{L^1({\bf R})}$

whenever ${G(t) e^{-it\xi}}$ is a non-negative function.

The second is a consequence of the Selberg symmetry formula and the fact that ${\Lambda}$ is real (as well as Mertens’ theorem, in the ${\xi=0}$ case), and is closely related to the non-vanishing of the Riemann zeta function ${\zeta}$ on the line ${\{ 1+i\xi: \xi \in {\bf R}\}}$ :

Theorem 3 (Breaking the parity barrier) Let ${\xi \in {\bf R}}$ . Then there exists ${G \in C_c({\bf R})}$ such that ${G(t) e^{-it\xi}}$ is non-negative, and

$\displaystyle \|G\| < \|G\|_{L^1({\bf R})}.$

Assuming Theorems 1, 2, 3, we may now quickly establish the prime number theorem as follows. Theorem 2 and Theorem 3 imply that the seminorm ${\| \|}$ constructed in Theorem 1 is trivial, and thus

$\displaystyle \sum_n \frac{\Lambda(n)}{n} G( \log \frac{x}{n} ) = \int_{\bf R} G(t)\ dt + o(1)$

as ${x \rightarrow \infty}$ for any Schwartz function ${G}$ (the decay rate in ${o(1)}$ may depend on ${G}$ ). Specialising to functions of the form ${G(t) = e^{-t} \eta( e^{-t} )}$ for some smooth compactly supported ${\eta}$ on ${(0,+\infty)}$ , we conclude that

$\displaystyle \sum_n \Lambda(n) \eta(\frac{n}{x}) = x \int_{\bf R} \eta(u)\ du + o(x)$

as ${x \rightarrow \infty}$ ; by the smooth Urysohn lemma this implies that

$\displaystyle \sum_{\varepsilon x \leq n \leq x} \Lambda(n) = x - \varepsilon x + o(x)$

as ${x \rightarrow \infty}$ for any fixed ${\varepsilon>0}$ , and the prime number theorem then follows by a telescoping series argument.

The same argument also yields the prime number theorem in arithmetic progressions, or equivalently that

$\displaystyle \sum_{n \leq x} \Lambda(n) \chi(n) = o(x)$

for any fixed Dirichlet character ${\chi}$ ; the one difference is that the use of Mertens’ theorem is replaced by the basic fact that the quantity ${L(1,\chi) = \sum_n \frac{\chi(n)}{n}}$ is non-vanishing.

Read the rest of this entry »

Real analysis relative to a finite measure space

15 July, 2014 in expository, math.CA, math.CT, math.PR, math.SP | Tags: elementary topos, Heine-Borel theorem, Hilbert modules, Hilbert-Schmidt operators, singular value decomposition, spectral theorem | by Terence Tao | 12 comments

In the traditional foundations of probability theory, one selects a probability space ${(\Omega, {\mathcal B}, {\mathbf P})}$ , and makes a distinction between deterministic mathematical objects, which do not depend on the sampled state ${\omega \in \Omega}$ , and stochastic (or random) mathematical objects, which do depend (but in a measurable fashion) on the sampled state ${\omega \in \Omega}$ . For instance, a deterministic real number would just be an element ${x \in {\bf R}}$ , whereas a stochastic real number (or real random variable) would be a measurable function ${x: \Omega \rightarrow {\bf R}}$ , where in this post ${{\bf R}}$ will always be endowed with the Borel ${\sigma}$ -algebra. (For readers familiar with nonstandard analysis, the adjectives “deterministic” and “stochastic” will be used here in a manner analogous to the uses of the adjectives “standard” and “nonstandard” in nonstandard analysis. The analogy is particularly close when comparing with the “cheap nonstandard analysis” discussed in this previous blog post. We will also use “relative to ${\Omega}$ ” as a synonym for “stochastic”.)

Actually, for our purposes we will adopt the philosophy of identifying stochastic objects that agree almost surely, so if one was to be completely precise, we should define a stochastic real number to be an equivalence class ${[x]}$ of measurable functions ${x: \Omega \rightarrow {\bf R}}$ , up to almost sure equivalence. However, we shall often abuse notation and write ${[x]}$ simply as ${x}$ .

More generally, given any measurable space ${X = (X, {\mathcal X})}$ , we can talk either about deterministic elements ${x \in X}$ , or about stochastic elements of ${X}$ , that is to say equivalence classes ${[x]}$ of measurable maps ${x: \Omega \rightarrow X}$ up to almost sure equivalence. We will use ${\Gamma(X|\Omega)}$ to denote the set of all stochastic elements of ${X}$ . (For readers familiar with sheaves, it may helpful for the purposes of this post to think of ${\Gamma(X|\Omega)}$ as the space of measurable global sections of the trivial ${X}$ –bundle over ${\Omega}$ .) Of course every deterministic element ${x}$ of ${X}$ can also be viewed as a stochastic element ${x|\Omega \in \Gamma(X|\Omega)}$ given by (the equivalence class of) the constant function ${\omega \mapsto x}$ , thus giving an embedding of ${X}$ into ${\Gamma(X|\Omega)}$ . We do not attempt here to give an interpretation of ${\Gamma(X|\Omega)}$ for sets ${X}$ that are not equipped with a ${\sigma}$ -algebra ${{\mathcal X}}$ .

Remark 1 In my previous post on the foundations of probability theory, I emphasised the freedom to extend the sample space ${(\Omega, {\mathcal B}, {\mathbf P})}$ to a larger sample space whenever one wished to inject additional sources of randomness. This is of course an important freedom to possess (and in the current formalism, is the analogue of the important operation of base change in algebraic geometry), but in this post we will focus on a single fixed sample space ${(\Omega, {\mathcal B}, {\mathbf P})}$ , and not consider extensions of this space, so that one only has to consider two types of mathematical objects (deterministic and stochastic), as opposed to having many more such types, one for each potential choice of sample space (with the deterministic objects corresponding to the case when the sample space collapses to a point).

Any (measurable) ${k}$ -ary operation on deterministic mathematical objects then extends to their stochastic counterparts by applying the operation pointwise. For instance, the addition operation ${+: {\bf R} \times {\bf R} \rightarrow {\bf R}}$ on deterministic real numbers extends to an addition operation ${+: \Gamma({\bf R}|\Omega) \times \Gamma({\bf R}|\Omega) \rightarrow \Gamma({\bf R}|\Omega)}$ , by defining the class ${[x]+[y]}$ for ${x,y: \Omega \rightarrow {\bf R}}$ to be the equivalence class of the function ${\omega \mapsto x(\omega) + y(\omega)}$ ; this operation is easily seen to be well-defined. More generally, any measurable ${k}$ -ary deterministic operation ${O: X_1 \times \dots \times X_k \rightarrow Y}$ between measurable spaces ${X_1,\dots,X_k,Y}$ extends to an stochastic operation ${O: \Gamma(X_1|\Omega) \times \dots \Gamma(X_k|\Omega) \rightarrow \Gamma(Y|\Omega)}$ in the obvious manner.

There is a similar story for ${k}$ -ary relations ${R: X_1 \times \dots \times X_k \rightarrow \{\hbox{true},\hbox{false}\}}$ , although here one has to make a distinction between a deterministic reading of the relation and a stochastic one. Namely, if we are given stochastic objects ${x_i \in \Gamma(X_i|\Omega)}$ for ${i=1,\dots,k}$ , the relation ${R(x_1,\dots,x_k)}$ does not necessarily take values in the deterministic Boolean algebra ${\{ \hbox{true}, \hbox{false}\}}$ , but only in the stochastic Boolean algebra ${\Gamma(\{ \hbox{true}, \hbox{false}\}|\Omega)}$ – thus ${R(x_1,\dots,x_k)}$ may be true with some positive probability and also false with some positive probability (with the event that ${R(x_1,\dots,x_k)}$ being stochastically true being determined up to null events). Of course, the deterministic Boolean algebra embeds in the stochastic one, so we can talk about a relation ${R(x_1,\dots,x_k)}$ being determinstically true or deterministically false, which (due to our identification of stochastic objects that agree almost surely) means that ${R(x_1(\omega),\dots,x_k(\omega))}$ is almost surely true or almost surely false respectively. For instance given two stochastic objects ${x,y}$ , one can view their equality relation ${x=y}$ as having a stochastic truth value. This is distinct from the way the equality symbol ${=}$ is used in mathematical logic, which we will now call “equality in the deterministic sense” to reduce confusion. Thus, ${x=y}$ in the deterministic sense if and only if the stochastic truth value of ${x=y}$ is equal to ${\hbox{true}}$ , that is to say that ${x(\omega)=y(\omega)}$ for almost all ${\omega}$ .

Any universal identity for deterministic operations (or universal implication between identities) extends to their stochastic counterparts: for instance, addition is commutative, associative, and cancellative on the space of deterministic reals ${{\bf R}}$ , and is therefore commutative, associative, and cancellative on stochastic reals ${\Gamma({\bf R}|\Omega)}$ as well. However, one has to be more careful when working with mathematical laws that are not expressible as universal identities, or implications between identities. For instance, ${{\bf R}}$ is an integral domain: if ${x_1,x_2 \in {\bf R}}$ are deterministic reals such that ${x_1 x_2=0}$ , then one must have ${x_1=0}$ or ${x_2=0}$ . However, if ${x_1, x_2 \in \Gamma({\bf R}|\Omega)}$ are stochastic reals such that ${x_1 x_2 = 0}$ (in the deterministic sense), then it is no longer necessarily the case that ${x_1=0}$ (in the deterministic sense) or that ${x_2=0}$ (in the deterministic sense); however, it is still true that “ ${x_1=0}$ or ${x_2=0}$ ” is true in the deterministic sense if one interprets the boolean operator “or” stochastically, thus “ ${x_1(\omega)=0}$ or ${x_2(\omega)=0}$ ” is true for almost all ${\omega}$ . Another way to properly obtain a stochastic interpretation of the integral domain property of ${{\bf R}}$ is to rewrite it as

$\displaystyle x_1,x_2 \in {\bf R}, x_1 x_2 = 0 \implies x_i=0 \hbox{ for some } i \in \{1,2\}$

and then make all sets stochastic to obtain the true statement

$\displaystyle x_1,x_2 \in \Gamma({\bf R}|\Omega), x_1 x_2 = 0 \implies x_i=0 \hbox{ for some } i \in \Gamma(\{1,2\}|\Omega),$

thus we have to allow the index ${i}$ for which vanishing ${x_i=0}$ occurs to also be stochastic, rather than deterministic. (A technical note: when one proves this statement, one has to select ${i}$ in a measurable fashion; for instance, one can choose ${i(\omega)}$ to equal ${1}$ when ${x_1(\omega)=0}$ , and ${2}$ otherwise (so that in the “tie-breaking” case when ${x_1(\omega)}$ and ${x_2(\omega)}$ both vanish, one always selects ${i(\omega)}$ to equal ${1}$ ).)

Similarly, the law of the excluded middle fails when interpreted deterministically, but remains true when interpreted stochastically: if ${S}$ is a stochastic statement, then it is not necessarily the case that ${S}$ is either deterministically true or deterministically false; however the sentence “ ${S}$ or not- ${S}$ ” is still deterministically true if the boolean operator “or” is interpreted stochastically rather than deterministically.

To avoid having to keep pointing out which operations are interpreted stochastically and which ones are interpreted deterministically, we will use the following convention: if we assert that a mathematical sentence ${S}$ involving stochastic objects is true, then (unless otherwise specified) we mean that ${S}$ is deterministically true, assuming that all relations used inside ${S}$ are interpreted stochastically. For instance, if ${x,y}$ are stochastic reals, when we assert that “Exactly one of ${x < y}$ , ${x=y}$ , or ${x>y}$ is true”, then by default it is understood that the relations ${<}$ , ${=}$ , ${>}$ and the boolean operator “exactly one of” are interpreted stochastically, and the assertion is that the sentence is deterministically true.

In the above discussion, the stochastic objects ${x}$ being considered were elements of a deterministic space ${X}$ , such as the reals ${{\bf R}}$ . However, it can often be convenient to generalise this situation by allowing the ambient space ${X}$ to also be stochastic. For instance, one might wish to consider a stochastic vector ${v(\omega)}$ inside a stochastic vector space ${V(\omega)}$ , or a stochastic edge ${e}$ of a stochastic graph ${G(\omega)}$ . In order to formally describe this situation within the classical framework of measure theory, one needs to place all the ambient spaces ${X(\omega)}$ inside a measurable space. This can certainly be done in many contexts (e.g. when considering random graphs on a deterministic set of vertices, or if one is willing to work up to equivalence and place the ambient spaces inside a suitable moduli space), but is not completely natural in other contexts. For instance, if one wishes to consider stochastic vector spaces of potentially unbounded dimension (in particular, potentially larger than any given cardinal that one might specify in advance), then the class of all possible vector spaces is so large that it becomes a proper class rather than a set (even if one works up to equivalence), making it problematic to give this class the structure of a measurable space; furthermore, even once one does so, one needs to take additional care to pin down what it would mean for a random vector ${\omega \mapsto v_\omega}$ lying in a random vector space ${\omega \mapsto V_\omega}$ to depend “measurably” on ${\omega}$ .

Of course, in any reasonable application one can avoid the set theoretic issues at least by various ad hoc means, for instance by restricting the dimension of all spaces involved to some fixed cardinal such as ${2^{\aleph_0}}$ . However, the measure-theoretic issues can require some additional effort to resolve properly.

In this post I would like to describe a different way to formalise stochastic spaces, and stochastic elements of these spaces, by viewing the spaces as measure-theoretic analogue of a sheaf, but being over the probability space ${\Omega}$ rather than over a topological space; stochastic objects are then sections of such sheaves. Actually, for minor technical reasons it is convenient to work in the slightly more general setting in which the base space ${\Omega}$ is a finite measure space ${(\Omega, {\mathcal B}, \mu)}$ rather than a probability space, thus ${\mu(\Omega)}$ can take any value in ${[0,+\infty)}$ rather than being normalised to equal ${1}$ . This will allow us to easily localise to subevents ${\Omega'}$ of ${\Omega}$ without the need for normalisation, even when ${\Omega'}$ is a null event (though we caution that the map ${x \mapsto x|\Omega'}$ from deterministic objects ${x}$ ceases to be injective in this latter case). We will however still continue to use probabilistic terminology. despite the lack of normalisation; thus for instance, sets ${E}$ in ${{\mathcal B}}$ will be referred to as events, the measure ${\mu(E)}$ of such a set will be referred to as the probability (which is now permitted to exceed ${1}$ in some cases), and an event whose complement is a null event shall be said to hold almost surely. It is in fact likely that almost all of the theory below extends to base spaces which are ${\sigma}$ -finite rather than finite (for instance, by damping the measure to become finite, without introducing any further null events), although we will not pursue this further generalisation here.

The approach taken in this post is “topos-theoretic” in nature (although we will not use the language of topoi explicitly here), and is well suited to a “pointless” or “point-free” approach to probability theory, in which the role of the stochastic state ${\omega \in \Omega}$ is suppressed as much as possible; instead, one strives to always adopt a “relative point of view”, with all objects under consideration being viewed as stochastic objects relative to the underlying base space ${\Omega}$ . In this perspective, the stochastic version of a set is as follows.

Definition 1 (Stochastic set) Unless otherwise specified, we assume that we are given a fixed finite measure space ${\Omega = (\Omega, {\mathcal B}, \mu)}$ (which we refer to as the base space). A stochastic set (relative to ${\Omega}$ ) is a tuple ${X|\Omega = (\Gamma(X|E)_{E \in {\mathcal B}}, ((|E))_{E \subset F, E,F \in {\mathcal B}})}$ consisting of the following objects:

A set ${\Gamma(X|E)}$ assigned to each event ${E \in {\mathcal B}}$ ; and

A restriction map ${x \mapsto x|E}$ from ${\Gamma(X|F)}$ to ${\Gamma(X|E)}$ to each pair ${E \subset F}$ of nested events ${E,F \in {\mathcal B}}$ . (Strictly speaking, one should indicate the dependence on ${F}$ in the notation for the restriction map, e.g. using ${x \mapsto x|(E \leftarrow F)}$ instead of ${x \mapsto x|E}$ , but we will abuse notation by omitting the ${F}$ dependence.)

We refer to elements of ${\Gamma(X|E)}$ as local stochastic elements of the stochastic set ${X|\Omega}$ , localised to the event ${E}$ , and elements of ${\Gamma(X|\Omega)}$ as global stochastic elements (or simply elements) of the stochastic set. (In the language of sheaves, one would use “sections” instead of “elements” here, but I prefer to use the latter terminology here, for compatibility with conventional probabilistic notation, where for instance measurable maps from ${\Omega}$ to ${{\bf R}}$ are referred to as real random variables, rather than sections of the reals.)

Furthermore, we impose the following axioms:

(Category) The map ${x \mapsto x|E}$ from ${\Gamma(X|E)}$ to ${\Gamma(X|E)}$ is the identity map, and if ${E \subset F \subset G}$ are events in ${{\mathcal B}}$ , then ${((x|F)|E) = (x|E)}$ for all ${x \in \Gamma(X|G)}$ .

(Null events trivial) If ${E \in {\mathcal B}}$ is a null event, then the set ${\Gamma(X|E)}$ is a singleton set. (In particular, ${\Gamma(X|\emptyset)}$ is always a singleton set; this is analogous to the convention that ${x^0=1}$ for any number ${x}$ .)

(Countable gluing) Suppose that for each natural number ${n}$ , one has an event ${E_n \in {\mathcal B}}$ and an element ${x_n \in \Gamma(X|E_n)}$ such that ${x_n|(E_n \cap E_m) = x_m|(E_n \cap E_m)}$ for all ${n,m}$ . Then there exists a unique ${x\in \Gamma(X|\bigcup_{n=1}^\infty E_n)}$ such that ${x_n = x|E_n}$ for all ${n}$ .

If ${\Omega'}$ is an event in ${\Omega}$ , we define the localisation ${X|\Omega'}$ of the stochastic set ${X|\Omega}$ to ${\Omega'}$ to be the stochastic set

$\displaystyle X|\Omega' := (\Gamma(X|E)_{E \in {\mathcal B}; E \subset \Omega'}, ((|E))_{E \subset F \subset \Omega', E,F \in {\mathcal B}})$

relative to ${\Omega'}$ . (Note that there is no need to renormalise the measure on ${\Omega'}$ , as we are not demanding that our base space have total measure ${1}$ .)

The following fact is useful for actually verifying that a given object indeed has the structure of a stochastic set:

Exercise 1 Show that to verify the countable gluing axiom of a stochastic set, it suffices to do so under the additional hypothesis that the events ${E_n}$ are disjoint. (Note that this is quite different from the situation with sheaves over a topological space, in which the analogous gluing axiom is often trivial in the disjoint case but has non-trivial content in the overlapping case. This is ultimately because a ${\sigma}$ -algebra is closed under all Boolean operations, whereas a topology is only closed under union and intersection.)

Let us illustrate the concept of a stochastic set with some examples.

Example 1 (Discrete case) A simple case arises when ${\Omega}$ is a discrete space which is at most countable. If we assign a set ${X_\omega}$ to each ${\omega \in \Omega}$ , with ${X_\omega}$ a singleton if ${\mu(\{\omega\})=0}$ . One then sets ${\Gamma(X|E) := \prod_{\omega \in E} X_\omega}$ , with the obvious restriction maps, giving rise to a stochastic set ${X|\Omega}$ . (Thus, a local element ${x}$ of ${\Gamma(X|E)}$ can be viewed as a map ${\omega \mapsto x(\omega)}$ on ${E}$ that takes values in ${X_\omega}$ for each ${\omega \in E}$ .) Conversely, it is not difficult to see that any stochastic set over an at most countable discrete probability space ${\Omega}$ is of this form up to isomorphism. In this case, one can think of ${X|\Omega}$ as a bundle of sets ${X_\omega}$ over each point ${\omega}$ (of positive probability) in the base space ${\Omega}$ . One can extend this bundle interpretation of stochastic sets to reasonably nice sample spaces ${\Omega}$ (such as standard Borel spaces) and similarly reasonable ${X}$ ; however, I would like to avoid this interpretation in the formalism below in order to be able to easily work in settings in which ${\Omega}$ and ${X}$ are very “large” (e.g. not separable in any reasonable sense). Note that we permit some of the ${X_\omega}$ to be empty, thus it can be possible for ${\Gamma(X|\Omega)}$ to be empty whilst ${\Gamma(X|E)}$ for some strict subevents ${E}$ of ${\Omega}$ to be non-empty. (This is analogous to how it is possible for a sheaf to have local sections but no global sections.) As such, the space ${\Gamma(X|\Omega)}$ of global elements does not completely determine the stochastic set ${X|\Omega}$ ; one sometimes needs to localise to an event ${E}$ in order to see the full structure of such a set. Thus it is important to distinguish between a stochastic set ${X|\Omega}$ and its space ${\Gamma(X|\Omega)}$ of global elements. (As such, it is a slight abuse of the axiom of extensionality to refer to global elements of ${X|\Omega}$ simply as “elements”, but hopefully this should not cause too much confusion.)

Example 2 (Measurable spaces as stochastic sets) Returning now to a general base space ${\Omega}$ , any (deterministic) measurable space ${X}$ gives rise to a stochastic set ${X|\Omega}$ , with ${\Gamma(X|E)}$ being defined as in previous discussion as the measurable functions from ${E}$ to ${X}$ modulo almost everywhere equivalence (in particular, ${\Gamma(X|E)}$ a singleton set when ${E}$ is null), with the usual restriction maps. The constraint of measurability on the maps ${x: E \rightarrow \Omega}$ , together with the quotienting by almost sure equivalence, means that ${\Gamma(X|E)}$ is now more complicated than a plain Cartesian product ${\prod_{\omega \in E} X_\omega}$ of fibres, but this still serves as a useful first approximation to what ${\Gamma(X|E)}$ is for the purposes of developing intuition. Indeed, the measurability constraint is so weak (as compared for instance to topological or smooth constraints in other contexts, such as sheaves of continuous or smooth sections of bundles) that the intuition of essentially independent fibres is quite an accurate one, at least if one avoids consideration of an uncountable number of objects simultaneously.

Example 3 (Extended Hilbert modules) This example is the one that motivated this post for me. Suppose that one has an extension ${(\tilde \Omega, \tilde {\mathcal B}, \tilde \mu)}$ of the base space ${(\Omega, {\mathcal B},\mu)}$ , thus we have a measurable factor map ${\pi: \tilde \Omega \rightarrow \Omega}$ such that the pushforward of the measure ${\tilde \mu}$ by ${\pi}$ is equal to ${\mu}$ . Then we have a conditional expectation operator ${\pi_*: L^2(\tilde \Omega,\tilde {\mathcal B},\tilde \mu) \rightarrow L^2(\Omega,{\mathcal B},\mu)}$ , defined as the adjoint of the pullback map ${\pi^*: L^2(\Omega,{\mathcal B},\mu) \rightarrow L^2(\tilde \Omega,\tilde {\mathcal B},\tilde \mu)}$ . As is well known, the conditional expectation operator also extends to a contraction ${\pi_*: L^1(\tilde \Omega,\tilde {\mathcal B},\tilde \mu) \rightarrow L^1(\Omega,{\mathcal B}, \mu)}$ ; by monotone convergence we may also extend ${\pi_*}$ to a map from measurable functions from ${\tilde \Omega}$ to the extended non-negative reals ${[0,+\infty]}$ , to measurable functions from ${\Omega}$ to ${[0,+\infty]}$ . We then define the “extended Hilbert module” ${L^2(\tilde \Omega|\Omega)}$ to be the space of functions ${f \in L^2(\tilde \Omega,\tilde {\mathcal B},\tilde \mu)}$ with ${\pi_*(|f|^2)}$ finite almost everywhere. This is an extended version of the Hilbert module ${L^\infty_{\Omega} L^2(\tilde \Omega|\Omega)}$ , which is defined similarly except that ${\pi_*(|f|^2)}$ is required to lie in ${L^\infty(\Omega,{\mathcal B},\mu)}$ ; this is a Hilbert module over ${L^\infty(\Omega, {\mathcal B}, \mu)}$ which is of particular importance in the Furstenberg-Zimmer structure theory of measure-preserving systems. We can then define the stochastic set ${L^2_\pi(\tilde \Omega)|\Omega}$ by setting

$\displaystyle \Gamma(L^2_\pi(\tilde \Omega)|E) := L^2( \pi^{-1}(E) | E )$

with the obvious restriction maps. In the case that ${\Omega,\Omega'}$ are standard Borel spaces, one can disintegrate ${\mu'}$ as an integral ${\mu' = \int_\Omega \nu_\omega\ d\mu(\omega)}$ of probability measures ${\nu_\omega}$ (supported in the fibre ${\pi^{-1}(\{\omega\})}$ ), in which case this stochastic set can be viewed as having fibres ${L^2( \tilde \Omega, \tilde {\mathcal B}, \nu_\omega )}$ (though if ${\Omega}$ is not discrete, there are still some measurability conditions in ${\omega}$ on the local and global elements that need to be imposed). However, I am interested in the case when ${\Omega,\Omega'}$ are not standard Borel spaces (in fact, I will take them to be algebraic probability spaces, as defined in this previous post), in which case disintegrations are not available. However, it appears that the stochastic analysis developed in this blog post can serve as a substitute for the tool of disintegration in this context.

We make the remark that if ${X|\Omega}$ is a stochastic set and ${E, F}$ are events that are equivalent up to null events, then one can identify ${\Gamma(X|E)}$ with ${\Gamma(X|F)}$ (through their common restriction to ${\Gamma(X|(E \cap F))}$ , with the restriction maps now being bijections). As such, the notion of a stochastic set does not require the full structure of a concrete probability space ${(\Omega, {\mathcal B}, {\mathbf P})}$ ; one could also have defined the notion using only the abstract ${\sigma}$ -algebra consisting of ${{\mathcal B}}$ modulo null events as the base space, or equivalently one could define stochastic sets over the algebraic probability spaces defined in this previous post. However, we will stick with the classical formalism of concrete probability spaces here so as to keep the notation reasonably familiar.

As a corollary of the above observation, we see that if the base space ${\Omega}$ has total measure ${0}$ , then all stochastic sets are trivial (they are just points).

Exercise 2 If ${X|\Omega}$ is a stochastic set, show that there exists an event ${\Omega'}$ with the property that for any event ${E}$ , ${\Gamma(X|E)}$ is non-empty if and only if ${E}$ is contained in ${\Omega'}$ modulo null events. (In particular, ${\Omega'}$ is unique up to null events.) Hint: consider the numbers ${\mu( E )}$ for ${E}$ ranging over all events with ${\Gamma(X|E)}$ non-empty, and form a maximising sequence for these numbers. Then use all three axioms of a stochastic set.

One can now start take many of the fundamental objects, operations, and results in set theory (and, hence, in most other categories of mathematics) and establish analogues relative to a finite measure space. Implicitly, what we will be doing in the next few paragraphs is endowing the category of stochastic sets with the structure of an elementary topos. However, to keep things reasonably concrete, we will not explicitly emphasise the topos-theoretic formalism here, although it is certainly lurking in the background.

Firstly, we define a stochastic function ${f: X|\Omega \rightarrow Y|\Omega}$ between two stochastic sets ${X|\Omega, Y|\Omega}$ to be a collection of maps ${f: \Gamma(X|E) \rightarrow \Gamma(Y|E)}$ for each ${E \in {\mathcal B}}$ which form a natural transformation in the sense that ${f(x|E) = f(x)|E}$ for all ${x \in \Gamma(X|F)}$ and nested events ${E \subset F}$ . In the case when ${\Omega}$ is discrete and at most countable (and after deleting all null points), a stochastic function is nothing more than a collection of functions ${f_\omega: X_\omega \rightarrow Y_\omega}$ for each ${\omega \in \Omega}$ , with the function ${f: \Gamma(X|E) \rightarrow \Gamma(Y|E)}$ then being a direct sum of the factor functions ${f_\omega}$ :

$\displaystyle f( (x_\omega)_{\omega \in E} ) = ( f_\omega(x_\omega) )_{\omega \in E}.$

Thus (in the discrete, at most countable setting, at least) stochastic functions do not mix together information from different states ${\omega}$ in a sample space; the value of ${f(x)}$ at ${\omega}$ depends only on the value of ${x}$ at ${\omega}$ . The situation is a bit more subtle for continuous probability spaces, due to the identification of stochastic objects that agree almost surely, nevertheness it is still good intuition to think of stochastic functions as essentially being “pointwise” or “local” in nature.

One can now form the stochastic set ${\hbox{Hom}(X \rightarrow Y)|\Omega}$ of functions from ${X|\Omega}$ to ${Y|\Omega}$ , by setting ${\Gamma(\hbox{Hom}(X \rightarrow Y)|E)}$ for any event ${E}$ to be the set of local stochastic functions ${f: X|E \rightarrow Y|E}$ of the localisations of ${X|\Omega, Y|\Omega}$ to ${E}$ ; this is a stochastic set if we use the obvious restriction maps. In the case when ${\Omega}$ is discrete and at most countable, the fibre ${\hbox{Hom}(X \rightarrow Y)_\omega}$ at a point ${\omega}$ of positive measure is simply the set ${Y_\omega^{X_\omega}}$ of functions from ${X_\omega}$ to ${Y_\omega}$ .

In a similar spirit, we say that one stochastic set ${Y|\Omega}$ is a (stochastic) subset of another ${X|\Omega}$ , and write ${Y|\Omega \subset X|\Omega}$ , if we have a stochastic inclusion map, thus ${\Gamma(Y|E) \subset \Gamma(X|E)}$ for all events ${E}$ , with the restriction maps being compatible. We can then define the power set ${2^X|\Omega}$ of a stochastic set ${X|\Omega}$ by setting ${\Gamma(2^X|E)}$ for any event ${E}$ to be the set of all stochastic subsets ${Y|E}$ of ${X|E}$ relative to ${E}$ ; it is easy to see that ${2^X|\Omega}$ is a stochastic set with the obvious restriction maps (one can also identify ${2^X|\Omega}$ with ${\hbox{Hom}(X, \{\hbox{true},\hbox{false}\})|\Omega}$ in the obvious fashion). Again, when ${\Omega}$ is discrete and at most countable, the fibre of ${2^X|\Omega}$ at a point ${\omega}$ of positive measure is simply the deterministic power set ${2^{X_\omega}}$ .

Note that if ${f: X|\Omega \rightarrow Y|\Omega}$ is a stochastic function and ${Y'|\Omega}$ is a stochastic subset of ${Y|\Omega}$ , then the inverse image ${f^{-1}(Y')|\Omega}$ , defined by setting ${\Gamma(f^{-1}(Y')|E)}$ for any event ${E}$ to be the set of those ${x \in \Gamma(X|E)}$ with ${f(x) \in \Gamma(Y'|E)}$ , is a stochastic subset of ${X|\Omega}$ . In particular, given a ${k}$ -ary relation ${R: X_1 \times \dots \times X_k|\Omega \rightarrow \{\hbox{true}, \hbox{false}\}|\Omega}$ , the inverse image ${R^{-1}( \{ \hbox{true} \}|\Omega )}$ is a stochastic subset of ${X_1 \times \dots \times X_k|\Omega}$ , which by abuse of notation we denote as

$\displaystyle \{ (x_1,\dots,x_k) \in X_1 \times \dots \times X_k: R(x_1,\dots,x_k) \hbox{ is true} \}|\Omega.$

In a similar spirit, if ${X'|\Omega}$ is a stochastic subset of ${X|\Omega}$ and ${f: X|\Omega \rightarrow Y|\Omega}$ is a stochastic function, we can define the image ${f(X')|\Omega}$ by setting ${\Gamma(f(X')|E)}$ to be the set of those ${f(x)}$ with ${x \in \Gamma(X'|E)}$ ; one easily verifies that this is a stochastic subset of ${Y|\Omega}$ .

Remark 2 One should caution that in the definition of the subset relation ${Y|\Omega \subset X|\Omega}$ , it is important that ${\Gamma(Y|E) \subset \Gamma(X|E)}$ for all events ${E}$ , not just the global event ${\Omega}$ ; in particular, just because a stochastic set ${X|\Omega}$ has no global sections, does not mean that it is contained in the stochastic empty set ${\emptyset|\Omega}$ .

Now we discuss Boolean operations on stochastic subsets of a given stochastic set ${X|\Omega}$ . Given two stochastic subsets ${X_1|\Omega, X_2|\Omega}$ of ${X|\Omega}$ , the stochastic intersection ${(X_1 \cap X_2)|\Omega}$ is defined by setting ${\Gamma((X_1 \cap X_2)|E)}$ to be the set of ${x \in \Gamma(X|E)}$ that lie in both ${\Gamma(X_1|E)}$ and ${\Gamma(X_2|E)}$ :

$\displaystyle \Gamma(X_1 \cap X_2)|E) := \Gamma(X_1|E) \cap \Gamma(X_2|E).$

This is easily verified to again be a stochastic subset of ${X|\Omega}$ . More generally one may define stochastic countable intersections ${(\bigcap_{n=1}^\infty X_n)|\Omega}$ for any sequence ${X_n|\Omega}$ of stochastic subsets of ${X|\Omega}$ . One could extend this definition to uncountable families if one wished, but I would advise against it, because some of the usual laws of Boolean algebra (e.g. the de Morgan laws) may break down in this setting.

Stochastic unions are a bit more subtle. The set ${\Gamma((X_1 \cup X_2)|E)}$ should not be defined to simply be the union of ${\Gamma(X_1|E)}$ and ${\Gamma(X_2|E)}$ , as this would not respect the gluing axiom. Instead, we define ${\Gamma((X_1 \cup X_2)|E)}$ to be the set of all ${x \in \Gamma(X|E)}$ such that one can cover ${E}$ by measurable subevents ${E_1,E_2}$ such that ${x_i|E_i \in \Gamma(X_i|E_i)}$ for ${i=1,2}$ ; then ${(X_1 \cup X_2)|\Omega}$ may be verified to be a stochastic subset of ${X|\Omega}$ . Thus for instance ${\{0,1\}|\Omega}$ is the stochastic union of ${\{0\}|\Omega}$ and ${\{1\}|\Omega}$ . Similarly for countable unions ${(\bigcup_{n=1}^\infty X_n)|\Omega}$ of stochastic subsets ${X_n|\Omega}$ of ${X|\Omega}$ , although for uncountable unions are extremely problematic (they are disliked by both the measure theory and the countable gluing axiom) and will not be defined here. Finally, the stochastic difference set ${\Gamma((X_1 \backslash X_2)|E)}$ is defined as the set of all ${x|E}$ in ${\Gamma(X_1|E)}$ such that ${x|F \not \in \Gamma(X_2|F)}$ for any subevent ${F}$ of ${E}$ of positive probability. One may verify that in the case when ${\Omega}$ is discrete and at most countable, these Boolean operations correspond to the classical Boolean operations applied separately to each fibre ${X_{i,\omega}}$ of the relevant sets ${X_i}$ . We also leave as an exercise to the reader to verify the usual laws of Boolean arithmetic, e.g. the de Morgan laws, provided that one works with at most countable unions and intersections.

One can also consider a stochastic finite union ${(\bigcup_{n=1}^N X_n)|\Omega}$ in which the number ${N}$ of sets in the union is itself stochastic. More precisely, let ${X|\Omega}$ be a stochastic set, let ${N \in {\bf N}|\Omega}$ be a stochastic natural number, and let ${n \mapsto X_n|\Omega}$ be a stochastic function from the stochastic set ${\{ n \in {\bf N}: n \leq N\}|\Omega}$ (defined by setting ${\Gamma(\{n \in {\bf N}: n\leq N\}|E) := \{ n \in {\bf N}|E: n \leq N|E\}}$ )) to the stochastic power set ${2^X|\Omega}$ . Here we are considering ${0}$ to be a natural number, to allow for unions that are possibly empty, with ${{\bf N}_+ := {\bf N} \backslash \{0\}}$ used for the positive natural numbers. We also write ${(X_n)_{n=1}^N|\Omega}$ for the stochastic function ${n \mapsto X_n|\Omega}$ . Then we can define the stochastic union ${\bigcup_{n=1}^N X_n|\Omega}$ by setting ${\Gamma(\bigcup_{n=1}^N X_n|E)}$ for an event ${E}$ to be the set of local elements ${x \in \Gamma(X|E)}$ with the property that there exists a covering of ${E}$ by measurable subevents ${E_{n_0}}$ for ${n_0 \in {\bf N}_+}$ , such that one has ${n_0 \leq N|E_{n_0}}$ and ${x|E_{n_0} \in \Gamma(X_{n_0}|E_{n_0})}$ . One can verify that ${\bigcup_{n=1}^N X_n|\Omega}$ is a stochastic set (with the obvious restriction maps). Again, in the model case when ${\Omega}$ is discrete and at most countable, the fibre ${(\bigcup_{n=1}^N X_n)_\omega}$ is what one would expect it to be, namely ${\bigcup_{n=1}^{N(\omega)} (X_n)_\omega}$ .

The Cartesian product ${(X \times Y)|\Omega}$ of two stochastic sets may be defined by setting ${\Gamma((X \times Y)|E) := \Gamma(X|E) \times \Gamma(Y|E)}$ for all events ${E}$ , with the obvious restriction maps; this is easily seen to be another stochastic set. This lets one define the concept of a ${k}$ -ary operation ${f: (X_1 \times \dots \times X_k)|\Omega \rightarrow Y|\Omega}$ from ${k}$ stochastic sets ${X_1,\dots,X_k}$ to another stochastic set ${Y}$ , or a ${k}$ -ary relation ${R: (X_1 \times \dots \times X_k)|\Omega \rightarrow \{\hbox{true}, \hbox{false}\}|\Omega}$ . In particular, given ${x_i \in X_i|\Omega}$ for ${i=1,\dots,k}$ , the relation ${R(x_1,\dots,x_k)}$ may be deterministically true, deterministically false, or have some other stochastic truth value.

Remark 3 In the degenerate case when ${\Omega}$ is null, stochastic logic becomes a bit weird: all stochastic statements are deterministically true, as are their stochastic negations, since every event in ${\Omega}$ (even the empty set) now holds with full probability. Among other pathologies, the empty set now has a global element over ${\Omega}$ (this is analogous to the notorious convention ${0^0=1}$ ), and any two deterministic objects ${x,y}$ become equal over ${\Omega}$ : ${x|\Omega=y|\Omega}$ .

The following simple observation is crucial to subsequent discussion. If ${(x_n)_{n \in {\bf N}_+}}$ is a sequence taking values in the global elements ${\Gamma(X|\Omega)}$ of a stochastic space ${X|\Omega}$ , then we may also define global elements ${x_n \in \Gamma(X|\Omega)}$ for stochastic indices ${n \in {\bf N}_+|\Omega}$ as well, by appealing to the countable gluing axiom to glue together ${x_{n_0}}$ restricted to the set ${\{ \omega \in \Omega: n(\omega) = n_0\}}$ for each deterministic natural number ${n_0}$ to form ${x_n}$ . With this definition, the map ${n \mapsto x_n}$ is a stochastic function from ${{\bf N}_+|\Omega}$ to ${X|\Omega}$ ; indeed, this creates a one-to-one correspondence between external sequences (maps ${n \mapsto x_n}$ from ${{\bf N}_+}$ to ${\Gamma(X|\Omega)}$ ) and stochastic sequences (stochastic functions ${n \mapsto x_n}$ from ${{\bf N}_+|\Omega}$ to ${X|\Omega}$ ). Similarly with ${{\bf N}_+}$ replaced by any other at most countable set. This observation will be important in allowing many deterministic arguments involving sequences will be able to be carried over to the stochastic setting.

We now specialise from the extremely broad discipline of set theory to the more focused discipline of real analysis. There are two fundamental axioms that underlie real analysis (and in particular distinguishes it from real algebra). The first is the Archimedean property, which we phrase in the “no infinitesimal” formulation as follows:

Proposition 2 (Archimedean property) Let ${x \in {\bf R}}$ be such that ${x \leq 1/n}$ for all positive natural numbers ${n}$ . Then ${x \leq 0}$ .

The other is the least upper bound axiom:

Proposition 3 (Least upper bound axiom) Let ${S}$ be a non-empty subset of ${{\bf R}}$ which has an upper bound ${M \in {\bf R}}$ , thus ${x \leq M}$ for all ${x \in S}$ . Then there exists a unique real number ${\sup S \in {\bf R}}$ with the following properties:

${x \leq \sup S}$ for all ${x \in S}$ .

For any real ${L < \sup S}$ , there exists ${x \in S}$ such that ${L < x \leq \sup S}$ .

${\sup S \leq M}$ .

Furthermore, ${\sup S}$ does not depend on the choice of ${M}$ .

The Archimedean property extends easily to the stochastic setting:

Proposition 4 (Stochastic Archimedean property) Let ${x \in \Gamma({\bf R}|\Omega)}$ be such that ${x \leq 1/n}$ for all deterministic natural numbers ${n}$ . Then ${x \leq 0}$ .

Remark 4 Here, incidentally, is one place in which this stochastic formalism deviates from the nonstandard analysis formalism, as the latter certainly permits the existence of infinitesimal elements. On the other hand, we caution that stochastic real numbers are permitted to be unbounded, so that formulation of Archimedean property is not valid in the stochastic setting.

The proof is easy and is left to the reader. The least upper bound axiom also extends nicely to the stochastic setting, but the proof requires more work (in particular, our argument uses the monotone convergence theorem):

Theorem 5 (Stochastic least upper bound axiom) Let ${S|\Omega}$ be a stochastic subset of ${{\bf R}|\Omega}$ which has a global upper bound ${M \in {\bf R}|\Omega}$ , thus ${x \leq M}$ for all ${x \in \Gamma(S|\Omega)}$ , and is globally non-empty in the sense that there is at least one global element ${x \in \Gamma(S|\Omega)}$ . Then there exists a unique stochastic real number ${\sup S \in \Gamma({\bf R}|\Omega)}$ with the following properties:

${x \leq \sup S}$ for all ${x \in \Gamma(S|\Omega)}$ .

For any stochastic real ${L < \sup S}$ , there exists ${x \in \Gamma(S|\Omega)}$ such that ${L < x \leq \sup S}$ .

${\sup S \leq M}$ .

Furthermore, ${\sup S}$ does not depend on the choice of ${M}$ .

For future reference, we note that the same result holds with ${{\bf R}}$ replaced by ${{\bf N} \cup \{+\infty\}}$ throughout, since the latter may be embedded in the former, for instance by mapping ${n}$ to ${1 - \frac{1}{n+1}}$ and ${+\infty}$ to ${1}$ . In applications, the above theorem serves as a reasonable substitute for the countable axiom of choice, which does not appear to hold in unrestricted generality relative to a measure space; in particular, it can be used to generate various extremising sequences for stochastic functionals on various stochastic function spaces.

Proof: Uniqueness is clear (using the Archimedean property), as well as the independence on ${M}$ , so we turn to existence. By using an order-preserving map from ${{\bf R}}$ to ${(-1,1)}$ (e.g. ${x \mapsto \frac{2}{\pi} \hbox{arctan}(x)}$ ) we may assume that ${S|\Omega}$ is a subset of ${(-1,1)|\Omega}$ , and that ${M < 1}$ .

We observe that ${\Gamma(S|\Omega)}$ is a lattice: if ${x, y \in \Gamma(S|\Omega)}$ , then ${\max(x,y)}$ and ${\min(x,y)}$ also lie in ${\Gamma(S|\Omega)}$ . Indeed, ${\max(x,y)}$ may be formed by appealing to the countable gluing axiom to glue ${y}$ (restricted the set ${\{ \omega \in \Omega: x(\omega) < y(\omega) \}}$ ) with ${x}$ (restricted to the set ${\{ \omega \in \Omega: x(\omega) \geq y(\omega) \}}$ ), and similarly for ${\min(x,y)}$ . (Here we use the fact that relations such as ${<}$ are Borel measurable on ${{\bf R}}$ .)

Let ${A \in {\bf R}}$ denote the deterministic quantity

$\displaystyle A := \sup \{ \int_\Omega x(\omega)\ d\mu(\omega): x \in \Gamma(S|\Omega) \}$

then (by Proposition 3!) ${A}$ is well-defined; here we use the hypothesis that ${\mu(\Omega)}$ is finite. Thus we may find a sequence ${(x_n)_{n \in {\bf N}}}$ of elements ${x_n}$ of ${\Gamma(S|\Omega)}$ such that

$\displaystyle \int_\Omega x_n(\omega)\ d\mu(\omega) \rightarrow A \hbox{ as } n \rightarrow \infty. \ \ \ \ \ (1)$

Using the lattice property, we may assume that the ${x_n}$ are non-decreasing: ${x_n \leq x_m}$ whenever ${n \leq m}$ . If we then define ${\sup S(\omega) := \sup_n x_n(\omega)}$ (after choosing measurable representatives of each equivalence class ${x_n}$ ), then ${\sup S}$ is a stochastic real with ${\sup S \leq M}$ .

If ${x \in \Gamma(S|\Omega)}$ , then ${\max(x,x_n) \in \Gamma(S|\Omega)}$ , and so

$\displaystyle \int_\Omega \max(x,x_n)\ d\mu(\omega) \leq A.$

From this and (1) we conclude that

$\displaystyle \int_\Omega \max(x-x_n,0) \rightarrow 0 \hbox{ as } n \rightarrow \infty.$

From monotone convergence, we conclude that

$\displaystyle \int_\Omega \max(x-\sup S,0) = 0$

and so ${x \leq \sup S}$ , as required.

Now let ${L < \sup S}$ be a stochastic real. After choosing measurable representatives of each relevant equivalence class, we see that for almost every ${\omega \in \Omega}$ , we can find a natural number ${n(\omega)}$ with ${x_{n(\omega)} > L}$ . If we choose ${n(\omega)}$ to be the first such positive natural number when it exists, and (say) ${1}$ otherwise, then ${n}$ is a stochastic positive natural number and ${L < x_n}$ . The claim follows. $\Box$

Remark 5 One can abstract away the role of the measure ${\mu}$ here, leaving only the ideal of null sets. The property that the measure is finite is then replaced by the more general property that given any non-empty family of measurable sets, there is an at most countable union of sets in that family that is an upper bound modulo null sets for all elements in that faily.

Using Proposition 4 and Theorem 5, one can then revisit many of the other foundational results of deterministic real analysis, and develop stochastic analogues; we give some examples of this below the fold (focusing on the Heine-Borel theorem and a case of the spectral theorem). As an application of this formalism, we revisit some of the Furstenberg-Zimmer structural theory of measure-preserving systems, particularly that of relatively compact and relatively weakly mixing systems, and interpret them in this framework, basically as stochastic versions of compact and weakly mixing systems (though with the caveat that the shift map is allowed to act non-trivially on the underlying probability space). As this formalism is “point-free”, in that it avoids explicit use of fibres and disintegrations, it will be well suited for generalising this structure theory to settings in which the underlying probability spaces are not standard Borel, and the underlying groups are uncountable; I hope to discuss such generalisations in future blog posts.

Remark 6 Roughly speaking, stochastic real analysis can be viewed as a restricted subset of classical real analysis in which all operations have to be “measurable” with respect to the base space. In particular, indiscriminate application of the axiom of choice is not permitted, and one should largely restrict oneself to performing countable unions and intersections rather than arbitrary unions or intersections. Presumably one can formalise this intuition with a suitable “countable transfer principle”, but I was not able to formulate a clean and general principle of this sort, instead verifying various assertions about stochastic objects by hand rather than by direct transfer from the deterministic setting. However, it would be desirable to have such a principle, since otherwise one is faced with the tedious task of redoing all the foundations of real analysis (or whatever other base theory of mathematics one is going to be working in) in the stochastic setting by carefully repeating all the arguments.

More generally, topos theory is a good formalism for capturing precisely the informal idea of performing mathematics with certain operations, such as the axiom of choice, the law of the excluded middle, or arbitrary unions and intersections, being somehow “prohibited” or otherwise “restricted”.

Read the rest of this entry »

Real stable polynomials and the Kadison-Singer problem

4 November, 2013 in expository, math.OA, math.SP | Tags: Adam Marcus, Dan Spielman, Daniel Spielman, Kadison-Singer problem, Nikhil Srivastava, paving, real stable polynomials | by Terence Tao | 41 comments

One of the basic tools in modern combinatorics is the probabilistic method, introduced by Erdos, in which a deterministic solution to a given problem is shown to exist by constructing a random candidate for a solution, and showing that this candidate solves all the requirements of the problem with positive probability. When the problem requires a real-valued statistic ${X}$ to be suitably large or suitably small, the following trivial observation is often employed:

Proposition 1 (Comparison with mean) Let ${X}$ be a random real-valued variable, whose mean (or first moment) ${\mathop{\bf E} X}$ is finite. Then

$\displaystyle X \leq \mathop{\bf E} X$

with positive probability, and

$\displaystyle X \geq \mathop{\bf E} X$

with positive probability.

This proposition is usually applied in conjunction with a computation of the first moment ${\mathop{\bf E} X}$ , in which case this version of the probabilistic method becomes an instance of the first moment method. (For comparison with other moment methods, such as the second moment method, exponential moment method, and zeroth moment method, see Chapter 1 of my book with Van Vu. For a general discussion of the probabilistic method, see the book by Alon and Spencer of the same name.)

As a typical example in random matrix theory, if one wanted to understand how small or how large the operator norm ${\|A\|_{op}}$ of a random matrix ${A}$ could be, one might first try to compute the expected operator norm ${\mathop{\bf E} \|A\|_{op}}$ and then apply Proposition 1; see this previous blog post for examples of this strategy (and related strategies, based on comparing ${\|A\|_{op}}$ with more tractable expressions such as the moments ${\hbox{tr} A^k}$ ). (In this blog post, all matrices are complex-valued.)

Recently, in their proof of the Kadison-Singer conjecture (and also in their earlier paper on Ramanujan graphs), Marcus, Spielman, and Srivastava introduced an striking new variant of the first moment method, suited in particular for controlling the operator norm ${\|A\|_{op}}$ of a Hermitian positive semi-definite matrix ${A}$ . Such matrices have non-negative real eigenvalues, and so ${\|A\|_{op}}$ in this case is just the largest eigenvalue ${\lambda_1(A)}$ of ${A}$ . Traditionally, one tries to control the eigenvalues through averaged statistics such as moments ${\hbox{tr} A^k = \sum_i \lambda_i(A)^k}$ or Stieltjes transforms ${\hbox{tr} (A-z)^{-1} = \sum_i (\lambda_i(A)-z)^{-1}}$ ; again, see this previous blog post. Here we use ${z}$ as short-hand for ${zI_d}$ , where ${I_d}$ is the ${d \times d}$ identity matrix. Marcus, Spielman, and Srivastava instead rely on the interpretation of the eigenvalues ${\lambda_i(A)}$ of ${A}$ as the roots of the characteristic polynomial ${p_A(z) := \hbox{det}(z-A)}$ of ${A}$ , thus

$\displaystyle \|A\|_{op} = \hbox{maxroot}( p_A ) \ \ \ \ \ (1)$

where ${\hbox{maxroot}(p)}$ is the largest real root of a non-zero polynomial ${p}$ . (In our applications, we will only ever apply ${\hbox{maxroot}}$ to polynomials that have at least one real root, but for sake of completeness let us set ${\hbox{maxroot}(p)=-\infty}$ if ${p}$ has no real roots.)

Prior to the work of Marcus, Spielman, and Srivastava, I think it is safe to say that the conventional wisdom in random matrix theory was that the representation (1) of the operator norm ${\|A\|_{op}}$ was not particularly useful, due to the highly non-linear nature of both the characteristic polynomial map ${A \mapsto p_A}$ and the maximum root map ${p \mapsto \hbox{maxroot}(p)}$ . (Although, as pointed out to me by Adam Marcus, some related ideas have occurred in graph theory rather than random matrix theory, for instance in the theory of the matching polynomial of a graph.) For instance, a fact as basic as the triangle inequality ${\|A+B\|_{op} \leq \|A\|_{op} + \|B\|_{op}}$ is extremely difficult to establish through (1). Nevertheless, it turns out that for certain special types of random matrices ${A}$ (particularly those in which a typical instance ${A}$ of this ensemble has a simple relationship to “adjacent” matrices in this ensemble), the polynomials ${p_A}$ enjoy an extremely rich structure (in particular, they lie in families of real stable polynomials, and hence enjoy good combinatorial interlacing properties) that can be surprisingly useful. In particular, Marcus, Spielman, and Srivastava established the following nonlinear variant of Proposition 1:

Proposition 2 (Comparison with mean) Let ${m,d \geq 1}$ . Let ${A}$ be a random matrix, which is the sum ${A = \sum_{i=1}^m A_i}$ of independent Hermitian rank one ${d \times d}$ matrices ${A_i}$ , each taking a finite number of values. Then

$\displaystyle \hbox{maxroot}(p_A) \leq \hbox{maxroot}( \mathop{\bf E} p_A )$

with positive probability, and

$\displaystyle \hbox{maxroot}(p_A) \geq \hbox{maxroot}( \mathop{\bf E} p_A )$

with positive probability.

We prove this proposition below the fold. The hypothesis that each ${A_i}$ only takes finitely many values is technical and can likely be relaxed substantially, but we will not need to do so here. Despite the superficial similarity with Proposition 1, the proof of Proposition 2 is quite nonlinear; in particular, one needs the interlacing properties of real stable polynomials to proceed. Another key ingredient in the proof is the observation that while the determinant ${\hbox{det}(A)}$ of a matrix ${A}$ generally behaves in a nonlinear fashion on the underlying matrix ${A}$ , it becomes (affine-)linear when one considers rank one perturbations, and so ${p_A}$ depends in an affine-multilinear fashion on the ${A_1,\ldots,A_m}$ . More precisely, we have the following deterministic formula, also proven below the fold:

Proposition 3 (Deterministic multilinearisation formula) Let ${A}$ be the sum of deterministic rank one ${d \times d}$ matrices ${A_1,\ldots,A_m}$ . Then we have

$\displaystyle p_A(z) = \mu[A_1,\ldots,A_m](z) \ \ \ \ \ (2)$

for all ${z \in C}$ , where the mixed characteristic polynomial ${\mu[A_1,\ldots,A_m](z)}$ of any ${d \times d}$ matrices ${A_1,\ldots,A_m}$ (not necessarily rank one) is given by the formula

$\displaystyle \mu[A_1,\ldots,A_m](z) \ \ \ \ \ (3)$

$\displaystyle = (\prod_{i=1}^m (1 - \frac{\partial}{\partial z_i})) \hbox{det}( z + \sum_{i=1}^m z_i A_i ) |_{z_1=\ldots=z_m=0}.$

Among other things, this formula gives a useful representation of the mean characteristic polynomial ${\mathop{\bf E} p_A}$ :

Corollary 4 (Random multilinearisation formula) Let ${A}$ be the sum of jointly independent rank one ${d \times d}$ matrices ${A_1,\ldots,A_m}$ . Then we have

$\displaystyle \mathop{\bf E} p_A(z) = \mu[ \mathop{\bf E} A_1, \ldots, \mathop{\bf E} A_m ](z) \ \ \ \ \ (4)$

for all ${z \in {\bf C}}$ .

Proof: For fixed ${z}$ , the expression ${\hbox{det}( z + \sum_{i=1}^m z_i A_i )}$ is a polynomial combination of the ${z_i A_i}$ , while the differential operator ${(\prod_{i=1}^m (1 - \frac{\partial}{\partial z_i}))}$ is a linear combination of differential operators ${\frac{\partial^j}{\partial z_{i_1} \ldots \partial z_{i_j}}}$ for ${1 \leq i_1 < \ldots < i_j \leq d}$ . As a consequence, we may expand (3) as a linear combination of terms, each of which is a multilinear combination of ${A_{i_1},\ldots,A_{i_j}}$ for some ${1 \leq i_1 < \ldots < i_j \leq d}$ . Taking expectations of both sides of (2) and using the joint independence of the ${A_i}$ , we obtain the claim. $\Box$

In view of Proposition 2, we can now hope to control the operator norm ${\|A\|_{op}}$ of certain special types of random matrices ${A}$ (and specifically, the sum of independent Hermitian positive semi-definite rank one matrices) by first controlling the mean ${\mathop{\bf E} p_A}$ of the random characteristic polynomial ${p_A}$ . Pursuing this philosophy, Marcus, Spielman, and Srivastava establish the following result, which they then use to prove the Kadison-Singer conjecture:

Theorem 5 (Marcus-Spielman-Srivastava theorem) Let ${m,d \geq 1}$ . Let ${v_1,\ldots,v_m \in {\bf C}^d}$ be jointly independent random vectors in ${{\bf C}^d}$ , with each ${v_i}$ taking a finite number of values. Suppose that we have the normalisation

$\displaystyle \mathop{\bf E} \sum_{i=1}^m v_i v_i^* = 1$

where we are using the convention that ${1}$ is the ${d \times d}$ identity matrix ${I_d}$ whenever necessary. Suppose also that we have the smallness condition

$\displaystyle \mathop{\bf E} \|v_i\|^2 \leq \varepsilon$

for some ${\varepsilon>0}$ and all ${i=1,\ldots,m}$ . Then one has

$\displaystyle \| \sum_{i=1}^m v_i v_i^* \|_{op} \leq (1+\sqrt{\varepsilon})^2 \ \ \ \ \ (5)$

with positive probability.

Note that the upper bound in (5) must be at least ${1}$ (by taking ${v_i}$ to be deterministic) and also must be at least ${\varepsilon}$ (by taking the ${v_i}$ to always have magnitude at least ${\sqrt{\varepsilon}}$ ). Thus the bound in (5) is asymptotically tight both in the regime ${\varepsilon\rightarrow 0}$ and in the regime ${\varepsilon \rightarrow \infty}$ ; the latter regime will be particularly useful for applications to Kadison-Singer. It should also be noted that if one uses more traditional random matrix theory methods (based on tools such as Proposition 1, as well as more sophisticated variants of these tools, such as the concentration of measure results of Rudelson and Ahlswede-Winter), one obtains a bound of ${\| \sum_{i=1}^m v_i v_i^* \|_{op} \ll_\varepsilon \log d}$ with high probability, which is insufficient for the application to the Kadison-Singer problem; see this article of Tropp. Thus, Theorem 5 obtains a sharper bound, at the cost of trading in “high probability” for “positive probability”.

In the paper of Marcus, Spielman and Srivastava, Theorem 5 is used to deduce a conjecture ${KS_2}$ of Weaver, which was already known to imply the Kadison-Singer conjecture; actually, a slight modification of their argument gives the paving conjecture of Kadison and Singer, from which the original Kadison-Singer conjecture may be readily deduced. We give these implications below the fold. (See also this survey article for some background on the Kadison-Singer problem.)

Let us now summarise how Theorem 5 is proven. In the spirit of semi-definite programming, we rephrase the above theorem in terms of the rank one Hermitian positive semi-definite matrices ${A_i := v_iv_i^*}$ :

Theorem 6 (Marcus-Spielman-Srivastava theorem again) Let ${A_1,\ldots,A_m}$ be jointly independent random rank one Hermitian positive semi-definite ${d \times d}$ matrices such that the sum ${A :=\sum_{i=1}^m A_i}$ has mean

$\displaystyle \mathop{\bf E} A = I_d$

and such that

$\displaystyle \mathop{\bf E} \hbox{tr} A_i \leq \varepsilon$

for some ${\varepsilon>0}$ and all ${i=1,\ldots,m}$ . Then one has

$\displaystyle \| A \|_{op} \leq (1+\sqrt{\varepsilon})^2$

with positive probability.

In view of (1) and Proposition 2, this theorem follows from the following control on the mean characteristic polynomial:

Theorem 7 (Control of mean characteristic polynomial) Let ${A_1,\ldots,A_m}$ be jointly independent random rank one Hermitian positive semi-definite ${d \times d}$ matrices such that the sum ${A :=\sum_{i=1}^m A_i}$ has mean

$\displaystyle \mathop{\bf E} A = 1$

and such that

$\displaystyle \mathop{\bf E} \hbox{tr} A_i \leq \varepsilon$

for some ${\varepsilon>0}$ and all ${i=1,\ldots,m}$ . Then one has

$\displaystyle \hbox{maxroot}(\mathop{\bf E} p_A) \leq (1 +\sqrt{\varepsilon})^2.$

This result is proven using the multilinearisation formula (Corollary 4) and some convexity properties of real stable polynomials; we give the proof below the fold.

Thanks to Adam Marcus, Assaf Naor and Sorin Popa for many useful explanations on various aspects of the Kadison-Singer problem.

Read the rest of this entry »

	Anonymous on A digestion of the Jacobian co…
	Anonymous on A digestion of the Jacobian co…
	info 19tet on A digestion of the Jacobian co…
	Anonymous on 245B, Notes 12: Continuous fun…
	Anonymous on A digestion of the Jacobian co…
	Christopher on A digestion of the Jacobian co…
	Anonymous on A digestion of the Jacobian co…
	Michael M. Ross on Gilbreath’s conjecture:…
	Wen Huang on Gilbreath’s conjecture:…
	Some thoughts about… on A digestion of the Jacobian co…
	Anonymous on A digestion of the Jacobian co…
	Terence Tao on A digestion of the Jacobian co…
	Terence Tao on 275A, Notes 2: Product measure…
	Terence Tao on A digestion of the Jacobian co…
	Christopher on A digestion of the Jacobian co…

Category Archive

The effective potential of an M-matrix

Inverting the Schur complement, and large-dimensional Gelfand-Tsetlin patterns

On the sign patterns of entrywise positivity preservers in fixed dimension

A wave equation approach to automorphic forms in analytic number theory

The standard branch of the matrix logarithm

Random matrices: tail bounds for gaps between eigenvalues

Random matrices have simple spectrum

A Banach algebra proof of the prime number theorem

Real analysis relative to a finite measure space

Real stable polynomials and the Kadison-Singer problem

Recent Comments

Top Posts

Archives

Categories

The Polymath Blog

For commenters