The Sparse Parity Matrix

Let A be an n×n-matrix over F2 whose every entry equals 1 with probability d/n independently for a fixed d>0. Draw a vector y randomly from the column space of A. It is a simple observation that the entries of a random solution x to Ax=y are asymptotically pairwise independent, i.e., ∑i<jE|P[xi=s,xj=t∣A]−P[xi=s∣A]P[xj=t∣A]|=o(n2) for s,t∈F2. But what can we say about the {\em overlap} of two random solutions x,x′, defined as n−1∑ni=11{xi=x′i}? We prove that for d<e the overlap concentrates on a single deterministic value α∗(d). By contrast, for d>e the overlap concentrates on a single value once we condition on the matrix A, while over the probability space of A its conditional expectation vacillates between two different values α∗(d)<α∗(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.