We provide the conditions under which a cellular automaton defined by certain classes of non-linear local rules exhibits surjectivity and reversibility. For the latter, the condition turns out to be a characterization. We also analyze the role of permutivity as a key factor influencing these properties and provide conditions that determine whether a non-linear CA in such classes is (bi)permutive.
A cellular automaton (CA) is a discrete dynamical system consisting of a regular grid of cells where
each cell updates its own state according to a local rule on the basis of the states of the neighboring cells
and in a synchronous way with all the other cells, allowing complex global behavior of the system to
emerge from simple interactions. CA have been extensively studied from a theoretical point of view(see
for instance [
Among the diferent classes of CA, linear CA have received considerable attention due to their
wellunderstood algebraic structure and predictable behavior (see [
From a theoretical perspective, studying non-linear CA is compelling, as their non linearity introduces a level of dynamical complexity which is not present in their linear counterparts. This complexity opens new avenues for analysis and classification, and may reveal behaviors that are fundamentally diferent from those observed in well-studied classes. In addition, this complexity and unpredictability make non-linear CA promising candidates for applications where such properties are desirable - most notably in cryptography: while linear CA have already been employed in the construction of various cryptographic primitives, the potential of non-linear CA in this domain remains largely untapped.
In this paper we present the beginning of the theoretical study of a class of non-linear CA, starting
from classical results addressing the injectivity and surjectivity questions. It is widely acknowledged
that characterizing local rules which make a CA injective or surjective proves arduous in the unrestricted
case [
We stress that this short paper is an extended abstract of [
We start with some terminology from word combinatorics. An alphabet is a finite set of symbols, called letters. In this paper, we take = Z, the set of integers modulo . A finite word over an alphabet is a finite sequence of letters from . The length of a finite word , denoted by ||, is the number of letters it contains. The unique word of length 0 is called the empty word and is denoted by . A configuration (or bi-infinite word ) = . . . − 2− 1012 . . . over is an infinite concatenation of letters from indexed by Z. For integers ≤ , we denote by J,K = +1 · · · − 1 the subword of from position to , where J, K = [, ] ∩ Z; further, we will indicate by ∞ the constant word, i.e. the word constructed by concatenating the same letter infinitely many times. The set of all finite (resp. bi-infinite) words over is denoted by * (resp. Z), and for each ∈ N, the set of words of length is denoted by .
Formally, a CA is a map : Z → Z such that there exist an integer ≥ 0 and a local rule : 2 +1 → satisfying, for all ∈ Z and ∈ Z : () = (J− , + K). We refer to as the radius and = 2 as the diameter of the CA.
A distinct and particularly relevant class of CA are the so-called permutive CA. We say that a CA of diameter and local rule is permutive at position (with 1 ≤ ≤ + 1) if, for every ∈ − 1, every ∈ − +1, and every ∈ , there exists a unique ∈ such that () = . In other words, when all variables except the -th are fixed, the function acts as a permutation in the -th variable. In particular, if = 1 (respectively, = + 1), we say that is left (respectively, right) permutive. A CA is said to be bipermutive if it is both left and right permutive, and simply permutive if it satisfies at least one of these conditions. According to [14, Proposition 5.22], every permutive CA is surjective.
We now turn our attention to an algebraic notion and a result which we will rely on in the upcoming
results. Recall that the Euler’s totient function [
() = #{ ∈ Z such that 1 ≤ ≤ and gcd(, ) = 1}.
Also, recall that every function from a finite field F to itself can be represented as a polynomial over F.
As mentioned in the introduction, to manage the complexity of non-linear local rules, we narrow our attention to a specific class of non-linear CA defined by a local rule such that is a multivariate polynomial with (at least) one variable separated from the others. We end this section by introducing this notion, which we will rely on in the remainder of the paper.
Definition 1. of the form:
(1, . . . , +1) = + (1, . . . , − 1, +1, . . . , +1), 1. We say that is separated in position , or simply -separated. 2. If = ℓ (resp. = ), where ℓ (resp. ) is the leftmost (resp. rightmost) non-zero coeficient, then is said to be leftmost (resp. rightmost) separated.
+1 (1, . . . , +1) = ∑︁ , =1
the following forms: 1. (1, . . . , +1) = ℓℓℓ , in which case ℓ = and is said to be shift-like. 2. (1, . . . , +1) = ℓℓℓ + (ℓ+1, . . . , − 1) + , where 1 ≤ ℓ < ≤ + 1, such that ℓ (resp. ) is the leftmost (resp. rightmost) non-zero coeficient, and : Z− ℓ− 1 → Z is an arbitrary map.
Notice that in both cases it is possible to write (1, . . . , +1) = ℓℓℓ + (ℓ+1, . . . , − 1) + with : Zℎ → Z, where ℎ = max{0, − ℓ − 1}.
It is also important to stress that this work focuses on the case = Z with ≥ 3, as the case
= 2 corresponds to linear CA, which have already been extensively studied in the literature (see, for
example, [
Among non-linear CA, a particularly notable subclass is that of quadratic CA. It directly turns out that no quadratic CA can be surjective over a finite field Z.
form on Z+1 (i.e. () = 2 () for any ∈ Z+1 and ∈ Z, and, the map (, ) ↦→ ( + ) − () − () is bilinear form that is linear in each argument separately).
Lemma 1. Let be a totally separated CA over the finite field i.e. the local rule is given by +1 (1, . . . , +1) = ∑︁ , =1 where each ∈ Z. If every is an even positive integers for all ∈ J1, + 1K, then the global map is not surjective.
We can specialize Lemma 1 to the context of quadratic local rules, yielding a corresponding result for quadratic CA.
Corollary 1. There is no surjective quadratic CA over Z for any prime ≥ 3.
Corollary 2. Let be a totally separated CA over Z for any prime ≥ 3. If the powers ’s are all even positive integers, then is not injective.
Z, where is prime number with ≥ 3,
In this section, we focus on the study of the permutivity property of non-linear -separated CA.
its local rule can be written as
(1, . . . , +1) = + (1, . . . , − 1, +1, . . . , +1), where ∈ Z is invertible and : Z → Z is any map.
It holds that is permutive in position if and only if gcd(, ()) = 1.
position if and only if gcd(, − 1) = 1, since () = − 1 for prime.
It was shown by Hermitein [
Hermite’s criterion can be simplified in the context of the finite field on elements Z [
(1, . . . , +1) = ( ) + (1, . . . , − 1, +1, . . . , +1), where () ∈ Z[] is a polynomial and is any map : Z → Z. Then is permutive in position if and only if deg( ) < and gcd( ′(), − ) = 1.
We now provide some alternative characterization results on surjectivity for the class of -separated
CA. We start by recalling some useful facts from [
Definition 3 ([20, Def. 8.2.1]). Let F be the finite field with elements. A polynomial ∈ F[1, ..., ] is a permutation polynomial in variables over F if the equation (1, ..., ) = has exactly − 1 solutions in F for each ∈ F.
Theorem 1 ([20, Theorem 8.2.9]). Let ∈ F[1, ..., ] be of the form (1, ..., ) = (1, ..., ) + ℎ(+1, ..., ), 1 ≤ < .
The following is a direct consequence of the results above.
Proposition 2. Let be a -separated CA with local rule over Z, for any prime ≥ 3 and let ℓ (resp. ) be the leftmost (resp. rightmost) position of .
if and only if gcd(ℓ, − 1) = 1 or gcd(, − 1) = 1. 2. If is a totally separated surjective CA, then there is at least one ∈ Jℓ, K such that gcd( , − 1) = 1.
The following result is a direct consequence of Lemma 2 and provides a partial characterization of surjective -separated CA.
Theorem 2. Let be a -separated CA over the finite ring Z, for any integer ≥ 3, and let ℓ (resp. ) be the leftmost (resp. rightmost) position of . If either gcd(ℓ, ()) = 1 or gcd(, ()) = 1, then is surjective.
This section is devoted to the study of reversibility for -separated CA. The following results hold. Theorem 3. Let be a -separated CA with diameter = 2 and local rule over Z, for any integer ≥ 3, and let ℓ (resp. ) be the leftmost (resp. rightmost) position of . Then is injective if and only if ℓ = and gcd(ℓ, ()) = 1.
Remark 4. As in the case of Proposition 2, if is a prime number, then, is injective if and only if ℓ = and gcd(ℓ, − 1) = 1.
Corollary 3. Let be a -separated CA over Z, where is an integer with ≥ bijective if and only if ℓ = and gcd(ℓ, ()) = 1. 3. Then is Example 1. Let be a CA with local rule: (, , ) = 4 + 3 mod 7. The global rule is not injective since ((56)∞) = ((43)∞) = (62)∞. However, () = 4 + 3 mod 7, is a permutation polynomial over Z7.
Example 2. Let be a CA with local rule: (, , ) = 3 + 2 + 2 mod 5. The global rule is not injective since ((10)∞) = ((3)∞) = 2∞. We can take also ((30)∞) = ((41)∞) = (34)∞. However, () = 3 + 2 + 2 mod 5, is a permutation polynomial over Z5 (even it is the sum of two non permutation polynomials 1() = 3 + 2 mod 5 and 2() = 2 mod 5).
In this work, we analyzed the structural properties of non-linear CA, focusing on permutivity, surjectivity, and reversibility. We introduced the class of -separated non-linear CA and provided conditions for the above mentioned properties in this class of CA.
Our findings show that permutivity plays a central role in determining surjectivity and reversibility. Specifically, we provided a condition under which a -separated nonlinear CA is surjective. Additionally, we stated that reversibility is equivalent to the CA being surjective and with local rule depending only on one variable. These results contribute to a deeper understanding of non-linear CA dynamics and provide a framework for identifying their computational potential.
Beyond theoretical results, we presented illustrative examples to clarify the interplay between permutivity, surjectivity, and reversibility.
We conclude by proposing some questions, related to the above discussion, that we find particularly interesting and worth exploring: 1. What is the complete characterization of surjectivity for LR-separated non-linear CA over Z with ≥ 3? 2. What can be said about the dynamical properties (like sensitivity to the initial conditions, topological transitivity, chaos, etc.) for some classes of non-linear CA? 3. In this work we focused on uniform CA, meaning all local interactions are determined by the same rule. How do our results transform in the case of non-uniform CA (i.e. a CA allowing diferent local rules)?
This work was supported by the HORIZON-MSCA-2022-SE-01 project 101131549 “Application-driven Challenges for Automata Networks and Complex Systems (ACANCOS)” and by the PRIN 2022 PNRR project “Cellular Automata Synthesis for Cryptography Applications (CASCA)” (P2022MPFRT) funded by the European Union – Next Generation EU.
The author(s) have not employed any Generative AI tools.