The sparse parity matrix

This works explores, and describes in a lot of detail, the surprisingly complex behaviour of an innocuous model of sparse random matrices.

Let \(\mathbf{A}\) be a random \(n\)-by-\(n\) matrix over \(\mathbb{F}_2\) 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 \(\mathbf{A}\mathbf{x} = \mathbf{y}\), where \(\mathbf{y}\) is a uniformly random vector from the column space of \(\mathbf{A}\)? More precisely, how many out of the \(n\) variables \(x_1, \dotsc, x_n\) are frozen, i.e., forced to take the same value in all \(|\ker \mathbf{A}|\) solutions? Denote this number by \(f(\mathbf{A})\).

A convincing heuristic suggests that \(f(\mathbf{A})/n\) should typically lie close to a fixed point of a certain function \(\phi_d \colon [0,1] \to [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 \le e\).

To make things more interesting, it turns out that in the complementary range \(d > e\), the function \(\phi_d\) has three fixed points. Does this mean that the heuristic that correctly predicted the typical values of \(f(\mathbf{A})\) is no longer valid? The second part of the main result states that \(f(\mathbf{A})/n\) is still typically close to some fixed point of \(\phi_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.