  Let $\mathbf{A}$ be an $n\times n$-matrix over $\mathbb{F}_2$ whose every
entry equals $1$ with probability $d/n$ independently for a fixed $d>0$. Draw a
vector $\mathbf{y}$ randomly from the column space of $\mathbf{A}$. It is a
simple observation that the entries of a random solution $\mathbf{x}$ to
$\mathbf{A} x=\mathbf{y}$ are asymptotically pairwise independent, i.e.,
$\sum_{i<j}\mathbb{E}|\mathbb{P}[\mathbf{x}_i=s,\,\mathbf{x}_j=t\mid\mathbf{A}]-\mathbb{P}[\mathbf{x}_i=s\mid\mathbf{A}]\mathbb{P}[\mathbf{x}_j=t\mid\mathbf{A}]|=o(n^2)$
for $s,t\in\mathbb{F}_2$. But what can we say about the {\em overlap} of two
random solutions $\mathbf{x},\mathbf{x}'$, defined as
$n^{-1}\sum_{i=1}^n\mathbf{1}\{\mathbf{x}_i=\mathbf{x}_i'\}$? We prove that for
$d<\mathrm{e}$ the overlap concentrates on a single deterministic value
$\alpha_*(d)$. By contrast, for $d>\mathrm{e}$ the overlap concentrates on a
single value once we condition on the matrix $\mathbf{A}$, while over the
probability space of $\mathbf{A}$ its conditional expectation vacillates
between two different values $\alpha_*(d)<\alpha^*(d)$, either of which occurs
with probability $1/2+o(1)$. This bifurcated non-concentration result provides
an instructive contribution to both the theory of random constraint
satisfaction problems and of inference problems on random structures.
