Chip-Firing on Metric Graphs: The Abel-Jacobi Map

Suppose ${G}$ is a finite, connected, edge-weighted graph, i.e. there is an associated weight function ${w: E(G) \rightarrow \mathbb{R}^{>0}}$. One can make ${G}$ into a metric space ${\Gamma(G)}$ by identifying each edge ${e\in E(G)}$ with a closed line segment ${L_e}$ of length ${w(e)}$, setting

$\displaystyle \Gamma = \bigcup_{e\in E(G)} L_e$

and declaring ${d(x,y)}$ to be the length of the shortest path between ${x}$ and ${y}$ when traveling along the edges of ${G}$. On the space ${\mathcal{G}}$ of finite, edge-weighted graphs, there is the equivalence relation ${G\sim G'}$ if ${\Gamma(G)}$ and ${\Gamma(G')}$ are isometric. A metric graph ${\Gamma}$ is the unique (up to isometry) metric space associated with an equivalence class in ${\mathcal{G}/\sim}$, and any graph in the equivalence class is called a model for ${\Gamma}$.

We begin with ${\mathcal{M}(\Gamma)}$, the group (under pointwise addition) of continuous, piecewise linear functions ${\Gamma \rightarrow \mathbb{R}}$ for which every linear piece has integer slope. This is a linearized analogue of the space of meromorphic functions on a Riemann surface, over which divisor theory is classically developed. We denote by ${\text{Div}(\Gamma)}$ the free abelian group on ${\Gamma}$, i.e.

$\displaystyle \text{Div}(\Gamma) := \left\{D =\sum_{p\in \Gamma} a_p (p) \, : \, a_p \in \mathbb{Z} \text{ for all } p \text{ and } a_p = 0 \text{ for almost all } p \right\}$

In other words, ${\text{Div}(\Gamma)}$ is the group of integer-valued functions on ${\Gamma}$ having finite support. With this interpretation, we introduce the notation ${D(p) := a_p}$ for a divisor ${D \in \text{Div}(\Gamma)}$.

There is a homomorphism ${\text{deg} : \text{Div}(\gamma) \rightarrow \mathbb{Z}}$ given by ${\sum a_p (p) \mapsto \sum a_p}$, and ${\text{deg}(D)}$ is called the degree of ${D}$. For any ${d\in \mathbb{Z}}$, we denote by ${\text{Div}^{d} (\Gamma)}$ the set of divisors with degree ${d}$. Only when ${d = 0}$ does ${\text{Div}^{d} (\Gamma)}$ form a subgroup of ${\text{Div}(\Gamma)}$, and ${\text{Div}^{0} (\Gamma)}$ is the kernel of ${\text{deg}}$.

With each ${f\in \mathcal{M}(\Gamma)}$, there is an associated divisor ${\Delta(f)}$, which records information on the “zeros” and “poles” of ${f}$. Namely, for each ${p\in \Gamma}$, we set ${\text{ord}_p (f)}$ to be the sum of the slopes of ${f}$ in all directions of the graph emanating from ${p}$. Then we define the principal divisor ${\Delta(f)}$ as

$\displaystyle \Delta(f) := \sum_{p\in \Gamma} \text{ord}_p (f) (p)$

The principal divisors form a subgroup ${\text{Prin}(\Gamma)}$, and one observes ${\deg(\Delta(f)) = 0}$ for every ${f \in \text{Prin}(\Gamma)}$, so that ${\text{Prin}(\Gamma) \subseteq \text{Div}^{0} (\Gamma)}$. This begs to form the quotient

$\displaystyle \text{Pic}^{0} (\Gamma) := \text{Div}^{0} (\Gamma) / \text{Prin}(\Gamma)$

which is called the Picard group of ${\Gamma}$. More generally, two divisors ${D}$, ${D' \in \text{Div}^{d} (\Gamma)}$ are linearly equivalent, denoted ${D\sim D'}$, if ${D - D' \in \text{Prin}(\Gamma)}$, and one can form the sets ${\text{Pic}^{d} (\Gamma) := \text{Div}^d (\Gamma) / \sim}$.

There is a combinatorial/dynamical interpretation of linear equivalence. Given a divisor ${D}$ on ${\Gamma}$, one can interpret ${D(p)}$ as the number of dollars person ${p}$ has (if ${D(p) < 0}$, then person ${p}$ is in debt). For any star-shaped subset ${X \subset \Gamma}$ and sufficiently small ${\epsilon > 0}$, there is a function ${f_{X, \epsilon} \in \mathcal{M}(\Gamma)}$ taking value 0 on ${X}$, taking value ${\epsilon}$ outside the ${\epsilon}$-neighborhood of ${X}$, and with slope 1 along each outgoing direction from ${X}$. Then ${D \sim D + \Delta(f_{X,\epsilon})}$, and this equivalence has the effect of each person on the boundary of ${X}$ giving one dollar to the individual situated exactly distance ${\epsilon}$ away. Every element of ${\mathcal{M}(\Gamma)}$ may be written as a finite ${\mathbb{Z}}$-linear combination of ${f_{X,\epsilon}}$‘s, so two divisors are linearly equivalent precisely when connected by a sequence of these “chip-firing” moves.

In terms of the chip-firing game, ${\text{Pic}^{0} (\Gamma)}$ is the space of inequivalent degree 0 wealth distributions on ${\Gamma}$. We would like to understand the structure of this space, both algebraically and geometrically. As it turns out, one can learn quite a bit about ${\text{Pic}^{0} (\Gamma)}$ through the integer homology group ${H_1 (\Gamma, \mathbb{Z})}$.

Recall that ${H_1 (\Gamma, \mathbb{Z})}$ is constructed as follows. Fix a model ${G}$ for ${\Gamma}$, fix an orientation of ${G}$, fix a spanning tree ${T}$ of ${G}$, and fix a base vertex ${q\in V(G)}$. Then, we denote by ${A}$ the ${\mathbb{R}}$-vector space with basis ${E(G) = \{e_1, \cdots, e_n\}}$, and by ${\text{P}}$ the ${\mathbb{R}}$-vector space with basis ${V(G)}$. The boundary map ${\partial : E(G) \rightarrow P}$ given by ${\partial(v\rightarrow w) = w-v}$ extends linearly to a map ${A\rightarrow P}$ of vector spaces. One defines the real homology ${H_1 (\Gamma, \mathbb{R})}$ to be the kernel of ${\partial: A \rightarrow P}$. Given the choices we have made, there is a canonical basis for ${H_1 (\Gamma, \mathbb{R})}$, consisting of simple cycles. For every ${e\in E(G) \setminus E(T)}$, there is a unique cycle beginning and ending at ${q}$ that traverses no edges other than ${e}$ and those in ${T}$. Recording each of these cycles as a sum of directed edges gives the aforementioned basis. Then ${H_1 (\Gamma, \mathbb{Z})}$ is defined to be the free abelian group on this canonical basis, i.e. the associated integer lattice inside ${H_1 (\Gamma, \mathbb{R})}$.

The Abel-Jacobi theorem states there is an isomorphism

$\displaystyle \text{Pic}^{0}(\Gamma) \stackrel{\Phi}{\cong} H_1 (\Gamma, \mathbb{R}) / H_1 (\Gamma, \mathbb{Z})$

We will not prove this fact, as it is rather difficult, but we will show how this isomorphism gives rise to interesting geometric features. One defines the Abel-Jacobi map ${\varphi_q : \Gamma \rightarrow \text{Pic}^{0} (\Gamma)}$ via

$\displaystyle p \mapsto [(p) - (q)]$

By the isomorphism above, ${\varphi_q}$ descends to a map ${\tilde{\varphi}_{q}}$ from ${\Gamma}$ into the ${g}$-dimensional torus

$\displaystyle H_1 (\Gamma, \mathbb{R})/H_1 (\Gamma, \mathbb{Z}) \cong \mathbb{R}^g / \mathbb{Z}^g \cong (S^1)^{g}$

where ${g = |E(G)| - |V(G)| + 1}$ is the genus of ${G}$. This ${\tilde{\varphi}_q}$ can be described in very geometric terms: it essentially draws a skeletonized version of ${G}$ on the torus ${(S^1)^g}$.

To specify the map ${\tilde{\varphi}_q}$, we will need to equip the ambient edge space ${A}$ with an inner product given by

$\displaystyle \langle e_i, e_j \rangle = \left\{\begin{array}{lr} 0 & : i\neq j\\ w(e_i) & : i=j \end{array} \right.$

This allows us to talk about orthogonality of vectors in ${A}$, and in particular, define an orthogonal projection ${\pi : A \rightarrow H_1 (\Gamma, \mathbb{R})}$. A line segment in ${H_1 (\Gamma, \mathbb{R})}$ can be specified by providing a vector and a base point onto which the tail of the vector should be translated. Accordingly, let ${(v,p)}$ denote the line segment in ${H_1 (\Gamma, \mathbb{R})}$ obtained by translating vector ${v}$ to ${p}$. We describe the image of ${\tilde{\varphi}_q}$ by constructing the map inductively. Assume in the basis ${\{e_1, \cdots, e_n\}}$ the edges are ordered such that for every ${2\le j \le n}$, the edge ${e_j}$ shares a vertex with some ${e_i}$ having ${i. Furthermore, assume the tail of ${e_1}$ is ${q}$. Begin by identifying ${e_1}$ with the segment ${(\pi(e_1), 0)}$ (so that ${\tilde{\varphi}_q}$ is defined on ${e_1}$). Now, if ${e_j}$ for ${j\ge 2}$ shares a vertex ${x}$ with ${e_i}$, where ${i, we identify ${e_j}$ with either the segment ${(\pi(e_j), \tilde{\varphi}_q (x))}$ or the segment ${(\pi(e_j), \tilde{\varphi}_q (x) - \pi(e_j))}$, depending on if ${x}$ is the tail of ${e_j}$ or the head of ${e_j}$, respectively. Once this process is complete, the entire image of ${\tilde{\varphi}_q}$ is contained in a unique fundamental domain of the lattice ${H_1(\Gamma, \mathbb{Z})}$, hence ${\tilde{\varphi}_q}$ actually gives a map ${\Gamma \rightarrow H_1 (\Gamma, \mathbb{R})/ H_1 (\Gamma, \mathbb{Z})}$.

How much information does ${\tilde{\varphi}_q}$ preserve? The only edges mapped into ${H_1 (\Gamma, \mathbb{R})}$ non-injectively are those which orthogonally project to ${0 \in H_1 (\Gamma, \mathbb{R})}$, i.e. those edges inhabiting the orthogonal complement of ${H_1 (\Gamma, \mathbb{R})}$. There is a nice characterization of this space when ${w(e_i) = 1}$ for all ${1\le i \le n}$. Recall that a cut of ${G}$ is any disjoint partition ${V(G) = P \cup Q}$, and any cut determines a cut set, consisting of the edges connecting a vertex in ${P}$ to a vertex in ${Q}$. For each cut set ${\{e_{i_1}, \cdots, e_{i_k}\}}$, there is an associated cut vector in ${A}$ encoding that set, namely ${\sum_{j=1}^{k} \omega(j) e_{i_j}}$. where ${\omega(j) = 1}$ if ${e_{i_j}}$ is oriented to flow from ${P}$ to ${Q}$ and ${\omega(j) = -1}$ if ${e_{i_j}}$ is oriented to flow from ${Q}$ to ${P}$. We claim the cut space

$\displaystyle C:= \text{span}\left( \text{all cut vectors} \right)$

is precisely the orthogonal complement of the cycle space ${H_1 (\Gamma, \mathbb{R})}$.

To prove this, we first note that any cut vector is orthogonal to any cycle vector. Suppose ${y \in H_1 (\Gamma, \mathbb{R})}$ represents a simple cycle (a cycle that traverses no edge twice) and ${u = \sum_{j=1}^{k} \omega(j) e_{i_j} }$ is a cut vector. Let ${\nu(j) = 1}$ if ${y}$ traverses ${e_{i_j}}$ along its orientation, let ${\nu(j)=-1}$ if ${y}$ traverses ${e_{i_j}}$ against its orientation, and let ${\nu(j) = 0}$ if ${y}$ does not traverse ${e_{i_j}}$. Then

$\displaystyle \langle y, u \rangle = \sum_{j=1}^{k} \nu(j) \omega(j)$

$\displaystyle = [\text{number of times } y \text{ goes } P \rightarrow Q] - [\text{number of times } y \text{ goes } Q \rightarrow P] = 0$

But simple cycles form a basis for ${H_1 (\Gamma, \mathbb{R})}$, so ${C \subseteq H_1 (\Gamma, \mathbb{R})^{\perp}}$. Since ${H_1 (\Gamma, \mathbb{R})^{\perp}}$ has dimension ${|E(G)| - g = |V(G)| - 1}$, to complete the argument it will suffice to exhibit ${|V(G)| - 1}$ linearly independent vectors in ${C}$. Fix an ordering ${\{v_1, \cdots, v_m\}}$ of the vertices, and set ${A_j = \{v_1, \cdots, v_j\}}$. Then for each ${1\le j \le m-1}$, the partition ${V(G) = A_j \cup (V(G) \setminus A_j)}$ is a cut, with a corresponding cut set ${C_j \subset V(G)}$. Since ${C_{j+1}}$ always contains a vertex that ${C_1}$, ${\cdots}$, ${C_j}$ all do not, the ${|V(G)| - 1}$ cut vectors corresponding to these cuts are linearly independent.

Hence, ${\pi (e_i) = 0}$ if and only if ${e_i}$ is a bridge, an edge whose removal would disconnect the graph. This means the only information lost by ${\tilde{\varphi}_q}$ is the existence of bridges, which are collapsed into a point when the graph is drawn on ${H_1 (\Gamma, \mathbb{R})}$; elsewhere on ${\Gamma}$, the map is injective. Because of the isomorphism between ${\text{Pic}^0 (\Gamma)}$ and ${H_1 (\Gamma, \mathbb{R})/ H_1 (\Gamma, \mathbb{Z})}$, this geometric observation can be translated to an equivalent algebraic fact about ${\text{Pic}^0 (\Gamma)}$: if ${(p) \sim (p')}$, then either ${p=p'}$ or there is some bridge ${e \in E(G)}$ such that ${p}$, ${p' \in e}$.

(Acknowledgment: the nice diagrams above are due to Samir Khan, UChicago ’19)