We introduce the notion of a move graph, that is, a directed graph whose vertex set is a \(\mathbb Z\)-module \(\mathbb Z_n^m\), and whose arc set is uniquely determined by the action \(M\!:\!\mathbb Z_n^m\to \mathbb Z_n^m\) where \(M\) is an \(m\times m\) matrix with integer entries. We study the manner in which properties of move graphs differ when one varies the choice of cyclic group \(\mathbb Z_n\). Our principal focus is on a special family of such graphs, which we refer to as “sub-add move graphs.”
The origin of this research stems from a 2023 summer REU (Research Experience for Undergraduates) held at Moravian University in Bethlehem, PA. Initial investigations were loosely based on the notions of pebbling and chip-firing, two areas that have fairly robust histories replete with many diverse applications, e.g. see [2, 3, 5, 12, 13].
Graph pebbling is a mathematical game played on a finite simple graph, i.e. a graph with no loops or multiple edges, see [12]. A standard pebbling move consists of removing two pebbles from a vertex \(v\) of \(G\) while simultaneously adding one pebble to a vertex adjacent to \(v\).
Early on, we felt it would be of interest to deviate from the standard rules of pebbling, whereby pebbles are transferred from a given vertex to some subset of its neighbors while exacting a “fee” for the transfer. It occurred to us that this problem could be of greater interest if the number of pebbles transferred would somehow depend on the particular vertices involved in the transaction. This eventually led to incorporating module structure into the problem so that pebble transfers could be dictated by some well-defined action of a group on the vertex set.
We say a group \(G\) acts on a directed graph \(\Gamma\) if the elements of \(G\) permute the vertices of \(\Gamma\) while preserving arcs and non-arcs.
Over the past few decades, there has been extensive literature focused on various aspects of groups acting on graphs (e.g. geometric group actions on trees [9, 15], finite graphs [7, 16], valency and girth [16, 17], and topological graphs [8], among many others). See [1, 6, 11, 14, 19, 20] for recent applications of groups acting on graphs to physiology, neural networks, chemistry, cryptography, and computational methods.
The notation and terminology we shall adopt are largely standard, e.g. see [4, 10, 18] as excellent sources of background material. As is customary, we denote by \(V(\Gamma)\) and \(A(\Gamma)\) the vertex set and arc set of a directed graph \(\Gamma\), respectively. We define the in-degree \(\deg^-(v)\) and out-degree \(\deg^+(v)\) of a vertex \(v\) as follows: \[\deg^-(v)=|\{w\in V(\Gamma)\mid (w,v)\in A(\Gamma)\}|,\] \[\deg^+(v)=|\{w\in V(\Gamma)\mid (v,w)\in A(\Gamma)\}|.\]
Given \((v,w)\in A(\Gamma)\), we refer to \(v\) as a parent of \(w\) and to \(w\) as a child of \(v\). Thus, a vertex \(v\) has \(\deg^-(v)\) parents and \(\deg^+(v)\) children.
Given a directed graph \(\Gamma\), we denote its underlying (undirected) graph by \(\Gamma^u\). A directed cycle \(C\) in \(\Gamma\) is a cycle in \(\Gamma^u\) with the property that in the subgraph of \(\Gamma\) induced on \(C\), one has \(\deg^-(v)=\deg^+(v)=1\) for every vertex \(v\) on \(C\). For notational convenience, we shall interpret \(({v,v})\in A(\Gamma)\) as a directed \(1\)-cycle and a pair \(({v,w}),({w,v})\in A(\Gamma)\) as a directed \(2\)-cycle.
We say a directed graph \(\Gamma\) is weakly connected if \(\Gamma^u\) is connected. Similarly, a weakly connected component of \(\Gamma\) corresponds to a connected component of \(\Gamma^u\).
For us, \(\mathbb N\) will always denote the set of positive integers. We adopt the notation \({\rm Mat}_m(\mathbb Z)\) for the algebra of \(m\times m\) matrices with integer entries, as well as \(GL_m(\mathbb Q)\) for the group of \(m\times m\) invertible matrices with rational entries. The order of a group element \(g\) will be designated by \({\rm ord}(g)\). Lastly, \(\boldsymbol{x}^T\) will denote the transpose of a vector \(\boldsymbol{x}\).
The balance of the paper is organized as follows. In Section 2, we set the stage by defining the notion of a move matrix and its corresponding move graph. In Section 3, we investigate move graphs where the choice of move matrix is arbitrary. The sub-add move graph is introduced in Section 4. In Sections 5–7, we treat special cases of the sub-add move graph. Specifically, we assume the underlying cyclic group \(\mathbb Z_n\) has order \(n=2^r\) (Section 5), odd order \(n\) (Section 6), and odd prime order \(p\) (Section 7).
Given \(M\in {\rm Mat}_m(\mathbb Z)\), we consider the \(m\)-dimensional \(\mathbb Z\)-module \(\mathbb Z_n^m\) where \(\mathbb Z_n\) is the group of integers modulo \(n\). If there exists a least positive integer \(k\) for which \(M^k\) acts as the identity on \(\mathbb Z_n^m\), we refer to \(k\) as the \(\mathbb Z_n\)-order of \(M\).
We now define the move graph \(\Gamma_{M,\,n}\), which is the central object of our investigation. It is the directed graph with vertex set \(V(\Gamma_{M,\,n})\) and arc set \(A(\Gamma_{M,\,n})\) described as follows: \[V(\Gamma_{M,\,n}) = \{\boldsymbol{x}=(x_1,x_2,\dots,x_m) \mid x_i \in \mathbb{Z}_n\},\] \[A(\Gamma_{M,\,n}) = \{ (\boldsymbol{x}, \boldsymbol{y}) \mid \boldsymbol{x}, \boldsymbol{y}\in V(\Gamma_{M,\,n}), \boldsymbol{y}^T=M\boldsymbol{x}^T\}.\]
We caution the reader that expressions of the form \(ax\) where \(a\in\mathbb Z\) and \(x\in\mathbb Z_n\) should not be confused with the binary operation in \(\mathbb Z_n\) which is addition modulo \(n\). Nevertheless, we can always interpret such expressions as elements of \(\mathbb Z_n\). For example, \(ax\) can be interpreted as the sum of \(x\) with itself \(a\) times if \(a\) is positive, or \(-x\) with itself \(-a\) times if \(a\) is negative.
Example 2.1. Consider the move matrix \(M\) given by \[M = \begin{pmatrix} 0 & 0 & 1\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{pmatrix}.\]
As \(M\) has order \(3\) as an element of \(GL_3(\mathbb Q)\), its \(\mathbb Z_n\)-order is \(3\) for all \(n\ge 2\). We depict the move graph \(\Gamma_{M,\,3}\) in Figure 1.
In this section, our main objective is to study structural properties of \(\Gamma_{M,\,n}\) and their dependence on the move matrix \(M\) and the cyclic group \(\mathbb{Z}_n\).
Theorem 3.1. Let \(M \in {\rm Mat}_{m}(\mathbb{Z})\) have \(\mathbb Z_n\)-order \(k\). Suppose \(M^{t}\boldsymbol{x}^T=\boldsymbol{x}^T\) for some \(\boldsymbol{x}\in V(\Gamma_{M,\,n})\), \(t\in\mathbb N\). Then \(\boldsymbol{x}\) is on a unique directed cycle in \(\Gamma_{M,\,n}\) of length dividing \(t\). In particular, all directed cycles in \(\Gamma_{M,\,n}\) have length dividing \(k\).
Proof. We first prove every vertex of \(\Gamma_{M,\,n}\) lies on a unique directed cycle. For this purpose, it suffices to show that \({\rm deg}^-(\boldsymbol{x})={\rm deg}^+(\boldsymbol{x})=1\) for all \(\boldsymbol{x}\in V(\Gamma_{M,\,n})\). Of course, \({\rm deg}^+(\boldsymbol{x})=1\) follows at once from the definition of \(A(\Gamma_{M,\,n})\).
The proof that \({\rm deg}^-(\boldsymbol{x})=1\) for all \(\boldsymbol{x}\in V(\Gamma_{M,\,n})\) hinges on the assumption that \(M\) has finite \(\mathbb Z_n\)-order \(k\). Here we observe that \(M^{k-1}\) is in \({\rm Mat}_{m}(\mathbb{Z})\) and this allows us to consider the move graph \(\Gamma_{M^{k-1},n}\). By the above argument, each vertex \(\boldsymbol{x}\in V(\Gamma_{M^{k-1},n})\) has out-degree \(1\). As \(M\) has finite \(\mathbb Z_n\)-order, \(M\) is injective, which means for each \(\boldsymbol{x}\in V(\Gamma_{M^{k-1},n})\) there exists a unique \(\boldsymbol{y}\in V(\Gamma_{M^{k-1},n})\) for which \(({\boldsymbol{x},y})\in A(\Gamma_{M^{k-1},n})\). But this implies \(\boldsymbol{y}^T=M^{k-1}\boldsymbol{x}^T\) and therefore \(M\boldsymbol{y}^T=M^k\boldsymbol{x}^T=\boldsymbol{x}^T\). It follows that \(({\boldsymbol{y},x})\in A(\Gamma_{M,\,n})\), i.e. \({\rm deg}^-(\boldsymbol{x})= 1\) for all \(\boldsymbol{x}\in V(\Gamma_{M,\,n})\). We conclude that \(\Gamma_{M,\,n}\) is a disjoint union of cycles.
Now suppose \(\boldsymbol{x}\) lies on a directed \(\ell\)-cycle in \(\Gamma_{M,\,n}\) for some \(\ell\in\mathbb N\). Since cycles in \(\Gamma_{M,\,n}\) are disjoint, it follows that \(\ell\) is minimal such that \(M^\ell \boldsymbol{x}^T=\boldsymbol{x}^T\). Thus \(\ell\le t\) whence by the Division Algorithm, \(t=\ell q + r\) for some \(q\in \mathbb{N}\) and \(r\in\mathbb Z\) with \(0 \le r < \ell\). But then \[\boldsymbol{x}^T = M^t\boldsymbol{x}^T = M^{\ell q+r}\boldsymbol{x}^T = M^r((M^\ell)^q\boldsymbol{x}^T) = M^r\boldsymbol{x}^T.\]
Since \(r\ne 0\) contradicts the minimality of \(\ell\), we conclude that \(r=0\), i.e. \(\ell\) divides \(t\) as claimed. \(\square\)
Proposition 3.2. For fixed \(\ell\in\mathbb N\), let \(S\) be the set of all vertices on directed cycles in \(\Gamma_{M,\,n}\) of length dividing \(\ell\). Then any \(\mathbb Z\)-linear combination of vertices from \(S\) yields a vertex on a cycle of length dividing \(\ell\). Moreover, if \(M\) has finite \(\mathbb Z_n\)-order, then for any \(\boldsymbol{x} \in S\) and \(s\in \mathbb Z\) with \(\gcd(s,n)=1\), the vertices \(\boldsymbol{x}\) and \(s\boldsymbol{x}\) lie on cycles of equal length.
Proof. The first assertion is an immediate consequence of the linearity of \(M\). To prove the second assertion, let \(\boldsymbol{x}\) be on a cycle of length \(\ell_1\) and let \(s\boldsymbol{x}\) be on a cycle of length \(\ell_2\). Then \(M^{\ell_1}\boldsymbol{x}^T = \boldsymbol{x}^T\) and \(sM^{\ell_2}\boldsymbol{x}^T=M^{\ell_2}(s\boldsymbol{x}^T) = s\boldsymbol{x}^T\). Since \(\gcd(s,n)=1\), the latter equality simplifies to \(M^{\ell_2}\boldsymbol{x}^T = \boldsymbol{x}^T\). It therefore follows from Theorem 3.1 that \(\ell_1\) and \(\ell_2\) divide one another, whence \(\ell_1=\ell_2\) as claimed. \(\square\)
Theorem 3.3. Let \(n_1,n_2 \in \mathbb N\). Then \(\Gamma_{M,\,n_1}\) embeds in \(\Gamma_{M,\,n_1n_2}\) as an induced subgraph.
Proof. Define the mapping \(f\!:\!V(\Gamma_{M,\,n_1}) \to V(\Gamma_{M,\,n_1n_2})\) by \(f(\boldsymbol{v})=n_2\boldsymbol{v}\). We show \(f\) is injective and preserves arcs and non-arcs.
First suppose \(f(\boldsymbol{x}) = f(\boldsymbol{y})\), i.e. \(n_2\boldsymbol{x} = n_2\boldsymbol{y}\) in \(\mathbb{Z}^m_{n_1n_2}\). Then \(\boldsymbol{x} = \boldsymbol{y}\) in \(\mathbb{Z}^m_{n_1}\) which proves \(f\) is injective. Next observe that \(n_2\boldsymbol{y}^T=(n_2\boldsymbol{y})^T=M(n_2\boldsymbol{x})^T=n_2M\boldsymbol{x}^T\) in \(\mathbb{Z}^m_{n_1n_2}\) if and only if \(\boldsymbol{y}^T=M\boldsymbol{x}^T\) in \(\mathbb{Z}^m_{n_1}\). This implies \(({\boldsymbol{x},y})\in A(\Gamma_{M,\,n_1})\) if and only if \((n_2\boldsymbol{x}, n_2\boldsymbol{y})\in A(\Gamma_{M,\,n_1n_2})\). The result follows. \(\square\)
Remark 3.4. Let \(\Delta_1\) and \(\Delta_2\) be graphs with respective adjacency matrices \(\mathcal A(\Delta_1)\) and \(\mathcal A(\Delta_2)\). Recall that the tensor product \(\Delta_1 \times \Delta_2\) is defined to be the graph with adjacency matrix \(\mathcal A(\Delta_1 \times \Delta_2)\) equal to the Kronecker product \(\mathcal A(\Delta_1) \otimes \mathcal A(\Delta_2)\).
Theorem 3.5. Let \(n_1,n_2\in \mathbb N\) with \(\gcd(n_1,n_2) = 1\). Then \(\Gamma_{M,\,n_1n_2}\) is isomorphic to the tensor product \(\Gamma_{M,\,n_1} \times \Gamma_{M,\,n_2}\).
Proof. Consider the mapping \(f\!:\! V(\Gamma_{M,\,n_1}) \times V(\Gamma_{M,\,n_2}) \rightarrow V(\Gamma_{M,\,n_1n_2})\) defined by \(f(\mathbf{x}, \mathbf{y}) = n_1\mathbf{y} + n_2\mathbf{x}\). We claim \(f\) is a graph isomorphism.
We first show \(f\) is bijective. Suppose \(f(\mathbf{x}, \mathbf{y}) = f(\mathbf{z}, \mathbf{w})\), i.e. \(n_1\mathbf{y} + n_2 \mathbf{x} = n_1\mathbf{w} + n_2\mathbf{z}\). As \(n_1n_2=0\) in \(\mathbb Z_{n_1n_2}\), multiplying by \(n_2\) yields \(n_2^2 \mathbf{x} = n_2^2 \mathbf{z}\), which implies \(n_2\mathbf{x} = n_2\mathbf{z}\) in \(\mathbb{Z}^m_{n_1}\). Since \(\gcd(n_1,n_2) = 1\), it follows that \(\mathbf{x} = \mathbf{z}\) in \(\mathbb{Z}^m_{n_1}\). A similar argument yields \(\mathbf{y} = \mathbf{w}\) in \(\mathbb{Z}^m_{n_2}\). Thus \((\mathbf{x},\mathbf{y}) = (\mathbf{z}, \mathbf{w})\), i.e. \(f\) is injective. Since \(|V(\Gamma_{M,\,n_1}) \times V(\Gamma_{M,\,n_2})| = n_1^mn_2^m=(n_1n_2)^m = |V(\Gamma_{M,\,n_1n_2})|\), we have that \(f\) is surjective as well.
We next prove \(f\) preserves arcs and non-arcs by establishing that \((n_1\mathbf{y} + n_2\mathbf{x}, n_1\mathbf{w}+n_2\mathbf{z}) \in A(\Gamma_{M,\,n_1n_2})\) if and only if \((\mathbf{x}, \mathbf{z}) \in A(\Gamma_{M,\,n_1})\) and \((\mathbf{y}, \mathbf{w}) \in A(\Gamma_{M,\,n_2})\).
By definition, \((\mathbf{x} , \mathbf{z}) \in A(\Gamma_{M,\,n_1})\) implies \(M\mathbf{x}^T = \mathbf{z}^T\) while \((\mathbf{y}, \mathbf{w})\in A(\Gamma_{M,\,n_2})\) implies \(M\mathbf{y}^T = \mathbf{w}^T\). As a consequence, in \(\mathbb{Z}^m_{n_1n_2}\) we have \(M(n_2\mathbf{x})^T= n_2M\mathbf{x}^T = n_2\mathbf{z}^T\) and \(M(n_1\mathbf{y})^T=n_1M\mathbf{y}^T = n_1\mathbf{w}^T\). Summing these equalities yields \(M(n_2\mathbf{x})^T + M(n_1\mathbf{y})^T = n_2\mathbf{z}^T + n_1\mathbf{w}^T\) or equivalently, \(M(n_2\mathbf{x}+ n_1\mathbf{y})^T= (n_2\mathbf{z} + n_1\mathbf{w})^T\). We conclude that \((n_1\mathbf{y} + n_2\mathbf{x}, n_1\mathbf{w}+n_2\mathbf{z}) \in A(\Gamma_{M,\,n_1n_2})\).
Conversely, suppose \((n_1\mathbf{y} + n_2\mathbf{x}, n_1\mathbf{w}+n_2\mathbf{z})\in A(\Gamma_{M,\,n_1n_2})\) in which case \(n_1\mathbf{w}^T + n_2\mathbf{z}^T=M(n_1\mathbf{y}^T + n_2\mathbf{x}^T)=n_1M\mathbf{y}^T + n_2M\mathbf{x}^T\). Multiplying by \(n_2\) gives \(n_2^2\mathbf{z}^T=n_2^2M\mathbf{x}^T\) since \(n_1n_2=0\) in \(\mathbb{Z}_{n_1n_2}\). Thus \(n_1n_2\) divides \(n_2^2(\mathbf{z}^T-M\mathbf{x}^T)\) whence \(n_1\) must divide \(\mathbf{z}^T-M\mathbf{x}^T\) since \(\gcd(n_1,n_2)=1\). We conclude that \(M\mathbf{x}^T=\mathbf{z}^T\) in \(\mathbb Z_{n_1}^m\) whence \((\mathbf{x} , \mathbf{z}) \in A(\Gamma_{M,\,n_1})\). By a symmetric argument, \((n_1\mathbf{y} + n_2\mathbf{x}, n_1\mathbf{w}+n_2\mathbf{z})\in A(\Gamma_{M,\,n_1n_2})\) implies \((\mathbf{y}, \mathbf{w})\in A(\Gamma_{M,\,n_2})\). It follows that \(f\) preserves arcs and non-arcs, i.e. \(f\) is a graph isomorphism as claimed. \(\square\)
Theorem 3.6. Let \(M_1,M_2\in {\rm Mat}_m(\mathbb{Z})\) and \(S\in {\rm Mat}_m(\mathbb Z)\cap GL_m(\mathbb Q)\) such that \(M_2=S^{-1}M_1S\). Then for any \(n\in\mathbb N\) with \(\gcd(n, {\rm det}(S))=1\), the move graphs \(\Gamma_{M_1,\,n}\) and \(\Gamma_{M_2,\,n}\) are isomorphic.
Proof. We define the map \(f\!:\!V(\Gamma_{M_2,\,n}) \to V(\Gamma_{M_1,\,n})\) by \(f(\boldsymbol{v}) = \boldsymbol{v}S^T\). Note that \(\boldsymbol{v}S^T\in V(\Gamma_{M_1,\,n})\) for all \(\boldsymbol{v}\in V(\Gamma_{M_2,\,n})\) because \(S^T\in {\rm Mat}_m(\mathbb{Z})\). We claim \(f\) is a graph isomorphism.
Suppose first that \(f(\boldsymbol{x})=\boldsymbol{0}\), i.e. \(\boldsymbol{x}S^T=\boldsymbol{0}\). Then \(\sum_{i=1}^m x_i \boldsymbol{r}_i=\boldsymbol{0}\) where \(x_i\) is the \(i\)-th coordinate of \(\boldsymbol{x}\), and \(\boldsymbol{r}_i\) is the \(i\)-th row of \(S^T\) taken modulo \(n\). Assuming \(\gcd(n,{\rm det}(S))=1\), it follows that the subset \(\{\boldsymbol{r}_1, \boldsymbol{r}_2,\dots, \boldsymbol{r}_m\}\subset \mathbb Z_n^m\) is linearly independent. Therefore \(x_i=0\) for all \(1\le i\le m\), i.e. \(\boldsymbol{x}=\boldsymbol{0}\).
Now suppose \(f(\boldsymbol{v})=f(\boldsymbol{w})\), i.e. \(\boldsymbol{v}S^T= \boldsymbol{w}S^T\). Then \((\boldsymbol{v}-\boldsymbol{w})S^T=\boldsymbol{0}\) whence it follows from above that \(\boldsymbol{v}-\boldsymbol{w}=\boldsymbol{0}\), i.e. \(\boldsymbol{v}=\boldsymbol{w}\) in \(\mathbb Z_n^m\). We thereby conclude that \(f\) is injective. Surjectivity, and therefore bijectivity, now follow since \(V(\Gamma_{M_1,\,n})= V(\Gamma_{M_2,\,n})\).
Finally, observe that \((\boldsymbol{x},\boldsymbol{y}) \in A(\Gamma_{M_2,\,n})\) if and only if \(\boldsymbol{y}^T = M_2\boldsymbol{x}^T=S^{-1}M_1S\boldsymbol{x}^T\), i.e. if and only if \((f(\boldsymbol{y}))^T=S\boldsymbol{y}^T=M_1S\boldsymbol{x}^T=M_1(f(\boldsymbol{x}))^T\). As this is equivalent to \((f(\boldsymbol{x}), f(\boldsymbol{y})) \in A(\Gamma_{M_1,\,n})\), we conclude that \(f\) preserves arcs and non-arcs, hence \(f\) is a graph isomorphism. \(\square\)
Theorem 3.7. Let \(M \in {\rm Mat}_{m}(\mathbb{Z})\) and \(S\in {\rm Mat}_m(\mathbb Z)\cap GL_m(\mathbb Q)\) such that \(S^{-1}MS\) is the rational canonical form of \(M\). Then for any prime \(p\) with \(\gcd({\rm det}(S),p)=1\) and for which \(M\) has finite \(\mathbb Z_p\)-order \(k\), the move graph \(\Gamma_{M,\,p}\) contains a directed \(k\)-cycle.
Proof. Assume \(p\) is a prime such that \(\gcd({\rm det}(S),p)=1\) and suppose \(M\) has \(\mathbb Z_p\)-order \(k\). By Theorem 3.6, it suffices to show \(\Gamma_{S^{-1}MS,\,p}\) contains a directed \(k\)-cycle.
Here \(S^{-1}MS=M_1 \oplus M_2 \oplus \cdots \oplus M_f\) where for each \(1\le i\le f\) and suitably chosen \(\boldsymbol{v}_i\in \mathbb Z^m\), the \(m_i\times m_i\) block matrix \(M_i\) is expressed in terms of the basis \(\{\boldsymbol{v}_i^T,M\boldsymbol{v}_i^T,M^2\boldsymbol{v}_i^T,\dots,\\ M^{m_i-1}\boldsymbol{v}_i^T\}\) for the \(i\)-th \(M\)-invariant subspace of dimension \(m_i\) over \(\mathbb Q\).
Now form the sum \(\boldsymbol{v} = \boldsymbol{v}_1 \oplus \boldsymbol{v}_2 \oplus \cdots \oplus \boldsymbol{v}_f\) where \(\boldsymbol{v}_i\) is chosen in the above manner for each \(1\le i\le f\). We consider the corresponding sum taken modulo \(p\), i.e. \(\boldsymbol{x} = \boldsymbol{x}_1 \oplus \boldsymbol{x}_2 \oplus \cdots \oplus \boldsymbol{x}_f\) where \(\boldsymbol{x}\in\mathbb Z_p^m\) and \(\boldsymbol{x}_i\in \mathbb Z_p^{m_i}\) with \(\boldsymbol{x}\equiv \boldsymbol{v}\,(\mathrm{mod}\ p)\) and \(\boldsymbol{x}_i\equiv \boldsymbol{v}_i\,(\mathrm{mod}\ p)\). By Theorem 3.1, \(\boldsymbol{x}\) lies on a directed \(\ell\)-cycle in \(\Gamma_{S^{-1}MS,\,p}\) for some \(\ell\) dividing \(k\). This implies \(\boldsymbol{x}^T = (S^{-1}MS)^\ell \boldsymbol{x}^T =(S^{-1}M^{\ell}S) \boldsymbol{x}^T = M_1^{\ell} \boldsymbol{x}_1^T \oplus M_2^{\ell} \boldsymbol{x}_2^T \oplus \cdots \oplus M_f^{\ell} \boldsymbol{x}_f^T\) from which we deduce that \(M_i^{\ell} \boldsymbol{x}_i^T = \boldsymbol{x}_i^T\) for each \(1 \leq i \leq f\).
Now let \(k_i\) be the \(\mathbb Z_p\)-order of \(M_i\), \(1\le i\le f\). Since \(S^{-1}MS\) and \(M\) have the same \(\mathbb Z_p\)-order, it follows that \(k={\rm lcm}(k_1,k_2, \dots,k_f)\). But \(M_i^{\ell} \boldsymbol{x}_i^T = \boldsymbol{x}_i^T\) implies \(k_i\) divides \(\ell\) for each \(1\le i\le f\). Thus \(k\) divides \(\ell\), whence \(k=\ell\) from above. We conclude that \(\Gamma_{S^{-1}MS,\,p}\) contains a directed \(k\)-cycle as desired. \(\square\)
For the balance of this paper, \(M\) will denote the so-called sub-add move matrix given by \[M = \begin{pmatrix} 1 &\!\! -1 \\ 1 &\;\, 1 \end{pmatrix}.\]
The name derives from the action of \(M\) on \(\mathbb{Z}_n^2\), which results in subtraction in the first coordinate and addition in the second coordinate as indicated below. \[\begin{pmatrix} 1 &\!\! -1 \\ 1 &\;\, 1 \end{pmatrix} \begin{pmatrix} a \\ b\end{pmatrix} = \begin{pmatrix} a-b \\ a+b \end{pmatrix}.\]
Our main goal is to investigate the structure of the move graph \(\Gamma_{M,\,n}\) for certain values of \(n\). We refer to \(\Gamma_{M,\,n}\) as a sub-add move graph.
Example 4.1. In Figures 2 and 3 we depict the sub-add move graphs \(\Gamma_{M,\,3}\) and \(\Gamma_{M,\,4}\), respectively.
For fixed \(r \in \mathbb N\), we may express the \(\mathbb Z\)-module \(\mathbb Z_{2^r}^2\) in the following manner. \[\mathbb Z_{2^r}^2 = \{(2^tx,2^ty) \in \mathbb{Z}_{2^r}^2 \mid \text{at least one of $x,y$ is odd}, 0\le t\le r\}.\]
This alternate description makes it transparent that the subsets defined below form a partition of the vertex set \(V(\Gamma_{M,\,2^r})= \mathbb Z_{2^r}^2\). \[\begin{cases} \;\;\mathcal P_{2t}= \{(2^t x, 2^t y)\mid \text{exactly one of $x$ and $y$ is odd}\}, & {0\le t\le r-1}\\[1ex] \;\;\mathcal P_{2t+1}=\{2^{t}x, 2^{t} y)\mid \text{both $x$ and $y$ are odd}\}, & {0\le t\le r-1}\\[1ex] \;\;\mathcal P_{2r} = \{(0,0)\}. \end{cases}\]
Remark 5.1. Technically, \(x\) and \(y\) are elements of \(\mathbb Z_{2^r}\) and not integers. Nevertheless, we may regard them as integers when designating their parities. Indeed, since the group \(\mathbb Z_{2^r}\) has even order, this designation is well-defined.
Occasionally, it will behoove us to express subsets of the partition simply as \(\mathcal P_i\), \(0\le i\le 2r\). This is purely for notational convenience.
Proposition 5.2. For every \(0 \le i < 2r\), each vertex \((a_i,b_i) \in \mathcal{P}_i\) has a unique child \((a_{i+1},b_{i+1})\). Moreover, this child lies in \(\mathcal{P}_{i+1}\). For \(i=2r\), the lone vertex \((0,0) \in \mathcal{P}_{2r}\) is its own unique child.
Proof. Observe that \((2^{t}(x-y),2^{t}(x+y))\) is the unique child of \((2^{t}x,2^{t}y)\in\mathcal P_i\). Hence it remains to prove \((2^{t}(x-y),2^{t}(x+y))\in \mathcal P_{i+1}\).
Case 1. \(i=2t\), \(0\le t<r\). Since \((2^{t}x,2^{t}y)\in\mathcal P_{2t}\), \(x\) and \(y\) must have opposite parity. This means \(x-y\) and \(x+y\) are both odd, so it follows that \((2^t(x-y),2^t(x+y)) \in \mathcal{P}_{2t+1}\).
Case 2. \(i=2t+1\), \(0\le t<r\). In this case, \((2^{t}x,2^{t}y)\in\mathcal P_{2t+1}\) so both \(x\) and \(y\) are odd. Thus \(x-y\) and \(x+y\) are both even, so the unique child \((2^{t}(x-y),2^{t}(x+y))\) is \((2^{t+1}(\frac{x-y}{2}), 2^{t+1}(\frac{x+y}{2}))\). Now observe that \(\frac{x-y}{2}+\frac{x+y}{2}=x\) which is odd. This proves \(\frac{x-y}{2}\) and \(\frac{x+y}{2}\) must have opposite parity whence \((2^{t+1}(\frac{x-y}{2}), 2^{t+1}(\frac{x+y}{2}))\in \mathcal P_{2t+2}\) as desired.
Finally it is obvious that the only child of \((0,0)\) is itself. \(\square\)
Proposition 5.3. All vertices in \(\mathcal P_0\) are parentless.
Proof. Let \((x,y)\) be an arbitrary vertex in \(\mathcal P_0\) whence exactly one of \(x, y\) is odd. This of course implies \(x+y\) must be odd. Suppose now that \((a,b)\) is a parent of \((x,y)\). Then \((a-b,a+b)=(x,y)\) from which we obtain the contradiction \(a=\frac{x+y}{2}\). \(\square\)
Remark 5.4. Note that Propositions 5.2 and 5.3 establish the existence of levels in the sub-add move graph \(\Gamma_{M,\,2^r}\). That is to say, all vertices in \(\mathcal P_0\) occur at the top level, their collective children occur at the next level, and so on down to the bottom level, which consists only of the single vertex \((0,0)\), see Figure 3.
Proposition 5.5. Let \(r>1\). Then \(\big(2^{\lfloor \frac{i}{2} \rfloor}(x-y),2^{\lfloor \frac{i}{2} \rfloor}(x+y)\big) \in \mathcal{P}_{i+1}\) has exactly two parents for every \(0 \leq i \le 2r-1\).
Proof. Clearly, \((2^{\lfloor \frac{i}{2} \rfloor}x,2^{\lfloor \frac{i}{2} \rfloor}y),(2^{\lfloor \frac{i}{2} \rfloor}x+2^{r-1},2^{\lfloor \frac{i}{2} \rfloor}y+2^{r-1})\) are two distinct parents of \((2^{\lfloor \frac{i}{2} \rfloor}(x-y),2^{\lfloor \frac{i}{2} \rfloor}(x+y)) \in \mathcal{P}_{i+1}\). Let us assume this latter vertex has a third parent. By Proposition 5.2, this parent must lie in \(\mathcal P_i\) and therefore be of the form \((2^{\lfloor \frac{i}{2} \rfloor}x_1,2^{\lfloor \frac{i}{2} \rfloor}y_1)\). Since \(\lfloor\frac{i}{2}\rfloor< r\), we thereby obtain \(2^{\lfloor \frac{i}{2} \rfloor}(x_1-y_1) \equiv 2^{\lfloor \frac{i}{2} \rfloor}(x-y) \,(\mathrm{mod}\ 2^r)\) and \(2^{\lfloor \frac{i}{2} \rfloor}(x_1+y_1) \equiv 2^{\lfloor \frac{i}{2} \rfloor}(x+y)\,(\mathrm{mod}\ 2^r)\). Since \(r>1\), these together imply \(2^{\lfloor \frac{i}{2} \rfloor}2x_1 \equiv 2^{\lfloor \frac{i}{2} \rfloor}2x\,(\mathrm{mod}\ 2^r)\) and \(2^{\lfloor \frac{i}{2} \rfloor}2y_1 \equiv 2^{\lfloor \frac{i}{2} \rfloor}2y\,(\mathrm{mod}\ 2^r)\). This gives rise to the following four possibilities: \[(2^{\lfloor \frac{i}{2} \rfloor}x_1,2^{\lfloor \frac{i}{2} \rfloor}y_1) = \begin{cases} (2^{\lfloor \frac{i}{2} \rfloor}x,2^{\lfloor \frac{i}{2} \rfloor}y), \\ (2^{\lfloor \frac{i}{2} \rfloor}x + 2^{r-1},2^{\lfloor \frac{i}{2} \rfloor}y), \\ (2^{\lfloor \frac{i}{2} \rfloor}x,2^{\lfloor \frac{i}{2} \rfloor}y + 2^{r-1}), \\ (2^{\lfloor \frac{i}{2} \rfloor}x + 2^{r-1},2^{\lfloor \frac{i}{2} \rfloor}y + 2^{r-1}). \end{cases}\]
But neither \((2^{\lfloor \frac{i}{2} \rfloor}x_1,2^{\lfloor \frac{i}{2} \rfloor}y_1)=(2^{\lfloor \frac{i}{2} \rfloor}x + 2^{r-1},2^{\lfloor \frac{i}{2} \rfloor}y)\) nor \((2^{\lfloor \frac{i}{2} \rfloor}x_1,2^{\lfloor \frac{i}{2} \rfloor}y_1)=(2^{\lfloor \frac{i}{2} \rfloor}x,2^{\lfloor \frac{i}{2} \rfloor}y + 2^{r-1})\) can occur because \(2^{\lfloor \frac{i}{2} \rfloor}x + 2^{\lfloor \frac{i}{2} \rfloor}y + 2^{r-1} \not\equiv 2^{\lfloor \frac{i}{2} \rfloor}x + 2^{\lfloor \frac{i}{2} \rfloor}y\,(\mathrm{mod}\ 2^r)\). As the remaining possibilities correspond to the two aforementioned parents of \((2^{\lfloor \frac{i}{2} \rfloor}(x+y),2^{\lfloor \frac{i}{2} \rfloor}(y-x))\), the result follows when \(i < 2r-1\).
The above argument also applies to the case \(i=2r-1\), but here there is an interesting subtlety. In this instance the child in question is \((2^{r-1}(x-y),2^{r-1}(x+y))\in\mathcal P_{2r}=\{(0,0)\}\). From above, its only parents are \((2^{r-1}x,2^{r-1}y)\) and \((2^{r-1}(x+1),2^{r-1}(y+1))\), however since \((2^{r-1}(x-y),2^{r-1}(x+y))=(0,0)\), we see that \(x-y\) and \(x+y\) must both be even implying that \(x\) and \(y\) have the same parity. If we assume \(x\) and \(y\) are both even, then \(x+1\) and \(y+1\) are both odd. Alternatively, if we assume \(x\) and \(y\) are both odd, then \(x+1\) and \(y+1\) are both even. In either case, one parent of \((0,0)\) is \((0,0)\) itself whereas the other parent lies in \(\mathcal P_{2r-1}\). This completes the proof of the proposition. \(\square\)
Proposition 5.6. For \(0 \leq i < 2r\), \(|\mathcal{P}_i|= 2^{2r-i-1}\).
Proof. As before, we consider individual cases based on the parity of \(i\).
Case 1. \(i=2t\). Here there are \(2^{r-t}\) choices for \(x\), and since \(x\) and \(y\) must have opposite parity there are \(2^{r-t-1}\) independent choices for \(y\). Thus, in total there are \(2^{r-t} \cdot 2^{r-t-1} = 2^{2r-2t-1}\) choices for the pair \((2^tx,2^ty)\). Hence \(|\mathcal{P}_{2t}| = 2^{2r-2t-1}=2^{2r-i-1}\).
Case 2. \(i=2t+1\). In this case \(x\) and \(y\) must both be odd. Thus there are \(2^{r-t-1}\) choices for each of \(x\) and \(y\), hence \(2^{r-t-1} \cdot 2^{r-t-1} = 2^{2r-2t-2}\) pairs \((2^tx,2^ty)\) in total. Thus \(|\mathcal{P}_{2t+1}| = 2^{2r-2t-2}= 2^{2r-i-1}\) in this case as well. \(\square\)
Recall that a perfect binary tree \(PBT_d\) is a type of binary tree where all non-leaf nodes have two children and all leaf nodes are at the same depth \(d\). We refer to the unique parentless node \(v\) of \(PBT_d\) as its root node, and we consider \(PBT_d\) to be directed in the sense that there is a unique directed path from \(v\) to each leaf node of \(PBT_d\). Finally, we call \(PBT_d\) inverted if the orientation of every arc of \(PBT_d\) is reversed.
Theorem 5.7. For each \(r\in \mathbb N\), consider the subgraph \(\Delta\) of \(\Gamma_{M,\,2^r}\) induced on the vertex set \(V(\Gamma_{M,\,2^r})\setminus \{(0,0)\}\). Then \(\Delta\) is an inverted \(PBT_d\) of depth \(d=2^r-1\). Moreover, one recovers \(\Gamma_{M,\,2^r}\) from \(\Delta\) by adding the vertex \((0,0)\) along with the two arcs \(((2^{r-1},2^{r-1}),(0,0))\) and \(((0,0),(0,0))\).
Proof. The structure of \(\Delta\) follows directly from Propositions 5.2–5.5. To prove the latter assertion, we observe that the unique childless vertex of \(\Delta\) is \((2^{r-1},2^{r-1})\) and clearly \(((2^{r-1},2^{r-1}),(0,0))\in A(\Gamma_{M,\,2^r})\). \(\square\)
We once more refer the reader to Figure 3, which illustrates Theorem 5.7 for the case \(r=2\).
Throughout this section, \(n\ge 3\) will be an odd integer.
Theorem 6.1. \(\Gamma_{M,\,n}\) is a disjoint union of directed cycles.
Proof. By Theorem 3.1, it suffices to show the move matrix \(M\) has finite \(\mathbb Z_n\)-order. However \(M^4=-4I\). Thus \(M\) has \(\mathbb Z_n\)-order dividing \(4t\) where \(t={\rm ord}(-4)\) in \(\mathbb Z_n\). \(\square\)
Theorem 6.2. For \(n\ge 3\) odd, the length of every directed cycle in \(\Gamma_{M,\,n}\) divides \(4\,\varphi(n)\) where \(\varphi\) denotes Euler’s totient function.
Proof. Since \(M^4=-4 I\), we have \(M^{4\varphi(n)}=(-4)^{\varphi(n)} I=4^{\varphi(n)} I\) since \(\varphi(n)\) is even for all \(n\ge 3\). Thus \(M^{4^\varphi(n)}({x},{y})^T=(4^{\varphi(n)}{x},4^{\varphi(n)}{y})^T\). However, by Euler’s totient theorem we have \(4^{\varphi(n)}\equiv 1\,(\mathrm{mod}\ n)\). Thus it follows that \(M^{4\varphi(n)}({x},{y})^T=({x},{y})^T\) whence the \(\mathbb Z_n\)-order of \(M\) divides \(4\,\varphi(n)\). The result now follows from Theorem 3.1. \(\square\)
Theorem 6.3. Let \(n_1 \ge 3\) be odd and \(n_2=2^k\). Then \(\Gamma_{M,\,n_1n_2}\) contains \(n_1^2\) vertex-disjoint copies of \(\Gamma_{M,\,n_2}\). Furthermore, \(\Gamma_{M,\,n_1n_2}\) and \(\Gamma_{M,\,n_1}\) have the same number of weakly-connected components.
Proof. By Remark 3.4 and Theorem 3.5, we have that \(\mathcal{A}(\Gamma_{M,\,n_1n_2})\) is permutation equivalent to the matrix \[\mathcal{A}(\Gamma_{M, n_1}) \otimes \mathcal{A}(\Gamma_{M, n_2}) = \begin{bmatrix} \big(\mathcal{A}(\Gamma_{M, n_1})\big)_{1,1} \mathcal{A}(\Gamma_{M, n_2}) & \cdots & \big(\mathcal{A}(\Gamma_{M, n_1})\big)_{1,n_1^2} \mathcal{A}(\Gamma_{M, n_2}) \\[1mm] \vdots & \ddots & \vdots \\[1mm] \big(\mathcal{A}(\Gamma_{M, n_1})\big)_{n_1^2,1} \mathcal{A}(\Gamma_{M, n_2}) & \cdots & \big(\mathcal{A}(\Gamma_{M, n_1})\big)_{n_1^2,n_1^2} \mathcal{A}(\Gamma_{M, n_2}) \end{bmatrix}.\]
Here, each of the \(n_1^2\) vertices of \(\Gamma_{M, n_1}\) corresponds to a block matrix \(\mathcal{A}(\Gamma_{M, n_2})\) as depicted in \(\mathcal{A}(\Gamma_{M, n_1}) \otimes \mathcal{A}(\Gamma_{M, n_2})\). Thus \(\Gamma_{M, n_1n_2}\) contains \(n_1^2\) vertex-disjoint copies of \(\Gamma_{M, n_2}\). Similarly, each directed cycle of \(\Gamma_{M, n_1}\) extends to a unique weakly-connected component in \(\Gamma_{M, n_1n_2}\). \(\square\)
In Figure 5, we provide an example of a move graph that illustrates Theorem 6.3.
Throughout this section, \(t\) will denote the order of \(-4\) in the multiplicative group of the finite field \(GF(p)\). Since \(M^4 = -4I\), it follows that \(k=4t\) is the order of \(M\).
Our goal is to determine the existence and length of directed cycles in \(\Gamma_{M,\,p}\) in terms of the eigenvalues of \(M\), viz. \(1+i\) and \(1-i\) where \(i^2=-1\). Without loss of generality, we may assume \(s\le s’\) where \(s={\rm ord}(1-i)\) and \(s’={\rm ord}(1+i)\). Since \(M^k=I\), it is clear that \(s’=k\) and \(s\) divides \(k\). Also, since \((1-i)^4 = -4\) and \({\rm ord}(-4) =t\), we have \(s= t\gcd{(s, 4)}\). Clearly, this implies \(s \in \{t, 2t, 4t\}\).
Proposition 7.1. With notation as above, the only possible cycle lengths in \(\Gamma_{M,\,p}\) are \(1\), \(s\) and \(k\), where \(s\) and \(k\) are not necessarily distinct. In particular, if \(p \equiv 3 \,(\mathrm{mod}\ 4)\) the only possible cycle lengths are \(1\) and \(k\).
Proof. Since \(p\) is prime, we may regard \(V(\Gamma_{M,\,p})=\mathbb Z_p^2\) as a \(2\)-dimensional vector space \(V\) over \(GF(p)\). Observe that \(i\in GF(p)\) if and only if \(-1\) is a square in \(GF(p)\), i.e. if and only if \(p\equiv 1\,(\mathrm{mod}\ 4)\). We treat this case first.
Let \(\boldsymbol{v}^T\) and \(\boldsymbol{w}^T\) be eigenvectors of \(M\) corresponding to the eigenvalues \(1+i\) and \(1-i\), respectively. Since \(1+ i, 1-i\in GF(p)\), we have that \(\{\boldsymbol{v}^T, \boldsymbol{w}^T\}\) is a basis for \(V\).
Let now \(C\) be an arbitrary directed cycle in \(\Gamma_{M,\,p}\) and denote its length by \(\ell\). If \(\ell\in \{1,k\}\) we are done, so assume otherwise. Let \(\boldsymbol{x}\) be a vertex on \(C\), in which case \(M^\ell \boldsymbol{x}^T=\boldsymbol{x}^T\). We may express \(\boldsymbol{x}^T\) as \(a\boldsymbol{v}^T + b\boldsymbol{w}^T\) for suitable scalars \(a,b\in GF(p)\). Thus we obtain \[a\boldsymbol{v}^T+ b\boldsymbol{w}^T=M^\ell (a\boldsymbol{v}^T+ b\boldsymbol{w}^T)= aM^\ell \boldsymbol{v}^T + b M^\ell \boldsymbol{w}^T=a(1+i)^\ell \boldsymbol{v}^T +b(1-i)^\ell \boldsymbol{w}^T,\] so that \(a=a(1+i)^\ell\) and \(b=b(1-i)^\ell\). The former equality implies either \(a=0\) or \((1+i)^\ell = 1\). But by Theorem 3.1, \((1+i)^\ell = 1\) implies \(\ell=k\), a case we have ruled out by assumption. Thus \(a=0\), in which case \(\boldsymbol{x}^T=b\boldsymbol{w}^T\), \(b\ne 0\), i.e. \(\boldsymbol{x}^T\) is an eigenvector corresponding to the eigenvalue \(1-i\). As such, \(\boldsymbol{x}\) lies on a directed cycle of length \(s\) since \(M^s\boldsymbol{x}^T=\boldsymbol{x}^T\). We thereby conclude from Theorem 3.1 that \(\ell=s\).
The case \(p\equiv 3\,(\mathrm{mod}\ 4)\) requires that the above proof be modified slightly. Specifically, \(i\) is no longer an element of \(GF(p)\) but lies in the unique quadratic extension \(GF(p^2)\) of \(GF(p)\). Here \(i+1,i-1\in GF(p^2)\) are algebraically conjugate over \(GF(p)\), hence they have the same order \(s=s’=k\). Note that in this case \(\boldsymbol{v}^T, \boldsymbol{w}^T\notin V\), however \(\{\boldsymbol{v}^T, \boldsymbol{w}^T\}\) still serves as a basis for a 2-dimensional vector space over \(GF(p^2)\). As such, the linear combination \(\boldsymbol{x}^T=a\boldsymbol{v}^T + b\boldsymbol{w}^T\) now allows \(a,b\in GF(p^2)\), where, as before, \(\boldsymbol{x}\in V\) is a vertex on an arbitrary directed cycle \(C\) in \(\Gamma_{M,p}\) of length \(\ell > 1\). Since \(M^\ell \boldsymbol{x}^T=\boldsymbol{x}^T\), we obtain \[\begin{aligned} a\mathbf{v}^T+b\mathbf{w}^T&=\boldsymbol{x}^T\\&=M^\ell \mathbf{x}^T\\&=M^\ell (a\mathbf{v}^T+b\mathbf{w}^T)\\& =aM^\ell \mathbf{v}^T + bM^\ell \mathbf{w}^T\\ &=a(1+i)^\ell \mathbf{v}^T+b(1-i)^\ell \mathbf{w}^T , \end{aligned}\] which implies \(a=a(1+i)^\ell\) and \(b=b(1-i)^\ell\). Since \(a\) and \(b\) cannot simultaneously be zero, at least one of \((1+i)^\ell\) and \((i-1)^\ell\) must equal \(1\). But \((1+i)^\ell=1\) implies \(s’\) divides \(\ell\), whereas \((1-i)^\ell=1\) implies \(s\) divides \(\ell\). In any case, since \(s=s’=k\) we conclude that \(\ell=k\). Accordingly, the only cycle lengths in \(\Gamma_{M,p}\) are \(1\) and \(k\) when \(p \equiv 3 \,(\mathrm{mod}\ 4)\). \(\square\)
We refer to a directed cycle of length \(k\) in \(\Gamma_{M,\,p}\) as a primary cycle. A secondary cycle will be any directed cycle in \(\Gamma_{M,\,p}\) that is neither primary nor a \(1\)-cycle.
Note that primary cycles always exist. Indeed, if \(\boldsymbol{v}^T\) is an eigenvector of \(M\) corresponding to the eigenvalue \(1+i\), then the vertex \(\boldsymbol{v}\) will lie on a \(k\)-cycle since \({\rm ord}(1+i)=k\). In contrast, we see from the proof of Proposition 7.1 that secondary cycles exist if and only if \(s\in \{t,2t\}\) where \(s={\rm ord}(1-i)\).
Our next result elaborates on Proposition 7.1 to a far greater extent.
Theorem 7.2. (a) If \(t\) is even, then \(\Gamma_{M,\,p}\) has no secondary cycles.
(b) If \(t \equiv 1 \,(\mathrm{mod}\ 4)\) and \((1+i)^t=i\), then all secondary cycles have length \(t\).
(c) If \(t \equiv 3 \,(\mathrm{mod}\ 4)\) and \((1+i)^t=i\), then all secondary cycles have length \(2t\).
(d) If \(t \equiv 1 \,(\mathrm{mod}\ 4)\) and \((1+i)^t = -i\), then all secondary cycles have length \(2t\).
(e) If \(t \equiv 3 \,(\mathrm{mod}\ 4)\) and \((1+i)^t=-i\), then all secondary cycles have length \(t\).
Proof. Recall that \({\rm ord}(1+i)=4t\) which implies \((1+i)^t \in \{i,-i\}\). We first consider the case where \((1+i)^t=i\). As \(1-i = -i(1+i)\) and \((1+i)^{3t}=-i\), we have \(1-i=(1+i)^{3t+1}\). Observe that \[{\rm ord}(1-i) = \frac{4t}{\gcd(3t+1,4t)} = \frac{4t}{\gcd(3t+1,t-1)} = \frac{4t}{\gcd(4,t-1)}.\]
Thus, if \(t\) is even we have \(\gcd(4,t-1)=1\) whence \({\rm ord}(1-i)=4t\). We conclude that \(\Gamma_{M,\,p}\) has no secondary cycles in this case.
Next assume \(t \equiv 1 \,(\mathrm{mod}\ 4)\). This implies \(\gcd(4,t-1)=4\) whence \({\rm ord}(1-i)=t\). In this case, all secondary cycles have length \(t\). Similarly, if \(t \equiv 3 \,(\mathrm{mod}\ 4)\), then \(\gcd(4,t-1)=2\) which implies all secondary cycles have length \(2t={\rm ord}(1-i)\).
Finally, we consider the case \((1+i)^t=-i\). Here we have \(1-i=(1+i)^{t+1}\) and therefore \[{\rm ord}(1-i) = \frac{4t}{\gcd(t+1,4t)} = \frac{4t}{\gcd(t+1,4)}.\]
In this case, the roles of congruence are reversed in the sense that \(t \equiv 1 \,(\mathrm{mod}\ 4)\) implies \({\rm ord}(1-i)=2t\) while \(t \equiv 3 \,(\mathrm{mod}\ 4)\) implies \({\rm ord}(1-i)=t\). Accordingly, all secondary cycles in \(\Gamma_{M,\,p}\) have length \(2t\) if \(t \equiv 1 \,(\mathrm{mod}\ 4)\) or they have length \(t\) if \(t \equiv 3 \,(\mathrm{mod}\ 4)\). As above, if \(t\) is even then \(\gcd(t+1,4)=1\), in which case \({\rm ord}(1-i)=4t\), i.e. \(\Gamma_{M,\,p}\) has no secondary cycles. \(\square\)
Corollary 7.3. \(\Gamma_{M,\,p}\) contains secondary cycles if and only if \(8\) does not divide \(k\).
Proof. This follows immediately from Theorem 7.2 since \(k\) is divisible by \(8\) if and only if \(t\) is even. \(\square\)
Theorem 7.4. (a) If \(p \equiv 3 \,(\mathrm{mod}\ 8)\) or \(p \equiv 7 \,(\mathrm{mod}\ 8)\), then secondary cycles do not exist in \(\Gamma_{M,\,p}\).
(b) If \(p \equiv 5 \,(\mathrm{mod}\ 8)\), then secondary cycles must exist in \(\Gamma_{M,\,p}\).
Proof. Both congruences in (a) imply \(p\equiv 3\,(\mathrm{mod}\ 4)\), in which case \(\Gamma_{M,\,p}\) contains no secondary cycles by Proposition 7.1. Now suppose \(p \equiv 5 \,(\mathrm{mod}\ 8)\). Clearly \(8\) does not divide \(p-1\), however \(k={\rm ord}(1+i)\) must divide \(p-1\) since \(1+i\) is an element of the multiplicative group of \(GF(p)\). We conclude that \(8\) does not divide \(k\), whence it follows from Corollary 7.3 that secondary cycles in \(\Gamma_{M,\,p}\) must exist in this case. \(\square\)
Remark 7.5. At the present time, we have yet to discern any reasonable criteria that settle the question of existence of secondary cycles when \(p \equiv 1 \,(\mathrm{mod}\ 8)\). Computer-generated data indicate that both outcomes are not only possible but occur with great frequency. Still, there doesn’t appear to be any highly recognizable pattern in the data.
We close with the following result, which determines the number of cycles of varied length in the sub-add move graph \(\Gamma_{M,\,p}\) when \(p\) is an odd prime. The proof is a straightforward counting argument using the cycle structure described in Proposition 7.1 and Theorem 7.2 so it is left to the reader.
Proposition 7.6. (a) If \(\,\Gamma_{M,\,p}\) has no secondary cycles, then there are \(\frac{p^2 – 1}{k}\) primary cycles in \(\Gamma_{M,\,p}\).
(b) If \(\,\Gamma_{M,\,p}\) has secondary cycles, all such cycles have common length \(s\) for some \(s \in \{t, 2t\}\). Here there are \(\frac{p-1}{s}\) secondary cycles and \(\frac{p^2-p}{k}\) primary cycles in \(\Gamma_{M,\,p}\).
Remark 7.7. The entry A363894 in the On-Line Encyclopedia Integer Sequences [21] reflects Proposition 7.6 in conjunction with Theorem 6.3. Note that what is referred to as the “halved addsub configuration graph” in A363894 is the “sub-add move graph” in our present terminology.
While many of our results in this section do not extend to proper odd prime powers, a number of them do. We intend to pursue this line of investigation in a sequel.
The authors declare that they have no conflict of interest.
Data sharing is not applicable to this article as no datasets were generated or analyzed during the current study.
This research was supported in part by the National Science Foundation, grant MPS-2150299.
Authors contributed to the study conception and design. Material preparation, data collection and analysis were performed by Patrick Cesarz, Charles Gong, Eugene Fiorini, Kyle Kelley, Philip Thomas, and Andrew Woldar. The first draft of the manuscript was written by Andrew Woldar and all authors commented on previous versions of the manuscript. All authors read and approved the final manuscript.