The sparse parity matrix

Abstract

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}}^{\prime }$, defined as $n^{-1}{\sum }_{i=1}^{n}1\{{\mathbf{x}}_i={\mathbf{x}}_i^{\prime }\}$? We prove that for $d<\mathrm{e}$ the overlap concentrates on a single deterministic value ${\alpha }_{\ast }(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 }_{\ast }(d)<{\alpha }^{\ast }(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.