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 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 ? (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 matrix. How likely it is that this is the full ?
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.
- To be surjective you need to be surjective modulo p for every prime number p.
- Take some p. The probability to be surjective modulo p when the entries are uniformly random (independently) numbers modulo p is .
- This probability continues to work if you consider 0-1 entries.
- You can assume that all these probabilities for different primes are statistically independent.
- 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-Oﬀord 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.
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.