Characteristics of random systems of linear equations over a~finite field

A. V. Shapovalov

Diskretnaya Matematika, Tome 20 (2008) no. 4, pp. 136-146.

Résumé

We consider random and a priori consistent random systems of equations over a finite field with $q$ elements in $n$ unknowns. A random system consists of $M=M(n)$ equations, each of which can depend on $2,3,\dots,m$ variables, which are obtained by sampling without replacement. We obtain limit distributions and estimates of moments for the numbers of solutions of random systems of equations provided that $n\to\infty$ and the relation between the parameters $n$ and $M$, the number of vertices and the number of hyperedges, falls into the subcritical domain of the evolution of random hypergraphs which describe the random systems of equations. The form and parameters of the limit distributions are determined by the characteristics of the limit distributions of the number of cycles of a special form in the corresponding random hypergraphs.

Bibliographie

[1] Balakin G. V., “Vvedenie v teoriyu sluchainykh sistem uravnenii”, Trudy po diskretnoi matematike, 1, 1997, 1–18 | MR | Zbl

[2] Balakin G. V., Kolchin V. F., Khokhlov V. I., “Gipertsikly v sluchainom gipergrafe”, Diskretnaya matematika, 3:3 (1991), 102–108 | MR | Zbl

[3] Billingsli P., Skhodimost veroyatnostnykh mer, Nauka, Moskva, 1977 | MR

[4] Kolchin V. F., Sistemy sluchainykh uravnenii, MIEM, Moskva, 1988

[5] Kolchin V. F., “O porogovom effekte dlya sistem sluchainykh uravnenii”, Trudy po diskretnoi matematike, 2, 1998, 183–190 | MR | Zbl

[6] Kolchin V. F., “Porogovoe svoistvo dlya sistem uravnenii v konechnykh polyakh”, Diskretnaya matematika, 11:3 (1999), 15–23 | MR | Zbl

[7] Kolchin V. F., Sluchainye grafy, Fizmatlit, Moskva, 2004

[8] Kolchin V. F., Khokhlov V. I., “Porogovyi effekt dlya sistem sluchainykh uravnenii spetsialnogo vida”, Diskretnaya matematika, 7:4 (1995), 29–39 | MR | Zbl

[9] Shapovalov A. V., “Veroyatnost sovmestnosti sluchainykh sistem bulevykh uravnenii”, Diskretnaya matematika, 7:3 (1995), 146–159 | MR | Zbl

[10] Shapovalov A. V., “The number of decisions of random monomial and binomial linear systems of equations”, Probabilistic Methods in Discrete Mathematics, VSP, Utrecht, 1997, 333–342 | MR | Zbl

[11] Shapovalov A. V., “Characteristics of random systems of Boolean equations with non-regular left-hand side”, Probabilistic Methods in Discrete Mathematics, VSP, Utrecht, 2002, 345–350

[12] Shapovalov A. V., “Porogovye funktsii sovmestnosti sluchainykh sistem uravnenii”, Trudy po diskretnoi matematike, 9, 2006, 377–400

[13] Shapovalov A. V., “Raspredeleniya chisel konechnykh podgrafov v sluchainykh neodnorodnykh gipergrafakh”, Diskretnaya matematika, 18:3 (2006), 102–114 | MR | Zbl

[14] Shapovalov A. V., “Tsiklovaya struktura sluchainogo neodnorodnogo gipergrafa na dokriticheskom etape evolyutsii”, Diskretnaya matematika, 19:4 (2007), 52–69 | MR

[15] Bollobás B., Random graphs, Academic Press, London, 1985 | MR | Zbl