This works explores, and describes in a lot of detail, the surprisingly complex behaviour of an innocuous model of sparse random matrices.
Let A be a random n-by-n matrix over F2 whose entries are i.i.d. Bernoulli random variables with success probability d/n, where d is a positive constant. The authors pose the following natural question: What can be said about the space of solutions to the linear system Ax=y, where y is a uniformly random vector from the column space of A? More precisely, how many out of the n variables x1,…,xn are frozen, i.e., forced to take the same value in all |kerA| solutions? Denote this number by f(A).
A convincing heuristic suggests that f(A)/n should typically lie close to a fixed point of a certain function ϕd:[0,1]→[0,1] that depends only on the sparsity parameter d. The first part of the main result of this work confirms this prediction for all d≤e.
To make things more interesting, it turns out that in the complementary range d>e, the function ϕd has three fixed points. Does this mean that the heuristic that correctly predicted the typical values of f(A) is no longer valid? The second part of the main result states that f(A)/n is still typically close to some fixed point of ϕd, only that it exhibits the following “critical” behaviour: (i) with probability 1/2−o(1) it is near the smallest fixed point; and (ii) with probability 1/2−o(1) it is near the largest fixed point.
Turning the fixed-point heuristic we have alluded to above into a rigorous argument requires a range of techniques from combinatorics, probability theory, and statistical physics and is carried out in three stages, as detailed in the lucid proof outline. The argument that ensues is a remarkable tour-de-force rife with beautiful combinatorial and probabilistic ideas.