Chip-firing clocks

Question

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$.

Answer 1

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$.

Answer 2

This is just to record the observation of lambda from the comments.

I'll keep your convention that the rows of $H$ determine the chip-firing moves, so that for a sequence of firings $v\in\mathbb{Z}^n$ the result of caring out these firings (starting from the zero configuration) is $vH$. (But this means that we should really be talking about the kernel and cokernel of $H^t$ everywhere...)

For $x\in \mathbb{Z}^n$, the linear function $f(v)=\langle v, x\rangle \mod k$ is a clock if and only if $Hx=\mathbf{1} \mod k$. (Here $\langle \cdot , \cdot \rangle$ is the usual inner product, and $\mathbf{1}$ is the all ones vector.) This is because the requirement we have to satisfy to be a clock is that $f(vH)=\langle v, \mathbf{1}\rangle \mod k$ for all $v\in\mathbb{Z}^n$, so we need $f(vH)=\langle vH, x\rangle =\langle v,Hx\rangle$ to be equal moulo $k$ to $\langle v, \mathbf{1}\rangle$ for all $v\in \mathbb{Z}^n$, which happens if and only if $Hx=\mathbf{1} \mod k$.

It still is not totally clear how given a graph $G$ to find the (finite!) list of $k$ for which a clock exists, but for a fixed $k$ at least this makes it clear that the question of whether such a $k$ exists is a "linear algebra" problem (if $k$ is prime then indeed we're talking about linear algebra over a field).

[ By the way, here is the argument that the set of such $k$ is finite. $H^t$ is a singular M-matrix, so there is some vector $v_{*}\in\mathrm{ker}(H^t)$ with $v_{*}\neq 0$ but all entries of $v_{*}$ nonnegative. Hence in particular $\langle v_{*}, \mathbf{1} \rangle > 0$. But, as mentioned, if there is a $k$-clock we need that $\langle v, \mathbf{1} \rangle = 0 \mod k$ for any $v \in \mathrm{ker}(H^t)$, so as long as $k > \langle v_{*}, \mathbf{1}\rangle$ then there cannot be a $k$-clock. ]