The distribution of sandpile groups of random graphs

Wood, Melanie¹

¹Department of Mathematics, University of Wisconsin–Madison, 480 Lincoln Drive, Madison, Wisconsin 53705, and American Institute of Mathematics, 360 Portage Avenue, Palo Alto, California 94306-2244

Journal of the American Mathematical Society, Tome 30 (2017) no. 4, pp. 915-958

Résumé

We determine the distribution of the sandpile group (or Jacobian) of the Erdős-Rényi random graph $G(n,q)$ as $n$ goes to infinity. We prove the distribution converges to a specific distribution conjectured by Clancy, Leake, and Payne. This distribution is related to, but different from, the Cohen-Lenstra distribution. Our proof involves first finding the expected number of surjections from the sandpile group to any finite abelian group (the “moments” of a random variable valued in finite abelian groups). To achieve this, we show a universality result for the moments of cokernels of random symmetric integral matrices that is strong enough to handle dependence in the diagonal entries. The methods developed to prove this result include inverse Littlewood-Offord theorems over finite rings and new techniques for studying homomorphisms of finite abelian groups with not only precise structure but also approximate versions of that structure. We then show these moments determine a unique distribution despite their $p^{k^2}$-size growth. In particular, our theorems imply universality of singularity probability and ranks mod $p$ for symmetric integral matrices.

Détail

DOI : 10.1090/jams/866

Bibliographie

[1] Alfaro, Carlos A., Valencia, Carlos E. On the sandpile group of the cone of a graph Linear Algebra Appl. 2012 1154 1176

[2] Bacher, Roland, De La Harpe, Pierre, Nagnibeda, Tatiana The lattice of integral flows and the lattice of integral cuts on a finite graph Bull. Soc. Math. France 1997 167 198

[3] Bai, Z. D. Circular law Ann. Probab. 1997 494 529

[4] Bai, Zhidong, Silverstein, Jack W. Spectral analysis of large dimensional random matrices 2010

[5] Balakin, G. V. The distribution of the rank of random matrices over a finite field Teor. Verojatnost. i Primenen. 1968 631 641

[6] Bhargava, Manjul The density of discriminants of quartic rings and fields Ann. of Math. (2) 2005 1031 1063

[7] Bhargava, Manjul, Kane, Daniel M., Lenstra, Hendrik W., Jr., Poonen, Bjorn, Rains, Eric Modeling the distribution of ranks, Selmer groups, and Shafarevich-Tate groups of elliptic curves Camb. J. Math. 2015 275 321

[8] Biggs, Norman Algebraic potential theory on graphs Bull. London Math. Soc. 1997 641 682

[9] Biggs, N. L. Chip-firing and the critical group of a graph J. Algebraic Combin. 1999 25 45

[10] Blömer, Johannes, Karp, Richard, Welzl, Emo The rank of sparse random matrices over finite fields Random Structures Algorithms 1997 407 419

[11] Bosch, Siegfried, Lorenzini, Dino Grothendieck’s pairing on component groups of Jacobians Invent. Math. 2002 353 396

[12] Björner, Anders, Lovász, László, Shor, Peter W. Chip-firing games on graphs European J. Combin. 1991 283 291

[13] Baker, Matthew, Norine, Serguei Riemann-Roch and Abel-Jacobi theory on a finite graph Adv. Math. 2007 766 788

[14] Baker, Matthew, Norine, Serguei Harmonic morphisms and hyperelliptic graphs Int. Math. Res. Not. IMRN 2009 2914 2955

[15] Brent, Richard P., Mckay, Brendan D. Determinants and ranks of random matrices over 𝑍ₘ Discrete Math. 1987 35 49

[16] Bak, Per, Tang, Chao, Wiesenfeld, Kurt Self-organized criticality Phys. Rev. A (3) 1988 364 374

[17] Bourgain, Jean, Vu, Van H., Wood, Philip Matchett On the singularity probability of discrete random matrices J. Funct. Anal. 2010 559 603

[18] Butler, Lynne M. A unimodality result in the enumeration of subgroups of a finite abelian group Proc. Amer. Math. Soc. 1987 771 775

[19] Cohen, H., Lenstra, H. W., Jr. Heuristics on class groups of number fields 1984 33 62

[20] Clancy, Julien, Kaplan, Nathan, Leake, Timothy, Payne, Sam, Wood, Melanie Matchett On a Cohen-Lenstra heuristic for Jacobians of random graphs J. Algebraic Combin. 2015 701 723

[21] Clancy, Julien, Leake, Timothy, Payne, Sam A note on Jacobians, Tutte polynomials, and two-variable zeta functions of graphs Exp. Math. 2015 1 7

[22] Cohen, Henri, Martinet, Jacques Étude heuristique des groupes de classes des corps de nombres J. Reine Angew. Math. 1990 39 76

[23] Cooper, C. On the rank of random matrices Random Structures Algorithms 2000 209 232

[24] Costello, Kevin P. Bilinear and quadratic variants on the Littlewood-Offord problem Israel J. Math. 2013 359 394

[25] Chandler, David B., Sin, Peter, Xiang, Qing The Smith and critical groups of Paley graphs J. Algebraic Combin. 2015 1013 1022

[26] Costello, Kevin P., Tao, Terence, Vu, Van Random symmetric matrices are almost surely nonsingular Duke Math. J. 2006 395 413

[27] Charlap, Leonard S., Rees, Howard D., Robbins, David P. The asymptotic probability that a random biased matrix is invertible Discrete Math. 1990 153 163

[28] Delaunay, Christophe Heuristics on Tate-Shafarevitch groups of elliptic curves defined over ℚ Experiment. Math. 2001 191 196

[29] Davenport, H., Heilbronn, H. On the density of discriminants of cubic fields. II Proc. Roy. Soc. London Ser. A 1971 405 420

[30] Dhar, Deepak Self-organized critical state of sandpile automaton models Phys. Rev. Lett. 1990 1613 1616

[31] Ducey, Joshua E., Jalil, Deelan M. Integer invariants of abelian Cayley graphs Linear Algebra Appl. 2014 316 325

[32] Durrett, Richard Probability: Theory and Examples 2007

[33] Ellenberg, Jordan S., Venkatesh, Akshay, Westerland, Craig Homological stability for Hurwitz spaces and the Cohen-Lenstra conjecture over function fields Ann. of Math. (2) 2016 729 786

[34] Fouvry, Étienne, Klüners, Jürgen Cohen-Lenstra heuristics of quadratic number fields 2006 40 55

[35] Fouvry, Étienne, Klüners, Jürgen On the 4-rank of class groups of quadratic number fields Invent. Math. 2007 455 513

[36] Friedman, Eduardo, Washington, Lawrence C. On the distribution of divisor class groups of curves over a finite field 1989 227 239

[37] Gabrielov, Andrei Abelian avalanches and Tutte polynomials Phys. A 1993 253 274

[38] Gabrielov, Andrei Avalanches, sandpiles and Tutte decomposition 1993 19 26

[39] Garton, Derek Random matrices and Cohen-Lenstra statistics for global fields with roots of unity 2012 73

[40] Gerth, Frank, Iii Densities for ranks of certain parts of 𝑝-class groups Proc. Amer. Math. Soc. 1987 1 8

[41] Gerth, Frank, Iii Extension of conjectures of Cohen and Lenstra Exposition. Math. 1987 181 184

[42] Girko, V. L. The circular law Teor. Veroyatnost. i Primenen. 1984 669 679

[43] Girko, V. L. The strong circular law. Twenty years later. II Random Oper. Stochastic Equations 2004 255 312

[44] Götze, F., Tikhomirov, A. N. Limit theorems for spectra of random matrices with martingale structure Teor. Veroyatn. Primen. 2006 171 192

[45] Götze, Friedrich, Tikhomirov, Alexander The circular law for random matrices Ann. Probab. 2010 1444 1491

[46] Heath-Brown, D. R. The size of Selmer groups for the congruent number problem. II Invent. Math. 1994 331 370

[47] Holroyd, Alexander E., Levine, Lionel, Mészáros, Karola, Peres, Yuval, Propp, James, Wilson, David B. Chip-firing and rotor-routing on directed graphs 2008 331 364

[48] Hillar, Christopher J., Rhea, Darren L. Automorphisms of finite abelian groups Amer. Math. Monthly 2007 917 923

[49] Horton, Matthew D., Stark, H. M., Terras, Audrey A. What are zeta functions of graphs and what are they good for? 2006 173 189

[50] Kahn, Jeff, Komlós, János Singularity probabilities for random matrices over finite fields Combin. Probab. Comput. 2001 137 157

[51] Kahn, Jeff, Komlós, János, Szemerédi, Endre On the probability that a random ±1-matrix is singular J. Amer. Math. Soc. 1995 223 240

[52] Kovalenko, I. N., Levitskaja, A. A. Limiting behavior of the number of solutions of a system of random linear equations over a finite field and a finite ring Dokl. Akad. Nauk SSSR 1975 778 781

[53] Kovalenko, I. N., Levit⋅Skaya, A. A., Savchuk, M. N. Izbrannye zadachi veroyatnostnoĭ kombinatoriki 1986 224

[54] Kozlov, M. V. On the rank of matrices with random Boolean elements Dokl. Akad. Nauk SSSR 1013 1016

[55] Komlós, J. On the determinant of (0,1) matrices Studia Sci. Math. Hungar. 1967 7 21

[56] Komlós, J. On the determinant of random matrices Studia Sci. Math. Hungar. 1968 387 399

[57] Merino López, Criel Chip firing and the Tutte polynomial Ann. Comb. 1997 253 259

[58] Lorenzini, Dino J. Arithmetical graphs Math. Ann. 1989 481 501

[59] Lorenzini, Dino J. A finite group attached to the Laplacian of a graph Discrete Math. 1991 277 282

[60] Lorenzini, Dino Arithmetical properties of Laplacians of graphs Linear and Multilinear Algebra 2000 281 306

[61] Lorenzini, Dino Smith normal form and Laplacians J. Combin. Theory Ser. B 2008 1271 1300

[62] Levine, Lionel, Propp, James What is … a sandpile? Notices Amer. Math. Soc. 2010 976 979

[63] Macwilliams, Jessie Orthogonal matrices over finite fields Amer. Math. Monthly 1969 152 164

[64] Malle, Gunter Cohen-Lenstra heuristic and roots of unity J. Number Theory 2008 2823 2835

[65] Malle, Gunter On the distribution of class groups of number fields Experiment. Math. 2010 465 474

[66] Mehta, M. L. Random matrices and the statistical theory of energy levels 1967

[67] Nguyen, Hoi H. Inverse Littlewood-Offord problems and the singularity of random symmetric matrices Duke Math. J. 2012 545 586

[68] Norine, Serguei, Whalen, Peter Jacobians of nearly complete and threshold graphs European J. Combin. 2011 1368 1376

[69] Pan, Guangming, Zhou, Wang Circular law, extreme singular values and potential theory J. Multivariate Anal. 2010 645 656

[70] Pastur, L. A. The spectrum of random matrices Teoret. Mat. Fiz. 1972 102 112

[71] Shokrieh, Farbod The monodromy pairing and discrete logarithm on the Jacobian of finite graphs J. Math. Cryptol. 2010 43 56

[72] Tao, Terence, Vu, Van On random ±1 matrices: singularity and determinant Random Structures Algorithms 2006 1 23

[73] Tao, Terence, Vu, Van On the singularity probability of random Bernoulli matrices J. Amer. Math. Soc. 2007 603 628

[74] Tao, Terence, Vu, Van Random matrices: the circular law Commun. Contemp. Math. 2008 261 307

[75] Tao, Terence, Vu, Van Random matrices: universality of ESDs and the circular law Ann. Probab. 2010 2023 2065

[76] Vershynin, Roman Invertibility of symmetric random matrices Random Structures Algorithms 2014 135 182

[77] Wigner, Eugene P. On the distribution of the roots of certain symmetric matrices Ann. of Math. (2) 1958 325 327