This post continues my series on favorite theorems of the twenty-first century. For an overview of the categories and my earlier selections, see this introductory post.
My choice for 2004 in probability theory is a theorem of Terence Tao and Van Vu giving a dramatically improved upper bound for the probability that a random matrix with entries in is singular. Their paper was received by the Journal of the American Mathematical Society in 2004 and published in 2007 (Tao and Vu 2007).
Recall that an matrix is invertible, or non-singular, if there exists a matrix such that Equivalently, is invertible if Otherwise, is called singular.
Let be an random matrix whose entries are independent and satisfy Equivalently, is chosen uniformly at random from all matrices with entries in . Put
There are several obvious ways for to be singular. For example, if two rows are equal or are negatives of one another, then the rows are linearly dependent. The same is true for two columns.
For a fixed pair of rows, the probability that they are equal up to sign is There are pairs of rows and the same number of pairs of columns. Since intersections between these events contribute only lower-order terms, we obtain
It has long been conjectured that these elementary coincidences account for almost all singular matrices. More precisely, The conjecture appears explicitly, for example, in work of Odlyzko (Odlyzko 1988). It predicts that, conditioned on being singular, with probability tending to the matrix has two rows or two columns equal up to sign.
Even proving that tends to zero is nontrivial. In 1967, Komlós (Komlós 1967) proved that In 1995, Kahn, Komlós, and Szemerédi (Kahn et al. 1995) obtained the first exponential upper bound, Tao and Vu subsequently improved this to in (Tao and Vu 2006). Their next paper produced a much larger improvement.
The proof combines probability, Fourier analysis, and additive combinatorics. Regard the rows of as independent random vectors If the matrix is singular, then these vectors lie in some proper linear subspace. After a reduction to a sufficiently large finite field, it is enough to study hyperplanes.
For a hyperplane , define where is uniformly distributed on . If then where the are independent random signs. Thus, estimating becomes a Littlewood–Offord problem about the concentration of random signed sums.
The main difficulty is that there are enormously many possible hyperplanes, so a direct union bound is much too weak. Tao and Vu divide the hyperplanes according to their concentration. Hyperplanes with small concentration are individually unlikely, while hyperplanes with large concentration must have strong additive structure. Inverse results from additive combinatorics show that the coefficients of such an exceptional hyperplane are largely contained in a low-rank generalized arithmetic progression. This rigidity makes the exceptional hyperplanes sufficiently rare to count.
For the remaining hyperplanes, a Fourier-analytic comparison gives the required exponential saving. The constant ultimately arises from the elementary inequality This connection between singular random matrices and the additive structure of concentrated random sums became one of the central ideas in the subsequent development of the subject.
In 2010, Bourgain, Vu, and Wood (Bourgain et al. 2010) improved the bound to In 2020, Tikhomirov (Tikhomirov 2020) determined the optimal exponential rate: Equivalently,
This result shows that no mechanism of singularity is exponentially more likely than the equality of two rows or columns up to sign. It does not, however, prove the sharper conjecture . The factor is invisible at the exponential scale, since Thus, the conjecture that remains open.
Although the numerical estimate in Theorem has since been surpassed, the theorem remains a landmark. Its proof revealed that rare linear dependencies in random matrices can be understood through inverse Littlewood–Offord theory and the additive structure of the coefficients defining the corresponding hyperplanes.