×

A threshold effect for systems of random equations in finite fields. (English. Russian original) Zbl 0980.60017

Discrete Math. Appl. 9, No. 4, 355-364 (1999); translation from Diskret. Mat. 11, No. 3, 15-23 (1999).
The author considers a system of linear equations in \(\text{GF} (q)\) with unknown variables \(x_1,\dots,x_N\) of the form \[ a_1^{(t)} x_{i_1(t)}+ \cdots+a_r^{(t)} x_{i_r(t)} =b_t,\quad t=1,\dots,T. \] \(i_1(t), \dots,i_r(t)\), \(t=1, \dots,T\), are independent and identically distributed random variables assuming the values \(1,\dots,N\) equally likely. The coefficients \(a_1^{(t)}, \dots, a_r^{(t)}\), \(t=1,\dots,T\), are independent and identically distributed non-zero random variables whose values from \(\text{GF}(q)\) are also equiprobable. They do not depend on \(i_1(t), \dots, i_r(t)\). Finally, \(b_t\), \(t=1, \dots,T\), are also independent, take their values from \(\text{GF}(q)\) with equal probabilities, and are independent from the left-hand side of the system. Let \(A_r\) denote the matrix of the system. Its rows with numbers \(t_1,\dots,t_m\) and non-zero weights \(\varepsilon_1,\dots,\varepsilon_m\), \(\varepsilon_j \in \text{GF}(q)\), \(j=1, \dots,m\), form a critical set if the sum \(\varepsilon_1 a_{t_1}+ \cdots +\varepsilon_m a_{t_m}\) is equal to the non-zero vector. The author establishes a threshold property for the total number \(s(A_r)\) of critical sets of the matrix \(A_r\). More precisely, assuming there the convergence \(T/N\to \alpha\) as \(T,N\to \infty\), he proves that there exists a constant \(\alpha_r\) such that \(E[S(A_r)] \to 0\) if \(\alpha <\alpha_r\), and \(E[S (A_r)]\to \infty\) if \(\alpha> \alpha_r\) for any fixed pair of integers \((q,r)\), \(q,r\geq 3\). The methods of proof involve a transfer to the classical problem of allocations of balls into cells.

MSC:

60C05 Combinatorial probability
15B52 Random matrices (algebraic aspects)
14G50 Applications to coding theory and cryptography of arithmetic geometry
Full Text: DOI