The Sparse Parity Matrix

Let A be an n × n-matrix over F₂ 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., (Math Presents) for s, (Math Presents). But what can we say about the overlap of two random solutions x, x^′, defined as (Math Presents)? We prove that for d < e the overlap concentrates on a single deterministic i 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.