The Distribution of Sandpile Groups of Random Graphs with their Pairings

We refer the reader to “What is… a sandpile?” [37] for an overview of sandpile groups. The article [48] also gives an outline of the ways in which sandpile groups are connected to various disparate subjects. While there are many equivalent definitions of the sandpile group of a graph $\Gamma$, perhaps the easiest is the following. Suppose $\Gamma$ is a simple graph with $n$ vertices labeled by the first $n$ integers. The Laplacian of $\Gamma$, denoted $L_{\Gamma}$, is the $n\times n$ matrix whose $(i,j)$ entry is given by

The reduced Laplacian of $\Gamma$, denoted $\Delta_{\Gamma}$, is the $(n-1)\times(n-1)$ matrix given by deleting the final row and column from $L_{\Gamma}$. We define the sandpile group of $\Gamma$, denoted $S_{\Gamma}$, to be the cokernel of the reduced Laplacian $\Delta_{\Gamma}$ of $\Gamma$. We remark here that the sandpile group does not depend on the row or column removed from $L_{\Gamma}$—the cokernels of the matrices given by deleting any row or column of $L_{\Gamma}$ are all isomorphic (see [10, 18]). From this definition, it follows immediately that if $\Gamma$ is connected, then $|S_{\Gamma}|=|\det(\Delta_{\Gamma})|$; Kirchhoff’s matrix tree theorem implies that $|S_{\Gamma}|$ is the number of spanning trees of $\Gamma$. Alternatively, if $Z\subset\mathbb{Z}^{n}$ denotes the subspace of vectors whose coordinates sum to 0, then it is equivalent to define $S_{\Gamma}$ as $S_{\Gamma}=Z/L_{\Gamma}\mathbb{Z}$.

Sandpile groups were first studied in 1988 by statistical physicists interested in the dynamics of a sandpile [4]; thus originating the name “sandpile.” The sandpile model is an example of a chip-firing game (see [12]): given a graph $\Gamma$, we imagine that on each vertex is some number of chips; if a vertex has at least as many chips as its degree, the chips topple, distributing a chip to each neighboring vertex. Supposing that chips fall randomly onto the vertices of $\Gamma$, toppling whenever they can, the sandpile group of $\Gamma$ is given by the recurrent states of the resulting Markov chain. For more in depth treatments, we refer the reader to [22, 25, 26, 11]. There is also a nice connection between sandpile groups and the Tutte polynomial of a graph; see [39, 25, 26]. An overview of these connections can be found in [31].

The sandpile group of a graph has also been referred to in the literature as the Jacobian (also the Picard group or critical group) of the graph. This moniker originates from a beautiful analogy between Riemann surfaces and graphs, in which the sandpile group corresponds to the Jacobian of a Riemann surface [10, 1]. This analogy is not purely philosophical and is spelled out in detail in [40, 13], where the group of components of the Néron model of the Jacobian of a curve over a local field is realized as the sandpile group of a graph. Moreover, the cardinality of the sandpile group occurs in the “analytic class number formula” for graphs [32], and there also exist analogs of the Riemann-Roch and Riemann-Hurwitz formulas for Jacobians of graphs [5, 6].

Sandpile groups of connected graphs are canonically equipped with a perfect, symmetric bilinear pairing (see [41, 13]), which is given by any generalized inverse of the Laplacian (see [51]). If the graph is not connected, then only the torsion subgroup of the sandpile group carries such a duality pairing. We will show in Section 3 that the duality pairing on $\widehat{S_{\Gamma}}$ induced by the pairing on $S_{\Gamma}$ can be described directly using the Laplacian of the graph. In the Riemann surface analogy, the pairing on $S_{\Gamma}$ has been considered as an analog of the Weil pairing [51] and also agrees with a pairing defined by Grothendieck [29, 30] giving an obstruction to extending the Poincaré bundle to the product of an abelian variety and its dual [13].

For a family of random finite abelian groups, a natural first guess for how the groups should be distributed is the Cohen-Lenstra heuristics [17], which conjecture the distribution of ideal class groups of quadratic number fields. Ideal class groups are finite abelian groups measuring the failure of unique factorization in rings of integers of number fields (e.g., $\mathbb{Z}[\sqrt{-5}]$). The underlying philosophy behind the Cohen-Lenstra heuristics is that objects “in nature” often occur with frequency that is inversely proportional to their number of automorphisms. Hence, in the case of finite abelian groups, given a random finite abelian group $X$ and a fixed finite abelian group $G$, a priori we expect $\operatorname{\mathbb{P}}(X\simeq G)$ to be inversely proportional to $|\operatorname{\mathrm{Aut}}(G)|$.

However, Wood showed in [54] that sandpile groups of random graphs do not satisfy a Cohen-Lenstra heuristic. Instead, Wood proved that they obey a “Cohen-Lenstra-like” distribution, in which the canonical duality pairing on the group influences the way in which they are distributed. Notably, Wood’s result is what we obtain by summing the conjectural distribution of random sandpile groups with their pairings due to Clancy, Leake, and Payne [16] over all possible pairings on a given group. Similarly, Tate-Shafarevich groups of elliptic curves are a class of conjecturally finite and abelian groups that, if finite, also come equipped with a nondegenerate, bilinear pairing. Unlike sandpile groups, the pairing on Tate-Shafarevich groups is alternating rather than symmetric. Delaunay developed heuristics [21, 8] similar to those of Clancy, Leake, and Payne in which the automorphisms of $G$ preserving the pairing take the place of $\operatorname{\mathrm{Aut}}(G)$.

While the distribution of sandpile groups of random graphs with their pairings is intriguing in its own right, our methods may give insight into how to approach other similar problems in both random group theory and arithmetic statistics. Recently, Lipnowski, Sawin, and Tsimerman showed in [38] that, in some cases, class groups of quadratic number fields come equipped with a bilinear structure closely related to the Weil pairing on abelian varieties and the aforementioned Cassels-Tate pairing on Tate-Shafarevich groups. It may be possible that the methods developed in this paper to deal with the pairing on the sandpile group can be used to determine the distribution of other families of random groups with pairings.

The Laplacian is a matrix with integral entries, so if $\Gamma$ is an Erdős-Rényi random graph, we inevitably find ourselves working in the realm of random matrix theory, a field in which significant effort has been devoted to finding (asymptotically) universal statistics of random matrices. In other words, it is often the case that some statistics are asymptotically equal for a broad class of random matrices, which often contain matrices from especially nice (e.g., symmetric) distributions for which we can actually explicitly compute these statistics. For example, a considerable amount of effort has been dedicated to finding such universality results for the eigenvalue distributions of random matrices: see [43, 27, 2, 3, 49, 52, 53].

In our scenario, we would like to find the distribution of the Sylow $p$-subgroups of the cokernels of random integral matrices with their natural duality pairings on the torsion subgroups of these cokernels. In Section 3, we will recall a theorem of Bosch and Lorenzini stating that the torsion subgroup of the cokernel of any integral symmetric matrix is naturally equipped with a duality pairing. For a random symmetric matrix with $p$-adic integral entries, drawn with respect to Haar measure on $\mathbb{Z}_{p}$, Clancy, Kaplan, Leake, Payne, and Wood showed in [15] that the cokernel of this matrix with its duality pairing are distributed as in Theorem 1.1. These Haar-random matrices should be viewed as the matrices that are “nicely distributed”—because Haar measure on $\mathbb{Z}_{p}$ is well-understood, we can actually compute the distribution of the cokernels with their pairings. A similar computation is done in [24] for the cokernels (sans pairings) of random (not necessarily symmetric) $p$-adic integral matrices and in [8] for Haar-random alternating matrices.

Because we can compute the aforementioned distribution in the nice Haar case, a natural next line of inquiry is to see whether these asymptotic cokernel and pairing distributions are universal—whether other large families of random symmetric matrices have the same cokernel and pairing distributions. In particular, Theorem 1.3 is a strong universality result for distributions of cokernels of random symmetric integral matrices with their pairings. The proof of Theorem 1.3 is essentially the same as Theorem 1.1.

As in the case with the sandpile group, we are able to show a stronger result than Theorem 1.3—for any finite set of primes, we give the asymptotic probabilities of particular Sylow subgroups with their pairings at these primes.

Recently, there has been significant effort devoted to finding universal distributions of various classes of random groups. In 2019, Wood showed that random integral matrices with independent entries are distributed according to a Cohen-Lenstra heuristic [55], and in [57], Yan extended this result to random matrices with independent entries taking values in Dedekind domains with finite quotients. In 2020, Mézáros gave the distribution of the sandpile groups of random regular graphs in [44]. Koplewitz studied the $p$-rank distribution of sandpile groups of random bipartite graphs in [33], and Bhargava, DePascale, and Koenig considered the directed bipartite case in [7]. Nguyen and Wood wrote several papers [46, 47] in which they study several other related problems on the distribution of cokernels of certain classes of random matrices. In particular, they found in [47] the asymptotic probability that the sandpile group of an Erdős-Rényi random graph is cyclic, answering a long-open conjecture due to Lorenzini [42]. Lee found the distribution of cokernels of random Hermitian matrices with entries in the ring of integers of a quadratic extension of $\mathbb{Q}_{p}$ [36] and proved results of similar flavor in [35, 34]. In 2022, Nguyen and Van Peski found in [45] the distribution of the cokernel of the product of random integral square matrices, and in 2023 Cheong and Yu proved a similar result in which they found the distribution of the cokernel of a polynomial evaluated at a random $p$-adic square matrix [14]. While much of the work in this area has been devoted to studying universal distributions of abelian groups, there has also been interest in the nonabelian case. For example, Gorokhovsky proved analogous universality results for random quotients of the free group on $n$ generators in [28], and Lee studied the distributions of similar random nonabelian groups in [34].

The overall structure of our argument is based off of the seminal methods developed by Wood in [54]. For a more detailed outline of the overall procedure, we refer the reader to the introduction of [54] and instead focus on the new techniques developed to deal with the pairing. The most important of these techniques is our usage of duality. As mentioned previously, we will primarily be working with finitely generated abelian groups with symmetric pairings attached to their dual groups. We will convert results about pairings on duals into statements about pairings on the groups themselves in Section 10. In Section 3, we attach a natural symmetric pairing to the Pontryagin dual of the cokernel of a symmetric integral matrix and show that, when the matrix is $L_{\Gamma}$, the pairing agrees with the duality pairing on $\widehat{S_{\Gamma}}$. To show Theorem 1.2, we compute the moments in a far more general setting where a random matrix as in Theorem 1.3 replaces the Laplacian of a random graph (see Theorem 8.1). Then, using results due to Sawin and Wood in [50], we prove (in Section 9) that these moments in fact determine a unique distribution. Thus, we may use the nice case of cokernels of uniform random symmetric matrices over $\mathbb{Z}/a\mathbb{Z}$ with their pairings, along with our universality results, to prove the distribution in the more general case (the distribution in the nice case was computed in [15]).

While the method of proof is inspired by [54], the extra data of the pairing complicates some of the proofs significantly. Indeed, it is not immediately clear that we should consider pairings on the duals of our groups or what the moments of the groups with pairings should be. Thus, to compute the averages $\operatorname{\mathrm{Sur}}^{*}(S_{\Gamma},G)$, we first translate the event that the pairing on $\widehat{S_{\Gamma}}$ pushes forward onto the pairing on $\widehat{G}$ into a piece of algebraic data which is easier to work with. In particular, if $F:S_{\Gamma}\to G$ is a surjection, the event that $F^{t}$ takes the pairing on $\widehat{S_{\Gamma}}$ to the pairing on $\widehat{G}$ occurs if and only if $FL_{\Gamma}F^{t}$ is equal to some fixed symmetric homomorphism from $\widehat{G}\to G$. Then since we are trying to compute the average number of surjections from $S_{\Gamma}\to G$ satisfying this property, and since the sandpile group is $Z/L_{\Gamma}Z$, it suffices to determine the probability that a surjection $F:Z\to G$ descends to $S_{\Gamma}$ and pushes the pairing on $\widehat{S_{\Gamma}}$ forward to the pairing on $\widehat{G}$. Equivalently, we determine the probability that $FL_{\Gamma}=0$ and that $FL_{\Gamma}F^{t}$ is equal to some fixed symmetric element of $\operatorname{\mathrm{Hom}}(\widehat{G},G)$.

We regard this as a system of linear equations in the entries of $L_{\Gamma}$, and we note that there are on the order of $n$ equations in ${{n}\choose{2}}$ variables. While in [54] it was enough to check whether $FL_{\Gamma}=0$, the pairing data makes this system particularly complex not only because the equations are more complicated, but because the equations given by $FL_{\Gamma}F^{t}$ are not even well-defined unless $FL_{\Gamma}=0$. To work around this inherent dependence between our equations, we choose a lift of $F:Z\to G$ to a larger group $H$ and modify our equations slightly so that we may work exclusively in this new group. Denote the lift by $\mathcal{F}$. Although this construction seems artificial, it turns out that all of our arguments depend only on $F$ itself rather than the specific choice of lift.

Our system of equations is parameterized by $\operatorname{\mathrm{Hom}}(Z,\widehat{G})\times\operatorname{\mathrm{Sym}}^{2}\widehat{H}$. Some pairs $(C,D)\in\operatorname{\mathrm{Hom}}(Z,\widehat{G})\times\operatorname{\mathrm{Sym}}^{2}\widehat{H}$, give equations in which all of the coefficients are 0; we refer to these as special pairs. The set of special pairs $(C,D)$ depends implicitly on $F$ and the chosen lift $\mathcal{F}$. Ultimately, we are interested in the structural properties of $\mathcal{F}$ and $C$ that influence the number of nonzero coefficients (see Section 5). We adapt two concepts from Wood’s work in [54], depth and robustness, to describe this structure. Finally, we count the number of special $(C,D)$ for each $F$. The special $(C,D)$ give the main term in Theorem 8.2 (the limit in Theorem 1.2), while the remaining cases contribute to the error term, which we bound by adapting techniques from [54].

Lastly, because the diagonal entries of $L_{\Gamma}$ depend on the off-diagonal ones, we run the program described above for a matrix with independent diagonal entries. Then we enlarge $F$ by taking its direct sum with another map that detects whether the column sums of a matrix are 0. This allows us to condition on what we require of the diagonal. However, in order to apply our methods to the enlarged group we must also extend the pairing on $\widehat{G}$ to the bigger group and sum over all possible extensions.

In Section 3, for a symmetric integral matrix $M$, we define a symmetric pairing on $\mathrm{c}\widehat{\mathrm{ok}}(M)$ and show that this induces a duality pairing on the torsion subgroup of $\mathrm{cok}(M)$. The induced duality pairing is equal to the duality pairing on the torsion part of $\mathrm{cok}(M)$ introduced by Bosch and Lorenzini in [13]. Theorem 1.2 (along with an analog of this theorem for cokernels of random symmetric matrices with their pairings) is proved in Sections 4, 5, 6, 7 and 8. In Section 9, we state several results from [50] and use these to prove that the moments of Theorem 1.2 in fact determine the distribution in question. Finally, in Section 10, we compare to the case of uniform random symmetric matrices over $\mathbb{Z}/a\mathbb{Z}$; Theorem 1.1 follows from Corollary 10.5.

Let $p$ be a prime. A finite abelian $p$-group is isomorphic to

for some positive integers $\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{r}$. If $\lambda$ is the partition given by the $\lambda_{i}$’s, we call $\lambda$ the type of our finite abelian $p$-group. When $p$ is understood, let $G_{\lambda}$ denote the $p$-group of type $\lambda$.

We may view any two abelian groups $G$ and $H$ as $\mathbb{Z}$-modules, and we may consider their tensor product $G\otimes_{\mathbb{Z}}H$. When $G=\bigoplus_{i}\mathbb{Z}/a_{i}\mathbb{Z}$ is finite and $H=\mathbb{Z}/a\mathbb{Z}$,

where $(a,a_{i})$ denotes the greatest common divisor of $a$ and $a_{i}$. The fact that tensor products distribute over direct sums in conjunction with the classification of finite abelian groups allows us to compute $G\otimes H$ for arbitrary finite abelian groups $G$ and $H$. In particular, if $G_{p}$ denotes the Sylow $p$-subgroup of $G$, then $G\otimes G\simeq\bigoplus_{p}G_{p}\otimes G_{p}.$ Moreover, if $G_{p}$ is of type $\lambda$ and is generated by $g_{i}$ with relations $p^{\lambda_{i}}g_{i}=0$, then $G_{p}\otimes G_{p}$ is generated as an abelian group by $g_{i}\otimes g_{j}$ with relations $p^{\min(\lambda_{i},\lambda_{j})}g_{i}\otimes g_{j}=0$. Thus,

Now, $G\otimes G$ comes equipped with a natural involution taking $g\otimes h\mapsto h\otimes g$. Denote the subgroup of elements fixed under this involution by $\operatorname{\mathrm{Sym}}_{2}G$. For $G_{p}$ as above, we have that $\operatorname{\mathrm{Sym}}_{2}G\simeq\bigoplus_{p}\operatorname{\mathrm{Sym}}_{2}G_{p}$ and that $\operatorname{\mathrm{Sym}}_{2}G_{p}$ is the abelian group generated by the elements $g_{i}\otimes g_{i}$ and $g_{i}\otimes g_{j}+g_{j}\otimes g_{i}$ for $i<j$ with relations $p^{\lambda_{j}}g_{i}\otimes g_{j}=p^{\lambda_{j}}g_{j}\otimes g_{i}=0$ for each $i<j$. Thus, $|\operatorname{\mathrm{Sym}}_{2}G_{p}|=p^{\sum_{i}i\lambda_{i}}$.

The exterior power $\wedge^{2}G$ is the quotient of $G\otimes G$ by the subgroup generated by elements of the form $g\otimes g$. For $G_{p}$ as above, we have that $\wedge^{2}G\simeq\bigoplus_{p}\wedge^{2}G_{p}$ and that $\wedge^{2}G_{p}$ is generated as an abelian group by $g_{i}\wedge g_{j}$ for $i<j$ with relations $p^{\lambda_{j}}g_{i}\wedge g_{j}=0$ for each $i<j$. Thus,

Likewise, the symmetric power $\operatorname{\mathrm{Sym}}^{2}G$ is the quotient of $G\otimes G$ by the subgroup generated by elements of the form $g\otimes h-h\otimes g$. For $G_{p}$ as above, we have that $\operatorname{\mathrm{Sym}}^{2}G\simeq\bigoplus_{p}\operatorname{\mathrm{Sym}}^{2}G_{p}$ and that $\operatorname{\mathrm{Sym}}^{2}G_{p}$ is generated as an abelian group by $g_{i}g_{j}$ for $i\leq j$ with relations $p^{\lambda_{j}}g_{i}g_{j}=0$ for $i\leq j$. Therefore,

The exponent of a finite abelian group is the smallest positive integer $e$ such that $eG=0$. If $R=\mathbb{Z}/a\mathbb{Z}$, then a finite abelian group $G$ with exponent dividing $a$ is also an $R$-module. If $H$ is another such group, then $\operatorname{\mathrm{Hom}}_{R}(G,H)=\operatorname{\mathrm{Hom}}_{\mathbb{Z}}(G,H)$ (i.e., the $R$-module homomorphisms $G\to H$ are the same as the group homomorphisms $G\to H$).

For any finite abelian group $G$, its Pontryagin dual is the group $\operatorname{\mathrm{Hom}}_{\mathbb{Z}}(G,\mathbb{Q}/\mathbb{Z})$, which we denote by $\widehat{G}$.

Let $G$ be an abelian group and consider a map $\phi:G\times G\to\mathbb{Q}/\mathbb{Z}$. We say that $\phi$ is symmetric if $\phi(g,h)=\phi(h,g)$ and bilinear if $\phi(g_{1}+g_{2},h)=\phi(g_{1},h)+\phi(g_{2},h)$ and $\phi(g,h_{1}+h_{2})=\phi(g,h_{1})+\phi(g,h_{2})$. If $\phi$ is bilinear, then it is called a pairing on $G$. Equivalently, a pairing on $G$ can be thought of as a homomorphism $G\otimes G\to\mathbb{Q}/\mathbb{Z}$. Given a pairing $\phi$ and generators $g_{1},\ldots,g_{r}$ of $G$, note that $\phi$ is entirely determined by the values $\phi(g_{i},g_{j})$ for all pairs $(i,j)$.

A symmetric pairing $\phi$ on $G$ induces a map from $G\to\operatorname{\mathrm{Hom}}(G,\mathbb{Q}/\mathbb{Z})$ taking $g\mapsto\phi(g,\cdotp)$ (if the pairing were not symmetric we would have two maps—one for each factor). Such a pairing is said to be nondegenerate if the induced map $G\to\operatorname{\mathrm{Hom}}(G,\mathbb{Q}/\mathbb{Z})$ is injective. If the induced map is not injective, the pairing is said to be degenerate, and the kernel of the map is called the kernel of the pairing. The cokernel of the pairing $\phi$, denoted $\mathrm{coker}(\phi)$, is defined to be $G/\ker(\phi)$. Note that there is a natural nondegenerate symmetric pairing on $\mathrm{coker}(\phi)$ induced by $\phi$.

If the map $G\to\widehat{G}$ induced by $\phi$ is an isomorphism, then the pairing is said to be perfect. Recall that a perfect symmetric pairing on a group is called a duality pairing. If $G$ is finite, then a nondegenerate pairing on $G$ is automatically perfect (this fact follows from counting). Given two groups $G$ and $H$ equipped with pairings $\langle\,,\rangle_{G}$ and $\langle\,,\rangle_{H}$, there is a notion of isomorphism between $(G,\langle\,,\rangle_{G})$ and $(H,\langle\,,\rangle_{H})$: an isomorphism between $(G,\langle\,,\rangle_{G})$ and $(H,\langle\,,\rangle_{H})$ is an isomorphism of groups $f:G\to H$ such that $\langle f^{-1}(h),f^{-1}(h^{\prime})\rangle_{G}=\langle h,h^{\prime}\rangle_{H}$ for all pairs $(h,h^{\prime})\in H\times H$. If $(G,\langle\,,\rangle_{G})$ is a group equipped with a pairing, an automorphism of $G$ is said to respect the pairing if it is an isomorphism of groups and pairings between $(G,\langle\,,\rangle_{G})$ and itself. Denote the set of automorphisms of $G$ that respect the pairing $\langle\,,\rangle_{G}$ by $\operatorname{\mathrm{Aut}}(G,\langle\,,\rangle_{G})$.

Let $R=\mathbb{Z}/b\mathbb{Z}$. When the ring $R$ is understood, for an $R$-module $G$, we may consider its dual, $G^{*}=\operatorname{\mathrm{Hom}}_{R}(G,R)$. If $G$ is a finite abelian group, there is a canonical isomorphism between $G^{*}$ and $\widehat{G}$. For finite $R$-modules $G$ and $H$, we have $(G\oplus H)^{*}\simeq G^{*}\oplus H^{*}$. While $G$ and $G^{*}$ are not naturally isomorphic, when $G$ is finite, there is a canonical isomorphism between $G$ and $(G^{*})^{*}$ given by evaluation.

For a finite abelian group $G$, the following are equivalent data:

1. (1)

   a perfect symmetric pairing on $G$;

2. (2)

   an isomorphism from $G$ to $\widehat{G}$;

3. (3)

   a perfect symmetric pairing on $\widehat{G}$.

Given a duality pairing $\langle\,,\rangle_{G}$ on $G$, let $\phi$ denote the induced isomorphism from $G\to\widehat{G}$. Then the duality pairing on $\widehat{G}$ is given by $\langle x,y\rangle=\langle\phi^{-1}(x),\phi^{-1}(y)\rangle_{G}$.

Let $G$ and $H$ be two finite abelian groups. Let $f:G\to H$ be a group homomorphism. The transpose of $f$ is the map $f^{t}:\widehat{H}\to\widehat{G}$ given by precomposing $\ell\in\operatorname{\mathrm{Hom}}(H,\mathbb{Q}/\mathbb{Z})$ with $f$ (a similar definition can be made if $G$ and $H$ are $R$-modules for $R=\mathbb{Z}/b\mathbb{Z}$ and $f$ an $R$-module homomorphism). If $\widehat{G}$ is equipped with a pairing $\langle\,,\rangle_{\widehat{G}}$, then $f^{t}$ pushes $\langle\,,\rangle_{\widehat{G}}$ forward to a pairing $\langle\,,\rangle_{\widehat{H}}$ on $\widehat{H}$ given by

In other words, $f^{t}$ induces a map from $\operatorname{\mathrm{Hom}}(\widehat{G}\otimes\widehat{G},\mathbb{Q}/\mathbb{Z})\to\operatorname{\mathrm{Hom}}(\widehat{H}\otimes\widehat{H},\mathbb{Q}/\mathbb{Z})$; let $f^{t}(\langle\,,\rangle_{\widehat{G}})$ denote the image of $\langle\,,\rangle_{\widehat{G}}$ under this map (denoted $\langle\,,\rangle_{\widehat{H}}$ above). Note that we do not require $\langle\,,\rangle_{\widehat{G}}$ to be perfect.

Let $(G,\langle\,,\rangle_{\widehat{G}})$ and $(H,\langle\,,\rangle_{\widehat{H}})$ be groups whose duals are equipped with pairings. Define

to be the set of group homomorphisms $f:G\to H$ such that $f^{t}(\langle\,,\rangle_{\widehat{G}})=\langle\,,\rangle_{\widehat{H}}$. In the category $\mathcal{C}$ defined in Section 1, $\operatorname{\mathrm{Hom}}((G,\langle\,,\rangle_{\widehat{G}}),(H,\langle\,,\rangle_{\widehat{H}}))$ is the set of morphisms between $(G,\langle\,,\rangle_{\widehat{G}})$ and $(H,\langle\,,\rangle_{\widehat{H}})$. When the pairings on both groups are understood, we denote $\operatorname{\mathrm{Hom}}((G,\langle\,,\rangle_{\widehat{G}}),(H,\langle\,,\rangle_{\widehat{H}}))$ by $\operatorname{\mathrm{Hom}}^{*}(G,H)$ for the sake of brevity. Note that this generalizes the notion of isomorphism between groups with duality pairings defined in the previous subsection. Moreover, given finite abelian groups $G$ and $H$ with duality pairings $\langle\,,\rangle_{G}$ and $\langle\,,\rangle_{H}$ and induced duality pairings $\langle\,,\rangle_{\widehat{G}}$ and $\langle\,,\rangle_{\widehat{H}}$ on the dual groups, note that $(G,\langle\,,\rangle_{G})\simeq(H,\langle\,,\rangle_{H})$ if and only if $(G,\langle\,,\rangle_{\widehat{G}})\simeq(H,\langle\,,\rangle_{\widehat{H}})$.

Let $M_{n}(R)$ denote the space of $n\times n$ matrices with entries in a commutative ring $R$. For $M\in M_{n}(R)$, let $\operatorname{\mathrm{col}}(M)$ denote the column space of $M$ (this is the image of the map $R^{n}\to R^{n}$ given by $M$). Define the cokernel of $M$ to be

For $M\in M_{n}(\mathbb{Z})$, regard $M$ as a linear map $M:\mathbb{Z}^{n}\to\mathbb{Z}^{n}$. Then $\mathrm{cok}(M)$ is a finitely generated abelian group; let $\mathrm{tcok}(M)$ denote its torsion subgroup. For any subgroup $Y\subset\mathbb{Z}^{n}$, let $Y^{\perp}$ denote its orthogonal with respect to the standard scalar product on $\mathbb{Z}^{n}$.

If $M$ is symmetric, $\operatorname{\mathrm{col}}(M)\subset\ker(M)^{\perp}$. Because $\mathrm{rank}(\operatorname{\mathrm{col}}(M))=\mathrm{rank}(\ker(M)^{\perp})$ and because $\ker(M)^{\perp}$ is a saturated submodule of $\mathbb{Z}^{n}$ (i.e., if $rx\in\ker(M)^{\perp}$ for $r\in\mathbb{Z}$ and $x\in\mathbb{Z}^{n}$, then $x\in\ker(M)^{\perp}$), it follows that

Since $\mathrm{tcok}(M)$ is pure torsion and $\mathrm{cok}(M)$ is finitely generated, $\mathrm{tcok}(M)$ is finite.

Recall the definition of the graph Laplacian. Let $[n]=\{1,\ldots,n\}$, and let $\Gamma$ be a graph on $n$ vertices labeled by $[n]$. The Laplacian of $\Gamma$, denoted $L_{\Gamma}$, is the $n\times n$ matrix whose $(i,j)$ entry is given by

Note that $L_{\Gamma}$ is a symmetric matrix in $M_{n}(\mathbb{Z})$. If $\Gamma$ is connected, then $L_{\Gamma}$ has rank $n-1$ and kernel spanned by the all-ones vector (see [51]). If $Z\subset\mathbb{Z}^{n}$ is the subgroup of elements whose coordinates sum to 0, then we see that $\operatorname{\mathrm{col}}(L_{\Gamma})\subset Z$. Define the sandpile group of $\Gamma$, denoted $S_{\Gamma}$, to be $Z/\operatorname{\mathrm{col}}(L_{\Gamma})$. We see immediately that $S_{\Gamma}$ must be finitely generated. Moreover, it is finite if and only if $\Gamma$ is connected.

Let $\Gamma\in G(n,q)$ denote that $\Gamma$ is an Erdős-Rényi random graph on $n$ labeled vertices with edges occurring independently with probability $q$.

We use $|\cdot|$ or $\#$ to denote the cardinality of sets (we use $\#$’s to avoid confusion with the notation $|$ for “divides”; while absolute value signs take up less space). Throughout, $\simeq$ denotes “is isomorphic to,” and $\operatorname{\mathbb{P}}$ and $\mathbb{E}$ denote probability and expected value, respectively. Also, $p$ will always denote a prime. For any integers $i$ and $j$, let $\delta_{ij}$ be the Kronecker delta—if $i=j$, then $\delta_{ij}=1$ and if $i\neq j$, then $\delta_{ij}=0$.