Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)

Request Permissions   Purchase Content 
 
 

 

The distribution of sandpile groups of random graphs


Author: Melanie Matchett Wood
Journal: J. Amer. Math. Soc. 30 (2017), 915-958
MSC (2010): Primary 05C80, 15B52, 60B20
DOI: https://doi.org/10.1090/jams/866
Published electronically: August 19, 2016
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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


References [Enhancements On Off] (What's this?)

  • [AV12] Carlos A. Alfaro and Carlos E. Valencia, On the sandpile group of the cone of a graph, Linear Algebra Appl. 436 (2012), no. 5, 1154-1176. MR 2890910, https://doi.org/10.1016/j.laa.2011.07.030
  • [BdlHN97] Roland Bacher, Pierre de la Harpe, and Tatiana Nagnibeda, The lattice of integral flows and the lattice of integral cuts on a finite graph, Bull. Soc. Math. France 125 (1997), no. 2, 167-198 (English, with English and French summaries). MR 1478029
  • [Bai97] Z. D. Bai, Circular law, Ann. Probab. 25 (1997), no. 1, 494-529. MR 1428519, https://doi.org/10.1214/aop/1024404298
  • [BS10] Zhidong Bai and Jack W. Silverstein, Spectral Analysis of Large Dimensional Random Matrices, 2nd ed., Springer Series in Statistics, Springer, New York, 2010. MR 2567175
  • [Bal68] G. V. Balakin, The distribution of the rank of random matrices over a finite field, Teor. Veroyatn. Primen. 13 (1968), 631-641 (Russian, with English summary). MR 0243571
  • [Bha05] Manjul Bhargava, The density of discriminants of quartic rings and fields, Ann. of Math. (2) 162 (2005), no. 2, 1031-1063. MR 2183288, https://doi.org/10.4007/annals.2005.162.1031
  • [BKLj$^+$13] Manjul Bhargava, Daniel M. Kane, Lenstra Hendrik W., Bjorn Poonen, and Eric Rains, Modeling the distribution of ranks, Selmer groups, and Shafarevich-Tate groups of elliptic curves, Camb. J. Math. 3 (2015), no. 3, 275-321. MR 3393023, https://doi.org/10.4310/CJM.2015.v3.n3.a1
  • [Big97] Norman Biggs, Algebraic potential theory on graphs, Bull. Lond. Math. Soc. 29 (1997), no. 6, 641-682. MR 1468054, https://doi.org/10.1112/S0024609397003305
  • [Big99] N. L. Biggs, Chip-firing and the critical group of a graph, J. Algebraic Combin. 9 (1999), no. 1, 25-45. MR 1676732, https://doi.org/10.1023/A:1018611014097
  • [BKW97] Johannes Blömer, Richard Karp, and Emo Welzl, The rank of sparse random matrices over finite fields, Random Structures Algorithms 10 (1997), no. 4, 407-419. MR 1608234, https://doi.org/10.1002/(SICI)1098-2418(199707)10:4$ \langle $407::AID-RSA1$ \rangle $3.0.CO;2-Y
  • [BL02] Siegfried Bosch and Dino Lorenzini, Grothendieck's pairing on component groups of Jacobians, Invent. Math. 148 (2002), no. 2, 353-396. MR 1906153, https://doi.org/10.1007/s002220100195
  • [BLS91] Anders Björner, László Lovász, and Peter W. Shor, Chip-firing games on graphs, European J. Combin. 12 (1991), no. 4, 283-291. MR 1120415, https://doi.org/10.1016/S0195-6698(13)80111-4
  • [BN07] Matthew Baker and Serguei Norine, Riemann-Roch and Abel-Jacobi theory on a finite graph, Adv. Math. 215 (2007), no. 2, 766-788. MR 2355607, https://doi.org/10.1016/j.aim.2007.04.012
  • [BN09] Matthew Baker and Serguei Norine, Harmonic morphisms and hyperelliptic graphs, Int. Math. Res. Not. IMRN 15 (2009), 2914-2955. MR 2525845, https://doi.org/10.1093/imrn/rnp037
  • [BM87] Richard P. Brent and Brendan D. McKay, Determinants and ranks of random matrices over $ Z_m$, Discrete Math. 66 (1987), no. 1-2, 35-49. MR 900928, https://doi.org/10.1016/0012-365X(87)90117-8
  • [BTW88] Per Bak, Chao Tang, and Kurt Wiesenfeld, Self-organized criticality, Phys. Rev. A (3) 38 (1988), no. 1, 364-374. MR 949160, https://doi.org/10.1103/PhysRevA.38.364
  • [BVW10] Jean Bourgain, Van H. Vu, and Philip Matchett Wood, On the singularity probability of discrete random matrices, J. Funct. Anal. 258 (2010), no. 2, 559-603. MR 2557947, https://doi.org/10.1016/j.jfa.2009.04.016
  • [But87] Lynne M. Butler, A unimodality result in the enumeration of subgroups of a finite abelian group, Proc. Amer. Math. Soc. 101 (1987), no. 4, 771-775. MR 911049, https://doi.org/10.2307/2046687
  • [CL84] H. Cohen and H. W. Lenstra Jr., Heuristics on Class Groups of Number Fields, Number theory, Noordwijkerhout 1983 (Noordwijkerhout, 1983) Lecture Notes in Math., vol. 1068, Springer, Berlin, 1984, pp. 33-62. MR 756082, https://doi.org/10.1007/BFb0099440
  • [CLK$^+$14] Julien Clancy, Nathan Kaplan, Timothy Leake, Sam Payne, and Melanie Matchett Wood, On a Cohen-Lenstra heuristic for Jacobians of random graphs, J. Algebraic Combin. 42 (2015), no. 3, 701-723. MR 3403177, https://doi.org/10.1007/s10801-015-0598-x
  • [CLP13] Julien Clancy, Timothy Leake, and Sam Payne, A note on Jacobians, Tutte polynomials, and two-variable zeta functions of graphs, Exp. Math. 24 (2015), no. 1, 1-7. MR 3305035, https://doi.org/10.1080/10586458.2014.917443
  • [CM90] Henri Cohen and Jacques Martinet, Étude heuristique des groupes de classes des corps de nombres, J. Reine Angew. Math. 404 (1990), 39-76 (French). MR 1037430
  • [Coo00] C. Cooper, On the rank of random matrices, Random Structures Algorithms 16 (2000), no. 2, 209-232. MR 1742352, https://doi.org/10.1002/(SICI)1098-2418(200003)16:2$ \langle $209::AID-RSA6$ \rangle $3.3.CO;2-T
  • [Cos13] Kevin P. Costello, Bilinear and quadratic variants on the Littlewood-Offord problem, Israel J. Math. 194 (2013), no. 1, 359-394. MR 3047075, https://doi.org/10.1007/s11856-012-0082-4
  • [CSX14] David B. Chandler, Peter Sin, and Qing Xiang, The Smith and critical groups of Paley graphs, J. Algebraic Combin. 41 (2015), no. 4, 1013-1022. MR 3342710, https://doi.org/10.1007/s10801-014-0563-0
  • [CTV06] Kevin P. Costello, Terence Tao, and Van Vu, Random symmetric matrices are almost surely nonsingular, Duke Math. J. 135 (2006), no. 2, 395-413. MR 2267289, https://doi.org/10.1215/S0012-7094-06-13527-5
  • [CRR90] Leonard S. Charlap, Howard D. Rees, and David P. Robbins, The asymptotic probability that a random biased matrix is invertible, Discrete Math. 82 (1990), no. 2, 153-163. MR 1057484, https://doi.org/10.1016/0012-365X(90)90322-9
  • [Del01] Christophe Delaunay, Heuristics on Tate-Shafarevitch groups of elliptic curves defined over $ \mathbb{Q}$, Experiment. Math. 10 (2001), no. 2, 191-196. MR 1837670
  • [DH71] H. Davenport and H. Heilbronn, On the density of discriminants of cubic fields. II, Proc. R. Soc. Lond. Ser. A 322 (1971), no. 1551, 405-420. MR 0491593
  • [Dha90] Deepak Dhar, Self-organized critical state of sandpile automaton models, Phys. Rev. Lett. 64 (1990), no. 14, 1613-1616. MR 1044086, https://doi.org/10.1103/PhysRevLett.64.1613
  • [DJ13] Joshua E. Ducey and Deelan M. Jalil, Integer invariants of abelian Cayley graphs, Linear Algebra Appl. 445 (2014), 316-325. MR 3151277, https://doi.org/10.1016/j.laa.2013.12.004
  • [Dur07] Richard Durrett, Probability: Theory and Examples, World Publishing Co., Beijing, 2007.
  • [EVW16] Jordan S. Ellenberg, Akshay Venkatesh, and Craig Westerland, Homological stability for Hurwitz spaces and the Cohen-Lenstra conjecture over function fields, Ann. of Math. (2) 183 (2016), no. 3, 729-786. MR 3488737, https://doi.org/10.4007/annals.2016.183.3.1
  • [EVW12] Jordan Ellenberg, Akshay Venkatesh, and Craig Westerland,
    Homological stability for Hurwitz spaces and the Cohen Lenstra conjecture over function fields, II.
    arXiv:1212.0923, 2012.
  • [FK06] Étienne Fouvry and Jürgen Klüners, Cohen-Lenstra heuristics of quadratic number fields, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 4076, Springer, Berlin, 2006, pp. 40-55. MR 2282914, https://doi.org/10.1007/11792086_4
  • [FK07] Étienne Fouvry and Jürgen Klüners, On the 4-rank of class groups of quadratic number fields, Invent. Math. 167 (2007), no. 3, 455-513. MR 2276261, https://doi.org/10.1007/s00222-006-0021-2
  • [FW89] Eduardo Friedman and Lawrence C. Washington, On the distribution of divisor class groups of curves over a finite field, Théorie des nombres (Quebec, PQ, 1987) de Gruyter, Berlin, 1989, pp. 227-239. MR 1024565
  • [Gab93a] Andrei Gabrielov, Abelian avalanches and Tutte polynomials, Phys. A 195 (1993), no. 1-2, 253-274. MR 1215018, https://doi.org/10.1016/0378-4371(93)90267-8
  • [Gab93b] Andrei Gabrielov, Avalanches, sandpiles and Tutte decomposition, The Gelfand Mathematical Seminars, 1990-1992, Birkhäuser Boston, Boston, MA, 1993, pp. 19-26. MR 1247281
  • [Gar12] Derek Garton, Random matrices and Cohen-Lenstra statistics for global fields with roots of unity, ProQuest LLC, Ann Arbor, MI, 2012. Thesis (Ph.D.)-The University of Wisconsin-Madison. MR 3078415
  • [Ger87a] Frank Gerth III, Densities for ranks of certain parts of $ p$-class groups, Proc. Amer. Math. Soc. 99 (1987), no. 1, 1-8. MR 866419, https://doi.org/10.2307/2046260
  • [Ger87b] Frank Gerth III, Extension of conjectures of Cohen and Lenstra, Expo. Math. 5 (1987), no. 2, 181-184. MR 887792
  • [Gir84] V. L. Girko, The circular law, Teor. Veroyatn. Primen. 29 (1984), no. 4, 669-679 (Russian). MR 773436
  • [Gir04] V. L. Girko, The strong circular law. Twenty years later. II, Random Oper. Stoch. Equ. 12 (2004), no. 3, 255-312. MR 2085255, https://doi.org/10.1163/1569397042222477
  • [GT06] F. Götze and A. N. Tikhomirov, Limit theorems for spectra of random matrices with martingale structure, Teor. Veroyatn. Primen. 51 (2006), no. 1, 171-192 (English, with Russian summary); English transl., Theory Probab. Appl. 51 (2007), no. 1, 42-64. MR 2324173, https://doi.org/10.1137/S0040585X97982268
  • [GT10] Friedrich Götze and Alexander Tikhomirov, The circular law for random matrices, Ann. Probab. 38 (2010), no. 4, 1444-1491. MR 2663633, https://doi.org/10.1214/09-AOP522
  • [HB94a] D. R. Heath-Brown.
    The size of Selmer groups for the congruent number problem, II.
    118 (1994).
    preprint version, http://eprints.maths.ox.ac.uk/154/.
  • [HB94b] D. R. Heath-Brown, The size of Selmer groups for the congruent number problem. II, Invent. Math. 118 (1994), no. 2, 331-370. With an appendix by P. Monsky. MR 1292115, https://doi.org/10.1007/BF01231536
  • [HLM$^+$] Alexander E. Holroyd, Lionel Levine, Karola Mészáros, Yuval Peres, James Propp, and David B. Wilson, Chip-firing and rotor-routing on directed graphs, In and out of equilibrium. 2, Progr. Probab., vol. 60, Birkhäuser, Basel, 2008, pp. 331-364. MR 2477390, https://doi.org/10.1007/978-3-7643-8786-0_17
  • [HR07] Christopher J. Hillar and Darren L. Rhea, Automorphisms of finite abelian groups, Amer. Math. Monthly 114 (2007), no. 10, 917-923. MR 2363058
  • [HST06] Matthew D. Horton, H. M. Stark, and Audrey A. Terras, What are zeta functions of graphs and what are they good for?, Quantum graphs and their applications, Contemp. Math., vol. 415, Amer. Math. Soc., Providence, RI, 2006, pp. 173-189. MR 2277616, https://doi.org/10.1090/conm/415/07868
  • [KK01] Jeff Kahn and János Komlós, Singularity probabilities for random matrices over finite fields, Combin. Probab. Comput. 10 (2001), no. 2, 137-157. MR 1833067, https://doi.org/10.1017/S096354830100462X
  • [KKS95] Jeff Kahn, János Komlós, and Endre Szemerédi, On the probability that a random $ \pm 1$-matrix is singular, J. Amer. Math. Soc. 8 (1995), no. 1, 223-240. MR 1260107, https://doi.org/10.2307/2152887
  • [KL75] I. N. Kovalenko and A. A. Levitskaya, 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 221 (1975), no. 4, 778-781 (Russian). MR 0380957
  • [KLS86] I. N. Kovalenko, A. A. Levitskaya, and M. N. Savchuk, Izbrannye zadachi veroyatnostnoi kombinatoriki, ``Naukova Dumka,'' Kiev, 1986 (Russian). MR 899073
  • [Koz66] M. V. Kozlov, On the rank of matrices with random Boolean elements, Sov. Math. Dokl. 7 (1966), 1048-1051. MR 0224119
  • [Kom67] J. Komlós, On the determinant of $ (0,\,1)$ matrices, Studia Sci. Math. Hungar. 2 (1967), 7-21. MR 0221962
  • [Kom68] J. Komlós, On the determinant of random matrices, Studia Sci. Math. Hungar. 3 (1968), 387-399. MR 0238371
  • [L97] Criel Merino López, Chip firing and the Tutte polynomial, Ann. Comb. 1 (1997), no. 3, 253-259. MR 1630779, https://doi.org/10.1007/BF02558479
  • [Lor89] Dino J. Lorenzini, Arithmetical graphs, Math. Ann. 285 (1989), no. 3, 481-501. MR 1019714, https://doi.org/10.1007/BF01455069
  • [Lor90] Dino J. Lorenzini, A finite group attached to the Laplacian of a graph, Discrete Math. 91 (1991), no. 3, 277-282. MR 1129991, https://doi.org/10.1016/0012-365X(90)90236-B
  • [Lor00] Dino Lorenzini, Arithmetical properties of Laplacians of graphs, Linear Multilinear Algebra 47 (2000), no. 4, 281-306. MR 1784872, https://doi.org/10.1080/03081080008818652
  • [Lor08] Dino Lorenzini, Smith normal form and Laplacians, J. Combin. Theory Ser. B 98 (2008), no. 6, 1271-1300. MR 2462319, https://doi.org/10.1016/j.jctb.2008.02.002
  • [LP10] Lionel Levine and James Propp, What is $ \dots $ a sandpile?, Notices Amer. Math. Soc. 57 (2010), no. 8, 976-979. MR 2667495
  • [Mac69] Jessie MacWilliams, Orthogonal matrices over finite fields, Amer. Math. Monthly 76 (1969), 152-164. MR 0238870
  • [Mal08] Gunter Malle, Cohen-Lenstra heuristic and roots of unity, J. Number Theory 128 (2008), no. 10, 2823-2835. MR 2441080, https://doi.org/10.1016/j.jnt.2008.01.002
  • [Mal10] Gunter Malle, On the distribution of class groups of number fields, Experiment. Math. 19 (2010), no. 4, 465-474. MR 2778658, https://doi.org/10.1080/10586458.2010.10390636
  • [Map10] Kenneth Maples,
    Singularity of random matrices over finite fields.
    arXiv:1012.2372[math], December 2010.
  • [Map13] Kenneth Maples,
    Cokernels of random matrices satisfy the Cohen-Lenstra heuristics, 2013.
    arXiv:1301.1239.
  • [Meh67] M. L. Mehta, Random Matrices and the Statistical Theory of Energy Levels, Academic Press, New York-London, 1967. MR 0220494
  • [Ngu12] Hoi H. Nguyen, Inverse Littlewood-Offord problems and the singularity of random symmetric matrices, Duke Math. J. 161 (2012), no. 4, 545-586. MR 2891529, https://doi.org/10.1215/00127094-1548344
  • [NW11] Serguei Norine and Peter Whalen, Jacobians of nearly complete and threshold graphs, European J. Combin. 32 (2011), no. 8, 1368-1376. MR 2838022, https://doi.org/10.1016/j.ejc.2011.04.003
  • [PZ10] Guangming Pan and Wang Zhou, Circular law, extreme singular values and potential theory, J. Multivariate Anal. 101 (2010), no. 3, 645-656. MR 2575411, https://doi.org/10.1016/j.jmva.2009.08.005
  • [Pas72] L. A. Pastur, The spectrum of random matrices, Teoret. Mat. Fiz. 10 (1972), no. 1, 102-112 (Russian, with English summary). MR 0475502
  • [Sho10] Farbod Shokrieh, The monodromy pairing and discrete logarithm on the Jacobian of finite graphs, J. Math. Cryptol. 4 (2010), no. 1, 43-56. MR 2660333, https://doi.org/10.1515/JMC.2010.002
  • [TV06] Terence Tao and Van Vu, On random $ \pm 1$ matrices: singularity and determinant, Random Structures Algorithms 28 (2006), no. 1, 1-23. MR 2187480, https://doi.org/10.1002/rsa.20109
  • [TV07] Terence Tao and Van Vu, On the singularity probability of random Bernoulli matrices, J. Amer. Math. Soc. 20 (2007), no. 3, 603-628. MR 2291914, https://doi.org/10.1090/S0894-0347-07-00555-3
  • [TV08] Terence Tao and Van Vu, Random matrices: the circular law, Commun. Contemp. Math. 10 (2008), no. 2, 261-307. MR 2409368, https://doi.org/10.1142/S0219199708002788
  • [TV10] Terence Tao and Van Vu, Random matrices: universality of ESDs and the circular law, Ann. Probab. 38 (2010), no. 5, 2023-2065. With an appendix by Manjunath Krishnapur. MR 2722794, https://doi.org/10.1214/10-AOP534
  • [Ver11] Roman Vershynin, Invertibility of symmetric random matrices, Random Structures Algorithms 44 (2014), no. 2, 135-182. MR 3158627, https://doi.org/10.1002/rsa.20429
  • [Wag00] David G. Wagner.
    The critical group of a directed graph.
    arXiv:math/0010241, October 2000.
  • [Wig58] Eugene P. Wigner, On the distribution of the roots of certain symmetric matrices, Ann. of Math. (2) 67 (1958), 325-327. MR 0095527

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2010): 05C80, 15B52, 60B20

Retrieve articles in all journals with MSC (2010): 05C80, 15B52, 60B20


Additional Information

Melanie Matchett Wood
Affiliation: 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
Email: mmwood@math.wisc.edu

DOI: https://doi.org/10.1090/jams/866
Received by editor(s): October 21, 2014
Received by editor(s) in revised form: April 21, 2016, July 6, 2016, and July 17, 2016
Published electronically: August 19, 2016
Additional Notes: This work was done with the support of an American Institute of Mathematics Five-Year Fellowship, a Packard Fellowship for Science and Engineering, a Sloan Research Fellowship, and National Science Foundation grants DMS-1147782 and DMS-1301690.
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society