Skip to main content
SpringerLink
Log in

Law of Large Numbers for infinite random matrices over a finite field

  • Published:
Selecta Mathematica Aims and scope Submit manuscript

Abstract

Asymptotic representation theory of general linear groups \(\hbox {GL}(n,F_\mathfrak {q})\) over a finite field leads to studying probability measures \(\rho \) on the group \(\mathbb {U}\) of all infinite uni-uppertriangular matrices over \(F_\mathfrak {q}\), with the condition that \(\rho \) is invariant under conjugations by arbitrary infinite matrices. Such probability measures form an infinite-dimensional simplex, and the description of its extreme points (in other words, ergodic measures \(\rho \)) was conjectured by Kerov in connection with nonnegative specializations of Hall–Littlewood symmetric functions. Vershik and Kerov also conjectured the following Law of Large Numbers. Consider an infinite random matrix drawn from an ergodic measure coming from the Kerov’s conjectural classification and its \(n \times n\) submatrix formed by the first rows and columns. The sizes of Jordan blocks of the submatrix can be interpreted as a (random) partition of \(n\), or, equivalently, as a (random) Young diagram \(\lambda (n)\) with \(n\) boxes. Then, as \(n\rightarrow \infty \), the rows and columns of \(\lambda (n)\) have almost sure limiting frequencies corresponding to parameters of this ergodic measure. Our main result is the proof of this Law of Large Numbers. We achieve it by analyzing a new randomized Robinson–Schensted–Knuth (RSK) insertion algorithm which samples random Young diagrams \(\lambda (n)\) coming from ergodic measures. The probability weights of these Young diagrams are expressed in terms of Hall–Littlewood symmetric functions. Our insertion algorithm is a modified and extended version of a recent construction by Borodin and Petrov (2013). On the other hand, our randomized RSK insertion generalizes a version of the RSK insertion introduced by Vershik and Kerov (SIAM J. Algebr. Discret. Math. 7(1):116–124, 1986) in connection with asymptotic representation theory of symmetric groups (which is governed by nonnegative specializations of Schur symmetric functions).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14

Similar content being viewed by others

Notes

  1. The conjecture was originally formulated in equivalent terms of nonnegative specializations of Hall–Littlewood symmetric functions. Another equivalent formulation involves coherent probability measures on the Young branching graph with formal edge multiplicities depending on \(\mathfrak {q}\) (cf. Sect. 5.4). See [6, 34], Thm. 2.3], [37, Prop. 4.7] for details of these equivalences.

  2. Our notation of parameters \((\varvec{\alpha };\varvec{\beta };\gamma )\) borrowed from Borodin and Corwin [8] and also used in Borodin and Petrov [16] differs from the one of Kerov [45], see also Gorin et al. [37]. Details are explained in Remark 2.6 below.

  3. \(P_\lambda \) is a constant multiple of \(Q_\lambda \). We use the standard notation of [50].

  4. Here and below \({\mathbf {1}}_{A}\) means the indicator of \(A\).

  5. See also Aissen et al. [1].

  6. However, note that a horizontal or a vertical strip is allowed to be empty.

  7. This means that \(\mathsf {Sym}\) is the projective limit (in the category of graded algebras) of algebras of symmetric polynomials in growing number of variables.

  8. Lexicographic order means that, for example, \(x_1^{2}\) is higher than \(\mathrm {const}\cdot x_1x_2\) which is in turn higher than \(\mathrm {const}\cdot x_2^{2}\).

  9. Sometimes we will also use the term Macdonald-nonnegative, cf. [8, §2.2.1].

  10. Sometimes to emphasize that we are working with dual variables, we will use the hat notation. For example, a dual variable equal to \(1\) will be denoted by \(\hat{1}\).

  11. However, in the present paper, we restrict ourselves to \(t\in [0,1)\), which excludes cases (3) and (4) from the consideration.

  12. Note that because \(P_\lambda \) is a multiple of \(Q_\lambda \), (3.1) reduces to (1.4) when \(q=0\), \(t=\mathfrak {q}^{-1}\), and \(p_1(\varvec{\alpha };{\varvec{\beta }};\mathbf {Pl}_\gamma )=1\).

  13. The reason for the multiplication of \(\tau \) by \(p_1(\varvec{\alpha };{\varvec{\beta }};\mathbf {Pl}_\gamma )\) is the future convenience of certain formulas. Note that for now we are not assuming that \(p_1(\varvec{\alpha };{\varvec{\beta }};\mathbf {Pl}_\gamma )=1\) (see Remark 3.2).

  14. Note that the expression \(\varPi (u;\mathbf {A})\) in (2.4) is a particular case of (4.2) corresponding to \(\mathbf {B}=(u)\), a specialization into a single usual variable.

  15. Note that the condition \(\big [{\begin{matrix} \lambda \\ \bar{\lambda } \end{matrix}}\big ]\in \mathbb {Y}^{(2)}(\mathbf {A};\mathbf {B})\) implies that \(\bar{\lambda }\subseteq \lambda \).

  16. These dynamics may be viewed as discrete \((q,t)\)-analogs of the classical Dyson Brownian motion [22] from random matrix theory, e.g., see [17].

  17. This actually is the first place when we drop the nonnegativity assumption.

  18. We are using probabilistic terms despite the fact that some ‘probabilities’ can be negative (see the beginning of Sect. 4 for more detail). When we speak about conditioning on an event which possibly can have negative probability, this should be understood as an intuitive appeal to the product rule (4.15) defining the jump rates via the quantities (5.15)–(5.17).

  19. Setting \(h=+\infty \) means that the last (i.e., the leftmost) particle jumps independently.

  20. We assume that the lower level particles evolve according to the univariate dynamics \(\mathsf {Q}_{\mathbf {A}}\). The functions \((W_{(\alpha )}^{h},V_{(\alpha )}^{h})\) then provide the necessary “induction step” leading to the upper univariate dynamics \(\mathsf {Q}^{(2)}_{\mathbf {A};(\alpha )}\).

  21. It is possible to develop randomized “sampling” algorithms (i.e., formal Markov “dynamics” with negative probabilities of certain elements in a “transition matrix”) for the general parameters \((q,t)\) by analogy, but we will not pursue this direction here.

  22. Thus, the lower Young diagram \(\bar{\lambda }(k)\) has a random number of boxes, but \(\lambda (k)\) has exactly \(k\) boxes.

  23. In fact, these particles evolve according to Dynamics 8 in [16], up to renaming \(t\) by \(q\) and considering the evolution in continuous time, cf. Remark 6.17.

  24. Of course, particles in the bulk of the interlacing array (i.e., all particles except the leftmost ones \(\lambda ^{(i)}_i\)) will move in some way, but this cannot break the desired inequalities. This remark applies to other two cases as well.

  25. Note that once a particle \(\tau ^{(m)}_{1}\), for some \(m>i\) was not pushed, all upper particles \(\tau ^{(j)}_{1}\) (\(j>m\)) also cannot be pushed, see Remark 6.20.

References

  1. Aissen, M., Edrei, A., Schoenberg, I.J., Whitney, A.: On the generating functions of totally positive sequences. Proc. Natl. Acad. Sci. USA 37, 303–307 (1951)

    Article  MathSciNet  MATH  Google Scholar 

  2. Aissen, M., Schoenberg, I.J., Whitney, A.: On the generating functions of totally positive sequences I. J. Anal. Math. 2, 93–103 (1952)

    Article  MathSciNet  MATH  Google Scholar 

  3. Baik, J., Deift, P., Johansson, K.: On the distribution of the length of the longest increasing subsequence of random permutations. J. Am. Math. Soc. 12(4), 1119–1178 (1999). arXiv:math/9810105 [math.CO]

  4. Berele, A., Regev, A.: Hook Young diagrams with applications to combinatorics and representations of Lie superalgebras. Adv. Math. 64(2), 118–175 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  5. Borodin, A.: Limit Jordan normal form of large triangular matrices over a finite field. Funct. Anal. Appl. 29(4), 279–281 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  6. Borodin, A.: The law of large numbers and the central limit theorem for the jordan normal form of large triangular matrices over a finite field. J. Math. Sci. 96(5), 3455–3471 (1999)

    Article  MathSciNet  Google Scholar 

  7. Borodin, A.: Schur dynamics of the Schur processes. Adv. Math. 228(4), 2268–2291 (2011). arXiv:1001.3442 [math.CO]

  8. Borodin, A., Corwin, I.: Macdonald processes. Prob. Theory Rel. Fields 158, 225–400 (2014). arXiv:1111.4408 [math.PR]

  9. Borodin, A., Corwin, I., Gorin, V., Shakirov, S.: Observables of Macdonald processes. (2013). arXiv:1306.0659 [math.PR]

  10. Borodin, A., Ferrari, P.: Anisotropic growth of random surfaces in 2 + 1 dimensions. (2008). arXiv:0804.3035 [math-ph] (to appear in Comm. Math. Phys)

  11. Borodin, A., Gorin, V.: Markov processes of infinitely many nonintersecting random walks. Probab. Theory Rel. Fields 155(3–4), 935–997 (2013). arXiv:1106.1299 [math.PR]

  12. Borodin, A., Olshanski, G.: Harmonic functions on multiplicative graphs and interpolation polynomials. Electron. J. Comb. 7, R28 (2000). arXiv:math/9912124 [math.CO]

  13. Borodin, A., Olshanski, G.: Markov processes on the path space of the Gelfand-Tsetlin graph and on its boundary. J. Funct. Anal. 263(1), 248–303 (2012). arXiv:1009.2029 [math.PR]

  14. Borodin, A., Olshanski, G.: The boundary of the Gelfand–Tsetlin graph: a new approach. Adv. Math. 230, 1738–1779 (2012). arXiv:1109.1412 [math.CO]

  15. Borodin, A., Olshanski, G.: The Young bouquet and its boundary. Mosc. Math. J. 13(2), 193–232 (2013). arXiv:1110.4458 [math.RT]

  16. Borodin, A., Petrov, L.: Nearest neighbor Markov dynamics on Macdonald processes. Adv. Math. (2013). arXiv:1305.5501 [math.PR] (to appear)

  17. Borodin, A., Petrov, L.: Integrable probability: from representation theory to Macdonald processes. Probab. Surv. 11, 1–58 (2014). arXiv:1310.8007 [math.PR]

  18. Boyer, R.: Infinite traces of AF-algebras and characters of \(U(\infty )\). J. Oper. Theory 9, 205–236 (1983)

    MATH  Google Scholar 

  19. Bufetov, Al: The central limit theorem for extremal characters of the infinite symmetric group. Funct. Anal. Appl. 46(2), 83–93 (2012). arXiv:1105.1519 [math.RT]

  20. Corwin, I., Petrov, L.: The q-PushASEP: a new integrable model for traffic in 1 + 1 dimension. J. Stat. Phys. (2013). arXiv:1308.3124 [math.PR] (to appear)

  21. Diaconis, P., Fill, J.A.: Strong stationary times via a new form of duality. Ann. Probab. 18, 1483–1522 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  22. Dyson, F.J.: A Brownian motion model for the eigenvalues of a random matrix. J. Math. Phys. 3(6), 1191–1198 (1962)

    Article  MathSciNet  MATH  Google Scholar 

  23. Edrei, A.: On the generating functions of totally positive sequences. II. J. Anal. Math. 2, 104–109 (1952)

    Article  MathSciNet  MATH  Google Scholar 

  24. Edrei, A.: On the generating function of a doubly infinite, totally positive sequence. Trans. Am. Math. Soc. 74, 367–383 (1953)

    MathSciNet  MATH  Google Scholar 

  25. Féray, V., Méliot, P.-L.: Asymptotics of q-plancherel measures. Probab. Theory Rel. Fields 152(3–4), 589–624 (2012). arXiv:1001.2180 [math.RT]

  26. Fomin, S.: Two-Dimensional Growth in Dedekind Lattices. Master’s thesis, Leningrad State University (1979)

  27. Fomin, S.: Generalized Robinson–Schnested–Knuth correspondence. Zapiski Nauchn. Sem. LOMI 155, 156–175 (1986) (in Russian)

  28. Fomin, S.: Duality of graded graphs. J. Algebr. Comb. 3(4), 357–404 (1994)

    Article  MATH  Google Scholar 

  29. Fomin, S.: Schensted algorithms for dual graded graphs. J. Algebr. Comb. 4(1), 5–45 (1995)

    Article  MATH  Google Scholar 

  30. Forrester, P.J., Rains, E.M.: Interpretations of some parameter dependent generalizations of classical matrix ensembles. Prob. Theory Rel. Fields 131(1), 1–61 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  31. Fulman, J.: Probabilistic measures and algorithms arising from the Macdonald symmetric functions (1997). arXiv:math/9712237 [math.CO]

  32. Fulman, J.: A probabilistic approach toward conjugacy classes in the finite general linear and unitary groups. J. Algebr. 212(2), 557–590 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  33. Fulman, J.: The eigenvalue distribution of a random unipotent matrix in its representation on lines. J. Algebr. 228(2), 497–511 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  34. Fulman, J.: Random matrix theory over finite fields. Bull. Am. Math. Soc. 39(1), 51–85 (2001). arXiv:math/0003195 [math.GR]

  35. Fulman, J.: Cohen–Lenstra heuristics and random matrix theory over finite fields. J. Group Theory 17(4), 619–648 (2014). arXiv:1307.0879 [math.NT]

  36. Gorin, V.: The q-Gelfand–Tsetlin graph, Gibbs measures and q-oeplitz matrices. Adv. Math. 229(1), 201–266 (2012). arXiv:1011.1769 [math.RT]

  37. Gorin, V., Kerov, S., Vershik, A.: Finite traces and representations of the group of infinite matrices over a finite field. Adv. Math. 254, 331–395 (2014). arXiv:1209.4945 [math.RT]

  38. Gorin, V., Panova, G.: Asymptotics of symmetric polynomials with applications to statistical mechanics and representation theory. DMTCS Proceedings, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), pp. 37–48 (2013). arXiv:1301.0634 [math.RT]

  39. Ivanov, V.: The dimension of Skew Shifted Young diagrams, and projective characters of the infinite symmetric group. J. Math. Sci., 96(5), 3517–3530 (1999) (in Russian: Zap. Nauchn. Sem. POMI 240, 115–135 (1997)). arXiv:math/0303169 [math.CO]

  40. Jack, H.: A class of symmetric functions with a parameter. Proc. R. Soc. Edinb. A 69, 1–18 (1970)

    MathSciNet  MATH  Google Scholar 

  41. Jack, H.: A surface integral and symmetric functions. Proc. R. Soc. Edinb. A 69, 347–363 (1972)

    MathSciNet  MATH  Google Scholar 

  42. Johansson, K.: Shape fluctuations and random matrices. Commun. Math. Phys. 209(2), 437–476 (2000). arXiv:math/9903134 [math.CO]

  43. Kerov, S.: Combinatorial examples in the theory of AF-algebras. Zapiski Nauchn. Semin. LOMI, 172, 55–67 (English translation. J. Soviet Math. 59(1992), 1063–1071) (1989)

  44. Kerov, S.: Generalized Hall–Littlewood symmetric functions and orthogonal polynomials. Adv. Sov. Math. 9, 67–94 (1992)

    MathSciNet  Google Scholar 

  45. Kerov, S.: Asymptotic Representation Theory of the Symmetric Group and Its Applications in Analysis, vol. 219. AMS, Translations of Mathematical Monographs, Providence (2003)

  46. Kerov, S., Okounkov, A., Olshanski, G.: The boundary of Young graph with Jack edge multiplicities. Int. Math. Res. Not. 4, 173–199 (1998). arXiv:q-alg/9703037

  47. Kingman, J.F.C.: Random partitions in population genetics. Proc. R. Soc. Lond. A 361, 1–20 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  48. Kirillov, A.A.: Variations on the triangular theme. Trans. Am. Math. Soc. 169, 43–74 (1995)

    MathSciNet  Google Scholar 

  49. Littlewood, D.E.: On certain symmetric functions. Proc. Lond. Math. Soc. 43, 485–498 (1961)

    Article  MathSciNet  Google Scholar 

  50. Macdonald, I.G.: Symmetric Functions and Hall Polynomials, 2nd edn. Oxford University Press, Oxford (1995)

    MATH  Google Scholar 

  51. Meliot, P.-L.: A central limit theorem for the characters of the infinite symmetric group and of the infinite Hecke algebra. (2011). arXiv:1105.0091 [math.RT]

  52. Nazarov, M.L.: Projective representations of the infinite symmetric group. In: Vershik, A.M. (ed.) Representation Theory and Dynamical Systems. Advances in Soviet Mathematics, vol. 9, pp. 115–130. American Mathematical Society (1992)

  53. O’Connell, N.: A path-transformation for random walks and the Robinson–Schensted correspondence. Trans. Am. Math. Soc. 355(9), 3669–3697 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  54. O’Connell, N.: Conditioned random walks and the RSK correspondence. J. Phys. A 36(12), 3049–3066 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  55. O’Connell, N., Pei, Y.: A q-weighted version of the Robinson–Schensted algorithm. Electron. J. Probab. 18(95), 1–25 (2013) arXiv:1212.6716 [math.CO]

  56. Okounkov, A., Olshanski, G.: Asymptotics of Jack polynomials as the number of variables goes to infinity. Int. Math. Res. Not. 1998(13), 641–682 (1998). arXiv:q-alg/9709011

  57. Olshanski, G., Vershik, A.: Ergodic unitarily invariant measures on the space of infinite Hermitian matrices. In: Contemporary Mathematical Physics. F.A. Berezi’s Memorial Volume. American Mathematical Society Translations (Advances in the Mathematical Sciences—31), vol. 175 of 2, pp. 137–175. (1996). arXiv:math/9601215v1 [math.RT]

  58. Pei, Y.: A symmetry property for q-weighted Robinson–Schensted algorithms and other branching insertion algorithms. J. Algebr. Comb. 40, 743–770 (2013) arXiv:1306.2208 [math.CO]

  59. Petrov, L.: The Boundary of the Gelfand–Tsetlin graph: new proof of Borodin–Olshanski’s formula, and its q-analogue. (2012). arXiv:1208.3443 [math.CO] (to appear in Moscow Math. J.)

  60. Petrov, L.: \(\mathfrak{sl}(2)\) operators and Markov processes on branching graphs. J. Algebr. Comb. 38(3), 663–720 (2013). arXiv:1111.3399 [math.CO]

  61. Romik, D., Sniady, P.: Jeu de taquin dynamics on infinite Young tableaux and second class particles. Ann. Probab. 43(2), 682–737 (2015). arXiv:1111.0575 [math.PR]

  62. Sagan, B.E.: The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions. Springer, Berlin (2001)

    Book  Google Scholar 

  63. Skudlarek, H.-L.: Die unzerlegbaren Charaktere einiger discreter Gruppen. Math. Ann. 223, 213–231 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  64. Sniady, P.: Robinson–Schensted–Knuth Algorithm, Jeu de Taquin, and Kerov–Vershik Measures on Infinite Tableaux. SIAM J. Discret. Math. 28(2), 598–630 (2014). arXiv:1307.5645 [math.CO]

  65. Stanley, R.: Enumerative Combinatorics, vol. 2. Cambridge University Press, Cambridge [with a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin (2001)]

  66. Thoma, E.: Die unzerlegbaren, positive-definiten Klassenfunktionen der abzählbar unendlichen, symmetrischen Gruppe. Math. Z. 85, 40–61 (1964)

    Article  MathSciNet  MATH  Google Scholar 

  67. Thoma, E.: Characters of the group \(GL(\infty , q)\). In: Lecture Notes in Mathematics, vol. 266, pp. 321–323. Springer, New York (1972)

  68. Vershik, A., Kerov, S.: Asymptotic theory of the characters of the symmetric group. Funktsional. Anal. i Priloz. 15(4), 15–27 (1981)

    MathSciNet  Google Scholar 

  69. Vershik, A., Kerov, S.: Characters and factor representations of the infinite symmetric group. Dokl. Akad. Nauk. SSSR 257(5), 1037–1040 (1981)

    MathSciNet  Google Scholar 

  70. Vershik, A., Kerov, S.: Characters and factor-representations of the infinite unitary group. Dokl. Akad. Nauk. SSSR 267(2), 272–276 (1982)

    MathSciNet  Google Scholar 

  71. Vershik, A., Kerov, S.: The characters of the infinite symmetric group and probabiliy properties of the Robinson–Shensted–Knuth algorithm. SIAM J. Algebr. Discret. Math. 7(1), 116–124 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  72. Vershik, A., Kerov, S.: Characters and realizations of infinite-dimensional Hecke algebra and knot invariants. Sov. Math. Dokl. 38, 134–137 (1989)

    MathSciNet  MATH  Google Scholar 

  73. Vershik, A., Kerov, S.: On a infinite-dimensional group over a finite field. Funct. Anal. Appl. 32(3), 147–152 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  74. Vershik, A., Kerov, S.: Four drafts of the representation theory of the group of infinite matrices over a finite field. J. Math. Sci. 147(6), 7129–7144 (2007). arXiv:0705.3605 [math.RT]

  75. Voiculescu, D.: Representations factorielles de type \(II_1\) de \(U(\infty )\). J. Math. Pures Appl. 55, 1–20 (1976)

    MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

This work was started at the 2013 Cornell Probability Summer School, and we would like to thank the organizers for the invitation and warm hospitality. We are very grateful to Alexei Borodin, Jason Fulman, Vadim Gorin, Grigori Olshanski, and Anatoly Vershik for helpful discussions. We also would like to thank the anonymous referee for extremely valuable suggestions on improving the presentation of our results. A.B. was partially supported by Simons Foundation—IUM scholarship, by Moebius Foundation for Young Scientists, by “Dynasty” foundation, and by the RFBR Grant 13-01-12449.

Author information

Authors and Affiliations

  1. International Laboratory of Representation Theory and Mathematical Physics, Department of Mathematics, Higher School of Economics, Vavilova Str. 7, Moscow, 117312, Russia

    Alexey Bufetov

  2. Institute for Information Transmission Problems, Bolshoy Karetny Per. 19, Moscow, 127994, Russia

    Alexey Bufetov & Leonid Petrov

  3. Department of Mathematics, Northeastern University, 360 Huntington Ave, Boston, MA, 02115, USA

    Leonid Petrov

Authors
  1. Alexey Bufetov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Leonid Petrov
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Leonid Petrov.

Additional information

To Grigori Olshanski on the occasion of his 65th birthday.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bufetov, A., Petrov, L. Law of Large Numbers for infinite random matrices over a finite field. Sel. Math. New Ser. 21, 1271–1338 (2015). https://doi.org/10.1007/s00029-015-0179-9

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00029-015-0179-9

Keywords

Mathematics Subject Classification

Search

Navigation