Convergence of Vector-Valued Fuzzy Cellular Automata with Weighted-Averaging Rules

Abstract

Fuzzy cellular automata are dynamical systems that are continuous counterparts of the usual cellular automata (CA). Compared with the binary case, defining a fuzzy CA with three or more states is challenging because defining mixed states is difficult. Recently, this difficulty was resolved by representing multiple states as independent vectors in higher dimensions, and the concept of vector-valued fuzzy CA (VFCA) was introduced. In this study, we theoretically analyze and discuss the asymptotic behavior of three-state, three-neighbor VFCA. First, we define the weighted-averaging rules of VFCA and show how many rules exist up to the equivalence relations. According to these rules, each state vector in the next step is determined by the weighted average of the vectors in its neighboring cells. Next, we prove that VFCA with weighted-averaging rules converge to a periodic configuration characterized by the symmetric group of order 3. In particular, the non-commutativity of the group action provides an interesting behavior that is not observed in fuzzy CA arising from binary states. These results can be extended to VFCA with more than three states and/or three neighbors.

1 Introduction

Cellular automata (CA) are dynamical systems that describe cell configurations that evolve concurrently in accordance with a local update rule based on neighboring cells. CA are used as tools for mathematical modeling in areas such as traffic flows and life sciences. One of the simplest CA is a one-dimensional two-state, three-neighbor CA, also known as the elementary CA (ECA). The local rule of an ECA can be expressed in a disjunctive normal form in Boolean algebra, which can be converted into a usual polynomial. It provides the local rule of an elementary fuzzy CA (EFCA) [1], which is a continuous counterpart of the ECA whose state set is the closed interval [0, 1]. In this study, fuzzy CA does not refer to CA on fuzzy sets [2] or the fuzzy choice of local rules [3]. Although ECA rule 184 is famous for traffic models, the application of EFCA rule 184 to traffic flows was recently proposed [4].

Compared with the binary case, defining a fuzzy CA with three or more states is not easy. We previously introduced a vector-valued CA to apply fuzzification to CA with three or more states [5]. The results are briefly summarized. Let $\boldsymbol{e}_{1}, \boldsymbol{e}_{2}, \boldsymbol{e}_{3}$ be the standard basis vectors of $\mathbb {R}^{3}$. The integer-valued states 2, 1, 0 are associated with $\boldsymbol{e}_{1}, \boldsymbol{e}_{2}, \boldsymbol{e}_{3}$, yielding the state set $Q = \{\boldsymbol{e}_{1}, \boldsymbol{e}_{2}, \boldsymbol{e}_{3}\}$ of three-state vector-valued CA. For $i \in \mathbb {Z}$ and $t \in \mathbb {Z}_{\ge 0}$, where $\mathbb {Z}_{\ge 0}$ is the set of nonnegative integers, let $\boldsymbol{x}^{t}_{i}$ denote the vector in cell i at time step t. In the case of three-neighbor CA, the evolution is determined by the local rule $f: Q^{3} \rightarrow Q$ as $\boldsymbol{x}_{i}^{t+1} = f(\boldsymbol{x}_{i-1}^{t}, \boldsymbol{x}_{i}^{t}, \boldsymbol{x}_{i+1}^{t})$. Then, the local rule f can also be expressed as:

(1)

where $\boldsymbol{x} = (x_{1},x_{2},x_{3})^{\top }, \boldsymbol{y} = (y_{1},y_{2},y_{3})^{\top }$ and $\boldsymbol{z} = (z_{1},z_{2},z_{3})^{\top }$. Consider the two-dimensional simplex $\varDelta$ with vertices $\boldsymbol{e}_{1}, \boldsymbol{e}_{2}, \boldsymbol{e}_{3}$:

$$\begin{aligned} \varDelta = \left\{ (x_{1}, x_{2}, x_{3})^{\top } \in \mathbb {R}^{3} \mid x_{1} + x_{2} + x_{3} = 1,\ x_{1},x_{2},x_{3} \ge 0 \right\} . \end{aligned}$$

The domain of function f can be expanded from $Q^{3}$ to $\varDelta ^{3}$ through the right-hand side of (1), and f satisfies $f(\varDelta ^{3}) \subset \varDelta$. Consequently, the state set Q can be expanded to $\varDelta$, and a vector-valued fuzzy CA (VFCA), which is a continuous-valued CA with local rule $f: \varDelta ^{3} \rightarrow \varDelta$, is obtained. The expression (1) is similar to the disjunctive normal form of a local rule of ECA. Thus, VFCA can be regarded as an extension of EFCA introduced in [1], which is the reason why we use the term fuzzy. In a recent study [6], VFCA are related to stochastic CA because vectors in $\varDelta$ are considered to express the probability for each state. As in EFCA, traffic flow models in terms of VFCA were discussed in [6, 7]. Thus, theoretical study of VFCA will help the analysis of both deterministic and stochastic mathematical models.

1.1 Our Contributions

In this study, we consider the asymptotic behavior of VFCA, especially the convergence of VFCA. Hereafter, all CA are assumed to satisfy the periodic boundary condition with a positive integer period L; that is, $\boldsymbol{x}_{i}^{t} = \boldsymbol{x}_{i+L}^{t}$ for $i \in \mathbb {Z}$ and $t \in \mathbb {Z}_{\ge 0}$. The local rule f of a VFCA induces the global rule $F: \varDelta ^{L} \rightarrow \varDelta ^{L}$. A VFCA with the initial configuration $\boldsymbol{X}^{0} \in \varDelta ^{L}$ can be expressed as the sequence $\{\boldsymbol{X}^{t}\}_{t \in \mathbb {Z}_{\ge 0}}$, where $\boldsymbol{X}^{t+1} = F(\boldsymbol{X}^{t})$ for $t \in \mathbb {Z}_{\ge 0}$. Let $[\boldsymbol{x}_{i}]_{k}$ denote the kth component of $\boldsymbol{x}_{i}$. The convergence of VFCA is defined with respect to the following metric d on $\varDelta ^{L}$:

$$\begin{aligned} d((\boldsymbol{x}_{0},\boldsymbol{x}_{1},\dots ,\boldsymbol{x}_{L-1}), (\boldsymbol{y}_{0},\boldsymbol{y}_{1},\dots ,\boldsymbol{y}_{L-1})) = \max _{i=0,1,\dots ,L-1} \max _{k=1,2,3} | [\boldsymbol{x}_{i}]_{k} - [\boldsymbol{y}_{i}]_{k} |. \end{aligned}$$

First, we define the weighted-averaging local rules of VFCA. In these rules, each state vector $\boldsymbol{x}^{t+1}_{i}$ is determined by the weighted average of two of the three neighboring vectors $\boldsymbol{x}^{t}_{i-1}, \boldsymbol{x}^{t}_{i}, \boldsymbol{x}^{t}_{i+1}$. These rules were discussed in EFCA [8]. Because we consider a three-dimensional vector, we can permute the entries of each vector before taking the weighted average. We present a brief description of how many different weighted-averaging rules exist up to the equivalence relations. These VFCA systems exhibit asymptotically periodic behavior in both time and space. The main section provides a theoretical proof of the convergence of VFCA with weighted-averaging rules. Using a transformation of VFCA into another CA admitting different local rules for each cell, we present a proof that is applicable to many types of weighted-averaging rules. We demonstrate that the action of the symmetric group $S_{3}$ plays a crucial role in classifying the periodic pattern of behavior. In particular, the non-commutativity of $S_{3}$ induces a special type of convergence not observed in EFCA.

1.2 Related Works

The asymptotic behavior of EFCA has been discussed in several studies. For example, self-averaging rules [9] and weighted-averaging rules [8] are important classes of EFCA local rules, such that their convergence may be analytically proven. The dynamics of several specific rules have been individually studied, such as EFCA rules 90 [10] and 184 [11]. In computer simulations for some VFCA corresponding to traffic models [6, 7], it was suggested that such VFCA converge to homogeneous configurations after sufficiently large steps. In contrast, this study focuses on a theoretical analysis of the convergence of VFCA.

2 Weighted-Averaging Rules in VFCA

In this section, we focus on several special rules of VFCA, called weighted-averaging rules. The formal definitions are as follows. Let us define the action of $S_{3}$ on $\varDelta$ by $\sigma (\boldsymbol{x}) = ([\boldsymbol{x}]_{\sigma ^{-1}(1)}, [\boldsymbol{x}]_{\sigma ^{-1}(2)}, [\boldsymbol{x}]_{\sigma ^{-1}(3)})^{\top }$ for $\boldsymbol{x} \in \varDelta$ and $\sigma \in S_{3}$. The local rule f of a VFCA is called a weighted-averaging rule if it is expressed in one of the following forms:

$$\begin{aligned} f(\boldsymbol{x}, \boldsymbol{y}, \boldsymbol{z})&= (1 - \langle \boldsymbol{x} \rangle ) \cdot \sigma (\boldsymbol{y}) + \langle \boldsymbol{x} \rangle \cdot \tau (\boldsymbol{z}), \end{aligned}$$

(2)

$$\begin{aligned} f(\boldsymbol{x}, \boldsymbol{y}, \boldsymbol{z})&= (1 - \langle \boldsymbol{z} \rangle ) \cdot \sigma (\boldsymbol{y}) + \langle \boldsymbol{z} \rangle \cdot \tau (\boldsymbol{x}), \end{aligned}$$

(3)

$$\begin{aligned} f(\boldsymbol{x}, \boldsymbol{y}, \boldsymbol{z})&= (1 - \langle \boldsymbol{y} \rangle ) \cdot \sigma (\boldsymbol{x}) + \langle \boldsymbol{y} \rangle \cdot \tau (\boldsymbol{z}). \end{aligned}$$

(4)

Here, $\sigma , \tau \in S_{3}$ and $\langle \boldsymbol{x} \rangle$ is one of $[\boldsymbol{x}]_{1}, [\boldsymbol{x}]_{2}, [\boldsymbol{x}]_{3}, 1 - [\boldsymbol{x}]_{1}, 1 - [\boldsymbol{x}]_{2}, 1 - [\boldsymbol{x}]_{3}$. Because there are six choices for $\sigma , \tau$ and $\langle \boldsymbol{x} \rangle$, we have $6 \times 6 \times 6 = 216$ local rules for each type (2)–(4). In particular, the local rules of forms (2) and (3) are called the weighted-averaging rules of type 1, and the local rules of the form (4) are called those of type 2.

We introduce an equivalence relation for the local rules of VFCA. The action of $\rho \in S_{3}$ on $f: \varDelta ^{3} \rightarrow \varDelta$ is defined as

$$\begin{aligned} (\rho \circ f)(\boldsymbol{x}, \boldsymbol{y}, \boldsymbol{z}) = \rho (f (\rho ^{-1}(\boldsymbol{x}), \rho ^{-1}(\boldsymbol{y}), \rho ^{-1}(\boldsymbol{z}))). \end{aligned}$$

We also define the reflection r as

$$\begin{aligned} (r \circ f)(\boldsymbol{x}, \boldsymbol{y}, \boldsymbol{z}) = f(\boldsymbol{z}, \boldsymbol{y}, \boldsymbol{x}). \end{aligned}$$

Then, the two local rules are said to be equivalent if one is obtained from the other by the action of $\rho \in S_{3}$, reflection, or their composition. Specifically, (2) and (3) provide equivalent local rules. Based on this equivalence relation, 432 weighted-averaging rules of forms (2) and (3) are divided into 40 equivalence classes. Note that some equivalence classes contain only 6 rules, whereas others contain 12 rules. For example, consider the local rule

$$\begin{aligned} f(\boldsymbol{x}, \boldsymbol{y}, \boldsymbol{z}) = (1 - [\boldsymbol{x}]_{1}) \cdot \sigma (\boldsymbol{y}) + [\boldsymbol{x}]_{1} \cdot \boldsymbol{z} \end{aligned}$$

with $\sigma = (2\ 3)$. It is essential that $\sigma (1) = 1$. Subsequently, for $\rho \in S_{3}$, we obtain

$$\begin{aligned}&((\rho \sigma ) \circ f) (\boldsymbol{x}, \boldsymbol{y}, \boldsymbol{z}) \\&\qquad = (1 - [\boldsymbol{x}]_{\rho \sigma (1)}) \cdot \rho \sigma (\sigma (\sigma ^{-1}\rho ^{-1}(\boldsymbol{y}))) + [\boldsymbol{x}]_{\rho \sigma (1)} \cdot \rho \sigma (\sigma ^{-1}\rho ^{-1}(\boldsymbol{z})) \\&\qquad = (1 - [\boldsymbol{x}]_{\rho (1)}) \cdot \rho (\sigma (\rho ^{-1}(\boldsymbol{y}))) + [\boldsymbol{x}]_{\rho (1)} \cdot \rho (\rho ^{-1}(\boldsymbol{z})) \\&\qquad = (\rho \circ f) (\boldsymbol{x}, \boldsymbol{y}, \boldsymbol{z}). \end{aligned}$$

Therefore, each rule appears twice owing to the action of $S_{3}$, which reduces the number of rules in the equivalence class by half. Representatives of such types of equivalence classes are of the form (2), where $\langle \boldsymbol{x} \rangle = [\boldsymbol{x}]_{1}$ or $1-[\boldsymbol{x}]_{1}$, and $\sigma , \tau$ are identities or $(2\ 3)$. Therefore, there are eight classes that contain six rules. Similarly, 216 weighted-averaging rules of the forms (4) are divided into 20 equivalence classes.

To prove the convergence of VFCA with the weighted-averaging rules, we use a general framework. Let $\textrm{int}(\varDelta )$ be the relative interior of $\varDelta$; that is

$$\begin{aligned} \textrm{int}(\varDelta ) = \left\{ (x_{1}, x_{2}, x_{3})^{\top } \in \mathbb {R}^{3} \mid x_{1} + x_{2} + x_{3} = 1,\ x_{1},x_{2},x_{3} > 0 \right\} . \end{aligned}$$

Hereafter, the indices of the cells are considered in modulo L if not specified.

Proposition 1

Let $\{ \boldsymbol{X}^{t} \}_{t \in \mathbb {Z}_{\ge 0}}$ be a sequence in $\varDelta ^{L}$ with $\boldsymbol{X}^{0} \in \textrm{int}(\varDelta )^{L}$, where $\boldsymbol{X}^{t} = (\boldsymbol{x}^{t}_{0},\boldsymbol{x}^{t}_{1},\dots ,\boldsymbol{x}^{t}_{L-1})$. Suppose that the evolution can be written as

$$\begin{aligned} \boldsymbol{x}^{t+1}_{i} = (1-\gamma ^{t}_{i}) \boldsymbol{x}^{t}_{i} + \gamma ^{t}_{i} \boldsymbol{x}^{t}_{i+1}. \end{aligned}$$

If there exists $\gamma$ with $0< \gamma < 1/2$ such that $\gamma ^{t}_{i} \in [\gamma , 1-\gamma ]$ for all $i \in \mathbb {Z}$ and $t \in \mathbb {Z}_{\ge 0}$, then there exists $\boldsymbol{p} \in \varDelta$ such that $\boldsymbol{X}^{t}$ converges to a homogeneous configuration $\boldsymbol{X}^{*} = (\boldsymbol{p}, \boldsymbol{p}, \dots , \boldsymbol{p})$ as $t \rightarrow \infty$.

In the proof of Proposition 1, we use the following result for EFCA:

Lemma 1

([8]). Let $\{ X^{t}\}_{t \in \mathbb {Z}_{\ge 0}}$ be a sequence in $[0,1]^{L}$ with $X^{0} \in (0,1)^{L}$, where $X^{t} = (x^{t}_{0}, x^{t}_{1},\dots , x^{t}_{L-1})$. Suppose that the evolution can be written as

$$\begin{aligned} x^{t+1}_{i} = (1-\gamma ^{t}_{i}) x^{t}_{i} + \gamma ^{t}_{i} x^{t}_{i+1}. \end{aligned}$$

If there exists $\gamma$ with $0< \gamma < 1/2$ such that $\gamma ^{t}_{i} \in [\gamma , 1-\gamma ]$ for all $i \in \mathbb {Z}$ and $t \in \mathbb {Z}_{\ge 0}$, then there exists $p \in [0,1]$ such that $X^{t}$ converges to the homogeneous configuration $(p,p,\dots ,p)$ as $t \rightarrow \infty$.

Proof (Proposition 1)

For each $k \in \{1,2,3\}$, the initial configuration satisfies $([\boldsymbol{x}^{0}_{0}]_{k}, [\boldsymbol{x}^{0}_{1}]_{k},\dots ,[\boldsymbol{x}^{0}_{L-1}]_{k}) \in (0,1)^{L}$. Moreover, the evolution can be written as

$$\begin{aligned}{}[\boldsymbol{x}^{t+1}_{i}]_{k} = (1-\gamma ^{t}_{i}) [\boldsymbol{x}^{t}_{i}]_{k} + \gamma ^{t}_{i} [\boldsymbol{x}^{t}_{i+1}]_{k}. \end{aligned}$$

Therefore, the sequence $\{ X^{t}_{k} \}_{t \in \mathbb {Z}_{\ge 0}}$ where $X^{t}_{k} = ([\boldsymbol{x}^{t}_{0}]_{k}, [\boldsymbol{x}^{t}_{1}]_{k},\dots ,[\boldsymbol{x}^{t}_{L-1}]_{k})$ satisfies the assumption of Lemma 1. Thus, $[\boldsymbol{x}^{t}_{i}]_{k}$ converges to the same constant $p_{k} \in [0,1]$ independent of cell i. This implies that $\boldsymbol{x}^{t}_{i}$ converges to the same vector $\boldsymbol{p} = (p_{1}, p_{2}, p_{3})^{\top } \in \varDelta$ independent of cell i. $\square$

3 Convergence of VFCA with Weighted-Averaging Rules

We now present the convergence statement of VFCA with weighted-averaging rules. In contrast to the case of EFCA, we observe two types of convergence depending on whether $\sigma$ and $\tau$ are commutative, that is, $\sigma \tau = \tau \sigma$. For simplicity, the period L is assumed to be a multiple of $|S_{3}| = 6$.

3.1 Commutative Case of the Weighted-Averaging Rules of Type 1

Figure 1(left) illustrates the space-time diagram of VFCA whose local rule is

$$\begin{aligned} f(\boldsymbol{x},\boldsymbol{y},\boldsymbol{z}) = \begin{pmatrix} (x_{2}+ x_{3}) y_{2} + x_{1} z_{3} \\ (x_{2}+ x_{3}) y_{3} + x_{1} z_{1} \\ (x_{2}+ x_{3}) y_{1} + x_{1} z_{2} \end{pmatrix} = (1-x_{1}) \begin{pmatrix} y_{2} \\ y_{3} \\ y_{1} \end{pmatrix} + x_{1} \begin{pmatrix} z_{3} \\ z_{1} \\ z_{2} \end{pmatrix}. \end{aligned}$$

Here, $\sigma = (1\ 3\ 2)$ and $\tau =(1\ 2\ 3)$ are commutative. We observed that this VFCA exhibited periodic behavior in both time (vertical axis) and space (horizontal axis) after a sufficient number of time steps. This is stated in the following theorem. Note that $\textrm{ord}\, \sigma$ is the order of a permutation $\sigma$ in $S_{3}$.

Fig. 1.

To visualize the evolution of VFCA, we use the RGB color system. The states $\boldsymbol{e}_1$, $\boldsymbol{e}_2$, and $\boldsymbol{e}_3$ are associated with red, green, and blue, respectively. An inner point of $\varDelta$ is expressed by the mixture of the three colors. (left) Space-time diagram for a complete number-conserving rule (rule 3,226,064,485,963 by Wolfram’s numbering rule [12]). (right) Space-time diagram for a weighted averaging rule (rule 3,226,250,775,339) (Color figure online)

Theorem 1

Suppose $\boldsymbol{X}^{0} = (\boldsymbol{x}^{0}_{0}, \boldsymbol{x}^{0}_{1},\dots ,\boldsymbol{x}^{0}_{L-1}) \in \textrm{int}(\varDelta )^{L}$. If $\sigma$ and $\tau$ are commutative, there exists $\boldsymbol{p} \in \varDelta$ such that the VFCA with the weighted-averaging rule (2) periodically converges as follows:

$$\begin{aligned} \boldsymbol{X}^{t} \rightarrow (\sigma ^{s}(\boldsymbol{p}), \sigma ^{s}\pi ^{-1} (\boldsymbol{p}), \dots , \sigma ^{s} \pi ^{-(L-1)}(\boldsymbol{p})), \quad t=s \bmod (\textrm{ord}\, \sigma ). \end{aligned}$$

Here, $\pi = \sigma ^{-1} \tau$ and $0 \le s \le \textrm{ord}\, \sigma -1$.

We note that the vector $\boldsymbol{p}$ in Theorem 1 depends on the initial configuration and is not obtained explicitly in a simple formula.

Proof

First, we verify that $m^{t} := \min _{i}\min _{k=1,2,3} [\boldsymbol{x}^{t}_{i}]_{k}$ is nondecreasing and $M^{t} := \max _{i} \max _{k=1,2,3} [\boldsymbol{x}^{t}_{i}]_{k}$ is nonincreasing. For any i and $k \in \{1,2,3\}$,

$$\begin{aligned}{}[\boldsymbol{x}^{t+1}_{i}]_{k}&= (1- \langle \boldsymbol{x}^{t}_{i-1} \rangle ) \cdot [\sigma (\boldsymbol{x}^{t}_{i})]_{k} + \langle \boldsymbol{x}^{t}_{i-1} \rangle \cdot [\tau (\boldsymbol{x}^{t}_{i+1})]_{k} \\&= (1- \langle \boldsymbol{x}^{t}_{i-1} \rangle ) \cdot [\boldsymbol{x}^{t}_{i}]_{\sigma ^{-1}(k)} + \langle \boldsymbol{x}^{t}_{i-1} \rangle \cdot [\boldsymbol{x}^{t}_{i+1}]_{\tau ^{-1}(k)} \\&\ge \min ([\boldsymbol{x}^{t}_{i}]_{\sigma ^{-1}(k)}, [\boldsymbol{x}^{t}_{i+1}]_{\tau ^{-1}(k)}) \\&\ge m^{t}. \end{aligned}$$

Here, the property of the weighted average was used. Therefore, $m^{t+1} \ge m^{t}$. Similarly, we show that $M^{t+1} \le M^{t}$. In particular, if we take $\gamma > 0$ such that $\gamma \le m^{0} \le M^{0} \le 1 - \gamma$, then both $[\boldsymbol{x}^{t}_{i}]_{k}$ and $1- [\boldsymbol{x}^{t}_{i}]_{k}$ are in the interval $[\gamma , 1-\gamma ]$ for all i, t, and k.

The local rule (2) can be written as

$$\begin{aligned} f(\boldsymbol{x}, \boldsymbol{y}, \boldsymbol{z}) = \sigma ((1 - \langle \boldsymbol{x} \rangle ) \cdot \boldsymbol{y} + \langle \boldsymbol{x} \rangle \cdot \pi (\boldsymbol{z})), \end{aligned}$$

where $\pi = \sigma ^{-1}\tau$. Let $F: \varDelta ^{L} \rightarrow \varDelta ^{L}$ be the global rule of this VFCA. For each $t \in \mathbb {Z}_{\ge 0}$ and $i = 0,1,\dots ,L-1$ we define the local function as

$$\begin{aligned} g_{t,i}(\boldsymbol{x}, \boldsymbol{y}, \boldsymbol{z}) = (1- \langle \sigma ^{t} \pi ^{-(i-1)}(\boldsymbol{x})\rangle ) \cdot \boldsymbol{y} + \langle \sigma ^{t} \pi ^{-(i-1)}(\boldsymbol{x})\rangle \cdot \boldsymbol{z}. \end{aligned}$$

(5)

Note that this local function differs for each cell i and time t. In addition, we define the global map $G_{t}: \varDelta ^{L} \rightarrow \varDelta ^{L}$ as

$$\begin{aligned} \begin{aligned}&G_{t}(\boldsymbol{x}_{0}, \boldsymbol{x}_{1},\dots ,\boldsymbol{x}_{L-1}) \\&\qquad = (g_{t,0}(\boldsymbol{x}_{L-1}, \boldsymbol{x}_{0}, \boldsymbol{x}_{1}), g_{t,1}(\boldsymbol{x}_{0}, \boldsymbol{x}_{1}, \boldsymbol{x}_{2}), \dots , g_{t,L-1}(\boldsymbol{x}_{L-2}, \boldsymbol{x}_{L-1}, \boldsymbol{x}_{0})). \end{aligned} \end{aligned}$$

(6)

We also define the bijection $h_{t}: \varDelta ^{L} \rightarrow \varDelta ^{L}$ as

$$\begin{aligned} h_{t}(\boldsymbol{x}_{0}, \boldsymbol{x}_{1},\dots ,\boldsymbol{x}_{L-1}) = (\sigma ^{-t}(\boldsymbol{x}_{0}), \sigma ^{-t}\pi (\boldsymbol{x}_{1}), \dots , \sigma ^{-t} \pi ^{L-1}(\boldsymbol{x}_{L-1})). \end{aligned}$$

We then show that $h_{t+1} \circ F = G_{t} \circ h_{t}$ for all positive integers $t \in \mathbb {Z}_{\ge 0}$.

The vector at cell i of $(h_{t+1} \circ F) (\boldsymbol{x}_{0}, \boldsymbol{x}_{1},\dots ,\boldsymbol{x}_{L-1})$ is

$$\begin{aligned}&\sigma ^{-(t+1)} \pi ^{i} (\sigma ( (1-\langle \boldsymbol{x}_{i-1} \rangle ) \cdot \boldsymbol{x}_{i} + \langle \boldsymbol{x}_{i-1} \rangle \cdot \pi (\boldsymbol{x}_{i+1}))) \\&\qquad = (1-\langle \boldsymbol{x}_{i-1} \rangle ) \cdot \sigma ^{-t} \pi ^{i}(\boldsymbol{x}_{i}) + \langle \boldsymbol{x}_{i-1} \rangle \cdot \sigma ^{-t} \pi ^{i+1} (\boldsymbol{x}_{i+1}). \end{aligned}$$

In contrast, the vector at cell i of $(G_{t} \circ h_{t}) (\boldsymbol{x}_{0}, \boldsymbol{x}_{1},\dots ,\boldsymbol{x}_{L-1})$ is

$$\begin{aligned}&g_{t,i}( \sigma ^{-t} \pi ^{i-1}(\boldsymbol{x}_{i-1}), \sigma ^{-t} \pi ^{i}(\boldsymbol{x}_{i}), \sigma ^{-t} \pi ^{i+1}(\boldsymbol{x}_{i+1})) \\&\qquad = (1 - \langle \sigma ^{t}\pi ^{-(i-1)} (\sigma ^{-t} \pi ^{i-1}(\boldsymbol{x}_{i-1})) \rangle ) \cdot \sigma ^{-t} \pi ^{i}(\boldsymbol{x}_{i}) \\&\qquad \qquad \quad + \langle \sigma ^{t}\pi ^{-(i-1)} (\sigma ^{-t} \pi ^{i-1}(\boldsymbol{x}_{i-1})) \rangle \cdot \sigma ^{-t} \pi ^{i+1}(\boldsymbol{x}_{i+1}) \\&\qquad = (1-\langle \boldsymbol{x}_{i-1} \rangle ) \cdot \sigma ^{-t} \pi ^{i}(\boldsymbol{x}_{i}) + \langle \boldsymbol{x}_{i-1} \rangle \cdot \sigma ^{-t} \pi ^{i+1} (\boldsymbol{x}_{i+1}). \end{aligned}$$

In both computations, we use $\sigma \pi = \pi \sigma$, which is derived from $\sigma \tau = \tau \sigma$. Because this holds for all $i = 0,1,\dots ,L-1$, we have $h_{t+1} \circ F = G_{t} \circ h_{t}$. Using this system repeatedly, we can express t times the composition of F as

$$\begin{aligned} F^{t} = h_{t}^{-1} \circ (G_{t-1} \circ \cdots \circ G_{1} \circ G_{0}) \circ h_{0}. \end{aligned}$$

(7)

We set $\boldsymbol{Y}^{0}:= h_{0}(\boldsymbol{X}^{0}) \in \textrm{int}(\varDelta )^{L}$. We define $\boldsymbol{Y}^{t}$ as

$$\begin{aligned} \boldsymbol{Y}^{t} = (G_{t-1} \circ \cdots \circ G_{1} \circ G_{0}) (\boldsymbol{Y}^{0}). \end{aligned}$$

From (5) and (6), the sequence $\{ \boldsymbol{Y}^{t} \}_{t \in \mathbb {Z}_{\ge 0}}$ satisfies Proposition 1. Therefore, $\boldsymbol{Y}^{t}$ converges to a homogeneous configuration $(\boldsymbol{p}, \boldsymbol{p}, \dots , \boldsymbol{p}) \in \varDelta ^{L}$ as $t \rightarrow \infty$. From (7), $\boldsymbol{X}^{t}$ converges to

$$\begin{aligned} h^{-1}_{t}(\boldsymbol{p}, \boldsymbol{p}, \dots , \boldsymbol{p}) = (\sigma ^{t}(\boldsymbol{p}), \sigma ^{t}\pi ^{-1} (\boldsymbol{p}), \dots , \sigma ^{t} \pi ^{-(L-1)}(\boldsymbol{p})). \end{aligned}$$

In particular, when $t=s \mod (\textrm{ord}\, \sigma )$, we obtain

$$\begin{aligned} \boldsymbol{X}^{t} \rightarrow (\sigma ^{s}(\boldsymbol{p}), \sigma ^{s}\pi ^{-1} (\boldsymbol{p}), \dots , \sigma ^{s} \pi ^{-(L-1)}(\boldsymbol{p})) \end{aligned}$$

as $t \rightarrow \infty$. $\square$

3.2 Non-commutative Case of the Weighted-Averaging Rules of Type 1

Next, we consider the case in which $\sigma$ and $\tau$ are non-commutative. The corresponding VFCA converges to a homogeneous configuration consisting of centroids whenever the initial configuration is in $\textrm{int}(\varDelta )^{L}$. Figure 1(right) shows the space-time diagram of a VFCA whose local rule is

$$\begin{aligned} f(\boldsymbol{x},\boldsymbol{y},\boldsymbol{z}) = \begin{pmatrix} (x_{2}+ x_{3}) y_{2} + x_{1} z_{3} \\ (x_{2}+ x_{3}) y_{1} + x_{1} z_{1} \\ (x_{2}+ x_{3}) y_{3} + x_{1} z_{2} \end{pmatrix} = (1-x_{1}) \begin{pmatrix} y_{2} \\ y_{1} \\ y_{3} \end{pmatrix} + x_{1} \begin{pmatrix} z_{3} \\ z_{1} \\ z_{2} \end{pmatrix}. \end{aligned}$$

Here, $\sigma = (1\ 2)$ and $\tau =(1\ 2\ 3)$ are non-commutative. We can see that all cells converge to “gray”, representing $(1/3, 1/3, 1/3)^{\top }$.

Theorem 2

Suppose $\boldsymbol{X}^{0} = (\boldsymbol{x}^{0}_{0}, \boldsymbol{x}^{0}_{1},\dots ,\boldsymbol{x}^{0}_{L-1}) \in \textrm{int}(\varDelta )^{L}$. If $\sigma$ and $\tau$ are non-commutative, then the VFCA with the weighted-averaging rule (2) converges to

$$\begin{aligned} \boldsymbol{X}^{*} = ( \boldsymbol{a}, \boldsymbol{a}, \dots , \boldsymbol{a}), \end{aligned}$$

where $\boldsymbol{a} = (1/3, 1/3, 1/3)^{\top }$.

The following two lemmas will be used in the proof of Theorem 2. Let $S(\sigma , \tau ; m, n)$ be the set of all permutations in $S_{3}$ obtained from a composition of m times $\sigma$ and n times $\tau$ in any order.

Lemma 2

Let $m^{t} = \min _{i} \min _{k=1,2,3} [\boldsymbol{x}^{t}_{i}]_{k}$, $M^{t} = \max _{i} \max _{k=1,2,3} [\boldsymbol{x}^{t}_{i}]_{k}$. Under the assumption in Theorem 2, we consider $\gamma > 0$ such that $\gamma \le m^{0} \le M^{0} \le 1 - \gamma$. At step t, suppose $M^{t} = [\boldsymbol{x}^{t}_{i}]_{k}$. Then, for any pair (j, s) with $0 \le j \le s$ and permutation $\rho \in S(\sigma ,\tau ;s-j,j)$,

$$\begin{aligned}{}[\boldsymbol{x}^{t+s}_{i-j}]_{\rho (k)} \ge m^{t} + \gamma ^{s}(M^{t} - m^{t}). \end{aligned}$$

Proof

As in the proof of Theorem 1, we see that $m^{t}$ is nondecreasing and $M^{t}$ is nonincreasing; in particular, both $\langle \boldsymbol{x}^{t}_{i} \rangle$ and $1- \langle \boldsymbol{x}^{t}_{i} \rangle$ are in the interval $[\gamma , 1-\gamma ]$ for all i and t. We prove the assertion of this lemma through induction on s. The case $s=0$ is trivial. Suppose that this assertion is true for $s-1$. Let $\rho \in S(\sigma ,\tau ; s-j,j)$.

Case 1::

$\rho = \sigma \rho '$ where $\rho ' \in S(\sigma ,\tau ;s-j-1,j)$. Under the assumption of induction, we obtain

$$\begin{aligned}{}[\boldsymbol{x}^{t+s-1}_{i-j}]_{\rho '(k)} \ge m^{t} + \gamma ^{s-1}(M^{t} - m^{t}). \end{aligned}$$

Therefore, we have

$$\begin{aligned}{}[\boldsymbol{x}^{t+s}_{i-j}]_{\rho (k)}&= [\sigma ^{-1}(\boldsymbol{x}^{t+s}_{i-j})]_{\rho '(k)} \\&= (1-\langle \boldsymbol{x}^{t+s-1}_{i-j-1}\rangle ) \cdot [\boldsymbol{x}^{t+s-1}_{i-j}]_{\rho '(k)} + \langle \boldsymbol{x}^{t+s-1}_{i-j-1}\rangle \cdot [\sigma ^{-1}\tau (\boldsymbol{x}^{t+s-1}_{i-j+1}) ]_{\rho '(k)} \\&\ge (1-\langle \boldsymbol{x}^{t+s-1}_{i-j-1}\rangle ) \cdot (m^{t} + \gamma ^{s-1}(M^{t} - m^{t})) + \langle \boldsymbol{x}^{t+s-1}_{i-j-1}\rangle \cdot m^{t} \\&\ge \gamma (m^{t} + \gamma ^{s-1}(M^{t} - m^{t})) + (1-\gamma ) m^{t} \\&= m^{t} + \gamma ^{s}(M^{t} - m^{t}). \end{aligned}$$

In the second inequality, we use the following fact. If $a \ge b$ and $p \ge q$, then $pa+(1-p)b \ge qa+(1-q)b$.

Case 2::

$\rho = \tau \rho '$ where $\rho ' \in S(\sigma ,\tau ;s-j,j-1)$. Under the assumption of induction, we obtain

$$\begin{aligned}{}[\boldsymbol{x}^{t+s-1}_{i-(j-1)}]_{\rho '(k)} \ge m^{t} + \gamma ^{s-1}(M^{t} - m^{t}). \end{aligned}$$

Therefore, we have

$$\begin{aligned}{}[\boldsymbol{x}^{t+s}_{i-j}]_{\rho (k)}&= [\tau ^{-1}(\boldsymbol{x}^{t+s}_{i-j})]_{\rho '(k)} \\&= (1-\langle \boldsymbol{x}^{t+s-1}_{i-j-1}\rangle ) \cdot [\tau ^{-1}\sigma (\boldsymbol{x}^{t+s-1}_{i-j})]_{\rho '(k)} + \langle \boldsymbol{x}^{t+s-1}_{i-j-1}\rangle \cdot [\boldsymbol{x}^{t+s-1}_{i-j+1}]_{\rho '(k)} \\&\ge (1-\langle \boldsymbol{x}^{t+s-1}_{i-j-1}\rangle ) \cdot m^{t} + \langle \boldsymbol{x}^{t+s-1}_{i-j-1}\rangle \cdot (m^{t} + \gamma ^{s-1}(M^{t} - m^{t})) \\&\ge (1-\gamma ) m^{t} + \gamma (m^{t} + \gamma ^{s-1}(M^{t} - m^{t})) \\&= m^{t} + \gamma ^{s}(M^{t} - m^{t}). \end{aligned}$$

Thus, we have proven this lemma by induction. $\square$

Lemma 3

Suppose $\sigma , \tau \in S_{3}$ are non-commutative. For any $k,k' \in \{1,2,3\}$ and $m, n \ge 3$, there exists a permutation $\rho \in S(\sigma ,\tau ;m,n)$ such that $\rho (k) = k'$.

Proof

If $\sigma$ is a cycle of length 3 and $\tau$ is a transposition, we define $\rho _{1},\rho _{2},\rho _{3} \in S(\sigma ,\tau ;m,n)$ as follows:

$$\begin{aligned} \rho _{1}&:= (\sigma ^{m-3}\tau ^{n-2}) (\sigma ^{3} \tau ^{2}) = (\sigma ^{m-3}\tau ^{n-2}), \\ \rho _{2}&:= (\sigma ^{m-3}\tau ^{n-2}) (\sigma ^{2} \tau \sigma \tau ) = (\sigma ^{m-3}\tau ^{n-2}) \sigma , \\ \rho _{3}&:= (\sigma ^{m-3}\tau ^{n-2}) (\sigma \tau \sigma ^{2} \tau ) = (\sigma ^{m-3}\tau ^{n-2}) \sigma ^{2}. \end{aligned}$$

Because one of $\rho _{1}(k), \rho _{2}(k)$ or $\rho _{3}(k)$ is $k'$, we can obtain a desired permutation $\rho \in S(\sigma ,\tau ;m,n)$. The case in which $\sigma$ and $\tau$ are distinct transpositions is proven similarly. $\square$

Proof (Theorem 2).

We apply Lemma 2 for $s=L+6$ and consider the case $3 \le j \le L+3$. From Lemma 3, for any $k'$, there exists $\rho \in S(\sigma ,\tau ;s-j,j)$ such that $\rho (k) = k'$. Here, k is the fixed index selected from Lemma 2. Then, for any $k'=1,2,3$ and $3 \le j \le L+3$, we have

$$\begin{aligned}{}[\boldsymbol{x}^{t+L+6}_{i-j}]_{k'} \ge m^{t} + \gamma ^{L+6}(M^{t} - m^{t}). \end{aligned}$$

Using the periodic boundary condition, we obtain

$$\begin{aligned}{}[\boldsymbol{x}^{t+L+6}_{i}]_{k'} \ge m^{t} + \gamma ^{L+6}(M^{t} - m^{t}) \end{aligned}$$

for $i=0,1,\dots ,L-1$, yielding

$$\begin{aligned} m^{t+L+6} \ge m^{t} + \gamma ^{L+6}(M^{t} - m^{t}). \end{aligned}$$

Let $m^{*} = \lim _{t \rightarrow \infty } m^{t}$ and $M^{*} = \lim _{t \rightarrow \infty } M^{t}$. We demonstrate that $m^{*} = M^{*}$. In contrast, suppose $m^{*} < M^{*}$. Then, there exists $\epsilon > 0$ such that $M^{t} - m^{t} > \epsilon$ for all $t \in \mathbb {Z}_{\ge 0}$. In contrast, for all $\delta > 0$, there exists $T \in \mathbb {Z}_{\ge 0}$ such that $m^{*} - m^{T} < \delta$. Setting $\delta = \gamma ^{L+6} \epsilon$, we obtain

$$\begin{aligned} m^{T + L + 6} \ge m^{T} + \gamma ^{L+6} (M^{T} - m^{T})> m^{T} + \gamma ^{L+6} \epsilon > m^{*}, \end{aligned}$$

which is contradictory. Therefore, we have proven $m^{*} = M^{*} = 1/3$. $\square$

3.3 Weighted-Averaging Rules of Type 2

In this subsection, we consider weighted-averaging rules of the form (4). The period of space is assumed to be 2L, which is a multiple of 12.

Theorem 3

Suppose $\boldsymbol{X}^{0} = (\boldsymbol{x}^{0}_{0}, \boldsymbol{x}^{0}_{1},\dots ,\boldsymbol{x}^{0}_{2L-1}) \in \textrm{int}(\varDelta )^{2L}$. If $\sigma$ and $\tau$ are commutative, then there exists $\boldsymbol{p},\boldsymbol{q} \in \varDelta$ such that the VFCA with weighted averaging rule (4) periodically converges as follows:

$$\begin{aligned} \boldsymbol{X}^{t} \rightarrow \ (\sigma ^{s}\pi ^{r}(\boldsymbol{p}), \sigma ^{s}\pi ^{r}(\boldsymbol{q}), \sigma ^{s}\pi ^{r-1} (\boldsymbol{p}), \sigma ^{s}\pi ^{r-1}(\boldsymbol{q}), \dots , \sigma ^{s}\pi ^{r-(L-1)}(\boldsymbol{q})), \end{aligned}$$

when $t=s \bmod (\textrm{ord}\, \sigma )$ and $t=2r \bmod 2(\textrm{ord}\, \pi )$ and

$$\begin{aligned} \boldsymbol{X}^{t} \rightarrow \ (\sigma ^{s}\pi ^{r+1}(\boldsymbol{q}), \sigma ^{s}\pi ^{r}(\boldsymbol{p}), \sigma ^{s}\pi ^{r} (\boldsymbol{q}), \sigma ^{s}\pi ^{r-1}(\boldsymbol{p}), \dots , \sigma ^{s}\pi ^{r-(L-1)}(\boldsymbol{p})) \end{aligned}$$

when $t=s \bmod (\textrm{ord}\, \sigma )$ and $t=2r+1 \bmod 2(\textrm{ord}\, \pi )$, where $\pi = \sigma ^{-1} \tau$, $0 \le s \le \textrm{ord}\, \sigma -1$ and $0 \le r \le \textrm{ord}\, \tau -1$.

Proof

The local rule (4) can be written as

$$\begin{aligned} f(\boldsymbol{x}, \boldsymbol{y}, \boldsymbol{z}) = \sigma ((1 - \langle \boldsymbol{y}\rangle ) \cdot \boldsymbol{x} + \langle \boldsymbol{y}\rangle \cdot \pi (\boldsymbol{z})). \end{aligned}$$

Let $F: \varDelta ^{2L} \rightarrow \varDelta ^{2L}$ be the global rule. Furthermore, let $\tilde{F}: \varDelta ^{2L} \rightarrow \varDelta ^{2L}$ be the shifted global rule defined by

$$\begin{aligned} \tilde{F}(\boldsymbol{x}_{0}, \boldsymbol{x}_{1},\dots ,\boldsymbol{x}_{2L-1})&:= (S \circ F) (\boldsymbol{x}_{0}, \boldsymbol{x}_{1},\dots ,\boldsymbol{x}_{2L-1}) \\&= (f(\boldsymbol{x}_{0}, \boldsymbol{x}_{1}, \boldsymbol{x}_{2}), f(\boldsymbol{x}_{1}, \boldsymbol{x}_{2}, \boldsymbol{x}_{3}), \dots , f(\boldsymbol{x}_{2L-1}, \boldsymbol{x}_{0}, \boldsymbol{x}_{1})), \end{aligned}$$

where $S: \varDelta ^{2L} \rightarrow \varDelta ^{2L}$ denotes the left-shift map

$$\begin{aligned} S(\boldsymbol{x}_{0}, \boldsymbol{x}_{1},\dots ,\boldsymbol{x}_{2L-1}) = (\boldsymbol{x}_{1},\dots ,\boldsymbol{x}_{2L-1}, \boldsymbol{x}_{0}). \end{aligned}$$

As in the case of the EFCA [8], the key idea is to divide the entire space into even and odd parts. The original VFCA can then be regarded as a direct product of the two sequences, satisfying the assumption of Proposition 1.

For $t \in \mathbb {Z}_{\ge 0}$ and $i = 0,1,\dots ,L-1$, we define the functions as

$$\begin{aligned} g^{\textrm{e}}_{t,i}(\boldsymbol{x}, \boldsymbol{z}; \boldsymbol{y})&= (1-\langle \sigma ^{t} \pi ^{-i}(\boldsymbol{y})\rangle ) \cdot \boldsymbol{x} + \langle \sigma ^{t} \pi ^{-i}(\boldsymbol{y})\rangle \cdot \boldsymbol{z}, \\ g^{\textrm{o}}_{t,i}(\boldsymbol{x}, \boldsymbol{z}; \boldsymbol{y})&= (1-\langle \sigma ^{t} \pi ^{-(i+1)}(\boldsymbol{y})\rangle ) \cdot \boldsymbol{x} + \langle \sigma ^{t} \pi ^{-(i+1)}(\boldsymbol{y})\rangle \cdot \boldsymbol{z}, \end{aligned}$$

and global maps $G_{t}^{\textrm{e}}, G_{t}^{\textrm{o}}: \varDelta ^{L} \rightarrow \varDelta ^{L}$ as

$$\begin{aligned}&G_{t}^{\textrm{e}}(\boldsymbol{x}_{0}, \boldsymbol{x}_{1},\dots ,\boldsymbol{x}_{L-1}; \boldsymbol{y}_{0}, \boldsymbol{y}_{1},\dots ,\boldsymbol{y}_{L-1}) \\&\qquad = (g^{\textrm{e}}_{t,0}(\boldsymbol{x}_{0}, \boldsymbol{x}_{1}; \boldsymbol{y}_{0}), g^{\textrm{e}}_{t,1}(\boldsymbol{x}_{1}, \boldsymbol{x}_{2}; \boldsymbol{y}_{1}), \dots , g^{\textrm{e}}_{t,L-1}(\boldsymbol{x}_{L-1}, \boldsymbol{x}_{0}, \boldsymbol{y}_{L-1})), \\&G_{t}^{\textrm{o}}(\boldsymbol{x}_{0}, \boldsymbol{x}_{1},\dots ,\boldsymbol{x}_{L-1}; \boldsymbol{y}_{0}, \boldsymbol{y}_{1},\dots ,\boldsymbol{y}_{L-1}) \\&\qquad = (g^{\textrm{o}}_{t,0}(\boldsymbol{x}_{0}, \boldsymbol{x}_{1}; \boldsymbol{y}_{1}), g^{\textrm{o}}_{t,1}(\boldsymbol{x}_{1}, \boldsymbol{x}_{2}; \boldsymbol{y}_{2}), \dots , g^{\textrm{o}}_{t,L-1}(\boldsymbol{x}_{L-1}, \boldsymbol{x}_{0}; \boldsymbol{y}_{0})). \end{aligned}$$

Here, $\boldsymbol{x}_{0}, \boldsymbol{x}_{1},\dots ,\boldsymbol{x}_{L-1}$ are the variables considered. In addition, we define two projective maps, $h_{t}^{\textrm{e}}, h_{t}^{\textrm{o}}: \varDelta ^{2L} \rightarrow \varDelta ^{L}$, as follows:

$$\begin{aligned} h_{t}^{\textrm{e}}(\boldsymbol{x}_{0}, \boldsymbol{x}_{1},\dots ,\boldsymbol{x}_{2L-1}) =&(\sigma ^{-t}(\boldsymbol{x}_{0}), \sigma ^{-t}\pi (\boldsymbol{x}_{2}), \dots , \sigma ^{-t} \pi ^{L-1}(\boldsymbol{x}_{2(L-1)})), \\ h_{t}^{\textrm{o}}(\boldsymbol{x}_{0}, \boldsymbol{x}_{1},\dots ,\boldsymbol{x}_{2L-1}) =&(\sigma ^{-t}(\boldsymbol{x}_{1}), \sigma ^{-t}\pi (\boldsymbol{x}_{3}), \dots , \sigma ^{-t} \pi ^{L-1}(\boldsymbol{x}_{2L-1})). \end{aligned}$$

Using these notations, we can verify

$$\begin{aligned} (h_{t+1}^{\textrm{e}} \circ \tilde{F}) (\boldsymbol{X}) = G_{t}^{\textrm{e}} (h_{t}^{\textrm{e}} (\boldsymbol{X}); h_{t}^{\textrm{o}} (\boldsymbol{X}) ), \quad (h_{t+1}^{\textrm{o}} \circ \tilde{F}) (\boldsymbol{X}) = G_{t}^{\textrm{o}} (h_{t}^{\textrm{o}} (\boldsymbol{X}); h_{t}^{\textrm{e}} (\boldsymbol{X}) ) \end{aligned}$$

for $t \in \mathbb {Z}_{\ge 0}$ and $\boldsymbol{X} = (\boldsymbol{x}_{0}, \boldsymbol{x}_{1},\dots ,\boldsymbol{x}_{2L-1}) \in \varDelta ^{2L}$. These equalities are obtained in a manner similar to the proof of Theorem 1.

We define $h_{t}: \varDelta ^{2L} \rightarrow \varDelta ^{L} \times \varDelta ^{L}$ and $G_{t}: \varDelta ^{L} \times \varDelta ^{L} \rightarrow \varDelta ^{L} \times \varDelta ^{L}$ as

$$\begin{aligned} h_{t}(\boldsymbol{X} ) = (h_{t}^{\textrm{e}}(\boldsymbol{X}), h_{t}^{\textrm{o}}(\boldsymbol{X})) \quad \text { and } \quad G_{t}((\boldsymbol{Y}, \boldsymbol{Z})) = (G_{t}^{\textrm{e}}(\boldsymbol{Y}; \boldsymbol{Z}), G_{t}^{\textrm{o}}(\boldsymbol{Z}; \boldsymbol{Y})). \end{aligned}$$

Then, $h_{t}$ is a bijection, and

$$\begin{aligned} (h_{t} \circ \tilde{F})(\boldsymbol{X}) = (G_{t}^{\textrm{e}} (h_{t}^{\textrm{e}} (\boldsymbol{X}); h_{t}^{\textrm{o}} (\boldsymbol{X}) ), G_{t}^{\textrm{o}} (h_{t}^{\textrm{o}} (\boldsymbol{X}); h_{t}^{\textrm{e}} (\boldsymbol{X}) )) = (G_{t} \circ h_{t})(\boldsymbol{X}). \end{aligned}$$

Therefore, the t-times composition of $\tilde{F}$ can be expressed as

$$\begin{aligned} \tilde{F}^{t} = h_{t}^{-1} \circ (G_{t-1} \circ G_{t-2} \circ \cdots \circ G_{0}) \circ h_{0}. \end{aligned}$$

Using the commutativity of F and left-shift map S, we have

$$\begin{aligned} F^{t} = (S^{t})^{-1} \circ h_{t}^{-1} \circ (G_{t-1} \circ G_{t-1} \circ \cdots \circ G_{0}) \circ h_{0}. \end{aligned}$$

We set $(\boldsymbol{Y}^{0}, \boldsymbol{Z}^{0}):= h_{0}(\boldsymbol{X}^{0}) \in \textrm{int}(\varDelta )^{L} \times \textrm{int}(\varDelta )^{L}$. If we define

$$\begin{aligned} (\boldsymbol{Y}^{t},\boldsymbol{Z}^{t}) = (G_{t-1} \circ G_{t-2} \circ \cdots \circ G_{0}) (\boldsymbol{Y}^{0}, \boldsymbol{Z}^{0}), \end{aligned}$$

both $\{ \boldsymbol{Y}^{t} \}_{t \in \mathbb {Z}_{\ge 0}}$ and $\{ \boldsymbol{Z}^{t} \}_{t \in \mathbb {Z}_{\ge 0}}$ satisfy the assumption of Proposition 1. Therefore, $\boldsymbol{Y}^{t}$ and $\boldsymbol{Z}^{t}$ converge to configurations $(\boldsymbol{p}, \boldsymbol{p}, \dots , \boldsymbol{p})$ and $(\boldsymbol{q}, \boldsymbol{q}, \dots , \boldsymbol{q})$ as $t \rightarrow \infty$, respectively. Then, $\boldsymbol{X}^{t}$ converges to

$$\begin{aligned}&((S^{-1})^{t} \circ h^{-1}_{t}) ((\boldsymbol{p}, \boldsymbol{p}, \dots , \boldsymbol{p}), (\boldsymbol{q}, \boldsymbol{q}, \dots , \boldsymbol{q})) \\ =&(S^{-1})^{t} ((\sigma ^{t}(\boldsymbol{p}), \sigma ^{t}(\boldsymbol{q}), \sigma ^{t}\pi ^{-1} (\boldsymbol{p}), \sigma ^{t}\pi ^{-1} (\boldsymbol{q}) \dots , \sigma ^{t} \pi ^{-(L-1)}(\boldsymbol{p}), \sigma ^{t} \pi ^{-(L-1)}(\boldsymbol{q})) ) \\ =&{\left\{ \begin{array}{ll} (\sigma ^{t}\pi ^{\frac{t}{2}}(\boldsymbol{p}), \sigma ^{t}\pi ^{\frac{t}{2}}(\boldsymbol{q}), \sigma ^{t}\pi ^{\frac{t}{2}-1} (\boldsymbol{p}), \sigma ^{t}\pi ^{\frac{t}{2}-1} (\boldsymbol{q}), \dots \quad &{} \\ \dots , \sigma ^{t} \pi ^{\frac{t}{2}-(L-1)}(\boldsymbol{p}), \sigma ^{t} \pi ^{\frac{t}{2}-(L-1)}(\boldsymbol{q})) &{} \text {if { t} is even,} \\ (\sigma ^{t}\pi ^{\frac{t+1}{2}}(\boldsymbol{q}), \sigma ^{t}\pi ^{\frac{t-1}{2}}(\boldsymbol{p}), \sigma ^{t}\pi ^{\frac{t+1}{2}-1} (\boldsymbol{q}), \sigma ^{t}\pi ^{\frac{t-1}{2}-1} (\boldsymbol{p}), \dots \quad &{} \\ \dots , \sigma ^{t} \pi ^{\frac{t+1}{2}-(L-1)}(\boldsymbol{q}), \sigma ^{t} \pi ^{\frac{t-1}{2}-(L-1)}(\boldsymbol{p})) &{} \text {if { t} is odd.} \end{array}\right. } \end{aligned}$$

From the periodicities of $\sigma$ and $\pi$, we may assert this theorem. $\square$

Combining the proofs of Theorems 2 and 3, we obtain the following result.

Theorem 4

Suppose $\boldsymbol{X}^{0} = (\boldsymbol{x}^{0}_{0}, \boldsymbol{x}^{0}_{1},\dots ,\boldsymbol{x}^{0}_{2L-1}) \in \textrm{int}(\varDelta )^{2L}$. If $\sigma$ and $\tau$ are non-commutative. The VFCA with the weighted-averaging rule (4) then converges to the homogeneous configuration with the centroid $\boldsymbol{a} = (1/3, 1/3, 1/3)^{\top }$:

$$\begin{aligned} \boldsymbol{X}^{*} = ( \boldsymbol{a}, \boldsymbol{a}, \dots , \boldsymbol{a}). \end{aligned}$$

4 Conclusion

In this study, we provide an analytical proof for the convergence of VFCA. The convergence patterns of some of the weighted-averaging rules in three-state, three-neighbor VFCA are similar to those in EFCA. However, there are weighted-averaging rules with a new type of convergence pattern in the three-state case because the symmetric group $S_{3}$ is non-commutative, whereas $S_{2}$ is commutative. Under these rules, all the components of the vectors are mixed, and each cell converges to the centroid. Moreover, this proof can be easily extended to VFCA in more than three states by considering the group $S_{n}$. Although weighted-averaging rules are a small part of all rules of three-state, three-neighbor VFCA, the proofs presented in this study may be effective for the general case. Future work will demonstrate the convergence of VFCA with other rules.