RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2010 Volume 22, Issue 2, Pages 3–21 (Mi dm1091)

This article is cited in 14 papers

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

V. A. Kopyttsev, V. G. Mikhailov


Abstract: 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.

UDC: 519.2

Received: 11.03.2010

DOI: 10.4213/dm1091


 English version:
Discrete Mathematics and Applications, 2010, 20:2, 191–211

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025