The satisfiability threshold for random linear equations (Q2003764)

In this paper the satisfiability threshold for random linear systems over any finite field \(\mathbb{F}_q\) by means of a transparent combinatorial argument is established. The key idea is to approach the problem from the angle of coding theory. To be precise, let \(q>1\) be a prime power, let \(k \geq 3\) be an integer and let \(\mathbb{F}_q^\ast\) be the finite field of order \(q\), excluding the zero element. Let \(P\) be a probability distribution on \(\mathbb{F}_q^{\ast k}\) such that \(P\) is permutation-invariant in the sense \(P(\sigma_1, \ldots , \sigma_k)=P(\sigma_{\lambda(1)}, \ldots , \sigma_{\lambda(k)})\) for any \(\sigma_1, \ldots , \sigma_k \in \mathbb{F}_q^\ast\) and any permutation \(\lambda\) of the first \(k\) positive integers. For \(d > 0\) and an integer \(n \geq k\), let \(m = m(d,n)\) be a Poisson variable with mean \(dn/k\). A random \(m \times n\) matrix \(A\) over \(\mathbb{F}_q\) is obtained as follows. For each \(i = 1, \ldots , m\) independently choose a sequence \(1 \leq \alpha_{i,1} < \cdots <\alpha_{i,h} \leq n\) of integers uniformly at random and independently choose a \(k\)-tuple \(a_{i,1}, \ldots , a_{i,k}\) from the distribution \(P\). Then the \(i^\prime\)-th row of \(A\) has entries \(a_{i,1}\) in the positions \(\alpha_{i,h}\), while all other entries are zero. Let \(y \in \mathbb{F}_q^{m}\) be a uniformly random vector, chosen independently of \(A\) given \(m\). The main result addresses the question for what \(d, k\) the random linear system \(A x = y\) is likely to have a solution. The following is proved. Let \(k \geq 3\), let \(q > 1\) be a prime power and let \(P\) be a permutation-invariant distribution on \(\mathbb{F}_q^{\ast k}\). For \(d > 0\), set \(\rho_{k, d} = \sup \{ x \in [0,1] : x = 1 - \exp (-dx^{k-1})\}\), and define \(d_k = \inf \{ d > 0 : \rho_{k,d} - d \rho_{k,d}^{k-1} + (1 - 1/k)d \rho_{k,d}^{k} < 0\}\). Then \[\lim_{n \to \infty} \mathbb{P} [ \exists x \in \mathbb{F}_q^n :A x = y ] = 1 \; {\text{ if} } \; d < d_k, \;\;0 \; {\text{ if }} \; d > d_k, \] and for \(d < d_k\) it holds that \(\lim_{n \to \infty} \mathbb{P} [\mathrm{rk}(A)=m]=1.\)