7
$\begingroup$

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


          Cyc6
          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) $$

$\endgroup$
  • 2
    $\begingroup$ Note that the operation is that of multiplying by the adjacency matrix mod $n$, so multiple steps are multiplication by powers of the adjacency mod $n$. $\endgroup$ – Brendan McKay Aug 26 '17 at 14:20
  • 1
    $\begingroup$ Have you done an exhaustive search? Or used symmetry to do a comprehensive search? I suspect this anomaly may be related to the automorphism group of Alt(6). Gerhard "Number Six Is Exceedingly Symmetric" Paseman, 2017.08.26. $\endgroup$ – Gerhard Paseman Aug 26 '17 at 16:26
  • 2
    $\begingroup$ I have been agonizing over whether to mention this at all, since it is so tangential, yet let me say that this reminds me of an interesting niche-subject within flow-theory of graphs: zero-sum flows, about which you can find much by searching. Roughly, these are flow-like-assignments to the edges, the flow-condition being defined without an orientation on the edges. This is quite different from classic flows on graphs, and I think that this will not help you much, yet it is a subject where weights are being added at each vertex (and modulo a fixed modulus). $\endgroup$ – Peter Heinig Aug 26 '17 at 16:59
  • 1
    $\begingroup$ for $n=10$, and the identity permutation, the process takes 48422 step until it cycles. In fact, taking powers of the adjacency matrix mod $n$ until it becomes cyclic, you need to take this many steps: $1, 1, 2, 4, 6, 8, 182, 12, 28, 48, 48422, 20, 1638, 24, 1200, 6240, 120, 32,...$. (not (yet) in OEIS). For the even cases, like 6, you seem to get back to the identity. $\endgroup$ – Moritz Firsching Aug 26 '17 at 18:42
  • 2
    $\begingroup$ $182=2\cdot7\cdot13$, $7\equiv13\equiv1\bmod6$; $48422=2\cdot11\cdot31\cdot71$, $11\equiv31\equiv71\equiv1\bmod{10}$. $\endgroup$ – Gerry Myerson Aug 27 '17 at 1:43
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Wonderful!! Does any reasoning suggest itself beyond "this happens to be"? $\endgroup$ – Joseph O'Rourke Aug 26 '17 at 19:44
  • 1
    $\begingroup$ I missed a zero at entry 91, there needs to be some more reasoning... $\endgroup$ – Moritz Firsching Aug 26 '17 at 19:49
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Actually, I have now verified that "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 labeling of the variables." $\endgroup$ – Joseph O'Rourke Aug 26 '17 at 19:23
  • 1
    $\begingroup$ Of course, the graph could be a disjoint union of connected graphs each with a single cycle (If I ignore Joseph's comment above). I will say more after some hand computation. Gerhard "Not Ready For Foot Computation" Paseman, 2017.08.26. $\endgroup$ – Gerhard Paseman Aug 26 '17 at 19:51
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ An oddity of interest: mod 6, the three by three matrix has fifth power equal to -1 -1 0 -1 -1 -1 0 -1 0. Gerhard "Too Tired For Square Brackets" Paseman, 2017.08.26. $\endgroup$ – Gerhard Paseman Aug 26 '17 at 22:42
1
$\begingroup$

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.

Emmanual Sapin, Olivier Bailleux, Jean-Jacques Chabrier: Research of a Cellular Automaton Simulating Logic Gates by Evolutionary Algorithms; in the proceedings of 'Genetic Programming: 6th European Conference' 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):

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 require1

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

1 I use the boldface for readability only; it is not inteded to have mathematical meaning.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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