The satisfiability threshold for random linear equations

Let A be a random m × n matrix over the finite field Fq with precisely k non-zero entries per row and let y∈Fmq be a random vector chosen independently of A. We identify the threshold m/n up to which the linear system Ax = y has a solution with high probability and analyse the geometry of the set of solutions. In the special case q = 2, known as the random k-XORSAT problem, the threshold was determined by [Dubois and Mandler 2002 for k = 3, Pittel and Sorkin 2016 for k > 3], and the proof technique was subsequently extended to the cases q = 3,4 [Falke and Goerdt 2012]. But the argument depends on technically demanding second moment calculations that do not generalise to q > 4. Here we approach the problem from the viewpoint of a decoding task, which leads to a transparent combinatorial proof.