# The Structure of Configurations in One-Dimensional Majority Cellular
Automata:
From Cell Stability to Configuration Periodicity

Yonatan Nakar
Tel-Aviv University
<EMAIL_ADDRESS>Dana Ron
Tel-Aviv University
<EMAIL_ADDRESS>
###### Abstract

We study the dynamics of (synchronous) one-dimensional cellular automata with
cyclical boundary conditions that evolve according to the majority rule with
radius $r$. We introduce a notion that we term _cell stability_ with which we
express the structure of the possible configurations that could emerge in this
setting. Our main finding is that apart from the configurations of the form
$(0^{r+1}0^{*}+1^{r+1}1^{*})^{*}$, which are always fixed-points, the other
configurations that the automata could possibly converge to, which are known
to be either fixed-points or 2-cycles, have a particular spatially periodic
structure. Namely, each of these configurations is of the form $s^{*}$ where
$s$ consists of $O(r^{2})$ consecutive sequences of cells with the same state,
each such sequence is of length at most $r$, and the total length of $s$ is
$O(r^{2})$ as well. We show that an analogous result also holds for the
minority rule.

###### Contents

  1. 1 Introduction
    1. 1.1 The majority rule with radius $r$
    2. 1.2 Temporal and spatial periodicity
    3. 1.3 Our main result and the notion of 1.1 stability
    4. 1.4 Illustrating Theorem 1 for $r=1,2,3$
    5. 1.5 Minority
    6. 1.6 Related work
    7. 1.7 Some high-level ideas
  2. 2 Definition 14 (Switch point).s
  3. 3 On the lengths of maximal homogeneous blocks
  4. 4 Temporally periodic configurations
  5. 5 Block intervals defined by the left and right mappings
  6. 6 The Definition 23 (alignment mapping).
  7. 7 Block lengths in Definition 6 (temporally periodic). configurations
  8. 8 The Definition 26 (block-length vector).s of Definition 20 (temporally periodic configuration pair).s
  9. 9 The Definition 29 (horizon). of Definition 26 (block-length vector).s
  10. 10 The difference vectors of Definition 12 (weakly stable). configurations are Definition 9 (spatially periodic).
  11. 11 The Definition 12 (weakly stable). configurations are Definition 9 (spatially periodic).
  12. 12 Putting it all together: Proving Theorem 1

##  1 Introduction

Dynamic processes that evolve according to the majority rule arise in various
settings and as such have received wide attention in the past, primarily
within the context of propagation of information or influence (e.g., [GM13,
Pel02, Zeh19]). Here we consider perhaps the most basic case, that of one-
dimensional cellular automata, where our focus is on analyzing the structure
of the configuration space. Specifically, we analyze the configuration space
of one-dimensional cellular automata with cyclical boundary conditions that
evolve according to the majority rule with radius $r$.

It is well-known [GO81, PS83] that these processes always converge to
configurations that correspond to cycles either of length 1 ( (fixed-point).s)
or of length 2 (period-2 cycles). In particular, it is easy to verify (see,
e.g., [TA04]) that configurations in which each 1.1 belongs to a consecutive
sequence of at least $r+1$ 1.1s with the same state111In this work, a 1 is a
value in $\\{0,1\\}$. are  (fixed-point).s. Not much is currently understood,
however, about the structure of the other  (fixed-point). configurations or of
configurations that correspond to cycles of length 2.

The reason for this gap in understanding is largely due to the fact that most
previous research has made assumptions about the mechanism producing the
initial configuration. Namely, it is usually assumed that the 1 of each 1.1 in
the initial configuration is randomly chosen, independently from the other
1.1s. See, for instance, the theoretical analysis in [TA04] and the
experimental results in [TR11], both for one-dimensional majority cellular
automata (and also the references within Section 1.6 for examples in other
models). Under such assumptions, as shown in [TA04], these other
configurations are indeed rarely encountered.

In this work, we tackle the problem of understanding the structure of the
possible configurations without making assumptions about the mechanism behind
the generation of the initial configuration. One of our main results (stated
formally in Theorem 1) is that all period-2 configurations and all  (fixed-
point). configurations (other than those mentioned above) have a very special
structure. Specifically, they have a “spatially” periodic structure with a
period that is quadratic in the radius $r$. In the course of the proof of this
result, we introduce several notions and prove several claims, which we
believe are of interest in their own right as they shed light on the dynamics
of the majority rule in cellular automata (and not only on the configurations
they converge to).

###  1.1 The majority rule with radius $r$

In all that follows, when performing operations on cells
$i\in{\mathbb{Z}_{n}}$, these operations are modulo $n$.

######  Definition 1 (cell interval).

For a pair of 1.1s $i,j\in{\mathbb{Z}_{n}}$ we use $[i,j]$ to denote the
sequence $i,i+1,\dots,j$ (so that it is possible that $j<i$), which we refer
to as a  (cell interval)..

For an integer $n$, we refer to a function
$\sigma:{\mathbb{Z}_{n}}\to\\{0,1\\}$ as a _configuration_ and view $\sigma$
as a (cyclic) binary string of length $n$.

######  Definition 2 (neighborhood).

For a 1.1 $i\in{\mathbb{Z}_{n}}$ and an integer $r$, the $r$- (neighborhood).
of $i$, denoted $\Gamma_{r}(i)$, is the  (cell interval). $[i-r,i+r]$. For a
set of 1.1s $I\subseteq{\mathbb{Z}_{n}}$, we let $\Gamma_{r}(I)$ denote the
set of 1.1s in the union of  (cell interval).s $[i-r,i+r]$ taken over all
$i\in I$.

Given a 1 $\beta\in\left\\{0,1\right\\}$, a configuration
$\sigma:{\mathbb{Z}_{n}}\to\\{0,1\\}$ and a  (cell interval). $[i,j]$, we
denote by $\\#_{\beta}(\sigma[i,j])$ the number of 1.1s $\ell\in[i,j]$ such
that $\sigma(\ell)=\beta$.

######  Definition 3 (the majority rule).

Denote by ${\textrm{MAJ}}_{r}$ (the majority rule). with radius $r$. That is,
for a configuration $\sigma:{\mathbb{Z}_{n}}\to\\{0,1\\}$,
${\textrm{MAJ}}_{r}(\sigma)$ is the configuration $\sigma^{\prime}$ in which
for each 1.1 $i\in{\mathbb{Z}_{n}}$,

$\displaystyle\sigma^{\prime}(i)=\begin{cases}0&\text{if
}\\#_{0}(\sigma[\Gamma_{r}(i)])>\\#_{1}(\sigma[\Gamma_{r}(i)])\\\
1&\text{otherwise}\end{cases}$

For each $t\geq 0$, denote by ${\textrm{MAJ}}_{r}^{t}(\sigma)$ the result of
repeatedly applying the majority rule with radius $r$, starting from the
configuration $\sigma$. In particular, ${\textrm{MAJ}}_{r}^{0}(\sigma)=\sigma$
and ${\textrm{MAJ}}_{r}^{1}(\sigma)={\textrm{MAJ}}_{r}(\sigma)$.

###  1.2 Temporal and spatial periodicity

Eventually, for every initial configuration, the majority rule, and, in fact,
any rule, reaches a _cycle_ : a periodic sequence of configurations. As
mentioned earlier, in the case of the majority rule, that cycle is always
either a _(2-cycle)._ or a _(fixed-point)._.

######  Definition 4 (fixed-point).

We say that a configuration $\sigma:{\mathbb{Z}_{n}}\to\\{0,1\\}$ is a
(fixed-point). if ${\textrm{MAJ}}_{r}(\sigma)=\sigma$.

######  Definition 5 (2-cycle).

We say that a pair of distinct configurations
$\sigma,\sigma^{\prime}:{\mathbb{Z}_{n}}\to\\{0,1\\}$ is a  (2-cycle). if
${\textrm{MAJ}}_{r}(\sigma)=\sigma^{\prime}$ and
${\textrm{MAJ}}_{r}(\sigma^{\prime})=\sigma$.

We refer to the _configurations_ that constitute a cycle as  (temporally
periodic). configurations. That is,

######  Definition 6 (temporally periodic).

We say that a configuration $\sigma:{\mathbb{Z}_{n}}\to\\{0,1\\}$ is
(temporally periodic). if ${\textrm{MAJ}}_{r}^{2}(\sigma)=\sigma$.

Note that if a configuration $\sigma$ is  (temporally periodic)., then it is
either the case that ${\textrm{MAJ}}_{r}(\sigma)=\sigma$ (i.e., $\sigma$ is a
(fixed-point).), or ${\textrm{MAJ}}_{r}(\sigma)=\sigma^{\prime}$ for
$\sigma^{\prime}\neq\sigma$, in which case $\sigma$ and $\sigma^{\prime}$
constitute a  (2-cycle)..

######  Definition 7 (transient).

If a configuration $\sigma:{\mathbb{Z}_{n}}\to\\{0,1\\}$ is not  (temporally
periodic)., we say that $\sigma$ is  (transient)..

Definitions 4-7 are all related to the notion of _temporal_ periodicity, i.e.,
periodicity that occurs over time. In this paper, we relate temporal
periodicity to _spatial_ periodicity, i.e., periodic behavior exhibited within
individual configurations. Formally,

######  Definition 8 (spatial period).

We say that a configuration $\sigma:{\mathbb{Z}_{n}}\to\\{0,1\\}$ has
(spatial period). $p$ if $p$ is the minimum positive integer such that for
every 1.1 $i\in{\mathbb{Z}_{n}}$, $\sigma(i+p)=\sigma(i).$

######  Definition 9 (spatially periodic).

We say that a configuration $\sigma:{\mathbb{Z}_{n}}\to\\{0,1\\}$ is
(spatially periodic). if its  (spatial period). $p$ satisfies $p<n$.

###  1.3 Our main result and the notion of 1.1 stability

In this section we state our main result, Theorem 1. In order to state Theorem
1, we introduce the notion of a 1.1’s stability within a configuration via
Definitions 10-12.

######  Definition 10 (unstable).

We say that a 1.1 $i\in{\mathbb{Z}_{n}}$ is  (unstable). with respect to a
configuration $\sigma:{\mathbb{Z}_{n}}\to\\{0,1\\}$ if
$\sigma(i)\neq\sigma^{\prime\prime}(i)$ where
$\sigma^{\prime\prime}={\textrm{MAJ}}_{r}^{2}(\sigma)$.

Recall that after a finite number of steps222Which we later show to be at most
linear in $n$., a one-dimensional cellular automaton that evolves according to
the majority rule, reaches either a  (fixed-point). or a  (2-cycle).. Thus, a
configuration $\sigma:{\mathbb{Z}_{n}}\to\\{0,1\\}$ is  (transient). if and
only if it contains  (unstable). 1.1s.

As for the “stable” 1.1s, we define two variants:  (strongly stable). and
(weakly stable)..

######  Definition 11 (strongly stable).

We say that a 1.1 $i\in{\mathbb{Z}_{n}}$ is  (strongly stable). with respect
to a configuration $\sigma:{\mathbb{Z}_{n}}\to\\{0,1\\}$ if there exists a
(cell interval). $[a,b]$ of length at least $r+1$ such that $i\in[a,b]$ and
for each $j\in[a,b]$, $\sigma(i)=\sigma(j)$.

######  Definition 12 (weakly stable).

We say that a 1.1 $i\in{\mathbb{Z}_{n}}$ is  (weakly stable). with respect to
a configuration $\sigma:{\mathbb{Z}_{n}}\to\\{0,1\\}$ if $i$ is not  (strongly
stable). with respect to $\sigma$, but $\sigma(i)=\sigma^{\prime\prime}(i)$
where $\sigma^{\prime\prime}={\textrm{MAJ}}_{r}^{2}(\sigma)$.

The crucial property of the  (strongly stable). 1.1s is that their 1s, unlike
the 1s of the  (weakly stable). 1.1s, cannot change in later configurations.
In that sense, their stability is “stronger” than that of the  (weakly
stable). 1.1s. It is worth noting, though, that if a 1.1 lies within a long
(cell interval). of  (weakly stable). 1.1s, then that 1.1 remains  (weakly
stable)., alternating between the same pair of 1s, for a number of steps that
depends on the  (cell interval). length.

Accordingly, given a configuration $\sigma:{\mathbb{Z}_{n}}\to\\{0,1\\}$, we
say that a  (cell interval). $[i,j]$ is  (strongly stable).,  (weakly stable).
or  (unstable). if all the 1.1s in that  (cell interval). are, respectively,
(strongly stable).,  (weakly stable). or  (unstable)..

Considering complete configurations, observe that all the configurations of
the form $(0^{r}0^{*}+1^{r}1^{*})^{*}$ contain only  (strongly stable). 1.1s.
As noted previously and explained in the characterization provided in [TA04],
these configurations are always  (fixed-point).s, which means that they are,
in particular, also  (temporally periodic). (with a period of 1). However,
there are more forms of  (temporally periodic). configurations, both period-1
and period-2, that contain only  (weakly stable). 1.1s and are not addressed
by [TA04]’s characterization, as the authors of [TA04] were only interested in
“typical” configurations, which are not of that kind.333 Indeed, it is shown
in [TA04] that the probability that a randomly selected configuration of
length $n$ being  (transient). approaches 1 as $n\longrightarrow\infty$. As
such, the additional  (temporally periodic). configurations that we address in
this work are, in a sense, not “typical”. We, in contrast to [TA04], make no
assumption about the distribution of the configuration space, and are
therefore interested in understanding the structure of _all_ configurations,
not only the “typical” ones.

Theorem 1 complements [TA04]’s characterization by additionally specifying the
structure of the remaining  (temporally periodic). configurations. In addition
to  (temporally periodic). configurations, Theorem 1 also includes a property
of the  (transient). configurations that is related to the dynamics by which
they eventually converge.

######  Theorem 1.

For any configuration $\sigma:{\mathbb{Z}_{n}}\to\\{0,1\\}$, exactly one of
the following must hold:

  1. 1.

The configuration $\sigma$ is a  (temporally periodic). configuration and it
is either the case that:

    1. (a)

all the 1.1s in $\sigma$ are  (strongly stable)., in which case $\sigma$ is of
the form $(0^{r+1}0^{*}+1^{r+1}1^{*})^{*}$), or

    2. (b)

all the 1.1s in $\sigma$ are  (weakly stable)., in which case $\sigma$ is
(spatially periodic). with  (spatial period). at most $2r(r+1)$.

  2. 2.

The configuration $\sigma$ is a  (transient). configuration and the length of
every  (unstable). (cell interval). in $\sigma$ is at most $2r$.

Under the assumption that $r$ is a constant, Theorem 1 directly yields an
output-sensitive algorithm that, given $n$, generates all the  (temporally
periodic). configurations of length $n$. The running-time of the algorithm is
linear in the number of  (temporally periodic). configurations.

Turning to  (transient). configurations, recall that all  (transient).
configurations contain  (unstable). 1.1s, and the evolution of the
(transient). configurations can be described using the notion of 1.1
stability. Namely, the following is shown regarding any  (transient).
configuration $\sigma:{\mathbb{Z}_{n}}\to\\{0,1\\}$. First, the configuration
${\textrm{MAJ}}_{r}(\sigma)$ contains strictly fewer  (unstable). 1.1s than
$\sigma$. Second, if $\sigma$ contains  (strongly stable). 1.1s, then
${\textrm{MAJ}}_{r}(\sigma)$ contains even more  (strongly stable). 1.1s than
$\sigma$, and the automaton eventually converges to a  (fixed-point). of the
form defined in Case (1a). Third, if there are no  (strongly stable). 1.1s in
$\sigma$, then there are cases in which the automaton eventually converges to
a  (fixed-point). of the form defined in Case (1a)444 e.g., for $r=3$, the
(transient). configuration $001001001001001001$ converges after one step to
the  (fixed-point). configuration $(0)^{*}$.  and there are also cases in
which it eventually converges to a  (fixed-point). or to a  (2-cycle). of the
form defined in Case (1b)555 e.g., for $r=4$, the  (transient). configuration
$001011001011001011001011001011001011$ converges after one step to the
(2-cycle). consisting of $(111000)^{6}$ and $(000111)^{6}$. .

###  1.4 Illustrating Theorem 1 for $r=1,2,3$

To get a feel for the nature of the statement in Theorem 1, we demonstrate
some of its aspects for $r=1,2,3$.

  1. 1.

For $r=1$, the  (temporally periodic). configurations are either

    1. (a)

of the form $(000^{*}+111^{*})^{*}$, or

    2. (b)

of the form $(01)^{*}$.666Also $(10)^{*}$, but since the configurations are
cyclic, the patterns $(01)^{*}$ and $(10)^{*}$ correspond to equivalent sets
of configurations.

  2. 2.

For $r=2$, the  (temporally periodic). configurations are either

    1. (a)

of the form $(0000^{*}+1111^{*})^{*}$, or

    2. (b)

of one of the following forms: $(01)^{*}$, $(0011)^{*}$, $(001101)^{*}$,
$(001011)^{*}$.

  3. 3.

For $r=3$, the  (temporally periodic). configurations are either

    1. (a)

of the form $(00000^{*}+11111^{*})^{*}$, or

    2. (b)

of the form $(s)^{*}$, where777 The string $s$ could also be the _mirror_ or
the _complement_ of any of the specified patterns, which we omit for the sake
of conciseness. For example, since we explicitly specified that $s$ could be
$010011$, it means that $s$ could also be $110010$ (which is the mirror of
$010011$) or $101100$ (which is the complement of $010011$), even though these
two are not explicitly specified.

$\displaystyle s\in\left\\{\begin{array}[]{lr}01,\\\ 0011,\\\
010011,010110,001110,\\\
01011001,10100101,10100110,01011100,10010011,00011101,10110001,\\\
0011001110,1000111001\end{array}\right\\}$

###  1.5 Minority

An analog of Theorem 1 holds for the minority rule as well, with exactly the
same variants of 1.1 stability as those of the majority rule. In particular,
Definitions 10-12 can be used verbatim to describe the evolution according to
the minority rule, with the only difference being the _temporal period_ of the
(weakly stable). and the  (strongly stable). 1.1s.

Namely, in the minority rule, the  (strongly stable). 1.1s have a temporal
period of 2 instead of 1, implying that the  (temporally periodic).
configurations of the form defined in Case (1a) of Theorem 1, rather than
being  (fixed-point).s as in the majority rule, become the constituents of
(2-cycle).s. Likewise, for every configuration, the  (weakly stable). 1.1s
that would have had a temporal period of 1 under the majority rule, have a
temporal period of 2 under the minority rule, and vice versa. This implies
that the  (temporally periodic). configurations of the form defined in Case
(1b) of Theorem 1, while generated by exactly the same patterns, and hence
having precisely the same form, have the _opposite_ temporal period to that
they would have had under the majority rule: the  (fixed-point).s become
(2-cycle).s and the  (2-cycle).s become  (fixed-point).s.

See illustrations in Figures 1.3 and 1.3.

Figure 1.1: Majority ($r=2$)

Figure 1.2: Minority ($r=2$)

Figure 1.3:  Figures 1.3 and 1.3 depict the evolution under the majority rule
(Figure 1.3) and under the minority rule (Figure 1.3) starting from the same
initial configuration. Gray squares correspond to 1-0 1.1s and dark squares
correspond to 1-1 1.1s. Each 1.1 is labeled by a letter indicating the 1.1’s
_stability_ , where _S_ stands for _Strongly_ stable, _W_ for _Weakly_ stable
and _U_ for _Unstable_. While the two trajectories appear quite different,
they are completely equivalent when viewed under the “stability mask”. In
particular, 1.1 $i$ at time $t$ has the same stability label in both figures
for every $t,i$ pair. Yet, each pair of corresponding stable 1.1s in the two
figures have _opposite_ periods. Thus, the  (fixed-point). configuration to
which the majority rule in Figure 1.3 converges to corresponds to a
(2-cycle). in Figure 1.3.

###  1.6 Related work

The main focus of most of the research on majority/minority (and more
generally, threshold) cellular automata so far has been on the convergence
time (e.g., [FGW83, FKW13, PW19]) and on the dominance problem888In the
dominance problem, one asks how many 1.1s must initially be at a certain 1 so
that eventually all 1.1s have the same 1. (e.g., [BBDCM12, FKR+03, MPGP17]).

As mentioned earlier, most of the work on the problem of understanding the
structure of the configuration space is based on the assumption that the
initial configuration is random. For the one-dimensional case, the case with
which the current paper is concerned, this includes the paper of Tosic and
Agha [TA04]. In their paper, they distinguish between synchronous/sequential
and finite/infinite majority cellular automata with radius $r$, and our work
can be viewed as extending their result for the finite and synchronous case.

They show that whereas  (2-cycle).s cannot emerge under the sequential model,
in the synchronous model (the one we focus on in this paper),  (2-cycle).s
exist even for $r=1$. They also show that a randomly picked configuration is a
(transient). configuration (and, in particular, not a  (2-cycle).) with
probability approaching 1 (both for finite and infinite configurations), and
it can additionally be shown that the probability that such a random
(transient). configuration eventually converges to a  (2-cycle). approaches 0.
Finally, they characterize the “common” forms of  (fixed-point).
configurations (those that in our paper are described in Case (1a) of Theorem
1).

Their theoretical result is supplemented by a later experimental work [TR11],
showing that in practice, convergence to these “common”  (fixed-point).
configurations occurs relatively quickly. Namely, the simulations in [TR11]
demonstrate that convergence tends to occur in less than five steps for
$n=1000$ and $1\leq r\leq 5$.

Additional work beyond the one-dimensional case includes [GZ21] for two-
dimensional majority cellular automata, [GZ18] for majority in random regular
graphs, [Zeh20] for majority in Erdos–Rényi random graphs as well as expander
graphs.

One notable work that does not rely on the assumption that the initial
configuration is random is Turau’s work [Tur22] on characterizing all the
(temporally periodic). configurations for majority and minority processes on
trees. The characterization presented in [Tur22] also yields an output-
sensitive algorithm for generating these configurations.

###  1.7 Some high-level ideas

As mentioned previously, in proving Theorem 1, we define a number of notions
and establish several claims, some of which we believe are valuable in and of
themselves. In this section we have chosen to highlight the high-level idea
behind one of the key tools we utilize, which is a _mapping_ we introduce
between _1.7 s_ of consecutive configurations. Given a configuration
$\sigma:{\mathbb{Z}_{n}}\to\\{0,1\\}$, we say that a  (cell interval). $[i,j]$
is a _maximal homogeneous block_ in $\sigma$ with value $\beta\in\\{0,1\\}$ if
for every 1.1 $\ell\in[i,j]$, $\sigma(\ell)=\beta$, and also
$\sigma(i-1)=\sigma(j+1)\neq\beta$ if the length of $[i,j]$ is less than $n$.

We refer to this mapping, defined below, as the  (alignment mapping).. The
(alignment mapping)., beyond being essential for the proof of Theorem 1, has
several nice features that make it useful for reasoning about the dynamics of
the majority rule, which is why we present its definition here.

######  Definition 13 (alignment mapping).

Let $\sigma$ and $\sigma^{\prime}$ be a pair of configurations satisfying
${\textrm{MAJ}}_{r}(\sigma)=\sigma^{\prime}$. Given a 1.7 $[i,j]$ in
$\sigma^{\prime}$, let $I$ be the 1.7 in $\sigma$ that contains the 1.1 $i+r$
and let $J$ be the 1.7 in $\sigma$ that contains the 1.1 $j-r$. The
(alignment mapping). maps the 1.7 $[i,j]$ (in $\sigma^{\prime}$) to the
_middle_ 1.7 between $I$ and $J$ in $\sigma$ (where the middle is well
defined, as it is shown later that the number of 1.7s between $I$ and $J$ must
be odd).

We stress that the  (alignment mapping)., also defined using different terms
in Definition 23, is a _backward_ mapping, in the sense that, given a
configuration $\sigma^{\prime}$, it maps all 1.7s in $\sigma^{\prime}$ into
those of the configuration $\sigma$ that _precedes_ $\sigma^{\prime}$. This
naturally suggests defining the notion of _the forward (alignment mapping)._
as the _inverse_ function of the backward  (alignment mapping). that would map
the 1.7s of the configuration $\sigma$ to those of the configuration
$\sigma^{\prime}$ that _follows_ $\sigma$.

However, while it can be shown that the backward  (alignment mapping). is
always one-to-one, it is not necessarily _onto_ (unless we apply it within a
pair of  (temporally periodic). configurations). Hence, under our definition
of the forward  (alignment mapping)., not all blocks will be mapped forward.

Formally, let $\sigma_{0},...\sigma_{m}$ be a sequence of configurations where
${\textrm{MAJ}}_{r}(\sigma_{t-1})=\sigma_{t}$ for each $1\leq t\leq m$. We
define the step-$t$ _forward (alignment mapping)._, denoted $\varphi_{t}$, as
follows. Given a 1.7 $[i,j]$ in $\sigma_{t}$, if there is a 1.7
$[i^{\prime},j^{\prime}]$ in $\sigma_{t+1}$ such that the backward  (alignment
mapping). between the configuration pair $\sigma_{t},\sigma_{t+1}$ maps
$[i^{\prime},j^{\prime}]$ into $[i,j]$, then
$\varphi_{t}([i,j])=[i^{\prime},j^{\prime}]$. Otherwise,
$\varphi_{t}([i,j])=\bot$. In the case in which $\varphi_{t}([i,j])\neq\bot$,
we also define $\varphi_{t}^{2}([i,j])$ as
$\varphi_{t+1}(\varphi_{t}([i,j]))$.

One notable property of the forward  (alignment mapping). is what we refer to
as “identity preservation in stable intervals”. Roughly speaking, consider any
1.7 $[i,j]$ residing in a sufficiently long  (weakly stable). or  (strongly
stable). (cell interval). of $\sigma_{t}$. Then $\varphi([i,j])\neq\bot$, and
hence $\varphi_{t}^{2}([i,j])$ is defined and is equal to the same 1.7 $[i,j]$
we started with. In particular, for a pair of configurations comprising a
(2-cycle)., applying the forward  (alignment mapping). _twice_ essentially
maps each 1.7 to itself.

In the proof of Theorem 1, we essentially use the forward  (alignment
mapping). and its properties to show that for a configuration in which all
1.7s are of length at most $r$, if the configuration is  (temporally
periodic)., then it is also  (spatially periodic).. We achieve this through
three steps.

In the first step, we employ the  (alignment mapping). to express the length
of each of the configuration’s 1.7s in terms of the lengths of other $O(r)$
1.7s in the preceding configuration. Specifically, given a pair of
(temporally periodic). configurations $\sigma_{t}$ and $\sigma_{t+1}$, we
obtain a relationship between the length of each 1.7 $[i,j]$ in $\sigma_{t}$
and the lengths of $O(r)$ consecutive 1.7s, belonging to a sequence centered
at the 1.7 $\varphi_{t}([i,j])$, in $\sigma_{t+1}$.

In the second step, we look at the _difference_ between the length of each 1.7
$[i,j]$ and the lengths of the 1.7s at the edges of the sequence mentioned
above, and define _difference vectors_ whose entries are these differences. We
use the properties of the forward  (alignment mapping). to establish that the
difference vectors (defined formally later) are  (spatially periodic). with a
(spatial period). that is _linear_ in $r$.

In the third and final step, by applying the relationship between aligned
difference vectors iteratively, we use their spatial periodicity to establish
that the configurations themselves are  (spatially periodic). as well, and
that each configuration’s  (spatial period). must be quadratic in $r$.

##  2  (Switch point).s

######  Definition 14 (Switch point).

Let $\sigma$ be a configuration. We say that a pair of consecutive 1.1s
$i,i+1$ constitute a  (Switch point). in $\sigma$ if
$\sigma(i)\neq\sigma(i+1)$.

We now prove two properties of  (Switch point).s, the first of which we refer
to as  (The Switch Point Argument)..

######  Claim 1 (The Switch Point Argument).

Let $\sigma$ and $\sigma^{\prime}$ be a pair of configurations satisfying
${\textrm{MAJ}}_{r}(\sigma)=\sigma^{\prime}$. If a pair of consecutive 1.1s
$i,i+1$ constitutes a  (Switch point). in $\sigma^{\prime}$, then
$\sigma(i-r)=\sigma^{\prime}(i)$ and $\sigma(i+1+r)=\sigma^{\prime}(i+1)$.

###### Proof.

We only prove that $\sigma(i-r)=\sigma^{\prime}(i)$, since the proof that
$\sigma(i+1+r)=\sigma^{\prime}(i+1)$ is symmetric.

Suppose $\sigma^{\prime}(i+1)=\beta$ for some $\beta\in\left\\{0,1\right\\}$.
Since the pair $i,i+1$ constitutes a  (Switch point). in $\sigma^{\prime}$, it
must be the case that $\sigma^{\prime}(i)=\bar{\beta}$. Assume, contrary to
the claim, that $\sigma(i-r)=\beta$. Since
$\Gamma_{r}(i+1)=\Gamma_{r}(i)\cup\left\\{i+1+r\right\\}\setminus\left\\{i-r\right\\}$
and $\sigma(i-r)=\beta$, it must hold that

$\displaystyle\\#_{\beta}(\sigma[\Gamma_{r}(i+1)])\leq\\#_{\beta}(\sigma[\Gamma_{r}(i)]).$

This implies that, by the definition of ${\textrm{MAJ}}_{r}$, since
$\sigma^{\prime}(i+1)=\beta$, it must also hold that
$\sigma^{\prime}(i)=\beta$, and we reach a contradiction. ∎

######  Claim 2.

Let $\sigma$ and $\sigma^{\prime}$ be a pair of configurations where
${\textrm{MAJ}}_{r}(\sigma)=\sigma^{\prime}$. If a pair of consecutive 1.1s
$i,i+1$ constitutes a  (Switch point). in $\sigma^{\prime}$, then

$\displaystyle\\#_{0}(\sigma[\Gamma_{r}(i)\cap\Gamma_{r}(i+1)])=\\#_{1}(\sigma[\Gamma_{r}(i)\cap\Gamma_{r}(i+1)]).$

###### Proof.

Assume the contrary, and let $\beta\in\left\\{0,1\right\\}$ be the majority
value in $\sigma[\Gamma_{r}(i)\cap\Gamma_{r}(i+1)]$. That is,

$\displaystyle\\#_{\beta}(\sigma[\Gamma_{r}(i)\cap\Gamma_{r}(i+1)])>\\#_{\bar{\beta}}(\sigma[\Gamma_{r}(i)\cap\Gamma_{r}(i+1)]).$

Hence, since $|\Gamma_{r}(i)\cap\Gamma_{r}(i+1)|=|[i-r+1,i+r]|=2r$,

$\displaystyle\\#_{\beta}(\sigma[\Gamma_{r}(i)\cap\Gamma_{r}(i+1)])\geq r+1.$

Thus, since $\Gamma_{r}(i)\cap\Gamma_{r}(i+1)\subseteq\Gamma_{r}(i)$ and
$\Gamma_{r}(i+1)\cap\Gamma_{r}(i)\subseteq\Gamma_{r}(i+1)$,

$\displaystyle\\#_{\beta}(\Gamma_{r}(i))\geq\\#_{\beta}(\sigma[\Gamma_{r}(i)\cap\Gamma_{r}(i+1)])\geq
r+1$

and

$\displaystyle\\#_{\beta}(\Gamma_{r}(i+1))\geq\\#_{\beta}(\sigma[\Gamma_{r}(i)\cap\Gamma_{r}(i+1)])\geq
r+1.$

Therefore, by the definition of ${\textrm{MAJ}}_{r}$,
$\sigma(i)=\sigma(i+1)=\beta$ and we reach a contradiction to the assumption
that the pair $i,i+1$ is a  (Switch point).. ∎

The two properties of  (Switch point).s captured by 1 and 2 together
correspond, in fact, to a characterization of  (Switch point).s, as formalized
in 3.

######  Claim 3.

Let $\sigma$ and $\sigma^{\prime}$ be a pair of configurations where
${\textrm{MAJ}}_{r}(\sigma)=\sigma^{\prime}$. If for a 1.1
$i\in{\mathbb{Z}_{n}}$,
$\\#_{0}(\sigma[\Gamma_{r}(i)\cap\Gamma_{r}(i+1)])=\\#_{1}(\sigma[\Gamma_{r}(i)\cap\Gamma_{r}(i+1)])$
and $\sigma(i-r)\neq\sigma(i+1+r)$, then the pair $i,i+1$ constitutes a
(Switch point). in $\sigma^{\prime}$ in which $\sigma^{\prime}(i)=\sigma(i-r)$
and $\sigma^{\prime}(i+1)=\sigma(i+1+r)$.

###### Proof.

Let $\beta\in\left\\{0,1\right\\}$ be the value that $\sigma(i-r)=\beta$ and
$\sigma(i+1+r)=\bar{\beta}$. Since
$|\Gamma_{r}(i)\cap\Gamma_{r}(i+1)|=|[i-r+1,i+r]|=2r$,

$\displaystyle\\#_{\beta}(\sigma[\Gamma_{r}(i)\cap\Gamma_{r}(i+1)])=r.$

Hence, since
$\Gamma_{r}(i)=(\Gamma_{r}(i)\cap\Gamma_{r}(i+1))\cup\left\\{i-r\right\\}$, it
must be the case that $\\#_{\beta}(\Gamma_{r}(i))=r+1$. Similarly, since
$\Gamma_{r}(i+1)=(\Gamma_{r}(i)\cap\Gamma_{r}(i+1))\cup\left\\{i+1+r\right\\}$,
it must be the case that $\\#_{\bar{\beta}}(\Gamma_{r}(i+1))=r+1$. Hence, by
the definition of ${\textrm{MAJ}}_{r}$,
$\sigma^{\prime}(i)=\beta,\sigma^{\prime}(i+1)=\bar{\beta}$ and the pair
$i,i+1$ constitutes a  (Switch point). in $\sigma^{\prime}$. ∎

##  3 On the lengths of maximal homogeneous blocks

######  Definition 15 (balanced).

We say that a configuration $\sigma$ is  (balanced). if
$\\#_{0}(\sigma)=\\#_{1}(\sigma)$. Similarly, we say that an interval $[i,j]$
is  (balanced). in the configuration $\sigma$ if
$\\#_{0}(\sigma[i,j])=\\#_{1}(\sigma[i,j])$.

######  Definition 16 (bias).

Given a configuration $\sigma$, we define its  (bias). as
$\\#_{0}(\sigma)-\\#_{1}(\sigma)$. Similarly, given an interval $[i,j]$, we
define its  (bias). in $\sigma$ as
$\\#_{0}(\sigma[i,j])-\\#_{1}(\sigma[i,j])$.

That is, a  (balanced). configuration is a configuration whose  (bias). is 0.
Similarly, an interval is  (balanced). in a configuration if its  (bias). is 0
in that configuration.

######  Claim 4.

Let $\sigma$ and $\sigma^{\prime}$ be a pair of configurations where
${\textrm{MAJ}}_{r}(\sigma)=\sigma^{\prime}$ and let $[i,j]\in
B^{\beta}(\sigma^{\prime})$ for some $\beta\in\left\\{0,1\right\\}$. If
$|[i,j]|\leq 2r+1$, then:999 In 4 and throughout its proof, we’re using the
assumption that $|[i,j]|\leq 2r+1$ whenever we refer to the interval
$[j-r,i+r]$ or the interval $[j-r+1,i+r-1]$.

$\displaystyle|[i,j]|=\\#_{\beta}(\sigma[i-r,j+r])-\\#_{\bar{\beta}}(\sigma[j-r,i+r]).$

###### Proof.

By the definition of $B^{\beta}$, the interval $[i,j]$ is a maximal
homogeneous block in $\sigma^{\prime}$. Also, $|[i,j]|\leq 2r+1<n$. Hence, the
pair $(i-1,i)$ is a  (Switch point). in $\sigma^{\prime}$. Therefore, by 2,
the interval $[i-r,i+r-1]$ is  (balanced). in $\sigma$. Similarly, since the
pair $(j,j+1)$ is also a  (Switch point). in $\sigma^{\prime}$, again, by 2,
the interval $[j-r+1,j+r]$ is  (balanced). in $\sigma$.

We claim that the intervals $[i-r,j-r]$ and $[i+r,j+r]$ have the same  (bias).
in $\sigma$. To see why, first observe that

$\displaystyle[i-r,j-r]=[i-r,i+r-1]\setminus[j-r+1,i+r-1],$ (3.1)
$\displaystyle[i+r,j+r]=[j-r+1,j+r]\setminus[j-r+1,i+r-1]..$ (3.2)

Since $|[i-r,i+r-1]|=|[j-r+1,j+r]|=2r$ and both $[i-r,i+r-1]$ and
$[j-r+1,j+r]$ are  (balanced). in $\sigma$, by equations (3.1) and (3.2), the
intervals $[i-r,j-r]$ and $[i+r,j+r]$ must have the same  (bias). in $\sigma$.
The reason is that each of $[i-r,j-r]$ and $[i+r,j+r]$ equal the difference
between a  (balanced). interval of length $2r$ and the common sub-interval
$[j-r+1,i+r-1]$.

Hence, since $|[i-r,j-r]|=|[i+r,j+r]|$,

$\displaystyle\\#_{0}(\sigma[i+r,j+r])=\\#_{0}(\sigma[i-r,j-r])\text{ and}$
(3.3) $\displaystyle\\#_{1}(\sigma[i+r,j+r])=\\#_{1}(\sigma[i-r,j-r]).$ (3.4)

Since $[j-r+1,j+r]=[j-r+1,i+r-1]\cup[i+r,j+r]$ and $[j-r+1,j+r]$ is
(balanced)., it must hold that

$\displaystyle\\#_{0}(\sigma[j-r+1,i+r-1])+\\#_{0}(\sigma[i+r,j+r])=$
$\displaystyle\\#_{1}(\sigma[j-r+1,i+r-1])+\\#_{1}(\sigma[i+r,j+r]).$

Hence,

$\displaystyle\begin{split}\\#_{\bar{\beta}}&(\sigma[i+r,j+r])=\\\
&\\#_{\beta}(\sigma[j-r+1,i+r-1])+\\#_{\beta}(\sigma[i+r,j+r])-\\#_{\bar{\beta}}(\sigma[j-r+1,i+r-1]).\end{split}$
(3.5)

By Equation (3.5), something.

$\displaystyle|[i,j]|$ $\displaystyle=|[i-r,j-r]|$ (3.6)
$\displaystyle=\\#_{0}(\sigma[i-r,j-r])+\\#_{1}(\sigma[i-r,j-r])$ (3.7)
$\displaystyle=\\#_{\beta}(\sigma[i-r,j-r])+\\#_{\bar{\beta}}(\sigma[i+r,j+r])$
(3.8) $\displaystyle\begin{split}&=\\#_{\beta}(\sigma[i-r,j-r])\\\
&\;\;\;\;+\\#_{\beta}(\sigma[j-r+1,i+r-1])\\\
&\;\;\;\;+\\#_{\beta}(\sigma[i+r,j+r])\\\
&\;\;\;\;-\\#_{\bar{\beta}}(\sigma[j-r+1,i+r-1])\end{split}$ (3.9)
$\displaystyle=\\#_{\beta}(\sigma[i-r,j+r])-\\#_{\bar{\beta}}(\sigma[j-r+1,i+r-1])$
(3.10)
$\displaystyle=\\#_{\beta}(\sigma[i-r,j+r])-\\#_{\bar{\beta}}(\sigma[j-r,i+r]),$
(3.11)

as claimed, where:

  * –

(3.8) follows from applying equations (3.3) and (3.4).

  * –

(3.9) follows from applying equation (3.5).

  * –

(3.10) follows from the fact that

$\displaystyle[i-r,j-r]\cup[j-r+1,i+r-1]\cup[i+r,j+r]=[i-r,j+r].$

  * –

(3.11) follows from the observation that, by  (The Switch Point Argument).,
since the pair $(i,i-1)$ is a  (Switch point). in $\sigma^{\prime}$,
$\sigma(i+r)=\sigma^{\prime}(i)=\beta$, and, similarly, since the pair
$(j,j+1)$ is a  (Switch point). in $\sigma^{\prime}$,
$\sigma(j-r)=\sigma^{\prime}(j)=\beta$ as well. Hence,
$\\#_{\bar{\beta}}(\sigma[j-r+1,i+r-1])=\\#_{\bar{\beta}}(\sigma[j-r,i+r])$.

∎

##  4 Temporally periodic configurations

######  Definition 17.

Given a configuration $\sigma$ and a value $\beta\in\left\\{0,1\right\\}$, we
denote by $B^{\beta}(\sigma)$ the set of maximal homogeneous blocks with value
$\beta$ in $\sigma$. That is,

$B^{\beta}(\sigma)=\left\\{[i,j]|\forall
k\in[i,j],\sigma(k)=\beta,\sigma(i-1)=\sigma(j+1)=1-\beta\right\\}.$

Also, let $B(\sigma)=B^{0}(\sigma)\cup B^{1}(\sigma)$ and let
$b(\sigma)=|B(\sigma)|$.

In [GO81], it has been shown that a more general class of cellular automata
that includes ${\textrm{MAJ}}_{r}$, always reach a cycle of temporal period 1
or 2. Nevertheless, we provide a proof tailored for our special case,
${\textrm{MAJ}}_{r}$, because it is simpler and shorter than the general proof
in [GO81].

######  Claim 5.

For every integer $r\leq 1$, the rule ${\textrm{MAJ}}_{r}$ has temporal period
$2$.

###### Proof.

We define a potential function
$\phi:\left\\{0,1\right\\}^{n}\times\left\\{0,1\right\\}^{n}\rightarrow\mathbb{Z}$
over pairs of consecutive configurations of a cellular automaton ${\rm E}$
that evolves according to ${\textrm{MAJ}}_{r}$ for some radius $r$.

We shall use the following shorthand (where $i+x$ is computed mod $n$):

$\displaystyle g_{t}(i)=\sum_{j=i-r}^{i+r}{\rm E}_{t}(j)\;,$ (4.1)

where we observe that if $g_{t}(i)\geq r+1$, then ${\rm E}_{t+1}(i)=1$, while
if $g_{t}(i)<r+1$, then ${\rm E}_{t+1}(i)=0$.

The potential function is defined as follows.

$\displaystyle\phi({\rm E}_{t},{\rm E}_{t-1})=\sum_{i=0}^{n-1}\left({\rm
E}_{t}(i)\cdot g_{t-1}(i)\right)-(r+1/2)\sum_{i=0}^{n-1}\left({\rm
E}_{t}(i)+{\rm E}_{t-1}(i)\right)\;.$ (4.2)

Observe that

$\displaystyle\sum_{i=0}^{n-1}\left({\rm E}_{t}(i)\cdot
g_{t-1}(i)\right)=\sum_{i=0}^{n-1}\left({\rm E}_{t-1}(i)\cdot
g_{t}(i)\right)\;.$ (4.3)

(It is easiest to see this if we think of pairs ${\rm E}_{t}(i)=1$ and ${\rm
E}_{t-1}(j)=1$ such that $|i-j|\leq r$ as edges.)

Now consider the change in the potential function:

$\displaystyle\phi({\rm E}_{t+1},{\rm E}_{t})-\phi({\rm E}_{t},{\rm E}_{t-1})$
(4.4) $\displaystyle=$ $\displaystyle\sum_{i=0}^{n-1}\left({\rm
E}_{t+1}(i)\cdot g_{t}(i)\right)-(r+1/2)\sum_{i=0}^{n-1}\left({\rm
E}_{t+1}(i)+{\rm E}_{t}(i)\right)$
$\displaystyle\;-\;\left(\sum_{i=0}^{n-1}\left({\rm E}_{t}(i)\cdot
g_{t-1}(i)\right)-(r+1/2)\sum_{i=0}^{n-1}\left({\rm E}_{t}(i)+{\rm
E}_{t-1}(i)\right)\right)$ $\displaystyle=$
$\displaystyle\sum_{i=0}^{n-1}\left(\left({\rm E}_{t+1}(i)\cdot
g_{t}(i)\right)-\left({\rm E}_{t}(i)\cdot
g_{t-1}(i)\right)\right)-(r+1/2)\sum_{i=0}^{n-1}\left({\rm E}_{t+1}(i)-{\rm
E}_{t-1}(i)\right)$ (4.5) $\displaystyle=$
$\displaystyle\sum_{i=0}^{n-1}\left({\rm E}_{t+1}(i)-{\rm
E}_{t-1}(i)\right)\cdot g_{t}(i)-(r+1/2)\sum_{i=0}^{n-1}\left({\rm
E}_{t+1}(i)-{\rm E}_{t-1}(i)\right)$ (4.6) $\displaystyle=$
$\displaystyle\sum_{i=0}^{n-1}\left({\rm E}_{t+1}(i)-{\rm
E}_{t-1}(i)\right)\cdot\left(g_{t}(i)-(r+1/2)\right)$ (4.7) $\displaystyle=$
$\displaystyle\sum_{i:{\rm E}_{t+1}(i)\neq{\rm E}_{t-1}(i)}|g_{t}(i)-(r+1/2)|$
(4.8) $\displaystyle\geq$ $\displaystyle\frac{1}{2}\left|\\{i:{\rm
E}_{t+1}(i)\neq{\rm E}_{t-1}(i)\\}\right|\;.$ (4.9)

That is, the value of $\phi$ is increasing at each step by
$\frac{1}{2}\left|\\{i:{\rm E}_{t+1}(i)\neq{\rm E}_{t-1}(i)\\}\right|\ $, and
since $\phi$ is by definition a bounded function, it must be the case that
there exists an integer $t^{*}$ s.t. for every $t>t^{*}$, $\\{i:{\rm
E}_{t+1}(i)\neq{\rm E}_{t-1}(i)\\}=\emptyset$. Hence, ${\textrm{MAJ}}_{r}$ has
temporal period $2$. ∎

######  Observation 6.

Let $\sigma$ be a configuration and let $[i,j]$ be an interval of 1.1s such
that for every 1.1 $\ell\in[i,j]$, $\sigma(\ell)=\beta$ for some
$\beta\in\left\\{0,1\right\\}$. For an integer $t\geq 0$, let
$\sigma_{t}={\textrm{MAJ}}_{r}^{t}(\sigma)$. If the length of the interval
$[i,j]$ is at least $r+1$, then for every $t\geq 0$ and for every 1.1
$\ell\in[i,j]$, $\sigma_{t}(\ell)=\beta$.

We now make a distinction that partitions the  (temporally periodic).
configurations into two classes:  (strongly stable). configurations and
(weakly stable). configurations.

######  Definition 18 (strongly stable).

We say that a configuration is $\sigma$ is  (strongly stable). if each 1.7 in
$B(\sigma)$ (see Definition 17) is of length at least $r+1$. Equivalently, a
configuration is  (strongly stable). if and only if it is of the form
$(0^{r+1}0^{*}+1^{r+1}1^{*})^{*}$.

######  Observation 7.

If a configuration is  (strongly stable)., then it is also a  (fixed-point)..

######  Observation 8.

Let $\sigma$ be a configuration. If $B(\sigma)$ contains a block of length at
least $r+1$, then there exists an integer $t\geq 0$ such that
${\textrm{MAJ}}_{r}^{t}(\sigma)$ is  (strongly stable)..

######  Definition 19 (weakly stable).

We say that a configuration is $\sigma$ is  (weakly stable). if it is
(temporally periodic). and not  (strongly stable)..

######  Claim 9.

If $\sigma$ is a  (temporally periodic). configuration, then it is either the
case that for every block $[i,j]\in B(\sigma)$, $|[i,j]|\leq r$ or that for
every block $[i,j]\in B(\sigma)$, $|[i,j]|>r$.

###### Proof.

Suppose by way of contradiction that $B(\sigma)$ contains both a block of
length at most $r$ and a block of length at least $r+1$. Then there must be
such a pair of consecutive blocks. Let $[a,b]$ and $[c,d]$ be the these two
consecutive blocks where $[a,b]$ is the block whose length is at most $r$ and
$[c,d]$ is the block whose length is at least $r+1$. Since the two blocks are
adjacent, it is either the case that $c=b+1$ or that $a=d+1$. Suppose without
loss of generality that $c=b+1$. Let $\beta$ be the value of the block
$[a,b]$. Since the block $[c,d]$ adjacent to the block $[a,b]$, the value of
$[c,d]$ must be $\bar{\beta}$.

Since the 1.1 $b$ belongs to $[a,b]$, it must be the case that
$\sigma(b)=\beta$. However, for each 1.1 $i\in[b+1,b+r]$, since $|[c,d]|>r$,
it must be the case that $\sigma(i)=\bar{\beta}$. Also, since $|[a,b]|\leq r$
and $a-1\in[b-r,b]$, it must be the case that $a-1\in\Gamma_{r}(b)$, so
$\left\\{a-1\right\\}\cup[b+1,b+r]\in\Gamma_{r}(b)$. As
$\sigma(a-1)=\bar{\beta}$, it is the case that
$\\#_{\bar{\beta}}(\sigma(\Gamma_{r}(b)))\geq r+1$. Thus,
${\textrm{MAJ}}_{r}(\sigma)(b)=\bar{\beta}$.

Since $|[c,d]|\geq r+1$ and for every 1.1 $\ell\in[c,d]$,
$\sigma(\ell)=\bar{\beta}$, by 6, it is also the case that for every 1.1
$\ell\in[c,d]$, ${\textrm{MAJ}}_{r}(\sigma)(\ell)=\beta$ as well. Now, since
$|[b,d]|\geq r+1$ as well, again, by 6, it must hold that for every 1.1
$\ell\in[b,d]$, ${\textrm{MAJ}}_{r}^{2}(\sigma)(\ell)=\bar{\beta}$ too. In
particular, ${\textrm{MAJ}}_{r}^{2}(\sigma)(b)=\bar{\beta}\neq\sigma(b)$, and
so $\sigma$ cannot be  (temporally periodic). and we reach a contradiction. ∎

######  Corollary 2.

If a configuration $\sigma$ is  (weakly stable)., then for each block
$[i,j]\in B(\sigma)$, $|[i,j]|\leq r$.

######  Definition 20 (temporally periodic configuration pair).

We say that a pair of configurations $\sigma,\sigma^{\prime}$ is a
(temporally periodic configuration pair). if
${\textrm{MAJ}}_{r}(\sigma)=\sigma^{\prime}$ and
${\textrm{MAJ}}_{r}(\sigma^{\prime})={\textrm{MAJ}}_{r}(\sigma)$.

######  Claim 10.

Let $\sigma,\sigma^{\prime}$ be a  (temporally periodic configuration pair)..
For every $[i,j]\in B(\sigma^{\prime})$, each of the intervals $[i-r-1,j-r]$
and $[i+r,j+r+1]$ contains exactly one  (Switch point). in $\sigma$.

###### Proof.

We prove the claim for the interval $[i-r-1,j-r]$, as the proof for the
interval $[i+r,j+r+1]$ is analogous. Let $\beta\in\left\\{0,1\right\\}$ be the
value such that $[i,j]\in B^{\beta}(\sigma^{\prime})$. Since $[i,j]\in
B^{\beta}(\sigma^{\prime})$, each of the pairs $(i-1,i)$ and $(j,j+1)$ is a
(Switch point). in $\sigma^{\prime}$. Since the pair $\sigma,\sigma^{\prime}$
is a  (temporally periodic configuration pair).,
${\textrm{MAJ}}_{r}(\sigma^{\prime})=\sigma$. Hence, by  (The Switch Point
Argument)., it must be the case that $\sigma(i-r-1)=\bar{\beta}$ and
$\sigma(j-r)=\beta$.

Therefore, there must be a 1.1 $\ell\in[i-r-1,j-r]$ such that
$\sigma(\ell)=\bar{\beta}$ and $\sigma(\ell+1)=\beta$. That is, the pair
$\ell,\ell+1$ is a $\sigma$- (Switch point). in the interval $[i-r-1,j-r]$.

It is left to show that the pair $\ell,\ell+1$ is the only $\sigma$- (Switch
point). in the interval $[i-r-1,j-r]$. Suppose by way of contradiction that
this is not the case. Let $\ell^{\prime},\ell^{\prime}+1$ be the $\sigma$-
(Switch point). in $[i-r-1,j-r]$ that is closest to $\ell$. Since
$\ell,\ell+1$ is a  (Switch point). of values $\bar{\beta},\beta$, it must be
the case that $\ell^{\prime},\ell^{\prime}+1$ is a  (Switch point). of values
$\beta,\bar{\beta}$. That is, $\sigma(\ell^{\prime}+1)=\bar{\beta}$. Since the
pair $\sigma,\sigma^{\prime}$ is a  (temporally periodic configuration pair).,
${\textrm{MAJ}}_{r}(\sigma)=\sigma^{\prime}$. Hence, by  (The Switch Point
Argument)., it must be the case that
$\sigma^{\prime}(\ell^{\prime}+1+r)=\bar{\beta}$. However, since
$\ell^{\prime}\in[i-r-1,j-r]$, it follows that $\ell^{\prime}+1\in[i-r,j-r]$,
so $\ell^{\prime}+1+r\in[i,j]$. That is, the conclusion that
$\sigma^{\prime}(\ell^{\prime}+1+r)=\bar{\beta}$ is in contradiction to the
assumption that $[i,j]\in B^{\beta}(\sigma^{\prime})$. ∎

##  5 Block intervals defined by the left and right mappings

######  Definition 21.

Let $B$ be a sequence of maximal homogeneous blocks. Given two maximal
homogeneous blocks $X=[x,y]$ and $X^{\prime}=[x^{\prime},y^{\prime}]$, not
necessarily belonging to $B$, the block-interval defined by the pair
$X,X^{\prime}$, denoted $[X,X^{\prime}]_{B}$, is the following sequence of
maximal homogeneous blocks:

$[X,X^{\prime}]_{B}=\left\\{[i,j]\in B:[i,j]\subseteq[x,y^{\prime}]\right\\}.$

######  Definition 22.

Let $\sigma$ and $\sigma^{\prime}$ be a pair of configurations where
${\textrm{MAJ}}_{r}(\sigma)=\sigma^{\prime}$. Given a maximal homogeneous
block $[i,j]\in B(\sigma^{\prime})$, let
$f^{\leftarrow}_{\sigma,\sigma^{\prime}}([i,j])$ be the maximal homogeneous
block in $B(\sigma)$ that contains the 1.1 $i^{\prime}=j-r$. Similarly, let
$f^{\rightarrow}_{\sigma,\sigma^{\prime}}([i,j])$ be the maximal homogeneous
block in $B(\sigma)$ that contains the 1.1 $j^{\prime}=i+r$.

We refer to the function $f^{\leftarrow}_{\sigma,\sigma^{\prime}}$ as the left
mapping from $\sigma^{\prime}$ to $\sigma$, and, similarly, we refer to the
function $f^{\rightarrow}_{\sigma,\sigma^{\prime}}$ as the right mapping from
$\sigma^{\prime}$ to $\sigma$.

######  Claim 11.

For every pair of configurations $\sigma$ and $\sigma^{\prime}$ satisfying
${\textrm{MAJ}}_{r}(\sigma)=\sigma^{\prime}$ and a maximal homogeneous block
$[i,j]\in B(\sigma^{\prime})$, the number of homogeneous blocks in the block
interval
$[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([i,j]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([i,j])]_{B(\sigma)}$
is odd.

###### Proof.

Since the pair $j,j+1$ is a  (Switch point)., by  (The Switch Point
Argument)., $\sigma(j-r)=\sigma^{\prime}(j)$. Hence, the value of the maximal
homogeneous block $f^{\leftarrow}_{\sigma,\sigma^{\prime}}([i,j])$ equals the
value of the maximal homogeneous block $[i,j]$. Similarly, since the pair
$i-1,i$ is a  (Switch point)., by  (The Switch Point Argument).,
$\sigma(i+r)=\sigma^{\prime}(i)$. Hence, the value of the maximal homogeneous
block $f^{\rightarrow}_{\sigma,\sigma^{\prime}}([i,j])$ also equals the value
of $[i,j]$. That is, the value of
$f^{\leftarrow}_{\sigma,\sigma^{\prime}}([i,j])$ equals the value of
$f^{\rightarrow}_{\sigma,\sigma^{\prime}}([i,j])$. Thus, the number of maximal
homogeneous blocks in the block interval
$[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([i,j]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([i,j])]_{B(\sigma)}$
must be odd. ∎

######  Claim 12.

For every pair of configurations $\sigma$ and $\sigma^{\prime}$ satisfying
${\textrm{MAJ}}_{r}(\sigma)=\sigma^{\prime}$, if $[i^{\prime},j^{\prime}]\in
B(\sigma^{\prime})$, then the value of $\sigma^{\prime}$ at
$[i^{\prime},j^{\prime}]$ equals the value of $\sigma$ at
$f^{\rightarrow}_{\sigma^{\prime},\sigma}([i^{\prime},j^{\prime}])$ as well as
at $f^{\leftarrow}_{\sigma^{\prime},\sigma}([i^{\prime},j^{\prime}])$

###### Proof.

By the definition of $B(\sigma^{\prime})$, the interval
$[i^{\prime},j^{\prime}]$ is a maximal homogeneous block. Therefore, the pair
$(i^{\prime}-1,i^{\prime})$ is a  (Switch point). in $\sigma^{\prime}$, so by
(The Switch Point Argument).,
$\sigma(i^{\prime}+r)=\sigma^{\prime}(i^{\prime})$.. A similar argument holds
for $\sigma(j^{\prime}-r)$, and the claim follows. ∎

######  Claim 13.

For every pair of configurations $\sigma$ and $\sigma^{\prime}$ satisfying
${\textrm{MAJ}}_{r}(\sigma)=\sigma^{\prime}$, each of the functions
$f^{\rightarrow}_{\sigma^{\prime},\sigma}([i^{\prime},j^{\prime}])$ and
$f^{\leftarrow}_{\sigma^{\prime},\sigma}([i^{\prime},j^{\prime}])$ is one-to-
one.

###### Proof.

We prove the claim for
$f^{\rightarrow}_{\sigma^{\prime},\sigma}([i^{\prime},j^{\prime}])$ and denote
it by $f$ for short. Let $[i,j]\in B(\sigma)$ and suppose by way of
contradiction that there are two different blocks
$[i^{\prime},j^{\prime}],[i^{\prime\prime},j^{\prime\prime}]\in
B(\sigma^{\prime})$ s.t.
$f([i^{\prime},j^{\prime}])=f([i^{\prime\prime},j^{\prime\prime}])=[i,j]$. Let
$\beta$ be the value of $\sigma$ at the block $[i,j]$. By 12, the value of
$\sigma^{\prime}$ at both $[i^{\prime},j^{\prime}]$ and
$[i^{\prime\prime},j^{\prime\prime}]$ is also $\beta$. By the definition of
the mapping, the fact that
$f([i^{\prime},j^{\prime}])=f([i^{\prime\prime},j^{\prime\prime}])=[i,j]$
implies that both $i^{\prime}+r$ and $i^{\prime\prime}+r$ belong to $[i,j]$.
Hence, either $[i^{\prime}+r,i^{\prime\prime}+r]\subseteq[i,j]$ or
$[i^{\prime\prime}+r,i^{\prime}+r]\subseteq[i,j]$. Assume without loss of
generality that $[i^{\prime}+r,i^{\prime\prime}+r]\subseteq[i,j]$. Hence,
there must exist a maximal homogeneous block $[i^{*},j^{*}]$ in
$\sigma^{\prime}$ where the value of $\sigma^{\prime}$ at $[i^{*},j^{*}]$ is
$1-\beta$ and $i^{*}\in[i^{\prime},i^{\prime\prime}]$. Hence, it must hold
that $i^{*}+r\in[i^{\prime}+r,i^{\prime\prime}+r]\subseteq[i,j]$. That is,
$f([i^{*},j^{*}])=[i,j]$, in contradiction to 12. ∎

######  Claim 14.

For every pair of configurations $\sigma$ and $\sigma^{\prime}$ satisfying
${\textrm{MAJ}}_{r}(\sigma)=\sigma^{\prime}$, it must be the case that
$b(\sigma^{\prime})\leq b(\sigma)$.

###### Proof.

By 13, there is a one-to-one mapping from $B(\sigma^{\prime})$ to $B(\sigma)$.
Hence, $b(\sigma^{\prime})\leq b(\sigma)$. ∎

######  Claim 15.

If $\sigma$ is a  (temporally periodic). configuration, then for every pair of
blocks $[a,b],[c,d]\in B(\sigma)$, the number of blocks in the block interval
$[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([a,b]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([a,b])]_{B(\sigma)}$
equals the number of blocks in the block interval
$[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([c,d]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([c,d])]_{B(\sigma)}$.

Moreover, if a pair of configurations $\sigma,\sigma^{\prime}$ is a
(temporally periodic configuration pair)., then for every pair of blocks
$[a,b]\in B(\sigma)$ and $[c,d]\in B(\sigma)$, the number of blocks in the
block interval
$[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([a,b]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([a,b])]_{B(\sigma)}$
equals the number of blocks in
$[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([c,d]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([c,d])]_{B(\sigma)}$.

###### Proof.

Let $k$ be the number of maximal homogeneous blocks in $\sigma$. By 13, the
functions $f^{\leftarrow}_{\sigma,\sigma^{\prime}}$ and
$f^{\rightarrow}_{\sigma,\sigma^{\prime}}$ are one-to-one, and therefore the
number of maximal homogeneous blocks in $\sigma^{\prime}$ is $k$ as well.
Denote by $[a_{1},b_{1}],\dots,[a_{k},b_{k}]$ the sequence of maximal
homogeneous blocks in $\sigma$ starting from an arbitrary block
$[a_{1},b_{1}]$ such that for each $1\leq i\leq$, $a_{i+1}=b_{i}+1$ (that is,
the blocks $[a_{i},b_{i}]$ and $[a_{i+1},b_{i+1}]$ are consecutive).

We claim that for every $1\leq i\leq k$, if
$f^{\leftarrow}_{\sigma,\sigma^{\prime}}([a_{i},b_{i}])=[a^{\prime}_{i},b^{\prime}_{i}]$
and
$f^{\leftarrow}_{\sigma,\sigma^{\prime}}([a_{i+1},b_{i+1}])=[a^{\prime}_{i+1},b^{\prime}_{i+1}]$,
then $a^{\prime}_{i+1}=b^{\prime}_{i}$ (that is, the blocks
$f^{\leftarrow}_{\sigma,\sigma^{\prime}}([a_{i},b_{i}])$ and
$f^{\leftarrow}_{\sigma,\sigma^{\prime}}([a_{i+1},b_{i+1}])$ are consecutive).
We also claim that for every $1\leq i\leq k$, if
$f^{\rightarrow}_{\sigma,\sigma^{\prime}}([a_{i},b_{i}])=[a^{\prime\prime}_{i},b^{\prime\prime}_{i}]$
and
$f^{\rightarrow}_{\sigma,\sigma^{\prime}}([a_{i+1},b_{i+1}])=[a^{\prime}_{i+1},b^{\prime}_{i+1}]$,
then $a^{\prime\prime}_{i+1}=b^{\prime\prime}_{i}$. We prove the former (since
the proof of the latter is analogous).

Suppose towards a contradiction that for some $1\leq i\leq k$,
$a^{\prime}_{i+1}\neq b^{\prime}_{i}$. In that case, there must exists an
integer $2\leq j\leq k-1$ for which

$\displaystyle
f^{\leftarrow}_{\sigma,\sigma^{\prime}}([a_{i+j},b_{i+j}])\subseteq[a^{\prime}_{i},b^{\prime}_{i+1}].$

Since $b_{i+j}-r\in
f^{\leftarrow}_{\sigma,\sigma^{\prime}}([a_{i+j},b_{i+j}])$, this means that
$b_{i+j}-r\in[a^{\prime}_{i},b^{\prime}_{i+1}]$, and hence
$b_{i+j}-r\in[b_{i}-r,b_{i+1}-r]$. Thus,

$\displaystyle
b_{i+j}\in[b_{i},b_{i+1}]\subseteq[a_{i},b_{i}]\cup[a_{i+1},b_{i+1}],$

in contradiction to $j\geq 2$ (in other words, in contradiction to
$[a_{i+j},b_{i+j}]$ being distinct from $[a_{i},b_{i}]$ and
$[a_{i+1},b_{i+1}]$).

This establishes the claim that $a^{\prime}_{i+1}=b^{\prime}_{i}$, and an
analog argument implies that $a^{\prime\prime}_{i+1}=b^{\prime\prime}_{i}$ as
well. Hence,

$\displaystyle[f^{\leftarrow}_{\sigma,\sigma^{\prime}}$
$\displaystyle([a_{i+1},b_{i+1}]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([a_{i+1},b_{i+1}])]_{B(\sigma)}$
$\displaystyle=[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([a_{i},b_{i}]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([a_{i},b_{i}])]_{B(\sigma)}\cup\left\\{[a^{\prime\prime}_{i},b^{\prime\prime}_{i}]\right\\}\setminus\left\\{[a^{\prime}_{i},b^{\prime}_{i}]\right\\}.$

Thus,

$\displaystyle|[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([a_{i+1},b_{i+1}]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([a_{i+1},b_{i+1}])]_{B(\sigma)}|=|[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([a_{i},b_{i}]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([a_{i},b_{i}])]_{B(\sigma)}|$
(5.1)

Since Equation (5.1) holds for every $1\leq i\leq k$, it must be the case that
for every pair of blocks $[a,b],[c,d]\in B(\sigma)$, the number of blocks in
the block interval
$[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([a,b]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([a,b])]_{B(\sigma)}$
equals the number of blocks in the block interval
$[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([c,d]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([c,d])]_{B(\sigma)}$,
which establishes the first part of the claim. ∎

##  6 The  (alignment mapping).

######  Definition 23 (alignment mapping).

Let $\sigma$ and $\sigma^{\prime}$ be a pair of configurations satisfying
${\textrm{MAJ}}_{r}(\sigma)=\sigma^{\prime}$. Given a maximal homogeneous
block $[i,j]\in B(\sigma^{\prime})$, let
$\varphi_{\sigma,\sigma^{\prime}}([i,j])$ be the middle block in the block
interval
$[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([i,j]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([i,j])]_{B(\sigma)}$
(the middle block is well-defined, since, by 11, the number of blocks in that
interval is odd).

We refer to the function $\varphi_{\sigma,\sigma^{\prime}}$ as the  (alignment
mapping). from $\sigma^{\prime}$ to $\sigma$.

######  Claim 16.

For every pair of configurations $\sigma$ and $\sigma^{\prime}$ satisfying
${\textrm{MAJ}}_{r}(\sigma)=\sigma^{\prime}$, the  (alignment mapping).
$\varphi_{\sigma,\sigma^{\prime}}$ is one-to-one.

###### Proof.

Suppose that, contrary to the claim, $\varphi_{\sigma,\sigma^{\prime}}$ is not
one-to-one. That is, there are two distinct blocks $[a,b],[c,d]\in
B(\sigma^{\prime})$ such that

$\displaystyle\varphi_{\sigma,\sigma^{\prime}}([a,b])=\varphi_{\sigma,\sigma^{\prime}}([c,d]).$

That being the case, denote by $I\in B(\sigma)$ the block satisfying
$I=\varphi_{\sigma,\sigma^{\prime}}([a,b])=\varphi_{\sigma,\sigma^{\prime}}([c,d])$.

Since $[a,b]$ and $[c,d]$ are maximal homogeneous blocks, it is either the
case that the intervals $[b,c]$ and $[a,d]$ satisfy $[b,c]\subseteq[a,d]$ or
that they satisfy $[a,d]\subseteq[b,c]$. We assume, then, without loss of
generality, that

$\displaystyle[b,c]\subseteq[a,d].$ (6.1)

By 11, for every maximal homogeneous block $[i,j]\in B(\sigma^{\prime})$, the
number of blocks in
$[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([i,j]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([i,j])]_{B(\sigma)}$
is odd. Let $\delta_{[a,b]}$ be the integer satisfying

$\displaystyle|[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([a,b]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([a,b])]_{B(\sigma)}|=2\delta_{[a,b]}+1,$

and, similarly, let $\delta_{[c,d]}$ be the integer satisfying

$\displaystyle|[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([c,d]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([c,d])]_{B(\sigma)}|=2\delta_{[c,d]}+1.$

By the Definition 23, the block $I$ defined above is the middle block of the
block interval
$[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([a,b]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([a,b])]_{B(\sigma)}$
as well as of the block interval
$[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([c,d]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([c,d])]_{B(\sigma)}$.
This means that the block $f^{\leftarrow}_{\sigma,\sigma^{\prime}}([a,b])$ is
located $\delta_{[a,b]}$ blocks away from $I$ to its left side and that the
block $f^{\rightarrow}_{\sigma,\sigma^{\prime}}([a,b])$ is located
$\delta_{[a,b]}$ blocks away from $I$ to its right side. Similarly, the block
$f^{\leftarrow}_{\sigma,\sigma^{\prime}}([c,d])$ is located $\delta_{[c,d]}$
blocks away from $I$ to the left, and that the block
$f^{\rightarrow}_{\sigma,\sigma^{\prime}}([c,d])$ is located $\delta_{[c,d]}$
blocks away from $I$ to the right.

Thus, if $\delta_{[a,b]}\leq\delta_{[c,d]}$, then

$\displaystyle[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([a,b]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([a,b])]_{B(\sigma)}\subseteq[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([c,d]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([c,d])]_{B(\sigma)},$
(6.2)

and if $\delta_{[a,b]}\geq\delta_{[c,d]}$, then

$\displaystyle[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([c,d]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([c,d])]_{B(\sigma)}\subseteq[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([a,b]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([a,b])]_{B(\sigma)}.$
(6.3)

In the former case (Equation (6.2)),

$\displaystyle[b-r,a+r]\subseteq[d-r,c+r].$ (6.4)

This is because, by Definition 22,

$\displaystyle b-r$ $\displaystyle\in
f^{\leftarrow}_{\sigma,\sigma^{\prime}}([a,b]),$ $\displaystyle a+r$
$\displaystyle\in f^{\rightarrow}_{\sigma,\sigma^{\prime}}([a,b]),$
$\displaystyle d-r$ $\displaystyle\in
f^{\leftarrow}_{\sigma,\sigma^{\prime}}([c,d]),\text{ and}$ $\displaystyle
c+r$ $\displaystyle\in f^{\rightarrow}_{\sigma,\sigma^{\prime}}([c,d]).$

For the same reason, in the latter case (Equation (6.3)),

$\displaystyle[d-r,c+r]\subseteq[b-r,a+r].$ (6.5)

However, both $[b-r,a+r]\subseteq[d-r,c+r]$ (Equation (6.4)) and
$[d-r,c+r]\subseteq[b-r,a+r]$ (Equation (6.5)) are impossible given the
assumption that $[b,c]\subseteq[a,d]$ (Equation (6.1)).

To see why $[b-r,a+r]\subseteq[d-r,c+r]$ contradicts $[b,c]\subseteq[a,d]$,
observe that $[b,c]\subseteq[a,d]$ implies $[d-r,c+r]\subseteq[d-r,d+r]$, and
since $[d-r,d+r]=2r+1$, it must be the case that $|[d-r,c+r]|<2r$.

Additionally, $[b,c]\subseteq[a,d]$ also implies $[b-r,b+r]\subseteq[b-r,c+r]$
and $|[b-r,b+r]|=2r+1$, so $|[b-r,c+r]|>2r$.

However, $[b-r,a+r]\subseteq[d-r,c+r]$ implies that
$[b-r,c+r]\subseteq[d-r,c+r]$, so it cannot be the case that both
$|[d-r,c+r]|<2r$ and $|[b-r,c+r]|>2r$.

The case in which $[d-r,c+r]\subseteq[b-r,a+r]$ can similarly be shown to
contradict $[b,c]\subseteq[a,d]$, so we reach a contradiction in either case.
∎

######  Claim 17.

Let $\sigma$, $\sigma^{\prime}$ be a  (temporally periodic configuration
pair). and let $[a,b],[c,d]\in B(\sigma^{\prime})$ be two adjacent blocks in
which $c=b+1$. If
$\varphi_{\sigma,\sigma^{\prime}}([a,b])=[a^{\prime},b^{\prime}]$ and
$\varphi_{\sigma,\sigma^{\prime}}([c,d])=[c^{\prime},d^{\prime}]$, then the
blocks $[a^{\prime},b^{\prime}]$ and $[c^{\prime},d^{\prime}]$ are also
adjacent and $c^{\prime}=b^{\prime}+1$.

###### Proof.

Let $\beta\in\left\\{0,1\right\\}$ be the value of the block $[a,b]$ in
$\sigma^{\prime}$. Since the block $[c,d]$ is adjacent to the block $[a,b]$,
the value of the block $[c,d]$ in $\sigma^{\prime}$ must be $\bar{\beta}$. By
(The Switch Point Argument)., $\sigma(a+r)=\beta$ and
$\sigma(c+r)=\bar{\beta}$, so the value of the block
$f^{\rightarrow}_{\sigma,\sigma^{\prime}}([a,b])$ in $\sigma$ is $\beta$ and
the value of the block $f^{\rightarrow}_{\sigma,\sigma^{\prime}}([c,d])$ in
$\sigma^{\prime}$ is $\bar{\beta}$.

By 10, the interval $[a+r,b+r+1]$ contains exactly one  (Switch point). in
$\sigma$. Since $c=b+r$, the interval $[a+r,c+r]$ contains exactly one
(Switch point). in $\sigma$. As both
$f^{\rightarrow}_{\sigma,\sigma^{\prime}}([a,b])$ and
$f^{\rightarrow}_{\sigma,\sigma^{\prime}}([c,d])$ intersect with the interval
$[a+r,c+r]$, that single  (Switch point). must be the $\beta,\bar{\beta}$
(Switch point). between $f^{\rightarrow}_{\sigma,\sigma^{\prime}}([a,b])$ and
$f^{\rightarrow}_{\sigma,\sigma^{\prime}}([c,d])$. Hence, the blocks
$f^{\rightarrow}_{\sigma,\sigma^{\prime}}([a,b])$ and
$f^{\rightarrow}_{\sigma,\sigma^{\prime}}([c,d])$ are adjacent with the block
$f^{\rightarrow}_{\sigma,\sigma^{\prime}}([a,b])$ preceding the block
$f^{\rightarrow}_{\sigma,\sigma^{\prime}}([c,d])$.

By a similar argument, the blocks
$f^{\leftarrow}_{\sigma,\sigma^{\prime}}([a,b])$ and
$f^{\leftarrow}_{\sigma,\sigma^{\prime}}([c,d])$ are adjacent with the block
$f^{\leftarrow}_{\sigma,\sigma^{\prime}}([a,b])$ preceding the block
$f^{\leftarrow}_{\sigma,\sigma^{\prime}}([c,d])$.

By the definition of the  (alignment mapping)., the block
$[a^{\prime},b^{\prime}]$ is the middle block of the block interval
$[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([a,b]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([a,b])]_{B(\sigma)}$,
and the block $[c^{\prime},d^{\prime}]$ is the middle block of the block
interval
$[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([c,d]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([c,d])]_{B(\sigma)}$.

Therefore, the blocks $[a^{\prime},b^{\prime}]$ and $[c^{\prime},d^{\prime}]$
must be adjacent to each other and it must also be the case that
$c^{\prime}=b^{\prime}+1$, as claimed. ∎

######  Definition 24.

Let $\sigma$, $\sigma^{\prime}$ be a  (temporally periodic configuration
pair).. Given an integer $k$, we define $\varphi_{\sigma,\sigma^{\prime}}^{k}$
as follows. For every block $[i,j]\in B(\sigma)$,

  1. 1.

$\varphi_{\sigma,\sigma^{\prime}}^{0}([i,j])=[i,j]$.

  2. 2.

$\varphi_{\sigma,\sigma^{\prime}}^{1}([i,j])=\varphi_{\sigma,\sigma^{\prime}}([i,j])$.

  3. 3.

for $k>1$, if $k$ is odd, then
$\varphi_{\sigma,\sigma^{\prime}}^{k}([i,j])=\varphi_{\sigma,\sigma^{\prime}}(\varphi_{\sigma,\sigma^{\prime}}^{k-1}([i,j]))$.

  4. 4.

for $k>1$, if $k$ is even, then
$\varphi_{\sigma,\sigma^{\prime}}^{k}([i,j])=\varphi_{\sigma^{\prime},\sigma}(\varphi_{\sigma,\sigma^{\prime}}^{k-1}([i,j]))$.

######  Observation 18.

Let $\sigma$, $\sigma^{\prime}$ be a  (temporally periodic configuration
pair).. For every block $[i,j]\in B(\sigma^{\prime})$,
$\varphi_{\sigma,\sigma^{\prime}}^{2}([i,j])=[i,j]$.

######  Definition 25.

Let ${\rm E}$ be a cellular automaton evolving according to
${\textrm{MAJ}}_{r}$. Given a time step $t\geq 1$, we define $\varphi_{t}$ as
$\varphi_{{\rm E}_{t-1},{\rm E}_{t}}([i,j])$ for every block $[i,j]\in B({\rm
E}_{t})$. Given an integer $k$ and a time step $t$ s.t. $t\geq k$, we define
$\varphi_{t}^{k}$ as follows. For every block $[i,j]\in B({\rm E}_{t})$:

  1. 1.

$\varphi_{t}^{0}([i,j])=[i,j]$.

  2. 2.

for $k>1$, $\varphi_{t}^{k}([i,j])=\varphi_{t-k+1}(\varphi_{t}^{k-1}([i,j]))$.

##  7 Block lengths in  (temporally periodic). configurations

######  Claim 19.

Let $\sigma$, $\sigma^{\prime}$ be a  (temporally periodic configuration
pair). of  (weakly stable). configurations and let
$\beta\in\left\\{0,1\right\\}$. For every block $[i,j]\in
B^{\beta}(\sigma^{\prime})$,

$\displaystyle|[i,j]|=\sum_{[i^{\prime},j^{\prime}]\in
A^{\beta}}|[i^{\prime},j^{\prime}]|-\sum_{[i^{\prime},j^{\prime}]\in
A^{\bar{\beta}}}|[i^{\prime},j^{\prime}]|,$ (7.1)

where

$A^{\beta}=[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([i,j]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([i,j])]_{B^{\beta}(\sigma)},$

and, similarly,

$A^{\bar{\beta}}=[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([i,j]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([i,j])]_{B^{\bar{\beta}}(\sigma)}.$

###### Proof.

Since $\sigma^{\prime}$ is a  (temporally periodic). (weakly stable).
configuration, by 9, $|[i,j]|\leq r<2r+1$. Therefore, the conditions for
applying 4 hold. So, by 4,

$\displaystyle|[i,j]|=\\#_{\beta}(\sigma[i-r,j+r])-\\#_{\bar{\beta}}(\sigma[j-r,i+r]).$
(7.2)

To prove the claim, we relate Equation (7.2) to Equation (7.1) by defining
four sets of 1.1s:

$\displaystyle X^{\beta}$
$\displaystyle=\left\\{\ell\in[i^{\prime},j^{\prime}]|[i^{\prime},j^{\prime}]\in
A^{\beta}\right\\},$ $\displaystyle X^{\bar{\beta}}$
$\displaystyle=\left\\{\ell\in[i^{\prime},j^{\prime}]|[i^{\prime},j^{\prime}]\in
A^{\bar{\beta}}\right\\},$ $\displaystyle Y^{\beta}$
$\displaystyle=\left\\{\ell\in[i-r,j+r]|\sigma(\ell)=\beta\right\\},$
$\displaystyle Y^{\bar{\beta}}$
$\displaystyle=\left\\{\ell\in[j-r,i+r]|\sigma(\ell)=\bar{\beta}\right\\}.$

In order to prove the claim, it is sufficient to show that

$\displaystyle X^{\beta}$ $\displaystyle=Y^{\beta},$ $\displaystyle
X^{\bar{\beta}}$ $\displaystyle=Y^{\bar{\beta}}.$

We first show that $X^{\bar{\beta}}=Y^{\bar{\beta}}$.

Let $i^{*}$ be the leftmost 1.1 in the block
$f^{\leftarrow}_{\sigma,\sigma^{\prime}}([i,j])$ and let $j^{*}$ be the
rightmost 1.1 in the block $f^{\rightarrow}_{\sigma,\sigma^{\prime}}([i,j])$.
By the definition of $A^{\bar{\beta}}$,

$\displaystyle
X^{\bar{\beta}}=\left\\{\ell\in[i^{*},j^{*}]|\sigma(\ell)=\bar{\beta}\right\\}.$

Since $[i,j]\in B^{\beta}(\sigma^{\prime})$, each of the pairs $(i-1,i)$ and
$(j,j+1)$ is a  (Switch point). in $\sigma^{\prime}$, so by  (The Switch Point
Argument)., $\sigma(j-r)=\sigma(i+r)=\beta$. As
$f^{\leftarrow}_{\sigma,\sigma^{\prime}}([i,j])$ and
$f^{\rightarrow}_{\sigma,\sigma^{\prime}}([i,j])$ are by definition the two
maximal homogeneous blocks in $\sigma$ that contain the 1.1s $j-r$ and $i+r$
respectively, it must be the case that for each 1.1
$\ell\in[i^{*},j-r]\cup[i+r,j^{*}]$, $\sigma(\ell)=\beta$. Hence, if a 1.1
$\ell\in[i^{*},j^{*}]$ satisfies $\sigma(\ell)=\bar{\beta}$, then
$\ell\in[j-r+1,i+r-1]\subseteq[j-r,i+r]$. That is,

$\displaystyle
X^{\bar{\beta}}=\left\\{\ell\in[j-r,i+r]|\sigma(\ell)=\bar{\beta}\right\\}=Y^{\bar{\beta}}.$

We now show that $X^{\beta}=Y^{\beta}$.

Recall that $i^{*}$ is the leftmost 1.1 in the block
$f^{\leftarrow}_{\sigma,\sigma^{\prime}}([i,j])$ and that $j^{*}$ is the
rightmost 1.1 in the block $f^{\rightarrow}_{\sigma,\sigma^{\prime}}([i,j])$,
which means that
$X^{\beta}=\left\\{\ell\in[i^{*},j^{*}]|\sigma(\ell)=\beta\right\\}$.

Since $(i-1,i)$ is a  (Switch point). in $\sigma^{\prime}$, by  (The Switch
Point Argument)., $\sigma(i-r-1)=\bar{\beta}$. This implies that
$i^{*}\in[i-r,j-r]$. As $(i^{*}-1,i^{*})$ is a  (Switch point). in $\sigma$ of
type $(\bar{\beta},\beta)$, by 10, there is exactly one  (Switch point). in
$[i-r-1,j-r]$, and therefore it must be the case that

$\displaystyle\left\\{\ell\in[i-r,j-r]|\sigma(\ell)=\beta\right\\}=[i^{*},j-r].$
(7.3)

Similarly, since $(j,j+1)$ is a  (Switch point). in $\sigma^{\prime}$, by
(The Switch Point Argument)., $\sigma(j+r+1)=\bar{\beta}$, which implies that
$j^{*}\in[i+r,j+r]$. Because $(i^{*}-1,i^{*})$ is a  (Switch point). in
$\sigma$ of type $(\bar{\beta},\beta)$, by 10, there is exactly one  (Switch
point). in $[i+r,j+r+1]$, and therefore it must be the case that

$\displaystyle\left\\{\ell\in[i+r,j+r]|\sigma(\ell)=\beta\right\\}=[i+r,j^{*}].$
(7.4)

Consequently,

$\displaystyle Y^{\beta}$
$\displaystyle=\left\\{\ell\in[i-r,j+r]|\sigma(\ell)=\beta\right\\}$ (7.5)
$\displaystyle=\left\\{\ell\in[i^{*},j^{*}]|\sigma(\ell)=\beta\right\\}$ (7.6)
$\displaystyle=X^{\beta},$ (7.7)

where (7.6) follows from equations (7.3) and (7.5) together with the
observations that $i^{*}\in[i-r,j-r]$ and $j^{*}\in[i+r,j+r]$.

We’ve shown that $X^{\beta}=Y^{\beta}$ and $X^{\bar{\beta}}=Y^{\bar{\beta}}$,
so the claim follows. ∎

##  8 The  (block-length vector).s of  (temporally periodic configuration
pair).s

######  Definition 26 (block-length vector).

Given a configuration $\sigma:{\mathbb{Z}_{n}}\to\\{0,1\\}$, we define its
(block-length vector). $\vec{v}:{\mathbb{Z}_{|B(\sigma)|}}\to\mathbb{N}$ as
the cyclic sequence of the lengths of the configuration’s maximal homogeneous
blocks.

That is, $\vec{v}(0)=|[i,j]|$ for an arbitrary block $[i,j]\in B(\sigma)$, and
for each $k\in{\mathbb{Z}_{|B(\sigma)|}}$, if $[a,b]\in B(\sigma)$ is the
block for which $\vec{v}(k-1)=|[a,b]|$ and $[c,d]\in B(\sigma)$ is the block
satisfying $c=b+1$, then $\vec{v}(k)=|[c,d]|$.

We note that every possible  (block-length vector)., viewed as a ring of
integers, corresponds to at most two configurations (up to cyclic shifts): one
where the blocks at the odd positions have a value of 0 and one where the
blocks at the even positions have a value of 0.101010 These two possible
configurations collapse into one in the case in which the  (block-length
vector). $\vec{v}$ equals the concatenation of some  (block-length vector).
$\vec{u}$ to itself (i.e, $\vec{v}=\vec{u}\vec{u}$), where $\vec{u}$ is of odd
length (for instance, the  (block-length vector). $123123$ corresponds to
exactly one configuration, up to a cyclic shift, as the configuration
resulting from assigning the value 0 to the first block is the same
configuration resulting from assigning the value 1 to the first block).  So
when we say that a  (block-length vector). corresponds to a configuration
$\sigma$, it means that the configuration $\sigma$ can be either of the at
most two possibilities.

######  Definition 27.

We define the length of a  (block-length vector). $\vec{v}$, denoted by
$|\vec{v}|$, as the number of entries in the vector. That is, if $\vec{v}$ is
the  (block-length vector). that corresponds to the configuration $\sigma$,
then $|\vec{v}|=|B(\sigma)|$.

######  Claim 20.

If $\vec{v}$ and $\vec{v^{\prime}}$ are a pair of  (block-length vector).s
corresponding to a  (temporally periodic configuration pair)., then
$|\vec{v}|=|\vec{v^{\prime}}|$.

###### Proof.

Let $\sigma$ be a configuration that corresponds to the  (block-length
vector). $\vec{v}$ and let $\sigma^{\prime}={\textrm{MAJ}}_{r}(\sigma)$.
Clearly, $\vec{v^{\prime}}$ is the the  (block-length vector). of the
configuration $\sigma^{\prime}$, and the pair $\sigma,\sigma^{\prime}$ is a
(temporally periodic configuration pair)..

Since $\sigma^{\prime}={\textrm{MAJ}}_{r}(\sigma)$, by 14,
$|B(\sigma^{\prime})|\leq|B(\sigma)|$. Since $\sigma,\sigma^{\prime}$ are a
(temporally periodic configuration pair)., it is also the case that
$\sigma={\textrm{MAJ}}_{r}(\sigma^{\prime})$, so again by 14,
$|B(\sigma)|\leq|B(\sigma^{\prime})|$.

That is, $|B(\sigma)|=|B(\sigma^{\prime})|$ and the claim follows. ∎

######  Definition 28 (aligned).

Let $\vec{v}$ and $\vec{v^{\prime}}$ be a pair of  (block-length vector).s of
length $k$ each corresponding to a  (temporally periodic configuration pair).
$\sigma$ and $\sigma^{\prime}$. For each $i\in{\mathbb{Z}_{k}}$, let $I_{i}$
the 1.7 in $\sigma$ that corresponds to $\vec{v}_{i}$ and let $I^{\prime}_{i}$
be the 1.7 in $\sigma^{\prime}$ that corresponds to $\vec{v^{\prime}}_{i}$. We
say that the pair $\vec{v}$ and $\vec{v^{\prime}}$ are  (aligned). if for each
$i\in{\mathbb{Z}_{k}}$,
$\varphi_{\sigma,\sigma^{\prime}}(I^{\prime}_{i})=I_{i}$ (where
$\varphi_{\sigma,\sigma^{\prime}}$ is the  (alignment mapping). from
$\sigma^{\prime}$ to $\sigma$).

##  9 The  (horizon). of  (block-length vector).s

######  Definition 29 (horizon).

Let $\vec{v}$ and $\vec{v^{\prime}}$ be a pair of  (block-length vector).s of
lengths $k$ and $k^{\prime}$ each, corresponding to a pair of configurations
$\sigma$ and $\sigma^{\prime}$ satisfying
${\textrm{MAJ}}_{r}(\sigma)=\sigma^{\prime}$. For each entry
$i\in{\mathbb{Z}_{k^{\prime}}}$ of $\vec{v^{\prime}}$, we define the
(horizon). of $i$ in $\vec{v^{\prime}}$, denoted by
$\delta_{\vec{v^{\prime}}}(i)$, as follows: $\delta_{\vec{v^{\prime}}}(i)$ is
the value that satisfies

$\displaystyle|[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([a,b]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([a,b])]_{B(\sigma)}|=2\delta_{\vec{v^{\prime}}}(i)+1,$

where $[a,b]\in B(\sigma^{\prime})$ is the block in $\sigma^{\prime}$ that
corresponds to entry $i$ of $\vec{v^{\prime}}$.111111 The  (horizon).
$\delta_{\vec{v^{\prime}}}(i)$ is well defined because, by 11, the number of
blocks in
$[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([a,b]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([a,b])]_{B(\sigma)}$
is odd.

######  Observation 21.

If $\vec{v}$ is the  (block-length vector). corresponding to a  (temporally
periodic). configuration $\sigma$, then for every $i\in{\mathbb{Z}_{k}}$,
where $k$ is the length of $\vec{v}$, the  (horizon). $\delta_{\vec{v}}$
satisfies $\delta_{\vec{v}}(i)\leq r$.

######  Claim 22.

Let $\vec{v},\vec{v^{\prime}}$ be a pair of  (block-length vector).s
corresponding to a  (temporally periodic configuration pair).
$\sigma,\sigma^{\prime}$. For every pair
$i,j\in{\mathbb{Z}_{|\vec{v^{\prime}}|}}$,

$\displaystyle\delta_{\vec{v^{\prime}}}(i)=\delta_{\vec{v^{\prime}}}(j).$

Moreover, for every $i\in{\mathbb{Z}_{|\vec{v^{\prime}}|}}$,

$\displaystyle\delta_{\vec{v}}(i)=\delta_{\vec{v^{\prime}}}(i).$

###### Proof.

Let $[a,b]\in B(\sigma)$ be the block corresponding to entry $i$ of the
(block-length vector). $\vec{v}$ and let $[c,d]\in B(\sigma)$ be the block
corresponding to entry $j$ of the  (block-length vector). $\vec{v}$. By 15,
the number of blocks in the block interval
$[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([a,b]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([a,b])]_{B(\sigma)}$
equals the number of blocks in the block interval
$[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([c,d]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([c,d])]_{B(\sigma)}$.
That is, $2\delta_{\vec{v^{\prime}}}(i)+1=2\delta_{\vec{v^{\prime}}}(j)+1$.
Hence, $\delta_{\vec{v^{\prime}}}(i)=\delta_{\vec{v^{\prime}}}(j)$, as
claimed.

The second part of the claim similarly follows from the second part of 15. ∎

######  Claim 23.

If $\vec{v}$ is the  (block-length vector). corresponding to a  (weakly
stable). configuration $\sigma$, then the total length of every sequence of
$2\delta$ 1.7s in $\sigma$ is at most $2r$, where $\delta$ is the  (horizon).
of $\vec{v}$ (which, by 22, is the same for all 1.7s in the configuration
$\sigma$).

###### Proof.

We show that for every sequence of $2\delta+1$ consecutive 1.7s in the
configuration $\sigma$, if we remove the leftmost 1.7 from the sequence, then
the total length of the remaining 1.7s is at most $2r$.

Let $\sigma^{\prime}={\textrm{MAJ}}_{r}(\sigma)$. Since
$\sigma,\sigma^{\prime}$ comprise a  (temporally periodic configuration pair).
of  (weakly stable). configuration, every sequence of $2\delta+1$ of
consecutive 1.7s in $\sigma$ is of the form
$[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([a^{\prime},b^{\prime}]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([a^{\prime},b^{\prime}])]_{B(\sigma)}$
for some 1.7 $[a^{\prime},b^{\prime}]\in B(\sigma^{\prime})$. Let $I$ be the
(cell interval). composed of the 1.7s in the set
$[f^{\leftarrow}_{\sigma,\sigma^{\prime}}([a^{\prime},b^{\prime}]),f^{\rightarrow}_{\sigma,\sigma^{\prime}}([a^{\prime},b^{\prime}])]_{B(\sigma)}\setminus\left\\{f^{\leftarrow}_{\sigma,\sigma^{\prime}}([a^{\prime},b^{\prime}])\right\\}$.
We prove that $|I|\leq 2r$.

Let $[a,b]=f^{\rightarrow}_{\sigma,\sigma^{\prime}}([a^{\prime},b^{\prime}])$.
That is, $[a,b]$ is the 1.7 in $B(\sigma)$ that contains the 1.1
$a^{\prime}+r$. By 17, if $I_{b^{\prime}+1}$ is the 1.7 that starts at the 1.1
$b^{\prime}+1$ in $\sigma^{\prime}$, then
$f^{\rightarrow}_{\sigma,\sigma^{\prime}}(I_{b^{\prime}+1})$ is the 1.7 that
follows $[a,b]$ in $\sigma$, which means that
$b\in[a^{\prime}+r,b^{\prime}+1+r]$. Thus,

$\displaystyle|[a^{\prime}+r,b]|\leq
b^{\prime}+1+r-(a^{\prime}+r)=|[a^{\prime},b^{\prime}]|.$ (9.1)

We conclude by bounding the length of the interval $I$.

$\displaystyle|I|$ $\displaystyle\leq[b^{\prime}-r,b]$ (9.2)
$\displaystyle\leq[b^{\prime}-r,a^{\prime}+r]+[a^{\prime}+r,b]$ (9.3)
$\displaystyle\leq(2r-|[a^{\prime},b^{\prime}]|)+|[a^{\prime},b^{\prime}]|$
(9.4) $\displaystyle=2r,$ (9.5)

where Equation (9.2) follows from the observation that
$I\subseteq[b^{\prime}-r,b]$, and Equation (9.4) follows from noting that
$|[b^{\prime}-r,a^{\prime}+r]|=2r-|[a^{\prime},b^{\prime}]|$ and
$|[a^{\prime}+r,b]|\leq|[a^{\prime},b^{\prime}]|$. ∎

######  Claim 24.

If $\vec{v}$ and $\vec{v^{\prime}}$ are a pair of  (aligned). (block-length
vector).s corresponding to a  (temporally periodic configuration pair)., then
for every $i\in{\mathbb{Z}_{k}}$,

$\displaystyle\vec{v^{\prime}}_{i}=\sum_{j=-\delta}^{\delta}(-1)^{j+\delta}\vec{v}_{i+j}.$

where $k$ is the length of the vectors $\vec{v}$ and $\vec{v^{\prime}}$ (by
20, the two  (block-length vector).s have the same length) and $\delta$ is the
(horizon). of the vectors $\vec{v}$ and $\vec{v^{\prime}}$ (by 22, the two
(block-length vector).s have the same  (horizon).).

###### Proof.

Let $\sigma,\sigma^{\prime}$ be the  (temporally periodic configuration pair).
that corresponds to the  (block-length vector). pair
$\vec{v},\vec{v^{\prime}}$. By 19, for $\beta\in\left\\{0,1\right\\}$ and for
every block $b\in B^{\beta}(\sigma^{\prime})$,

$\displaystyle|b|=\sum_{b^{\prime}\in
A^{\beta}}|b^{\prime}|-\sum_{b^{\prime}\in A^{\bar{\beta}}}|b^{\prime}|,$

where

$\displaystyle A^{\beta}$
$\displaystyle=[f^{\leftarrow}_{\sigma,\sigma^{\prime}}(b),f^{\rightarrow}_{\sigma,\sigma^{\prime}}(b)]_{B^{\beta}(\sigma)},$
$\displaystyle A^{\bar{\beta}}$
$\displaystyle=[f^{\leftarrow}_{\sigma,\sigma^{\prime}}(b),f^{\rightarrow}_{\sigma,\sigma^{\prime}}(b)]_{B^{\bar{\beta}}(\sigma)}.$

By  (The Switch Point Argument)., the value of the block
$f^{\leftarrow}_{\sigma,\sigma^{\prime}}(b)$ as well as the value of the block
$f^{\rightarrow}_{\sigma,\sigma^{\prime}}(b)$ is $\beta$. In more detail, if
$\ell$ is the rightmost 1.1 of the block $b$, then the pair $j,j+1$ is a
(Switch point). in the configuration $\sigma^{\prime}$, so by  (The Switch
Point Argument)., $\sigma(j-r)=\sigma^{\prime}(j)$, which implies that the
value of the block $f^{\leftarrow}_{\sigma,\sigma^{\prime}}(b)$ is $\beta$
because $j-r\in f^{\leftarrow}_{\sigma,\sigma^{\prime}}(b)$. A similar
argument holds for the block $f^{\rightarrow}_{\sigma,\sigma^{\prime}}(b)$.

The other block-values in the length $2\delta+1$ interval
$[f^{\leftarrow}_{\sigma,\sigma^{\prime}}(b),f^{\rightarrow}_{\sigma,\sigma^{\prime}}(b)]_{B(\sigma)}$
alternate between $\bar{\beta}$ and $\beta$.

Hence, for every $i\in{\mathbb{Z}_{k}}$,

$\displaystyle\vec{v^{\prime}}_{i}=\sum_{j=-\delta}^{\delta}(-1)^{j+\delta}\vec{v}_{i+j}.$

∎

######  Claim 25.

If $\vec{v}$ and $\vec{v^{\prime}}$ are a pair of  (aligned). (block-length
vector).s corresponding to a  (temporally periodic configuration pair)., where
the vectors are of length $k$ and  (horizon). $\delta$, then for every
$i\in{\mathbb{Z}_{k}}$,

$\displaystyle\vec{v^{\prime}}_{i}+\vec{v^{\prime}}_{i+1}=\vec{v}_{i-\delta}+\vec{v}_{i+\delta+1}.$

Similarly,

$\displaystyle\vec{v}_{i}+\vec{v}_{i+1}=\vec{v^{\prime}}_{i-\delta}+\vec{v^{\prime}}_{i+\delta+1}.$

###### Proof.

By 24, for every $i\in{\mathbb{Z}_{k}}$,

$\displaystyle\vec{v^{\prime}}_{i}$
$\displaystyle=\sum_{j=-\delta}^{\delta}(-1)^{j+\delta}\vec{v}_{i+j},$
$\displaystyle\vec{v^{\prime}}_{i+1}$
$\displaystyle=\sum_{j=-\delta}^{\delta}(-1)^{j+\delta}\vec{v}_{i+1+j}.$

Summing up the two equations we get:

$\displaystyle\vec{v^{\prime}}_{i}+\vec{v^{\prime}}_{i+1}=\vec{v}_{i-\delta}+\vec{v}_{i+\delta+1}.$

And by symmetry,

$\displaystyle\vec{v}_{i}+\vec{v}_{i+1}=\vec{v^{\prime}}_{i-\delta}+\vec{v^{\prime}}_{i+\delta+1}.$

∎

######  Claim 26.

If $\sigma$ is a  (temporally periodic). configuration with block lengths at
most $r$ each, then $\sigma$ is  (balanced)..

###### Proof.

Let $\sigma^{\prime}={\textrm{MAJ}}_{r}(\sigma)$ and $b=|B(\sigma)|$. Let
$\vec{v}$ and $\vec{v^{\prime}}$ be the corresponding  (block-length vector).s
of the  (temporally periodic configuration pair). $\sigma,\sigma^{\prime}$.

By 20, $|\vec{v}|=\vec{v^{\prime}}$. Denote that length by $2k$ (note that
since configurations are cyclical, it is either the case that the
configuration is homogeneous or that the length is even, and in the former
case the claim trivially holds).

Let

$\displaystyle a=\sum_{i=0}^{k-1}\vec{v}_{2i},\qquad b$
$\displaystyle=\sum_{i=0}^{k-1}\vec{v}_{2i+1}$ $\displaystyle
a^{\prime}=\sum_{i=0}^{k-1}\vec{v^{\prime}}_{2i},\qquad b^{\prime}$
$\displaystyle=\sum_{i=0}^{k-1}\vec{v^{\prime}}_{2i+1}.$

By 24,

$\displaystyle a$ $\displaystyle=(\delta+1)a^{\prime}-\delta b^{\prime}$
$\displaystyle a$ $\displaystyle=(\delta+1)((\delta+1)a-\delta
b)-\delta((\delta+1)b-\delta a)$ $\displaystyle a$ $\displaystyle=b.$

∎

##  10 The difference vectors of  (weakly stable). configurations are
(spatially periodic).

######  Definition 30.

Let $\vec{v}$ and $\vec{v^{\prime}}$ be a pair of  (aligned). (block-length
vector).s corresponding to a  (temporally periodic configuration pair). of
(weakly stable). configurations, let $k$ be their (equal121212by 20.) length
and let $\delta$ be the  (horizon). common to all entries in the two
vectors131313by 22.. We define the pair of $(\delta+1)$-steps difference
vectors $\Delta$ and $\Delta^{\prime}$ between $\vec{v}$ and
$\vec{v^{\prime}}$.

For each $i\in{\mathbb{Z}_{k}}$,

$\displaystyle\Delta_{i}$
$\displaystyle=\vec{v^{\prime}}_{i+\delta+1}-\vec{v}_{i},$
$\displaystyle\Delta^{\prime}_{i}$
$\displaystyle=\vec{v}_{i+\delta+1}-\vec{v^{\prime}}_{i}.$

######  Claim 27.

If $\vec{v}$ and $\vec{v^{\prime}}$ are a pair of  (horizon).-$\delta$
(aligned). (block-length vector).s corresponding to a  (temporally periodic
configuration pair). of  (weakly stable). configurations, and $\Delta$ and
$\Delta^{\prime}$ are the pair’s two $(\delta+1)$-steps difference vectors,
then for every $i\in{\mathbb{Z}_{k}}$ and every integer $m\geq 0$,

$\displaystyle\sum_{j=0}^{m-1}\Delta_{i+2j(\delta+1)}+\sum_{j=0}^{m-1}\Delta^{\prime}_{i+(2j+1)(\delta+1)}=\vec{v}_{i+2m(\delta+1)}-\vec{v}_{i},$

where $k$ is the length of $\vec{v}$ and $\vec{v^{\prime}}$.

###### Proof.

We prove the claim by induction on $m$. For $m=0$, the sums in the left-hand
side are empty and the right-hand side consist of a difference between two
equal terms, so the equation clearly holds. We assume as our induction
hypothesis that the equation holds for $m$, and prove it for $m+1$.

$\displaystyle\sum_{j=0}^{m}\Delta_{i+2j(\delta+1)}+\sum_{j=0}^{m}\Delta^{\prime}_{i+(2j+1)(\delta+1)}$
$\displaystyle=\sum_{j=0}^{m-1}\Delta_{i+2j(\delta+1)}+\sum_{j=0}^{m-1}\Delta^{\prime}_{i+(2j+1)(\delta+1)}$
(10.1)
$\displaystyle\quad+\Delta_{i+2m(\delta+1)}+\Delta^{\prime}_{i+(2m+1)(\delta+1)}$
(10.2)
$\displaystyle=\vec{v}_{i+2m(\delta+1)}-\vec{v}_{i}+\Delta_{i+2m(\delta+1)}+\Delta^{\prime}_{i+(2m+1)(\delta+1)}$
(10.3)
$\displaystyle=(\vec{v^{\prime}}_{i+(2m+1)(\delta+1)}-\Delta_{i+2m(\delta+1)})$
(10.4)
$\displaystyle\quad-\vec{v}_{i}+\Delta_{i+2m(\delta+1)}+\Delta^{\prime}_{i+(2m+1)(\delta+1)}$
(10.5)
$\displaystyle=(\vec{v}_{i+(2m+2)(\delta+1)}-\Delta^{\prime}_{i+(2m+1)(\delta+1)})-\Delta_{i+2m(\delta+1)}$
(10.6)
$\displaystyle\quad-\vec{v}_{i}+\Delta_{i+2m(\delta+1)}+\Delta^{\prime}_{i+(2m+1)(\delta+1)}$
(10.7) $\displaystyle=\vec{v}_{i+(2m+2)(\delta+1)}-\vec{v}_{i},$ (10.8)

where Equation (10.3) follows from applying the induction hypothesis, and
Equations (10.4) and (10.6) follow directly from applying Definition 30 to the
(block-length vector). $\vec{v}_{i+2m(\delta+1)}$ and then to the  (block-
length vector). $\vec{v^{\prime}}_{i+(2m+1)(\delta+1)}$. ∎

######  Claim 28.

If $\vec{v}$ and $\vec{v^{\prime}}$ are a pair of
(horizon).-$\delta\nameref{def:aligned}$ (block-length vector).s corresponding
to a  (temporally periodic configuration pair). of  (weakly stable).
configurations, then each of the pair’s two $(\delta+1)$-steps difference
vectors $\Delta$ and $\Delta^{\prime}$ are  (spatially periodic). with a
(spatial period). that divides $2\delta$. In other words, for every
$i\in{\mathbb{Z}_{k}}$,

$\displaystyle\Delta_{i}$ $\displaystyle=\Delta_{i+2\delta},$
$\displaystyle\Delta^{\prime}_{i}$
$\displaystyle=\Delta^{\prime}_{i+2\delta},$

where $k$ is the length of $\vec{v}$ and $\vec{v^{\prime}}$.

###### Proof.

By 25, for every $i\in{\mathbb{Z}_{k}}$,

$\displaystyle\vec{v^{\prime}}_{i}+\vec{v^{\prime}}_{i+1}=\vec{v}_{i-\delta}+\vec{v}_{i+\delta+1}.$

Hence,

$\displaystyle\vec{v}_{i+\delta+1}-\vec{v^{\prime}}_{i}=\vec{v^{\prime}}_{i+1}-\vec{v}_{i-\delta}.$

By definition, $\Delta^{\prime}_{i}=\vec{v}_{i+\delta+1}-\vec{v^{\prime}}_{i}$
and $\Delta_{i-\delta}=\vec{v^{\prime}}_{i+1}-\vec{v}_{i-\delta}$. Thus,

$\displaystyle\Delta^{\prime}_{i}$ $\displaystyle=\Delta_{i-\delta}.$ (10.9)

Similarly, also by 25, for every $i\in{\mathbb{Z}_{k}}$,

$\displaystyle\vec{v}_{i}+\vec{v}_{i+1}=\vec{v^{\prime}}_{i-\delta}+\vec{v^{\prime}}_{i+\delta+1},$

which means that

$\displaystyle\vec{v^{\prime}}_{i+\delta+1}-\vec{v}_{i}=\vec{v}_{i+1}-\vec{v^{\prime}}_{i-\delta}$

as well, and since $\Delta_{i}=\vec{v^{\prime}}_{i+\delta+1}-\vec{v}_{i}$ and
$\Delta^{\prime}_{i-\delta}=\vec{v}_{i+1}-\vec{v^{\prime}}_{i-\delta}$ we also
get

$\displaystyle\Delta_{i}$ $\displaystyle=\Delta^{\prime}_{i-\delta}.$ (10.10)

Combining equations (10.9) and (10.10) for $i+2\delta$ and for $i+\delta$,

$\displaystyle\Delta_{i+2\delta}$
$\displaystyle=\Delta^{\prime}_{i+\delta}=\Delta_{i},$
$\displaystyle\Delta^{\prime}_{i+2\delta}$
$\displaystyle=\Delta_{i+\delta}=\Delta^{\prime}_{i}.$

That is, the  (spatial period). of each of the vectors $\Delta$ and
$\Delta^{\prime}$ is at most $2\delta$. ∎

######  Claim 29.

Let $\vec{v}$ and $\vec{v^{\prime}}$ be a pair of length-$k$
(horizon).-$\delta$ (aligned). (block-length vector).s corresponding to a
(temporally periodic configuration pair). of  (weakly stable). configurations,
and let $\Delta$ and $\Delta^{\prime}$ be the pair’s two $(\delta+1)$-steps
difference vectors. For every $i\in{\mathbb{Z}_{k}}$, define

$\displaystyle\varsigma(i)=\sum_{j=0}^{2\delta-1}\Delta_{i+2j(\delta+1)}+\sum_{j=0}^{2\delta-1}\Delta^{\prime}_{i+(2j+1)(\delta+1)}.$

Then $\varsigma(i)=\varsigma(i^{\prime})$ for every pair
$i,i^{\prime}\in{\mathbb{Z}_{k}}$.

###### Proof.

We show that for every $i\in{\mathbb{Z}_{k}}$, the value of $\varsigma(i)$
does not depend on $i$.

$\displaystyle\varsigma(i)$
$\displaystyle=\sum_{j=0}^{2\delta-1}\Delta_{i+2j(\delta+1)}+\sum_{j=0}^{2\delta-1}\Delta^{\prime}_{i+(2j+1)(\delta+1)}$
(10.11)
$\displaystyle=\sum_{j=0}^{2\delta-1}\Delta_{i+2j}+\sum_{j=0}^{2\delta-1}\Delta^{\prime}_{i+2\delta+2j+1}$
(10.12)
$\displaystyle=\sum_{j=0}^{2\delta-1}\Delta_{i+2j}+\sum_{j=0}^{2\delta-1}\Delta_{i+2j+1}$
(10.13) $\displaystyle=\sum_{j=0}^{2\delta-1}\Delta_{i+j}$ (10.14)
$\displaystyle=\sum_{j=0}^{2\delta-1}\Delta_{j},,$ (10.15)

where:

  * –

Equation (10.12) follows from noting that, by 28, the vector $\Delta$ is
(spatially periodic). with a  (spatial period). that divides $2\delta$, so
$\Delta_{i+2j(\delta+1)}=\Delta_{i+2j}$ and
$\Delta^{\prime}_{i+(2j+1)(\delta+1)}=\Delta^{\prime}_{i+\delta+2j+1}$ for
every $0\leq j\leq 2\delta-1$.

  * –

Equation (10.13) follows from the observation that, by Equation 10.9 in the
proof of 28, $\Delta^{\prime}_{i+\delta+2j+1}=\Delta_{i+2j+1}$ for every
$0\leq j\leq m-1$.

  * –

Equation (10.14) follows from combining the two summations.

  * –

Equation (10.15) follows again from the property that the vector $\Delta$ is
(spatially periodic). with a  (spatial period). that divides $2\delta$ (28).

∎

##  11 The  (weakly stable). configurations are  (spatially periodic).

######  Claim 30.

The  (spatial period). of every  (weakly stable). configuration is at most
$2r(r+1)$.

###### Proof.

Let $\sigma,\sigma^{\prime}$ be a  (temporally periodic configuration pair).
of  (weakly stable). configurations, and let $\vec{v}$ and $\vec{v^{\prime}}$
be the corresponding  (aligned). (block-length vector).s. Let $k$ be the
length of $\vec{v}$ and $\vec{v^{\prime}}$ (which must be the same, by 20) and
let $\delta$ be their  (horizon). (which is constant, by 22).

Let $\Delta$ and $\Delta^{\prime}$ be the two $(\delta+1)$-steps difference
vectors of the pair $\vec{v},\vec{v^{\prime}}$. By 27, for every integer
$m\geq 0$,

$\displaystyle\vec{v}_{i}+\sum_{j=0}^{m-1}\Delta_{i+2j(\delta+1)}+\sum_{j=0}^{m-1}\Delta^{\prime}_{i+(2j+1)(\delta+1)}=\vec{v}_{i+2m(\delta+1)}.$
(11.1)

If we assign $m=2\delta$, by 29, the expression consisting of the two sums in
Equation (11.1) does not depend on $i$, so we denote that expression by
$\varsigma$. That is, for every $i\in{\mathbb{Z}_{k}}$,

$\displaystyle\vec{v}_{i}+\varsigma=\vec{v}_{i+2\delta(\delta+1)},$ (11.2)

Since $\vec{v}$ is a  (block-length vector)., the values in its entries are
bounded, and so it must be the case that $\varsigma=0$. Thus, for every
$i\in{\mathbb{Z}_{k}}$,

$\displaystyle\vec{v}_{i}$ $\displaystyle=\vec{v}_{i+2\delta(\delta+1)}.$

That is, the  (block-length vector). $\vec{v}$ is  (spatially periodic). with
(spatial period). at most $2\delta(\delta+1)$. By 23, the total length of
every sequence of $2\delta$ 1.7s in $\sigma$ is at most $2r$, and, by 21,
$\delta\leq r$, implying that the configuration $\sigma$ is  (spatially
periodic). with  (spatial period). at most $2r(r+1)$. ∎

##  12 Putting it all together: Proving Theorem 1

###### Proof of Theorem 1.

Let $\sigma:{\mathbb{Z}_{n}}\to\\{0,1\\}$ be any configuration, let
$\sigma^{\prime}={\textrm{MAJ}}_{r}(\sigma)$ and let
$\sigma^{\prime\prime}={\textrm{MAJ}}_{r}(\sigma^{\prime})$.

Suppose first that the configuration $\sigma$ is  (temporally periodic).. If
all the 1.1s in $\sigma$ are  (strongly stable)., then $\sigma$ is by
definition of the form $(0^{r+1}0^{*}+1^{r+1}1^{*})^{*}$, and by 7, it is a
(fixed-point).. Otherwise, still assuming that $\sigma$ is  (temporally
periodic)., it must be the case that $\sigma$ is  (weakly stable)., which
means that, by Corollary 2, all the 1.1s in $\sigma$ are  (weakly stable).,
and by 30, the configuration $\sigma$ is  (spatially periodic). with  (spatial
period). at most $2r(r+1)$.

Suppose now that the configuration $\sigma$ is  (transient).. By 9, the length
of every 1.7 in $B(\sigma)$ is at most $r$. We say that a  (cell interval).
$[i,j]\subseteq{\mathbb{Z}_{n}}$ is  (unstable). with respect to $\sigma$ if
for every $\ell\in[i,j]$, $\sigma(\ell)\neq\sigma^{\prime\prime}(\ell)$. We
claim that every  (unstable). (cell interval). with respect to $\sigma$
contains at most one  (Switch point)..

Suppose by way of contradiction that there exists an  (unstable). (cell
interval). with respect to $\sigma$ that contains at least two  (Switch
point).s. Let $(i,i+1)$ and $(j-1,j)$ be the first two  (Switch point).s in
the  (unstable). (cell interval). (without loss of generality, $(i,i+1)$ is to
the left of $(j-1,j)$ and there is no other  (Switch point). between them).
Hence, for some $\beta\in\left\\{0,1\right\\}$, it holds that
$\sigma(i)=\sigma(j)=\beta$, and for every $\ell\in(i,j)$,
$\sigma(\ell)=\bar{\beta}$.

Since $[i,j]$ is also an  (unstable). (cell interval)., it must be the case
that $\sigma^{\prime\prime}(i)=\sigma^{\prime\prime}(i+1)=\bar{\beta}$ and for
every $\ell\in(i,j)$, $\sigma^{\prime\prime}(\ell)=\beta$. Hence, both
$(i,i+1)$ and $(j-1,j)$ are  (Switch point).s in $\sigma^{\prime\prime}$. By
(The Switch Point Argument)., $\sigma^{\prime}(i+1+r)=\beta$ and
$\sigma^{\prime}(j+r)=\bar{\beta}$.

Let $\ell^{\prime}$ be the rightmost 1.1 in the open interval $(i+r,j+r)$
where $\sigma^{\prime}(\ell^{\prime})=\beta$. Since the pair
$(\ell^{\prime},\ell^{\prime}+1)$ constitutes a  (Switch point). in
$\sigma^{\prime}$, by  (The Switch Point Argument)., it must hold that
$\sigma(\ell^{\prime}-r)=\beta$. However, since $\ell^{\prime}-r\in(i,j)$
(because $\ell^{\prime}\in(i+1,j+r)$), we reach a contradiction to the
assumption that for every $\ell\in(i,j)$, it must hold that
$\sigma(\ell)=\bar{\beta}$.

Thus, every  (unstable). (cell interval). with respect to $\sigma$ contains at
most one  (Switch point)., which implies that the maximum possible length of
an  (unstable). (cell interval). is $2r$. ∎

## References

  * [BBDCM12] József Balogh, Béla Bollobás, Hugo Duminil-Copin, and Robert Morris.  The sharp threshold for bootstrap percolation in all dimensions.  Transactions of the American Mathematical Society, 364(5):2667–2701, 2012.
  * [FGW83] Françoise Fogelman, Eric Goles, and Gérard Weisbuch.  Transient length in sequential iteration of threshold functions.  Discrete Applied Mathematics, 6(1):95–98, 1983.
  * [FKR+03] Paola Flocchini, Rastislav Královič, Peter Ružička, Alessandro Roncato, and Nicola Santoro.  On time versus size for monotone dynamic monopolies in regular topologies.  Journal of Discrete Algorithms, 1(2):129–150, 2003.
  * [FKW13] Silvio Frischknecht, Barbara Keller, and Roger Wattenhofer.  Convergence in (social) influence networks.  In International Symposium on Distributed Computing, pages 433–446. Springer, 2013.
  * [GM13] Eric Goles and Servet Martinez.  Neural and automata networks: dynamical behavior and applications, volume 58.  Springer Science & Business Media, 2013.
  * [GO81] Eric Goles and Jorge Olivos.  Comportement périodique des fonctions à seuil binaires et applications.  Discrete Applied Mathematics, 3(2):93–105, 1981.
  * [GZ18] Bernd Gärtner and Ahad N Zehmakan.  Majority model on random regular graphs.  In Latin American Symposium on Theoretical Informatics, pages 572–583. Springer, 2018.
  * [GZ21] Bernd Gärtner and Ahad N Zehmakan.  Majority rule cellular automata.  Theoretical Computer Science, 889:41–59, 2021.
  * [MPGP17] Dieter Mitsche, Xavier Pérez-Giménez, and Paweł Prałat.  Strong-majority bootstrap percolation on regular graphs with low dissemination threshold.  Stochastic Processes and their Applications, 127(9):3110–3134, 2017\.
  * [Pel02] David Peleg.  Local majorities, coalitions and monopolies in graphs: a review.  Theoretical Computer Science, 282(2):231–257, 2002.
  * [PS83] Svatopluk Poljak and Miroslav Sura.  On periodical behaviour in societies with symmetric influences.  Combinatorica, 3(1):119–121, 1983.
  * [PW19] Pál András Papp and Roger Wattenhofer.  Stabilization time in minority processes.  arXiv preprint arXiv:1907.02131, 2019.
  * [TA04] Predrag T Tosic and Gul A Agha.  Characterizing configuration spaces of simple threshold cellular automata.  In International Conference on Cellular Automata, pages 861–870. Springer, 2004.
  * [TR11] Predrag T Tošic and Shankar NV Raju.  On convergence properties of one-dimensional cellular automata with majority cell update rule.  In Proceedings of International Conference on Scientific Computing, pages 308–314, 2011.
  * [Tur22] Volker Turau.  Fixed points and 2-cycles of synchronous dynamic coloring processes on trees.  arXiv preprint arXiv:2202.01580, 2022.
  * [Zeh19] Abdolahad N Zehmakan.  On the spread of information through graphs.  PhD thesis, ETH Zurich, 2019.
  * [Zeh20] Ahad N Zehmakan.  Opinion forming in ErdHos–Rényi random graph and expanders.  Discrete Applied Mathematics, 277:280–290, 2020.