The distribution of sandpile groups of random graphs

Wood, Melanie

doi:10.1090/jams/866

The distribution of sandpile groups of random graphs
HTML articles powered by AMS MathViewer

by Melanie Matchett Wood

J. Amer. Math. Soc. 30 (2017), 915-958

DOI: https://doi.org/10.1090/jams/866

Published electronically: August 19, 2016

PDF | Request permission

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

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 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, DOI 10.24033/bsmf.2303
Z. D. Bai, Circular law, Ann. Probab. 25 (1997), no. 1, 494–529. MR 1428519, DOI 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, DOI 10.1007/978-1-4419-0661-8
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 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 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 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 10.1023/A:1018611014097
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 10.1002/(SICI)1098-2418(199707)10:4<407::AID-RSA1>3.0.CO;2-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 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 10.1016/S0195-6698(13)80111-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 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 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 10.1016/0012-365X(87)90117-8
Per Bak, Chao Tang, and Kurt Wiesenfeld, Self-organized criticality, Phys. Rev. A (3) 38 (1988), no. 1, 364–374. MR 949160, DOI 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 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 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 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 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 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 10.1002/(SICI)1098-2418(200003)16:2<209::AID-RSA6>3.3.CO;2-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 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 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 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 10.1016/0012-365X(90)90322-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, DOI 10.1080/10586458.2001.10504442
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 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 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 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 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 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 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 10.1016/0378-4371(93)90267-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 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 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 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 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 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 10.1007/978-3-7643-8786-0_{1}7
Christopher J. Hillar and Darren L. Rhea, Automorphisms of finite abelian groups, Amer. Math. Monthly 114 (2007), no. 10, 917–923. MR 2363058, DOI 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 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 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 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 10.1007/BF02558479
Dino J. Lorenzini, Arithmetical graphs, Math. Ann. 285 (1989), no. 3, 481–501. MR 1019714, DOI 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 10.1016/0012-365X(90)90236-B
Dino Lorenzini, Arithmetical properties of Laplacians of graphs, Linear and Multilinear Algebra 47 (2000), no. 4, 281–306. MR 1784872, DOI 10.1080/03081080008818652
Dino Lorenzini, Smith normal form and Laplacians, J. Combin. Theory Ser. B 98 (2008), no. 6, 1271–1300. MR 2462319, DOI 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 10.2307/2317262
Gunter Malle, Cohen-Lenstra heuristic and roots of unity, J. Number Theory 128 (2008), no. 10, 2823–2835. MR 2441080, DOI 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 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 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 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 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 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 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 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 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 10.1214/10-AOP534
Roman Vershynin, Invertibility of symmetric random matrices, Random Structures Algorithms 44 (2014), no. 2, 135–182. MR 3158627, DOI 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 10.2307/1970008