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

Question

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

---

         
^{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$, for each of the $6!$ starting permutations, the process always results in a cycle of length exactly $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$. 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.

---

         
          ^{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) $$

Answer 1

Too long for a comment.

Let $$A=\left(\begin{array}{rrrrrr} 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 \end{array}\right)$$ be the adjacency matrix of the path graph for $n=6$. The characteristic polynomial of $A^k$ evaluated at $1$ gives the following for $0\leq k\leq 182$ (we take everything over the ring $\mathbb{Z}/6\mathbb{Z}$): $$[0,1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 5, 1, 3, 4, 1, 1, 5, 1, 1, 1, 2, 1, 5, 1, 5, 3, 1, 4, 1, 1, 1, 1, 5, 1, 4, 1, 5, 1, 3, 1, 1, 4, 5, 1, 1, 1, 5, 1, 2, 1, 5, 3, 1, 1, 1, 4, 1, 1, 5, 1, 1, 1, 2, 1, 3, 1, 1, 1, 5, 4, 1, 1, 5, 1, 5, 1, 2, 3, 1, 1, 1, 1, 1, 4, 5, 1, 1, 1, 5, 1, 0, 1, 1, 1, 5, 1, 1, 4, 5, 1, 5, 1, 5, 3, 4, 1, 1, 1, 1, 1, 5, 4, 1, 1, 5, 1, 3, 1, 4, 1, 5, 1, 1, 1, 5, 4, 5, 1, 5, 3, 1, 1, 4, 1, 1, 1, 5, 1, 1, 4, 5, 1, 3, 1, 1, 1, 2, 1, 1, 1, 5, 1, 5, 4, 5, 3, 1, 1, 1, 1, 4, 1, 5, 1, 1, 1, 5, 4, 3, 1, 1, 1, 5, 1, 4, 1, 5, 1, 5, 1, 5, 0]$$The smallest $k$ where this happens to be $0$ is the 91st entry in the list. Here the matrix is $$ A^{91} = \left(\begin{array}{rrrrrr} 0 & 0 & 0 & 0 & 0 & 5 \\ 0 & 0 & 0 & 0 & 5 & 0 \\ 0 & 0 & 0 & 5 & 0 & 0 \\ 0 & 0 & 5 & 0 & 0 & 0 \\ 0 & 5 & 0 & 0 & 0 & 0 \\ 5 & 0 & 0 & 0 & 0 & 0 \end{array}\right) $$ $A^{182}$ is the identity.

Unfortunately, not even the reasoning $\chi(A^k)(1)\neq0$ implies there is no $w$, such that $Aw=w$ seems to apply in the $\mathbb{Z}/6\mathbb{Z}$ situation; for example we have $$A^7\cdot (3,3,3,3,3,3)^t = (3,3,3,3,3,3)^t$$

Answer 2

Here is a dumb conjectural answer to Joseph's question: there is only one cycle (of length 182) in the transition graph for the space involving a path of length 6 with a starting point of a permuted labelling of the variables.

More generally, we can consider a set V of labelled graphs v, and a directed edge (v,w) if T(v)=w, where (as Brendan McKay commented) T is modular matrix multiplication on the vertex vector of v under a standard system of notation. For simplicity, consider V as composed of an initial set of labelled graphs P union T(P), T(T(P)), and further iterated. Since P and the nature of T is bounded, it is unsurprising that V is finite and contains cycles.

If we choose P to be the set of all mod 6 labelling of a path of length 6, we should find some other cycle lengths as well. There may be some numeric invariants describing T^k(P), which I will investigate and report back here with results. The literature Peter Heinig mentioned may be more relevant than he states. I am looking for connections to additive permutations (link to MathOverflow question forthcoming).

I have not calculated V for anything above n=3 yet, so at this time remember the first sentence, however likely it at seem, is conjectural.

Gerhard "Taking Small Steps Towards Theorems" Paseman, 2017.08.26.

Answer 3

Here is more data for small cases, with a suggestion that someone who knows representation theory and combinatorics might be able to give a general answer and explain some of the numbers Joseph and Moritz are computing.

For the n=2 case, the dynamic takes (a b) to (b a), so the general state space and it's transition graph are easily computed and understood. For n=3, we get (a,b,c) goes to (b,a+c,b). (Here and below, assume + is addition modulo the appropriate number, usually n.) If we iterate this dynamic twice, we get two pieces stitched together , (.b.) goes to (.-b.) and (a.c) goes to (a+c.a+c). Thus repeating the operation twice on a path shows a pair of dynamics in tandem, and we can analyze each separately. Or, we can look at it as a long cycle if we just want to analyze the period, as in (a.c) goes to (.a+c.) goes to (a+c.a+c). Here it is not hard to show the dynamic repeats with a period dividing 4, and one can look at fixed points to find what period lengths actually occur.

For n=4, (half of) the dynamic becomes (a.c.) goes to (.a+c.c) goes to (a+c.a+2c.), and a string reversal version occurs for the other half. Note the Fibonacci like pattern that occurs, which when iterated 4 times becomes (2a+3c.3a+5c.) and 6 times (5a+8c.8a+13c.)=(a.c.) mod 4. So for n=4 periods must divide 6.

For n=5 we have (a.c.e) to (.a+c.c+e.) to (a+c.a+2c+e.c+e) to (.2a+3c+e.a+3c+2e.) to (2a+3c+e.3a+6c+3e.a+3c+2e) to (mod 5) (.-c-e.-a-c.), so we see a cycle of length 8 about to occur.

I haven't computed fully for n=6 yet, but following the pattern acting on (a.c.e.) suggests a transition matrix of [[2 1 0],[1 2 1],[0 1 1]] for the square of half the dynamic, and a similar but not identical matrix for the square of the other disjoint half. I suspect mod 6 these matrices will have a period of 91.

Gerhard "Not Ready For Prime Time" Paseman, 2017.08.26.

Answer 4

_{I do not consider the following an answer, most especially since I take you main question to be very focused one: to mathematically explain the 182. Yet I think pointing out the relevance to what is called 'totalistic cellular automata' is on-topic. The comment boxes are too small to appropriately do so.}

The most relevant technical terms related to your question known to me are 'totalistic cellular automaton' and 'isotropic rules', as in e.g.

The most relevant published article known to me is

Carsten Marr, Marc-Thorsten Hütte: Outer-totalistic cellular automata on graphs. Physics Letters A 373 (2009) 546-549

The definitions therein do not really meet your needs though. This already begins with 'states' being only allowed to be elements of $2$ in loc. cit. I also cursorily checked whether some of your numbers show up in loc. cit., without finding any. Yet I think you might make progress by looking into this part of the literature, or contacting the authors of loc. cit.

Also very relevant (especially since it allows integer valued states, yet again not answering your question, is Dan Gordon: On the Computational Power of Totalistic Cellular Automata. Mathematical Systems Theory. 20, 43-52 (1987).

Again, there are the expected slight mismatches, notably that loc.cit. includes the value of a cell whose next state is to be computed into the sum which determines the next state. And philosophically, loc. cit. contains results which are sadly rather discouraging when it comes to mathematically explaining you discovery (where 'mathematically explaining' here means 're-generating your empirical discoveries from the traditional logical primitives of modern mathematics', which would be the most desirable outcome), since it contains results of computational universality.

And yet again, loc. cit.seems very close and contacting the author of loc. cit. seems a good thing to try.

Edit: I think your discovery fits into an existing terminological framework (though this does not give much of an explanation):

• the iteration you defined is an $n$-color totalistic cellular automaton with, however, non-periodic boundary conditions.

Remarks.

• Note that your rule that the vertex-to-be-updated does not contribute its current value to the sum which determines its next state can be 'simulated'/'is an instance of' the definition of 'totalistic cellular automaton' on this website. I am only speaking about your question for paths; and I take it that you are working over the ring $\mathbb{Z}/(n)$, where $(n)$ denotes the principal ideal generated by $n$.

I assume you are working with the path graph $0\text{-}1\text{-}\dotsm\text{-}n-1$.

I write $v_i^{t}$ for the value of vertex $i$ at time $t$.

For $0<i<n-1$ you require¹

$\mathbf{v_{i}^{t+1} + (n)} = v_{i-1}^{t}+v_{i+1}^{t} + (n)$ ${}\qquad\qquad$ (global.rule)

At the boundaries you require (which is a serious complication when it comes to making a precise connection with the existing literature on cellular automata)

$\mathbf{v_{0}^{t+1} + (n)} = v_{1}^{t} + (n)$ ${}\qquad\qquad$(left.boundary.rule)

$\mathbf{v_{n-1}^{t+1} + (n)} = v_{n-2}^{t} + (n)$ ${}\qquad\qquad$(right.boundary.rule)

Now the point I would like to make is that your (global.rule) just is one of the hundreds upon hundreds of rules known and documented by Wolfram. I did not try to find out which decimal number they have assigned to your rule. Nor did I try to find out whether Wolfram has a classification for rules which suddenly change at the boundaries (such as yours do). Let me just mention that this violates what

Carsten Marr, Marc-Thorsten Hütte: Outer-totalistic cellular automata on graphs. Physics Letters A 373 (2009) 546-549

in Section 2 call 'Homogeneity'.

Let me also mention that looking into K. Salman: ANALYSIS OF ELEMENTARY CELLULAR AUTOMATA BOUNDARY CONDITIONS,

and contacting the author, seems a relevant thing to try.

¹ _{I use the boldface for readability only; it is not inteded to have mathematical meaning.}