Topics in random matrix theory

I’ve just finished writing the first draft of my second book coming out of the 2010 blog posts, namely “Topics in random matrix theory“, which was based primarily on my graduate course in the topic, though it also contains material from some additional posts related to random matrices on the blog.  It is available online here.  As usual, comments and corrections are welcome.  There is also a stub page for the book, which at present does not contain much more than the above link.

The Szemeredi-Trotter theorem via the polynomial ham sandwich theorem

The ham sandwich theorem asserts that, given bounded open sets in , there exists a hyperplane that bisects each of these sets , in the sense that each of the two half-spaces on either side of the hyperplane captures exactly half of the volume of . The shortest proof of this result proceeds by invoking the Borsuk-Ulam theorem.

A useful generalisation of the ham sandwich theorem is the polynomial ham sandwich theorem, which asserts that given bounded open sets in , there exists a hypersurface of degree (thus is a polynomial of degree such that the two semi-algebraic sets and capture half the volume of each of the . (More precisely, the degree will be at most , where is the first positive integer for which exceeds .) This theorem can be deduced from the Borsuk-Ulam theorem in the same manner that the ordinary ham sandwich theorem is (and can also be deduced directly from the ordinary ham sandwich theorem via the Veronese embedding).

The polynomial ham sandwich theorem is a theorem about continuous bodies (bounded open sets), but a simple limiting argument leads one to the following discrete analogue: given finite sets in , there exists a hypersurface of degree , such that each of the two semi-algebraic sets and contain at most half of the points on (note that some of the points of can certainly lie on the boundary ). This can be iterated to give a useful cell decomposition:

Proposition 1 (Cell decomposition) Let be a finite set of points in , and let be a positive integer. Then there exists a polynomial of degree at most , and a decomposition

into the hypersurface and a collection of cells bounded by , such that , and such that each cell contains at most points.

A proof is sketched in this previous blog post. The cells in the argument are not necessarily connected (being instead formed by intersecting together a number of semi-algebraic sets such as and ), but it is a classical result (established independently by Oleinik-Petrovskii, Milnor, and Thom) that any degree hypersurface divides into connected components, so one can easily assume that the cells are connected if desired. (Incidentally, one does not need the full machinery of the results in the above cited papers – which control not just the number of components, but all the Betti numbers of the complement of – to get the bound on connected components; one can instead observe that every bounded connected component has a critical point where , and one can control the number of these points by Bezout’s theorem, after perturbing slightly to enforce genericity, and then count the unbounded components by an induction on dimension.)

Remark 1 By setting as large as , we obtain as a limiting case of the cell decomposition the fact that any finite set of points in can be captured by a hypersurface of degree . This fact is in fact true over arbitrary fields (not just over ), and can be proven by a simple linear algebra argument (see e.g. this previous blog post). However, the cell decomposition is more flexible than this algebraic fact due to the ability to arbitrarily select the degree parameter .

The cell decomposition can be viewed as a structural theorem for arbitrary large configurations of points in space, much as the Szemerédi regularity lemma can be viewed as a structural theorem for arbitrary large dense graphs. Indeed, just as many problems in the theory of large dense graphs can be profitably attacked by first applying the regularity lemma and then inspecting the outcome, it now seems that many problems in combinatorial incidence geometry can be attacked by applying the cell decomposition (or a similar such decomposition), with a parameter to be optimised later, to a relevant set of points, and seeing how the cells interact with each other and with the other objects in the configuration (lines, planes, circles, etc.). This strategy was spectacularly illustrated recently with Guth and Katz‘s use of the cell decomposition to resolve the Erdös distinct distance problem (up to logarithmic factors), as discussed in this blog post.

In this post, I wanted to record a simpler (but still illustrative) version of this method (that I learned from Nets Katz), namely to provide yet another proof of the Szemerédi-Trotter theorem in incidence geometry:

Theorem 2 (Szemerédi-Trotter theorem) Given a finite set of points and a finite set of lines in , the set of incidences has cardinality

This theorem has many short existing proofs, including one via crossing number inequalities (as discussed in this previous post) or via a slightly different type of cell decomposition (as discussed here). The proof given below is not that different, in particular, from the latter proof, but I believe it still serves as a good introduction to the polynomial method in combinatorial incidence geometry.

The Wigner-Dyson-Mehta bulk universality conjecture for Wigner matrices

Van Vu and I have just uploaded to the arXiv our paper “The Wigner-Dyson-Mehta bulk universality conjecture for Wigner matrices“, submitted to the Proceedings of the National Academy of Sciences. This short note concerns the convergence of the -point correlation functions of Wigner matrices in the bulk to the Dyson -point functions, a statement conjectured by Wigner, Dyson, and Mehta. Thanks to the results of Erdös, Peche, Ramirez, Schlein, Vu, Yau, and myself, this conjecture has now been established for all Wigner matrices (assuming a finite moment condition on the entries), but only if one uses a quite weak notion of convergence, namely averaged vague convergence in which one averages in the energy parameter . The main purpose of this note is to observe that by combining together existing results in the literature, one can improve the convergence to vague convergence (which is the natural notion of convergence in the discrete setting); and furthermore, if one assumes some regularity and decay conditions on the coefficient distribution, one can improve the convergence further to local convergence.

More precisely, let be an Wigner matrix – a random Hermitian matrix whose off-diagonal elements for are iid with mean zero and variance (and whose diagonal elements also obey similar hypotheses, which we omit here). For simplicity, we also assume that the real and imaginary parts of are also iid (as is the case for instance for the Gaussian Unitary Ensemble (GUE)). The eigenvalues of such a matrix are known to be asymptotically distributed accordingly to the Wigner semicircular distribution , where

In particular, this suggests that at any energy level in the bulk of the spectrum, the average eigenvalue spacing should be about . It is then natural to introduce the normalised -point correlation function

for any distinct reals and , where is the event that there is an eigenvalue in each of the intervals for each . (This definition is valid when the Wigner ensemble is continuous; for discrete ensembles, one can define instead in a distributional sense.)

The Wigner-Dyson-Mehta conjecture asserts that converges (in various senses) as to the Dyson -point function

where is the Dyson sine kernel. This conjecture was verified first for the GUE (with a quite strong notion of convergence, namely local uniform convergence) by Dyson, using an explicit formula for in the GUE case due to Gaudin and Mehta. Later results of Johansson, Erdos-Ramirez-Schlein-Yau, Erdos-Peche-Ramirez-Schlein-Yau, and Vu and myself, extended these results to increasingly wider ranges of Wigner matrices, but in the context of either weak convergence (which means that

for any , compactly supported function ), or the slightly weaker notion of vague convergence (which is the same as weak convergence, except that the function is also required to be continuous).

In a joint paper of Erdos, Ramirez, Schlein, Vu, Yau, and myself, we established the Wigner-Dyson-Mehta conjecture for all Wigner matrices (assuming only an exponential decay condition on the entries), but using a quite weak notion of convergence, namely averaged vague convergence, which allows for averaging in the energy parameter. Specifically, we showed that

Subsequently, Erdos, Schlein, and Yau introduced the powerful local relaxation flow method, which achieved a simpler proof of the same result which also generalised to other ensembles beyond the Wigner case. However, for technical reasons, this method was restricted to establishing averaged vague convergence only.

In the current paper, we show that by combining the argument of Erdos, Ramirez, Schlein, Vu, Yau, and myself with some more recent technical results, namely the relaxation of the exponential decay condition in the four moment theorem to a finite moment condition (established by Vu and myself) and a strong eigenvalue localisation bound of Erdos, Yau, and Yin, one can upgrade the averaged vague convergence to vague convergence, and handle all Wigner matrices that assume a finite moment condition. Vague convergence is the most natural notion of convergence for discrete random matrix ensembles; for such ensembles, the correlation function is a discrete measure, and so one does not expect convergence to a continuous limit in any stronger sense than the vague sense. Also, by carefully inspecting the earlier argument of Erdos, Peche, Ramirez, Schlein, and Yau, we were able to establish convergence in the stronger local sense once one assumed some regularity and positivity condition on the underlying coefficient distribution. These are somewhat modest and technical improvements over previous work on the Wigner-Dyson-Mehta conjecture, but they help to clarify and organise the profusion of results in this area, which are now reaching a fairly definitive form.

It may well be possible to go beyond local convergence in the case of smooth ensembles, for instance establishing local uniform convergence; this was recently accomplished in the case by Maltsev and Schlein. Indeed one may optimistically expect to even have convergence in the local smooth topology, which would basically be the strongest convergence one could hope for.