Threshold property for systems of equations in finite fields

V. F. Kolchin

Diskretnaya Matematika, Tome 11 (1999) no. 3, pp. 15-23

Résumé

We consider the system of equations in $\operatorname{GF}(q)$ with respect to unknowns $x_1,\ldots,x_N$ $$ a_1^{(t)}x_{i_1(t)}+\ldots+a_r^{(t)}x_{i_r(t)}=b_t,\qquad t=1,\ldots, T, $$ where $i_1(t),\ldots, i_r(t)$, $t=1,\ldots,T$, are independent identically distributed random variables taking the values $1,\dots, N$ with equal probabilities, the coefficients $a_1^{(t)},\ldots,a_r^{(t)}$, $t=1,\ldots,T$, are independent identically distributed random variables independent of $i_1(t),\ldots,i_r(t)$, $t=1,\ldots,T$, and taking the non-zero values from $\operatorname{GF}(q)$ with equal probabilities, and $b_t$, $t=1,\ldots,T$, are independent random variables not depending on the left-hand side of the system and taking the values from $\operatorname{GF}(q)$ with equal probabilities. We denote by $A_r$ the matrix of the system. A critical set of rows of $A_r$ is defined in the same way as in the case of $\operatorname{GF}(2)$ but here a critical set contains a number of rows with weights from $\operatorname{GF}(q)$. We prove that the total number $S(A_r)$ of critical sets of the matrix $A_r$ has a threshold property. Let $N,T\to \infty$ and $T/N\to\alpha$. Then for any fixed integers $r\geq 3$ and $q\geq 3$ there exists a constant $\alpha_r$ such that $\mathsf E S(A_r)\to 0$ if $\alpha\alpha_r$, and $\mathsf E S(A_r)\to\infty$ if $\alpha>\alpha_r$. The research was supported by the Russian Foundation for Basic Research, grants 96–01–00338 and 96–15–96092.