The satisfiability threshold for random linear equations

-XORSAT problem, the threshold was determined by [Dubois and Mandler 2002, Dietzfelbinger et al. 2010, Pittel and Sorkin 2016], 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 > 3

. Here we approach the problem from the viewpoint of a decoding task, which leads to a transparent combinatorial proof.

Review text

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.\)

Recommendations

Cites work

Cited in

(21)

This page was built for publication: The satisfiability threshold for random linear equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2003764)