A Theorem on the Limiting Distribution for the Number of False Solutions of a System of Nonlinear Random Boolean Equations (Q4252976)

The author considers the following equation system over the field GF(2) \[ \sum_{k=1}^\infty\sum_{1\leq j_1<\cdots< j_k\leq n}a_{j_1\cdots j_k}^{(i)} x_{j_1}\cdots x_{j_k}=b_i, \quad i=1,\dots, N, \] where \(a_{j_1\cdots j_k}^{(i)}\in \{0,1\}\). The principal assumptions are: the coefficients of the system are independent random variables which take values 0 and 1 with probabilities close to \(1/2\); \(n\) and the number \(N\) of equations of the system differ by a constant \(m\) as \( n\to\infty\); the system has a solution which contains \(\rho(n)\) units where \(\rho(n)\to\infty\) as \(n\to\infty\). Under some additional technical restrictions it is shown that the distribution of the number of false solutions of this consistent system of random nonlinear Boolean equations converges, as \(n\to\infty\), to the Poisson law with parameter \(2^m\).