{'fraction_non_alphanumeric': 0.06065459981846334, 'fraction_numerical': 0.01505686368732981, 'mean_word_length': 3.717884130982368, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 27, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Number-conserving cellular automata with a von Neumann neighborhood of range one

We present necessary and sufficient conditions for a cellular automaton with a von Neumann neighborhood of range one to be number-conserving. The conditions are formulated for any dimension and for any set of states containing zero. The use of the geometric structure of the von Neumann neighborhood allows for computationally tractable conditions even in higher dimensions.


Introduction
This paper focuses on d-dimensional cellular automata (CAs) that possess the most popular additive invariant, namely the sum of the states of all cells. This kind of CA, called number-conserving, has been introduced by Nagel and Schreckenberg [1] in the early nineties and has received ample attention in the literature, especially as a model of a system of interacting particles moving in a lattice. In particular, such CAs occur naturally in the context of highway traffic [2][3][4] and fluid flow [5]. In one dimension, necessary and sufficient conditions for a CA to be number-conserving are given by Boccara and Fukś in [6] for two states (Q = {0, 1}) and in [7] for q states (Q = {0, 1, . . . , q − 1}). The formulas in these works can be also derived from the Hattori and Takesue theorem [8] concerning general additive conserved quantities. The approach of Boccara and Fukś allows to enumerate all number-conserving one-dimensional CAs in the case of few states and a small neighborhood.
Durand et al. [9] state necessary and sufficient conditions for a CA to be number-conserving in two or more dimensions for q states (Q = {0, 1, . . . , q − 1}). They also formalized three notions of number conservation (periodic, finite, infinite) and proved their equivalence. These results were obtained for product neighborhoods, so it is universal and shows, for example, that number conservation is a decidable property (provided that the number of states is finite). Moreira [10] extended the work of Durand et al. to any finite subset of Z as set of states. Unfortunately, the formulas in [9] and [10] are too complicated to be effective in enumerating all number-conserving two-or higher-dimensional CAs, even in the case of two states. Furthermore, in these approaches a CA with the von Neumann neighborhood was considered as a CA with the Moore neighborhood, which implies an unnecessary complication and strongly increases the computational complexity.
Tanimoto and Imai [11] provided a characterization of two-dimensional number-conserving CAs with the von Neumann neighborhood. Their result is stated in terms of some flow functions (in the vertical, horizontal and diagonal direction), and allows, for example, to prove facts about rotation-symmetric CAs. They showed that rotation-symmetric number-conserving CAs with at most four states are trivial and also gave a full characterization of five-state rotation-symmetric number-conserving CAs.
In this paper, we restrict our attention to the simplest but most commonly used neighborhood: the von Neumann neighborhood of range one, referred to as "the von Neumann neighborhood" for the sake of simplicity. We formulate necessary and sufficient conditions for d-dimensional CAs with the von Neumann neighborhood to be number-conserving in a way similar as in [7]. The conditions apply for any state set (finite or not), but for our convenience, we assume that the set of states includes 0. In fact, the only property of 0 we use is its quiescence, so 0 can be replaced by any other state, since all states of a number-conserving CA are quiescent (see Lemma 3.1). The form of our characterization allows to enumerate all number-conserving d-dimensional CAs in the case of few states and small d.
This paper is organized as follows. In Section 2 the basic concepts and notations are introduced. Section 3 presents the necessary and sufficient conditions for a two-dimensional CA to be numberconserving, while the higher-dimensional case is considered in Section 4. Presenting the results in this way, guarantees that they are accessible for any reader. The final section summarizes the main results and gives some hints for further research.

Preliminaries
In this section, we introduce CAs and recall some results that we will use in the following sections. To define a CA, one needs to specify a space of cells, a neighborhood and a local rule.

The cellular space
Let us fix the dimension d ≥ 1 and consider natural numbers n 1 , n 2 , . . . , n d greater than 4. We consider the cellular space as a grid with periodic boundary conditions, defined by With this notation, each cell i ∈ C is a d-tuple (i 1 , . . . , i d ), where i k ∈ Z/n k Z. In the case d = 2, we prefer to denote cells by (i, j) rather than (i 1 , i 2 ). Denoting the number of elements of a set A as |A|, we have |C| = n 1 · n 2 · . . . · n d .
Due to the periodic boundary conditions, each cell in C has exactly 2d adjacent cells: two in each of the orthogonal axis directions. For example, if d = 2, then there are four adjacent cells: two in the horizontal direction, − → v 1 (right) and -− → v 1 (left), and two in the vertical direction, − → v 2 (up) and -− → v 2 (down), as shown in Fig. 1(a). If d = 3, then there are two additional adjacent cells: in the directions − → v 3 (forward) and -− → v 3 (backward), as shown in Fig. 1 To be able to describe the situation in general, i.e. for any dimension d, we introduce the following notation. For each k ∈ {1, 2, . . . , d}, we define the vector − → v k = (0, 0, . . . , 0, 1, 0, . . . , 0) ∈ R d , where the k-th component is equal to 1 and all others are equal to zero. Let us denote the set of all considered directions as V + , i.e.
Additionally, let

The neighborhood
As we mentioned in Section 1, we only consider the von Neumann neighborhood. For each cell i ∈ C, its von Neumann neighborhood P (i) consists of the cell i and its 2d adjacent cells: This neighborhood can be described using the Manhattan distance defined by where i = (i 1 , i 2 , . . . , i d ) ∈ C and j = (j 1 , j 2 , . . . , j d ) ∈ C. From this point of view, the von Neumann neighborhood P (i) consists of those cells whose distance from i is not greater than 1, i.e.
We now describe some relations between P (i) and P (j) in case i = j.
First of all, we observe that if dist(i, j) > 2, then P (i) ∩ P (j) = ∅. Indeed, if there is some cell l ∈ P (i) ∩ P (j), then dist(i, l) ≤ 1 and dist(j, l) ≤ 1, which implies that dist(i, j) ≤ dist(i, l) + dist(l, j) ≤ 2. Secondly, if dist(i, j) = 1, then cells i and j are adjacent. Hence, j ∈ P (i) and i ∈ P (j) and there are no other cells in P (i) ∩ P (j), which implies that Finally, the case dist(i, j) = 2 is the most interesting one. The size of P (i) ∩ P (j) depends on the relative positions of i and j, as we can either move from i to j in two steps in the same direction or one step in one direction and a second step in some orthogonal direction. Hence, there are two cases: In this case, The following lemma summarizes these observations.
(d) In all other cases, it holds that P (i) ∩ P (j) = ∅.
We now define the set Ω, containing all possible pairs of vectors from V + used in Lemma 2.1 in the descriptions of P (i) ∩ P (j) in cases (a) and (c). Thus Ω consists of pairs while if d = 3, it holds that |Ω| = 18: (3) From Lemma 2.1, we deduce the following.
Obviously, different pairs in Ω have different matching pairs. If from each of the d 2 pairs of matching pairs we select one pair, then we obtain a set denoted by Λ. We can construct Λ in 2 d 2 ways, but it always holds that |Λ| = d 2 .

The configuration space
Here, we consider an arbitrary non-singleton set Q ⊆ R containing zero and define Q + := Q \ {0}. By a configuration, we mean any mapping from the grid C to Q. The set of all possible configurations is denoted by X = Q C . The state of cell i in a configuration x ∈ X is denoted by Given a configuration x ∈ X, we define the sum of the states in x as:

The set of neighborhood configurations
By the set of all possible neighborhood configurations N , we mean the set of all functions N : If N is identically equal to zero, then we call it trivial. As the set V has 2d + 1 elements, . In the two-dimensional case, for mnemotechnical reasons, we represent N as In this way, the set N can be defined as For d = 3, we similarly have Let q ∈ Q. By H q we denote the homogeneous neighborhood configuration, i.e.
Let − → v ∈ V and q ∈ Q be given. By M− → v :q we denote the neighborhood configuration which differs denotes the neighborhood configuration that takes the value p in direction − → u , the value q in direction − → w and zero in the other directions, i.e.
If x ∈ X and i ∈ C are given, then N x,i denotes the configuration of the von Neumann neighborhood of cell i in the configuration x, i.e.

Local and global rules
all other values to zero. Thus, in the monomer expansion, the neighborhood configuration is decomposed into monomers, the local rule f is applied to each monomer separately the resulting valued are added. For example, if d = 2, then we have Similarly, in the d-dimensional case, we have for any ( − → u , − → w ) ∈ Ω and any p, q ∈ Q.
Any local rule f induces a global rule F as follows Having introduced the required notations, we now define a number-conserving rule.

Definition 2.3
A local rule f is called number-conserving if its corresponding global rule F conserves the sum of states, i.e. for each x ∈ X it holds that σ(F (x)) = σ(x).

Number-conserving CAs for d = 2
In order to introduce our main ideas and rationale, we first describe the two-dimensional case. In Section 4, we will show how our arguments extend to arbitrary dimension.

Basic properties
We first establish three simple, but useful facts.
Lemma 3.1 If a local rule f is number-conserving, then each state is quiescent, i.e. for any q ∈ Q, it holds that f q q q q q = q .
Proof. Consider a homogeneous configuration q in which all cells have state q. Then σ(q) = |C| · q, while it is immediately clear that σ (F (q)) = |C| · f q q q q q , where F is the corresponding global rule. Since F conserves the sum of states, our statement follows.

Lemma 3.2
If a local rule f is number-conserving, then for any q ∈ Q, it holds that f E q q q q q = q, i.e.
Proof. From Lemma 3.1, we know that f The following lemma concerns the relationships between the values of the matching dimers.

Lemma 3.3
If a local rule f is number-conserving, then for any q 1 , q 2 ∈ Q, the following equalities hold Proof. Each of the above equalities is easy to show if one considers a properly chosen configuration (see Fig. 2) and relies on Lemma 3.2. Indeed, if we denote the configuration shown in Fig. 2(a) by x, then from σ(x) = σ (F (x)), it follows that From Lemma 3.2, we know that and Combining Eqs. (11) One can see that the terms in the right-hand sides of Eqs.

Necessary and sufficient conditions
Using the lemmas presented in Section 3.1, we can prove the main theorem for d = 2.

Theorem 3.4
A local rule f is number-conserving if and only if for any q 1 , q 2 , q 3 , q 4 , q 5 ∈ Q, it holds that Proof: To show that Eq. (14) is necessary, let us consider the configuration in Fig. 3. Suppose that f is number-conserving, then it holds that As expected, in the right-hand side of Eq. (15) we retrieve eight dimers, because there are exactly eight pairs in Ω. Now, for every two matching pairs we select one such that Using Lemma 3.3, we represent the dimers for the pairs not present in Λ in terms of their matching dimers: Conversely, one can easily see that Eq. (14) is sufficient, but we give a detailed proof for the sake of completeness. Let us assume that Eq. (14) holds and let x be any configuration. Then it holds that .
(17) It is obvious that assuming periodic boundary conditions. Thus, we get that and likewise all terms of type [. . . − . . .] are equal to 0. Moreover, following the same reasoning, we see that .
Using these equalities in Eq. (17), we obtain which implies that f is number-conserving.
We remark that one can formulate Theorem 3.4 in at least different 5 · 2 4 ways. Firstly, one should choose an entry q i as the leading term, after which one has to select terms with two nonzero entries to expand using Lemma 3.3. Then, one has to fill the right-hand side with monomers to match the monomer expansion of the left-hand side. An example of an alternative formula with q 3 as the leading term reads: One can see that this expression contains more terms than Eq. (14).

Corollary 3.5
To define a number-conserving rule, it is sufficient to specify its values for nontrivial monomers and dimers for pairs belonging to Λ. If for any q 1 , q 2 , q 3 , q 4 , q 5 ∈ Q, the value of the right-hand side of Eq. (14) belongs to Q, then this rule is number-conserving. 4 The case of an arbitrary dimension d

Basic properties
In this section, we consider an arbitrary dimension d and we establish necessary and sufficient conditions for CAs with the von Neumann neighborhood to be number-conserving. We formulate the conditions in terms of the local rule of the given CA.
Analogously to the case d = 2, we start by showing the following lemma, which is the d-dimensional counterpart of Lemmata 3.1 and 3.2.

Lemma 4.1
If a local rule f is number-conserving, then each state is quiescent, i.e. for any q ∈ Q, it holds that f (H q ) = q. Moreover, f E (H q ) = q.
Proof: The first statement is well known and can be shown by considering a homogeneous configuration x, in which every cell has state q. To prove the second one, let us consider a configuration x in which only one cell has state q and the other ones have state 0: Obviously, σ(x) = q. Note that if 0 ∈ P (i), then the neighborhood configuration N x,i is trivial, while if 0 ∈ P (i), then the neighborhood configuration N x,i is a monomer. Moreover, if P (i) contains 0, then it holds that 0 As σ(x) = σ(F (x)), we obtain our claim.
The following fact concerns properties of pairs of matching dimers. For d = 2, we listed all four equations in Lemma 3.3. Here we write d 2 equations as a single one using the dimer notation.

Lemma 4.2
If a local rule f is number-conserving, then for any ( − → u , − → w ) ∈ Ω and any p, q ∈ Q, it holds that Proof: Let { − → u , − → w } ∈ Ω and p, q ∈ Q. Further, we consider the following configuration x: Clearly, σ(x) = p + q. If neither 0 + − → u , nor 0 + − → w belongs to P (i), then N x,i is trivial, so it suffices to consider the following 3 cases: (a) 0 + − → u ∈ P (i) and 0 + − → w ∈ P (i): in this case, N x,i is a monomer, where we used the fact that the monomer expansion of a dimer is given by Eq. (4). As σ(x) = σ(F (x)) = p + q, the above collapses to Eq. (20).

Necessary and sufficient condition
The following theorem presents one of (2d + 1) · 2 d 2 possible formulations of necessary and sufficient conditions for a local rule to be number-conserving. This is because we have 2d + 1 possibilities for choosing the leading term ( − → η below) and 2 d 2 possibilities for choosing Λ.
Proof: It is easy to see that this condition is sufficient. Indeed, consider the grid C and an arbitrary configuration x. Now, it is enough to fix − → η ∈ V , write Eq. (26) for each neighborhood configuration N x,i and combine the expressions. Doing so, on the left-hand side, we obtain σ(F (x)), while on the right-hand side the dimers cancel out analogously to the case d = 2 (see how Eq. (17) implies Eq. (18)). For monomers, it suffices to check that their number with a positive sign in , which equals 2d(2d + 1), equals the number of monomers with a minus sign, which equals d 2 · (2 + 2) + 2d. Hence, we obtain σ(x) on the right-hand side.
To prove that Eq. (26) is necessary, let us fix N ∈ N and consider the configuration x defined by Note that N x,0 = N . By Lemma 4.1, it follows that for any − On the other hand, as configuration x is zero outside P (0), from Lemma 2.1 we obtain In view of Remark 2.2, if |P (i) ∩ P (0)| = 2, then there exists a unique pair ( − → u , − → w ) ∈ Ω such that . Hence, for a given Λ, we have while from Lemma 4.2, we have that for any ( − → u , − → w ) ∈ Ω: any q 1 , q 2 , q 3 , q 4 , q 5 , q 6 , q 7 ∈ Q, it holds that f q 1 q 7 q 2 q 3 q 4 q 6 q 5 = q 1 + f Although this formula is rather lengthy, it is much simpler than conditions presented by other authors (cf. [9] and [11]). In three dimensions, there are 13 number-conserving rules if Q = {0, 1}. It means they are extensions of one-dimensional elementary rules equivalent to the identity rule (ECA 204 according to the classical enumeration in [12]), the shift rule (ECA 170), or the traffic rule (ECA 184), acting in each of the six possible directions.

Conclusions
In this work, we have studied d-dimensional CAs with the von Neumann neighborhood. We have presented necessary and sufficient conditions for the local rule of such CA to be number-conserving. The greatest advantage of these conditions is that their form not only allows to decide whether a given rule is number-conserving, but also to enumerate all number-conserving rules for not too large d and small |Q|. This is due to the fact that we do not have to consider every rule from a huge space of |Q| |Q| 2d+1 possible rules one by one, but only need to set at most (2d + 1) · (|Q| − 1) monomers and d 2 (|Q| − 1) 2 dimers and then verify whether the values given by Eq. (26) belong to Q for any q 1 , q 2 , q 3 , q 4 , q 5 ∈ Q.
This method is especially useful to describe number-conserving rules satisfying some additional conditions -in particular in cases where these additional conditions result in dependencies between monomers or dimers. This happens, for example, in the case of local rules with some kind of symmetry, the most natural one being rotation symmetry. Rotation-symmetric number-conserving CAs (RNCAs) were studied in [11] and [13], where it was shown that there is no nontrivial CA that is number-conserving when |Q| ≤ 4. Furthermore, all RNCAs with 5 states were described. These results, obtained with a considerable effort, now are a simple consequence of Eq. (14). Moreover, using Eq. (14), we can find all rotation-symmetric number-conserving CAs with six or even seven states. Perhaps, one may find strongly universal automata among the newly described rules (all RNCAs with 5 states are not strongly universal).
Another type of local rules that are very interesting are passive rules, i.e. rules that satisfy the condition that if a cell is surrounded by zero state cells, then its state does not change. In other words, cells are passive and change their value only when at least one of the neighbors has a nonzero state. Since this condition can be easily described in terms of constraints on monomers, it is