|
This article is cited in 2 scientific papers (total in 2 papers)
Threshold property for systems of equations in finite fields
V. F. Kolchin
Abstract:
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.
Received: 20.02.1999
Citation:
V. F. Kolchin, “Threshold property for systems of equations in finite fields”, Diskr. Mat., 11:3 (1999), 15–23; Discrete Math. Appl., 9:4 (1999), 355–364
Linking options:
https://www.mathnet.ru/eng/dm382https://doi.org/10.4213/dm382 https://www.mathnet.ru/eng/dm/v11/i3/p15
|
Statistics & downloads: |
Abstract page: | 408 | Full-text PDF : | 192 | First page: | 4 |
|