Skip to main content
9 of 11
Removed TeX markup in title.
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

Iteration cycles of Z_n weights in path graphs: Why cycles of length 182 for a 6-node path?

Assign to the $n$ nodes of a path graph vertex weights forming a permutation of $(0,\ldots,n{-}1)$. Now iterate the following update repeatedly: Each node sums the weights of its neighbors, and that node's weight is replaced (in the next iteration) by the sum $\bmod n$. Here is the start of an example for $n=4$:


          [![Path4][1]][1]
The leftmost node just copies the $1$ of its neighbor.
The 2nd node from the left is replaced with $(3+0) \bmod 4$.

Continuing, we fall into a cycle of length $6$: $$ \left( \begin{array}{cccc} 3 & 1 & 0 & 2 \\ 1 & 3 & 3 & 0 \\ 3 & 0 & 3 & 3 \\ 0 & 2 & 3 & 3 \\ 2 & 3 & 1 & 3 \\ 3 & 3 & 2 & 1 \\ 3 & 1 & 0 & 2 \\ \end{array} \right) $$ With a different starting permutation, the cycle length can be $3$: $$ \left( \begin{array}{cccc} 2 & 3 & 1 & 0 \\ 3 & 3 & 3 & 1 \\ 3 & 2 & 0 & 3 \\ 2 & 3 & 1 & 0 \\ \end{array} \right) $$ Similarly, for $n=5$, cycles of length $2$ and $8$ occur. But I was surprised to find that for $n=6$, it appears the process always results in a cycle of length $182$.

Q. What explains cycles of length $182$ for paths of $6$ nodes?

More generally, what explains the cycle lengths for different $n$? Here are the cycle lengths I've explored so far, verified by exhaustive search up to $n=9$. The $n=9$ cycle length of $48$ is prominent among random permutations but I am not certain there is no other cycle length. See Moritz Firsching's comments and postings for data beyond my calculations. $$ \left( \begin{array}{cccccccc} 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 2 & \{1,4\} & \{3,6\} & \{2,8\} & 182 & \{6,12\} & 28 & \{24,48\} \\ \end{array} \right) $$ I've also explored cycle graphs instead of path graphs. For a cycle graph of $n=6$ nodes, the process falls into cycles of length $2$ or $6$. For $n=8$, the cycle length is $1$—all zeros.


          [![Cyc6][2]][2]
          Iteration falls into a cycle of length $2$.
The process may be similarly defined on any graph. I've made some preliminary explorations without seeing a clear pattern.
Replying to Moritz Firsching's question in a comment, a cycle of length $6$ for $n=7$: $$ \left( \begin{array}{ccccccc} 4 & 5 & 6 & 0 & 1 & 2 & 3 \\ 5 & 3 & 5 & 0 & 2 & 4 & 2 \\ 3 & 3 & 3 & 0 & 4 & 4 & 4 \\ 3 & 6 & 3 & 0 & 4 & 1 & 4 \\ 6 & 6 & 6 & 0 & 1 & 1 & 1 \\ 6 & 5 & 6 & 0 & 1 & 2 & 1 \\ 5 & 5 & 5 & 0 & 2 & 2 & 2 \\ 5 & 3 & 5 & 0 & 2 & 4 & 2 \\ \end{array} \right) $$
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958