## On the rate of convergence to the normal distribution of the number of false solutions of a system of nonlinear random Boolean equations.(Ukrainian, English)Zbl 1199.60031

Teor. Jmovirn. Mat. Stat. 76, 105-116 (2007); translation in Theory Probab. Math. Stat. 76, 117-129 (2008).
The authors deal with the following system of equations $\sum_{k=1}^{g_i(n)}\sum_{1\leq j_1<\cdots<j_k\leq n}a_{j_1,\dots,j_k}^{(i)} x_{j_1}\cdots x_{j_k}=b_i,\,i=1,\dots,N,$ over the field $$GF(2)$$ containing only two elements, where the coefficients $$a_{j_1,\dots,j_k}^{(i)}, 1\leq j_1<\cdots<j_k\leq n,k=1,\dots,g_i(n)$$ are independent random variables taking the value 1 with probability $$P\{a_{j_1,\dots,j_k}^{(i)}=1\}=p_{ik}$$, and the value 0 with probability $$1-p_{ik}$$, the elements $$b_i,i=1,\dots,N$$, are equal to the left hand side of the system, if a fixed $$n$$-dimensional vector $$\vec{x}_0$$ is substituted for unknowns, and the functions $$g_i(n),i=1,\dots,N$$, are nonrandom and such that $$g_i(n)\in \{2,\dots,N\}$$.
Denote by $$\nu(n)$$ the number of false solutions of the system, that is, the number of solutions that do not coincide with the vector $$\vec{x}_0$$. Conditions are proposed under which the random variable $$\nu(n)$$ has the limit normal distribution as $$n\to\infty$$. It is assumed that every equation contains at least one coefficient for which the probability that it attains the value 1 is close to $$1/2$$; the number of equations $$N$$ and the number of unknowns $$n$$ are such that $$n-N\to\infty$$ as $$n\to\infty$$; the system has a solution containing units $$\rho(n)$$ and $$\rho(n)\to\infty$$ as $$n\to\infty$$.

### MSC:

 60C05 Combinatorial probability 15B52 Random matrices (algebraic aspects) 60F99 Limit theorems in probability theory

### Citations:

Zbl 0842.60009; Zbl 0926.60022
Full Text: