Let $G$ be some outdegree-regular directed graph with $n$ vertices and let $H$ be the Laplacian of $G$, so that the rows of $H$ correspond to chip-firing moves. I’m interested in linear functions $f$ from $\mathbb{Z}^n$ to $\mathbb{Z}/k\mathbb{Z}$ with the property that performing a chip-firing move on a vector in $\mathbb{Z}^n$ increases the value of $f$ by 1 mod $k$ (I call such a function $f$ a chip-firing “clock”). Such an $f$ will exist only for certain values of $k$. This feels like it’s related to the structure of the cokernel of the Laplacian but I’m having trouble seeing exactly what's going on. I’m interested in knowing about all such functions $f$ for a given $G$.



Chip-firing clocks
For two such functions $f$ and $g$, the difference $f-g$ is invariant under chip-firing, i.e. it factors through a function from the cokernel of the Laplacian to $\mathbb Z/k$. Conversely, for such a function $f$, adding any linear function from the cokernel of the Laplacian to $\mathbb Z/k$ produces another such function.


So if there are any such functions, they are classified by linear functions from the cokernel of the Laplacian to $\mathbb Z/k$.


Such a function exists if and only if there do not exist integer vectors $v, w \in \mathbb Z^n$ where $k v =\Lambda w$, for $\Lambda$ the Laplacian, and the sum of the entries of $w$ is nonzero mod $k$.


The "only if" direction is straightforward. Given such $v,w$, we would have $0 = kf(v)= f(kv) = f(\Lambda w) $ equal to the sum of entries of $w$.


For the "if" direction, write the cokernel of the Laplacian as a product of cyclic groups $\mathbb Z/n\_i$ generated by vectors $v\_i$.
Then $n\_iv\_i$ lies in image of the Laplacian, so we can write $n\_i v\_i = \Lambda w\_i$ for some vector $w\_i$. We can choose $f(v\_i)$ such that $f(n\_i v\_i) $ is the sum of entries of $w\_i$. We can do this as long as the some of entries of $w\_i$ is divisible by $\gcd(n\_i, k)$, which it is because $\Lambda w\_i k/\gcd(n\_i,k) = k ( v\_i n\_i / \gcd(n\_i,k))$ and $v\_i n\_i / \gcd(n\_i,k)$ is integral so the sum of entries of $w\_i k/\gcd(n\_i,k)$ is divisible by $k$ by construction.


Having made this chose, we can define $f$ for an arbitrary $v$ by writing it as a integer linear combination of $v\_i$ plus a vector of the form $\Lambda w$, and taking the appropriate linear combination of $f(v\_i)$ and the sum of the entries of $w$. This is well-defined because the only ambiguity consists of adding $n\_i$ to the coefficients of $v\_i$, which we checked is consistent, and adding something in the kernel of the Laplacian, whose consistency follows from the assumption.




---


Here is a simple example of a chip-firing clock. Consider the graph with vertices $1,\dots, n$ and edges from vertex $i$ to $i+1$ and $n$ to $1$.


Then the function of a vector $a\_1,\dots, a\_n$ given by $f(a\_1,\dots,a\_n) = \sum\_i i a\_i \mod n$ is a chip-firing clock.


In this case, the cokernel of the Laplacian is $\mathbb Z$, which is torsion-free, so there is no obstruction, and there is a unique stationary probability distribution, so the longest period of a chip-firing clock is just the least common denominators of the probabilties, which is $n$.


For a more complicated example, consider a graph with vertices $1,\dots n$ where vertex $i$ has edges to $i+1$ and $n$ except for $n$ which just connects to $n+1$.


Then the function of a vector $a\_1,\dots a\_n$ given by $f(a\_1,\dots, a\_n) = \sum\_{i=1}^n 2^i a\_i \mod (2^n-1)$ is a chip-firing clock. Again this is an example where the cokernel of the Laplacian is just $\mathbb Z$.


