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
MathSciNet review:
3671933
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.
- 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, DOI https://doi.org/10.1016/j.laa.2011.07.030
- 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
- Z. D. Bai, Circular law, Ann. Probab. 25 (1997), no. 1, 494–529. MR 1428519, DOI https://doi.org/10.1214/aop/1024404298
- 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
- G. V. Balakin, The distribution of the rank of random matrices over a finite field., Teor. Verojatnost. i Primenen. 13 (1968), 631–641 (Russian, with English summary). MR 0243571
- Manjul Bhargava, The density of discriminants of quartic rings and fields, Ann. of Math. (2) 162 (2005), no. 2, 1031–1063. MR 2183288, DOI https://doi.org/10.4007/annals.2005.162.1031
- Manjul Bhargava, Daniel M. Kane, Hendrik W. Lenstra Jr., 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, DOI https://doi.org/10.4310/CJM.2015.v3.n3.a1
- Norman Biggs, Algebraic potential theory on graphs, Bull. London Math. Soc. 29 (1997), no. 6, 641–682. MR 1468054, DOI https://doi.org/10.1112/S0024609397003305
- N. L. Biggs, Chip-firing and the critical group of a graph, J. Algebraic Combin. 9 (1999), no. 1, 25–45. MR 1676732, DOI https://doi.org/10.1023/A%3A1018611014097
- 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, DOI https://doi.org/10.1002/%28SICI%291098-2418%28199707%2910%3A4%3C407%3A%3AAID-RSA1%3E3.0.CO%3B2-Y
- Siegfried Bosch and Dino Lorenzini, Grothendieck’s pairing on component groups of Jacobians, Invent. Math. 148 (2002), no. 2, 353–396. MR 1906153, DOI https://doi.org/10.1007/s002220100195
- 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, DOI https://doi.org/10.1016/S0195-6698%2813%2980111-4
- 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, DOI https://doi.org/10.1016/j.aim.2007.04.012
- Matthew Baker and Serguei Norine, Harmonic morphisms and hyperelliptic graphs, Int. Math. Res. Not. IMRN 15 (2009), 2914–2955. MR 2525845, DOI https://doi.org/10.1093/imrn/rnp037
- 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, DOI https://doi.org/10.1016/0012-365X%2887%2990117-8
- Per Bak, Chao Tang, and Kurt Wiesenfeld, Self-organized criticality, Phys. Rev. A (3) 38 (1988), no. 1, 364–374. MR 949160, DOI https://doi.org/10.1103/PhysRevA.38.364
- 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, DOI https://doi.org/10.1016/j.jfa.2009.04.016
- 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, DOI https://doi.org/10.1090/S0002-9939-1987-0911049-8
- 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, DOI https://doi.org/10.1007/BFb0099440
- 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, DOI https://doi.org/10.1007/s10801-015-0598-x
- 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, DOI https://doi.org/10.1080/10586458.2014.917443
- 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
- C. Cooper, On the rank of random matrices, Random Structures Algorithms 16 (2000), no. 2, 209–232. MR 1742352, DOI https://doi.org/10.1002/%28SICI%291098-2418%28200003%2916%3A2%3C209%3A%3AAID-RSA6%3E3.3.CO%3B2-T
- Kevin P. Costello, Bilinear and quadratic variants on the Littlewood-Offord problem, Israel J. Math. 194 (2013), no. 1, 359–394. MR 3047075, DOI https://doi.org/10.1007/s11856-012-0082-4
- 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, DOI https://doi.org/10.1007/s10801-014-0563-0
- 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, DOI https://doi.org/10.1215/S0012-7094-06-13527-5
- 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, DOI https://doi.org/10.1016/0012-365X%2890%2990322-9
- Christophe Delaunay, Heuristics on Tate-Shafarevitch groups of elliptic curves defined over $\Bbb Q$, Experiment. Math. 10 (2001), no. 2, 191–196. MR 1837670
- H. Davenport and H. Heilbronn, On the density of discriminants of cubic fields. II, Proc. Roy. Soc. London Ser. A 322 (1971), no. 1551, 405–420. MR 491593, DOI https://doi.org/10.1098/rspa.1971.0075
- Deepak Dhar, Self-organized critical state of sandpile automaton models, Phys. Rev. Lett. 64 (1990), no. 14, 1613–1616. MR 1044086, DOI https://doi.org/10.1103/PhysRevLett.64.1613
- Joshua E. Ducey and Deelan M. Jalil, Integer invariants of abelian Cayley graphs, Linear Algebra Appl. 445 (2014), 316–325. MR 3151277, DOI https://doi.org/10.1016/j.laa.2013.12.004
- Richard Durrett, Probability: Theory and Examples, World Publishing Co., Beijing, 2007.
- 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, DOI https://doi.org/10.4007/annals.2016.183.3.1
- 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.
- É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, DOI https://doi.org/10.1007/11792086_4
- É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, DOI https://doi.org/10.1007/s00222-006-0021-2
- 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
- Andrei Gabrielov, Abelian avalanches and Tutte polynomials, Phys. A 195 (1993), no. 1-2, 253–274. MR 1215018, DOI https://doi.org/10.1016/0378-4371%2893%2990267-8
- Andrei Gabrielov, Avalanches, sandpiles and Tutte decomposition, The Gel′fand Mathematical Seminars, 1990–1992, Birkhäuser Boston, Boston, MA, 1993, pp. 19–26. MR 1247281
- 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
- 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, DOI https://doi.org/10.1090/S0002-9939-1987-0866419-3
- Frank Gerth III, Extension of conjectures of Cohen and Lenstra, Exposition. Math. 5 (1987), no. 2, 181–184. MR 887792
- V. L. Girko, The circular law, Teor. Veroyatnost. i Primenen. 29 (1984), no. 4, 669–679 (Russian). MR 773436
- V. L. Girko, The strong circular law. Twenty years later. II, Random Oper. Stochastic Equations 12 (2004), no. 3, 255–312. MR 2085255, DOI https://doi.org/10.1163/1569397042222477
- 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, DOI https://doi.org/10.1137/S0040585X97982268
- Friedrich Götze and Alexander Tikhomirov, The circular law for random matrices, Ann. Probab. 38 (2010), no. 4, 1444–1491. MR 2663633, DOI https://doi.org/10.1214/09-AOP522
- 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/.
- 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, DOI https://doi.org/10.1007/BF01231536
- 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, DOI https://doi.org/10.1007/978-3-7643-8786-0_17
- Christopher J. Hillar and Darren L. Rhea, Automorphisms of finite abelian groups, Amer. Math. Monthly 114 (2007), no. 10, 917–923. MR 2363058, DOI https://doi.org/10.1080/00029890.2007.11920485
- 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, DOI https://doi.org/10.1090/conm/415/07868
- 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, DOI https://doi.org/10.1017/S096354830100462X
- 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, DOI https://doi.org/10.1090/S0894-0347-1995-1260107-2
- I. N. Kovalenko and A. A. Levitskaja, 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
- I. N. Kovalenko, A. A. Levit⋅skaya, and M. N. Savchuk, Izbrannye zadachi veroyatnostnoĭ kombinatoriki, “Naukova Dumka”, Kiev, 1986 (Russian). MR 899073
- M. V. Kozlov, On the rank of matrices with random Boolean elements, Soviet Math. Dokl. 7 (1966), 1048–1051. MR 0224119
- J. Komlós, On the determinant of $(0,\,1)$ matrices, Studia Sci. Math. Hungar. 2 (1967), 7–21. MR 221962
- J. Komlós, On the determinant of random matrices, Studia Sci. Math. Hungar. 3 (1968), 387–399. MR 238371
- Criel Merino López, Chip firing and the Tutte polynomial, Ann. Comb. 1 (1997), no. 3, 253–259. MR 1630779, DOI https://doi.org/10.1007/BF02558479
- Dino J. Lorenzini, Arithmetical graphs, Math. Ann. 285 (1989), no. 3, 481–501. MR 1019714, DOI https://doi.org/10.1007/BF01455069
- Dino J. Lorenzini, A finite group attached to the Laplacian of a graph, Discrete Math. 91 (1991), no. 3, 277–282. MR 1129991, DOI https://doi.org/10.1016/0012-365X%2890%2990236-B
- Dino Lorenzini, Arithmetical properties of Laplacians of graphs, Linear and Multilinear Algebra 47 (2000), no. 4, 281–306. MR 1784872, DOI https://doi.org/10.1080/03081080008818652
- Dino Lorenzini, Smith normal form and Laplacians, J. Combin. Theory Ser. B 98 (2008), no. 6, 1271–1300. MR 2462319, DOI https://doi.org/10.1016/j.jctb.2008.02.002
- Lionel Levine and James Propp, What is $\dots $ a sandpile?, Notices Amer. Math. Soc. 57 (2010), no. 8, 976–979. MR 2667495
- Jessie MacWilliams, Orthogonal matrices over finite fields, Amer. Math. Monthly 76 (1969), 152–164. MR 238870, DOI https://doi.org/10.2307/2317262
- Gunter Malle, Cohen-Lenstra heuristic and roots of unity, J. Number Theory 128 (2008), no. 10, 2823–2835. MR 2441080, DOI https://doi.org/10.1016/j.jnt.2008.01.002
- Gunter Malle, On the distribution of class groups of number fields, Experiment. Math. 19 (2010), no. 4, 465–474. MR 2778658, DOI https://doi.org/10.1080/10586458.2010.10390636
- Kenneth Maples, Singularity of random matrices over finite fields. arXiv:1012.2372[math], December 2010.
- Kenneth Maples, Cokernels of random matrices satisfy the Cohen-Lenstra heuristics, 2013. arXiv:1301.1239.
- M. L. Mehta, Random matrices and the statistical theory of energy levels, Academic Press, New York-London, 1967. MR 0220494
- 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, DOI https://doi.org/10.1215/00127094-1548344
- Serguei Norine and Peter Whalen, Jacobians of nearly complete and threshold graphs, European J. Combin. 32 (2011), no. 8, 1368–1376. MR 2838022, DOI https://doi.org/10.1016/j.ejc.2011.04.003
- Guangming Pan and Wang Zhou, Circular law, extreme singular values and potential theory, J. Multivariate Anal. 101 (2010), no. 3, 645–656. MR 2575411, DOI https://doi.org/10.1016/j.jmva.2009.08.005
- L. A. Pastur, The spectrum of random matrices, Teoret. Mat. Fiz. 10 (1972), no. 1, 102–112 (Russian, with English summary). MR 475502
- 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, DOI https://doi.org/10.1515/JMC.2010.002
- Terence Tao and Van Vu, On random $\pm 1$ matrices: singularity and determinant, Random Structures Algorithms 28 (2006), no. 1, 1–23. MR 2187480, DOI https://doi.org/10.1002/rsa.20109
- 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, DOI https://doi.org/10.1090/S0894-0347-07-00555-3
- Terence Tao and Van Vu, Random matrices: the circular law, Commun. Contemp. Math. 10 (2008), no. 2, 261–307. MR 2409368, DOI https://doi.org/10.1142/S0219199708002788
- 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, DOI https://doi.org/10.1214/10-AOP534
- Roman Vershynin, Invertibility of symmetric random matrices, Random Structures Algorithms 44 (2014), no. 2, 135–182. MR 3158627, DOI https://doi.org/10.1002/rsa.20429
- David G. Wagner. The critical group of a directed graph. arXiv:math/0010241, October 2000.
- Eugene P. Wigner, On the distribution of the roots of certain symmetric matrices, Ann. of Math. (2) 67 (1958), 325–327. MR 95527, DOI https://doi.org/10.2307/1970008
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
MR Author ID:
709533
Email:
mmwood@math.wisc.edu
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
