Poisson-type theorems for the number of special solutions of a~random linear inclusion

V. A. Kopyttsev ; V. G. Mikhailov

Diskretnaya Matematika, Tome 22 (2010) no. 2, pp. 3-21

Résumé

For given sets $D$ and $B$ of vectors of linear spaces over a finite field of dimensions $n$ and $T$, respectively, and a random $T\times n$ matrix $A$ over this field, we consider the distribution of the number of vectors satisfying the system of relations $x\in D$, $Ax\in B$ (that is, the number of solutions of the random linear inclusion $Ax\in B$ belonging to the set $D$). The conditions of convergence of this distribution, as $n,T\to\infty$, to the simple and compound Poisson distributions are given. These conditions require that the distribution of the matrix $A$ converge to the uniform distribution and at least one of the sets $D$ and $B$ satisfy the condition which is called here the condition of asymptotic freedom from linear combinations. These results generalise the known limit theorems on the number of special solutions of a system of random linear equations. In particular, they give a possibility to describe the asymptotic behaviour of the number of approximate solutions of a priori solvable systems.