Cellular Automata, Fractals, Self-Similarity, and Integers
Staring at patterns during a pandemic.Contents
- Resources
- Overview
- Formalism
- Defining a Homomorphism
- Points of Interest
- On Integer Factorization
- Example
Graduate early draft of cycle detection in using modular reduction and its relation to the Hidden Subgroup Problem. My hypothesis is that the methodology outlined in my paper (link below), is equivalent to that of the GNFS method of integer factorization.
Something that I got started on a couple of years ago and put on the back burner was the evolution of 2D cellular automata over based on rules involving modular reduction.
So far this is something that I'm working on only in my spare time mainly to explore higher concepts of abstract algebra and number theory. As I've been continuously reading more literature and research, my interpretation has been changing quite a bit. So for now, this is just my scratchpad.
As of now, there are two things that I've been exploring: embedded fractal patterns and finding the prime factors of the modulus.
Resources
- Code: harakas-automata.tar.xz
- Images: here (gallery view is kinda slow and buggy)
- Example (below) animation: here.
- Mod3 rule file for Golly: here
Overview
In mathematical terms, for a cell $x$ on a 2D integer lattice, and a neighborhood $N(x)$, the $ith$ step of $x_{i-1}$, is given by: \[x_{i+1} = \Big{(} \sum N(x_{i})\Big{)} \mod m \] where $N$ is the neighborhood and $\varepsilon$ is neighborhood radius. So taking the sum of the neighboring cells and reducing it modulo some number $m$, produces some interesting results. Using the Moore neighborhood, this can be looked at as a 2D convolution with a kernel filter \[ \begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \end{bmatrix} \]
Letting $m=11 \times 17$, and $N$ be the von-Neumann neighborhood, the grid evolves through a series of births and annhililations as seen below.
Taking the Fourier Transform over a period of $m$, we see peak frequencies correspond to multiples of $11$ and $17$.
It also seems that we can construct many fractals that can be constructed from some string-rewriting methods. The below figures are constructed using a modulus of 3 with von-Neumann and Moore neighborhoods.
More Formalism
Chris Langton's paper Computation at the Edge of Chaos: Phase Transition and Emergent Chaos provides a good mathematical framework from which to build on.
A cellular automata is described as a $D$-dimensional lattice with finite automatons at each point that transition states based on some function. Lets call the transition function $\Delta$.
Each automaton changes to a new state based on some finite local local region $N$ where $\vert N \vert \le \vert D \vert$. Simply put, the neighborhood $N(x)$ is a set of lattice points within some radius $\varepsilon$ of $x$. So, $\vert N \vert$ is the number of lattice points of that set. Let $\Sigma$ be a finite set of states and $\alpha$ be an input alphabet. Then the transition function is defined as \[ \Delta : \alpha \to \Sigma \]
The specific transition function I've been looking at is similar to that of Totalistic Cellular Automata. A totalistic transition function for $x_{t+1}$ is the sum of each neighbor $u \in N(x_t)$: \[ x_{t+1} = \Delta(x_t) = \sum_{u \in N(x_t)} u \] Now consider what happens when the transition function reduces the state modulo some $m$. That is, \[ x_{t+1} = \Delta(x_t) = \Bigg( \sum_{u \in N(x_t)}{u} \Bigg) \mod m \] The results are fairly interesting. For some modulus $m$, $\Delta$ can be more succinctly described by \[ \Delta: \mathbb{Z} \to \mathbb{Z}_m \] Obviously the domain of this function is not all integers since $N$ is a finite region. Whats more interesting is that $\Delta$ is a surjection onto $\mathbb{Z}_m$. To get an upper bound on the domain, let the neighborhood $N$ be such that $r=\vert N \vert$, the number of "active" (nonzero) components of $N$. Given a cell $x$ and a modulus $m$, then $ 0 \le x < m$. So $x$ is bounded above by $m$ and $$ \begin{eqnarray*} &0 & \le N(x) &\lt rm \\ & & &\le r(m-1). \end{eqnarray*} $$ Letting $n =r(m-1)$ gives a transition function \[ \Delta: \mathbb{Z}_n \to \mathbb{Z}_m. \]
So what?
There is an interesting relationship here that I haven't explored very much yet. But consider the case where $m=3$ and $\vert N \vert$ = 9. So $n=\vert N \vert (m-1)= r(m-1) = 9(3-1) =18$ and the transition function is given by \[ \Delta : \mathbb{Z}_{18}\to \mathbb{Z}_3 \] The crucial thing here is $ 3 \vert 18 $. More generally, a function \[ \varphi: \mathbb{Z}_n \to \mathbb{Z}_m \] is a homormorphism if and only if $ m $ divides $n$. So This can be proved easily using the First Isomorphism Theorem. To find these homomorphisms, we only need to find parameters satisfying \[ r(m-1) = km \] where $k$ is some integer constant. Now consider what that equation is actually telling us. If $k$ and $\vert N \vert $ have no common divisors, then to construct $\Delta$, choose a neighborhood $N$ such that \[ r = lcm(m, m-1) \] Further refinements can be made depending on the initial cell states, e.g. accounting for initial states that are group generators. This is important because if the initial state does not contain a group generator, the only reachable states will be of integer multiples modulo $m$.
One example of some "good" parameters is in the figure below. Usings $m=3$ and $\vert N \vert = r = 12$, we have $12(3-1) = 3k$ $$\begin{eqnarray*} km &=& r(m-1) \\ 3k &=& 12(3-1) \\ &=& 24 \\ k&=& 8 \end{eqnarray*}$$ giving us a transition function $\Delta: \mathbb{Z}_{24} \to \mathbb{Z}_3 $ which is a homomorphism.
Since $k=8$ is now known, factoring out the common factor (4) of $k$ and $r$, how it ties to the $lcm$ is more clear: $$\begin{eqnarray*} km &=& r(m-1) \\ 8m &=& 12(m-1) \\ 2m &=& 3(m-1) \\ &=& 6 \end{eqnarray*}$$
It is also evident that the initial state of the cells can produce very different outcomes. For example, using $m=24$ and setting one initial state to 12 will produce the same outcome as if $m=2$. This is not unsurprising since $\mathbb{Z}_{24}$ has a subgroup $ \{0, 12\} \cong \mathbb{Z}_2 $. The same goes for any subgroup. The transitions of two initial cells starting at 8 and 12 modulo 24. The resulting states are equivalent to $\mod 3$ and $\mod 2$ respectively.
Other Points of Interest
It is evident that using composite integers produce patterns that are compositions of their integer components. In a sense there are multiple distinct patterns embedded in the system. This becomes even more clear when using a transition matrix that is not limited to just values of $\{0,1\}$. More succinctly, weights can be applied to the matrix. As a result, distinct embeddings of other neighborhoods are clearly visible. The below figure shows a weighted Moore neighborhood. Residues from the von-Neumann neighborhood are still evident though.
However, it does beg the question: at what point does this stop being cellular automata?
On Integer Factorization
This originally came to mind after reading Peter Shor's paper: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. I'm interested in looking at an automata variant of this algorithm - finding the period of a function. The main reason is that modular exponentiation can be done achieved in this mechanism; or rather locally by defining a homomorphic transition function. In this case, I'm going to define a bijection $\Delta: \mathbb{Z}_m \to \mathbb{Z}_m$. This is actually an isomorphism. The steps I've come up with so far are:
- Define a neighborhood $N$ such that $\vert N \vert = r = m$. This can be done either through the neighborhood radius or through weighted entries.
- Choose some $x$ as the initial state of a cell
- Record the ratio of active cells (or their sum) for each step.
- Run the cellular automata for some proportional number of steps (recording the population)
- Apply the Fourier Transform over the recorded population at each step using $m$ as the period.
Example
Using a simple example with $m=7367 = 53 \times 139$ define a neighborhood $N$ to be: \[ \begin{bmatrix} 1473 & 0 & 1473 \\ 0 & 1475 & 0 \\ 1473 & 0 & 1473 \end{bmatrix} \] whose entries sum up to $m=7367$. The grid size was $ 2000 \times 2000 $, At each step, the number of non-zero cells are recorded as a sequence. Applying a Fourier Transform over this sequence using a period of $m=7367$ an arbitrary initial state $a=24$ was chosen, and ran for ~1800 steps. shows peaks at its prime factors: 53 and 139.
Video: An animation for the first 500 steps can be viewed here.
The construction of $N$ is fundamental to this process. At the very least, it must be a homomorphism because the ultimate goal is to send lots of cells to zero. That is, $ker(\Delta)$ corresponds to the cycles we are trying to find.
From a cryptographic standpoint, I'm also interested in observing the results for cryptographically "good" numbers. For example, in choosing $n=p_1 p_2$ where $p_1 = 2p_2 + 1$.
Useful?
Maybe. It would be interesting to see how well this would scale to larger numbers. Since most of the code I wrote is for handling the animation, it is not particularly fast. But the biggest question is: how can I make this reversible?