7
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ Another way to phrase this question in terms of lifts of group homomorphisms: we have the linear map $H\colon \mathbb{Z}^n\to \mathbb{Z}^n$, and the linear map $\alpha\colon\mathbb{Z}^n\to\mathbb{Z}/k\mathbb{Z}$ for which $\alpha(v)$ is the sum of its coordinates modulo $k$; then the $f$ in question are the lifts of $\alpha$ along $H$. But this doesn't really answer your question because I think in general questions about lifts of group homomorphisms are hard/might involve group cohomology. $\endgroup$ Apr 4, 2021 at 19:18
  • $\begingroup$ If $\alpha$ were instead the zero morphism, then indeed these $f$ would just be maps from $\mathrm{coker}(H)$ to $\mathbb{Z}/k\mathbb{Z}$. $\endgroup$ Apr 4, 2021 at 19:19
  • $\begingroup$ One more (rather trivial) observation: we need that $\alpha(v) = 0$ for any $v \in \mathrm{ker}(H)$. You say "outdegree-regular graph" which maybe suggests you are thinking of directed graphs. But if $G$ is undirected, then for instance one element of the kernel is the all $1$'s vector $\mathbf{1}$. And $\alpha(\mathbf{1}) = 0$ if and only if $k$ divides $n$. If $G$ is moreover connected then $\mathbf{1}$ generates the kernel of $H$ so this is the only requirement that we get from consideration of the kernel. But I don't see any reason why if $k$ divides $n$ then such an $f$ must exist. $\endgroup$ Apr 4, 2021 at 21:56
  • 1
    $\begingroup$ Is this the same as a solution to $Hx \equiv \mathbf 1 \pmod k$? $\endgroup$
    – lambda
    Apr 5, 2021 at 14:07
  • 1
    $\begingroup$ @Josh: If $H = \begin{pmatrix} 1 & -1 \\ -1 & 1 \end{pmatrix}$ then, with $k=2$, $(v_1,v_2)\mapsto v_1$ is such a function $f$. $\endgroup$ Apr 5, 2021 at 15:16

2 Answers 2

3
$\begingroup$

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

$\endgroup$
19
  • $\begingroup$ Is the $f(x)$ you defined in the 6th paragraph linear though? $\endgroup$ Apr 5, 2021 at 2:58
  • $\begingroup$ @SamHopkins Oh, sorry, I missed the "linear" thing. Will revise... $\endgroup$
    – Will Sawin
    Apr 5, 2021 at 2:58
  • $\begingroup$ Indeed I think the linear requirement makes it a tricky question... $\endgroup$ Apr 5, 2021 at 2:59
  • 1
    $\begingroup$ @SamHopkins I put in the correct criterion one gets from thinking about group cohomology (whose expression doesn't really need group cohomology in this case). This reverses the problem - instead of checking existence by giving an explicit list of $n$ numbers, one can check nonexistence by giving an explicit list of $2n$ numbers - but doesn't give a completely satisfying answer. I don't know if a more satisfying answer is possible. $\endgroup$
    – Will Sawin
    Apr 5, 2021 at 3:19
  • 1
    $\begingroup$ @SamHopkins Just take $n_i=0$ : ) $\endgroup$
    – Will Sawin
    Apr 5, 2021 at 3:23
3
$\begingroup$

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

$\endgroup$
10
  • 1
    $\begingroup$ If there exist clocks modulo coprime numbers $k$ and $\ell$ then there is also one mod $k\ell$ by the chinese remainder theorem, and clearly a clock mod $k$ will also work mod any divisor of $k$. So the finiteness actually implies there is some $m$ such that the integers for which clocks exist are exactly the divisors of $m$. Your argument shows that $m$ divides $\langle v, \mathbf 1 \rangle$ for all $v \in \operatorname{Ker} H^T$. So I guess the optimistic conjecture would be that it equals the gcd of these. (For undirected graphs this is just the number of vertices.) $\endgroup$
    – lambda
    Apr 5, 2021 at 21:18
  • $\begingroup$ @lambda: yes, that would be the ideal situation, if the maximum $k$ for which a $k$-clock exists was the gcd of $\langle v, \mathbf{1}\rangle$ for $v\in\mathrm{ker}(H^t)$. I think it's possible to give a combinatorial description of the generators of $\mathrm{ker}(H^t)$ (and by the way if $G$ is strongly connected then this kernel should be generated by a single primitive vector). $\endgroup$ Apr 5, 2021 at 21:23
  • 1
    $\begingroup$ On that note, I of course really meant it equals the number of vertices for a connected undirected graph. $\endgroup$
    – lambda
    Apr 5, 2021 at 21:31
  • 2
    $\begingroup$ @lambda This is not necesarily true. For example, if you take any directed graph and double every edge, i.e. double every entry in $H$, it is not possible to solve $Hx =1$ mod $2$, so $k$ cannot be even, but the kernel of $H^T$ is unchanged. It is true when the cokernel of the Laplacian $H^t$ is torsion-free. $\endgroup$
    – Will Sawin
    Apr 5, 2021 at 22:04
  • 1
    $\begingroup$ Okay, I'm no longer optimistic: the undirected 4-cycle has a clock mod 2 but not mod 4. $\endgroup$
    – lambda
    Apr 6, 2021 at 0:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.