Hoi Nguyen and Melanie Wood: Remarkable Formulas for the Probability that Projections of Lattices are Surjective

Following a lecture by Hoi Nguyen at Oberwolfach, I would like to tell you a little about the paper: Random integral matrices: universality of surjectivity and the cokernel by Hoi Nguyen and Melanie Wood.

Two background questions:

Hoi started with two background questions –

Background Question 1: Consider an n \times n 0-1 matrix where the entries are taken at random. What is the probability that the matrix is singular (over the rationals)?

Hoi mentioned the recent result of Konstantin Tikhomirov, and moved to talk about matrices over the integers.

Background Question 2: Now, think about the lattice spanned by the rows of the matrix. How likely it is that this is the full \mathbb Z^n? (In other words that the determinant is +1 or -1.)

Probably, I thought, the answer is less than exponentially small.

The main question

Hoi moved quickly to the main question

Main question: Now think about the rows of a random 0-1 (n+1) \times n matrix. How likely it is that this is the full \mathbb Z^n?

Hmm, I was not sure how quickly the answer should tend to zero. But I learnt quickly that the answer does not tend to zero at all!

A remarkable heuristic formula: the probability for a random integral matrix from (n+1)-dimensions to n-dimenssions to be surjective is

one over  (ζ(2)ζ(3)ζ(4)ζ(5)…) 

What would justify this formula? Hoi described the following heuristic argument.

  1. To be surjective you need to be surjective modulo p for every prime number p.
  2.  Take some p. The probability to be surjective modulo p when the entries are uniformly random (independently) numbers modulo p is \prod_{j=2}^{n+1}(1-p^{-j}).
  3. This probability continues to work if you consider 0-1 entries.
  4. You can assume that all these probabilities for different primes are statistically independent.
  5. When you multiply all these probabilities you get


When Hoi reached this formula in his Oberfolfach lecture my immediate thought was this: This is a remarkable formula; maybe it is even true although it looks very hard to justify the two crucial steps  in the heuristics. Why you can assume that 0-1 matrices behave like random matrices with uniform entries and why we have statistical independence that allows us to multiply probabilities just like in high school probability class? And maybe it is not true.

(This heuristics is known as the Cohen Lenstra heuristics and it was made for understanding the structure of class groups of quadratic fields.)

And then came the next slide of the presentation.


Hoi Nguyen and Melanie Wood actually proved this formula!

This is  a special case of a considerably more general formula. Look at the paper for more details and for the proofs.

It looks to me that the proof is tour de force and it uses various difficult and delicious techniques and earlier results. Various new and old Littlewood-Offord type results which are independently interesting are used.

And here is a related paper by Hoi and Melanie: Cokernels of adjacency matrices of random r-regular graphs.


Little more

As mentioned in the Nguyen-Wood paper, Shaked Koplewitz   roposed and proved some cases the Cohen-Lenstra heuristic for integral n by n+k matrices. (See Skaed’s comment below.)

As for background problem 2, the paper mentioned that the fact that the probability tends to 0 follows from Corollary 3.4 from a paper by Melanie Wood: Random integral matrices and the Cohen Lenstra Heuristics.  (Maybe there are different avenues for showing that there is a vanishing probability for every specific value of the determinant as well.) I don’t know if it is known that the probability that the determinant is 1 is exponentially small. (You can guess it is like square root of n! or something like that.) Also I don’t know if the ratio between the probabilities that the determinant is 3 and that it is 7 respects the Cohen Lenstra heuristics. Do we expect it at all? You can regard the determinant as a strange random walk so what is the reason that stopping at 3 will be different than stopping at 7?  It is also not known and this is raised as a question in the paper if the probability that the determinant is a perfect square respects the Cohen-Lenstra heuristics (and this seems reasonable).

There are similar nice questions for simplicial complexes. See the paper Cohen–Lenstra heuristics for torsion in homology of random complexes, by Matthew Kahle, Frank Lutz, Andrew Newman, and Kyle Parsons.

So if you consider the torsion of the 7 dimensional homology of a random 14 dimensional manifolds. Then (unless there are theorems to the contrary) it is natural to guess that the torsion will obey a Cohen-Lenstra heuristic of some kind.  This also applies to rationally acyclic complexes (hypertrees) and various other gadgets.


This entry was posted in Algebra, Combinatorics, Number theory, Probability and tagged , . Bookmark the permalink.

6 Responses to Hoi Nguyen and Melanie Wood: Remarkable Formulas for the Probability that Projections of Lattices are Surjective

  1. Gil Kalai says:

    Here is a great FB comment by Avinoam Mann: Since Gil mentioned the Cohen-Lenstra heuristics, let me tell you about a lovely formula of the great Philip Hall, of which I was first told by the great John Thompson, and which Cohen-Lenstra employed, actually gave another proof of it. I have to admit being partial to that result, having myself published an alternative proof (as did several other people), and also proved generalizations and analogous results.
    Let us fix a prime q, let A(q) be the set of all finite abelian q-groups (groups whose order is a power of q, taken up to isomorphim), and consider the infinite series \sum 1/|G|, where |G| is the order of G, and the sum is over all groups in A(q). The structure theorem of finite abelian groups implies that the sum is the same as \sum p(n)/q^n, where the sum is over all non-negative integers n, and p(n) is the partition function, i.e. the number of possibilities of writing n as the sum of positive integers. Known estimates for p(n) imply easily that the series converges (by the way, the sum is irrational).
    Now, for the same set of groups, consider the series \sum 1/|Aut(G)|, where Aut(G) is the automorphism group of G. This also converges, because, first, if we consider only cyclic groups, the series is a geometric one, and converges. Scond, looking at the non-cyclic ones, it is easy to see that |Aut(G)| \ge |G|, therefore the convergence of the series follows from the convergence of the previous one.
    Hall’s formula, which he describes as ‘rather curious’, is that the two series have the same sum

    \sum 1/G| = \sum 1/|Aut(G)|,

    both sums ranging over all groups in A(q).

  2. Gil Kalai says:

    A comment of Ian Agol on Twitter:
    This looks very close to the covolume of SL_n(Z). https://arxiv.org/abs/math/0402085

  3. shakeddown says:

    I originally raised this conjecture here, which has a survey on some of the limits and results. (Wood and Nguyen later proved the general case using more precise bounds, but this is a good descriptor of the methods involved) https://arxiv.org/pdf/1611.06441.pdf

    In particular, the conjecture (and later proof by Wood and Nguyen) also generalizes to the N*(N+m) case for any constant m.

  4. Can the fact that the heuristics works here help shed some light on Hardy-littlewood k-tuples conjecture?

  5. Will Sawin says:

    There are two different products of zeta in this post, which can’t both be right. In fact the first one (in red), is, and the second (in black) isn’t. The point is that each value of zeta is itself a product over all the primes.

    I think it is most reasonable to expect that the number of n x n 0-1 matrices with determinant 3 divided by the number of 0-1 matrices with determinant 7 follows a Cohen-Lenstra-like formula (which I guess means it would be (1/(3-1) )/ (1/(7-1)) = 3), but I don’t see any reason to expect this with great confidence. Certainly one shouldn’t expect that this ratio goes to 1 – I think one knows from the local p-adic versions of these results that the probability that the determinant is 0 mod 3, say, is not 1/3, and that should affect the probability that the determinant is 3. (Much as in a random walk where our step lengths are almost always multiples of 3, for a long time we will not have equal probabilities of hitting 3 and 7.)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s