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., Pi<j E|P[xi = s, x j = t | A] − P[xi = s | A]P[x j = t | A]| = o(n2) for s, t ∈ F2. But what can we say about the overlap of two random solutions x, x0, defined as n−1 Pni=1 1{xi = x0i }? 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 anti-concentration result provides an instructive contribution to both the theory of random constraint satisfaction problems and of inference problems on random structures