Abstract:
The distribution of the number of solutions of the systems in which each equation is specified by the substitution into a function $\varphi(u_1,\dots,u_d)$, $u_j\in\{0,1\}$, binary unknowns taken at random and without replacement from the set $\{x_1,\dots,x_n\}$, $n\ge d$, is studied. It is proved that, under certain conditions the distribution of the logarithm to base 2 of the number of solutions of the obtained system converges to a Poisson distribution.
Keywords:random systems of equations, true solution, the number of solutions, Poisson distribution.