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.