LAUSR

Let A be a random m × n matrix over the finite field $$\mathbb{F}_q$$ F q with precisely k non-zero entries per row and let $$y\in\mathbb{F}_q^m$$ y ∈ F q m be a random vector chosen independently of A . We identify the threshold m / n up to which the linear system A x = 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.