Florian Bridoux

Maximilien Gadouleau

Guillaume Theyssier

Expansive Automata Networks $

Keywords: Automata networks, expansivity, MDS codes, PSPACE-completeness

An Automata Network is a map f : Q n → Q n where Q is a finite alphabet. It can be viewed as a network of n entities, each holding a state from Q, and evolving according to a deterministic synchronous update rule in such a way that each entity only depends on its neighbors in the network's graph, called interaction graph. In this work we introduce the following property called expansivity: the observation of the sequence of states at any given node is sufficient to determine the initial configuration of the whole network. A major trend in automata network theory is to understand how the interaction graph affects dynamical properties of f . Our first result is a characterization of interaction graphs that allow expansivity. Moreover, we show that this property is generic among linear automata networks over such graphs with large enough alphabet. We show however that the situation is more complex when the alphabet is fixed independently of the size of the interaction graph: no alphabet is sufficient to obtain expansivity on all admissible graphs, and only non-linear solutions exist in some cases. Besides, we show striking differences between the linear and the general non-linear case, in particular we prove that deciding expansivity is PSPACE-complete in the general case, while it can be done in polynomial time in the linear case. Finally, we consider a stronger version of expansivity where we ask to determine the initial configuration from any large enough observation of the system. We show that it can be achieved for any number of nodes and naturally gives rise to maximum distance separable codes.

Introduction

Networks of interacting entities can be modelled as follows. The network consists of n entities, where each entity v has a local state represented by a q-ary variable x v ∈ vqw = {0, 1, . . . , q -1}, which evolves according to a deterministic function f v : vqw n → vqw of all the local states. More concisely, the configuration of the network is x = (x 1 , . . . , x n ) ∈ vqw n , which evolves according to a deterministic function f = (f 1 , . . . , f n ) : vqw n → vqw n . The function f , which encodes everything about the network, is referred to as an Automata Network, or simply network (the term Finite Dynamical Systems has also been applied for these networks). When speaking about properties of an automata network (like bijectivity), we mean a property of the function f . Automata networks have been used to model different networks, such as gene networks, neural networks, social networks, or network coding (see [START_REF] Gadouleau | Simple dynamics on graphs[END_REF] and references therein for the applications of Automata networks). They can also be considered as a distributed computational model with various specialized definitions like in [START_REF] Wu | Cellular graph automata. i. basic concepts, graph property measurement, closure properties[END_REF][START_REF] Wu | Cellular graph automata. ii. graph and subgraph isomorphism, graph structure recognition[END_REF]. The architecture of an Automata network f : vqw n → vqw n can be represented via its interaction graph, which indicates which update functions depend on which variables. In other words, the interaction graph represents the underlying network of entities and their influences on one another. A major topic of interest is to determine how the interaction graph affects different properties of the network, such as the number of fixed points or images (see [START_REF] Gadouleau | On the influence of the interaction graph on a finite dynamical system[END_REF] for a review of known results on the influence of the interaction graph). In particular, a stream of work aims to design networks with a prescribed interaction graph and with a specific dynamical property, such as a being bijective [START_REF] Gadouleau | On the rank and periodic rank of finite dynamical systems[END_REF], or having many fixed points [START_REF] Gadouleau | Graph-theoretical constructions for graph entropy and network coding based communications[END_REF], or converging towards a fixed point [START_REF] Gadouleau | Simple dynamics on graphs[END_REF].

In this paper, we introduce the concept of expansive networks. A network is expansive if the initial configuration of the network can be determined from the future temporal evolution of any local state. Formally, if f t v denotes the map x → (f t (x)) v , f is expansive if it satisfies the equivalent conditions:

1. For any v ∈ {1, . . . , n}, there exists a natural number T such that the function x → (f v (x), . . . , f T v (x)) : vqw n → vqw T is injective.

2. For any v ∈ {1, . . . , n} and any distinct x, y ∈ vqw n , there exists t ≥ 1 such that f t v (x) = f t v (y).

We are mostly interested in general results on automata networks per se, without any particular application in mind. Nonetheless, as mentioned above, automata networks are versatile and can be seen and used from different points of view. The concept of expansive automata networks introduced here is meaningful for several of them.

Dynamical systems. The term 'expansive' is coined after the classical notion of dynamical system theory which corresponds to a strong form of topological unpredictability [START_REF] Utz | Unstable homeomorphisms[END_REF]. In the case of cellular automata [START_REF] Kůrka | Topological and symbolic dynamics[END_REF], this topological notion has a concrete interpretation in terms of traces: the orbit of the whole system can be deduced from its temporal trace on a limited spatial region (there is a similar notion in the field of symbolic dynamics [START_REF] Boyle | [END_REF]). The definition above follows the same idea and in fact there is a precise correspondence between expansivity in cellular automata and expansivity in automata networks (see section 2.2). Recall that a finite deterministic system has an eventually periodic behavior and one could naively object that they are therefore always "simple" dynamically. Of course, finite doesn't mean small and the period can be exponentially large in the size of the system, making the previous objection largely inoperative in practice. Beyond this matter of size, we stress that the definition of expansivity above does represent a form of unpredictability in the following sense: a partial knowledge of the initial configuration (the state of at least one node is not completely known) is never sufficient to determine the orbit observed at a node (for any node). Said differently, although perfectly deterministic by definition, the system always behaves non-deterministically as soon as there is some imprecision in the initial conditions.

Modeling tool and control theory. With the general point of view of modeling in mind, one is interested in making predictions on the future of a system from partial observations. In particular some components of the systems might be difficult or impossible to observe. Expansive automata network correspond to a favorable case where observing any single component for some time is sufficient. It is also interesting to relax the kind of observations allowed on the system, like in the stronger form of expansivity we consider in section 8. In the context of control theory, the well-established notion of observability (R. Kalmanin, 1960s) corresponds to systems whose internal state can be determined by the observation of its output (see e.g. [START_REF] Collins | Observability of hybrid systems and turing machines[END_REF][START_REF] Laschov | Observability of boolean networks: A graph-theoretic approach[END_REF] for different settings which are relevant in computer science). In this context, one is interested in determining whether a given system is observable or not. Expansivity can be seen as a form of observability if we consider that the output of our system is the trace at some node. Control theory was largely developed for linear systems and observability is well-understood and easy to determine in this case. The situation is similar for expansivity in our setting (see sections 2 and 3). In the non-linear case, testing these properties is hard and hardness results on expansivity are actually hardness results for the problem of observability in automata networks (see section 7).

Orthogonal arrays and maximum distance separable code. In an expansive automata network, the orbit of any configuration contains a lot of redundancy because knowing T consecutive states of any given node is sufficient to reconstruct the complete orbit. Pushing this idea further we obtain a stronger form of expansivty in section 8 which yields orthogonal arrays of index unity or equivalently maximum distance separable codes (see [START_REF] Hedayat | Orthogonal Arrays[END_REF][START_REF] Macwilliams | The Theory of Error-Correcting Codes[END_REF]). More precisely the set of orbits of a certain length is the code, and, in the linear case, it can be compactly represented by just giving the global map f of the automata network.

Distributed computation. An expansive automata network can be seen as a distributed protocol which solves the problem of giving the knowledge of the whole network's configuration to each of its entities, and that works for any initial condition of the system. Moreover, if the constant T in Property 1 above is optimal, i.e. equal to n, then the automata network has another interesting algorithmic property: initial configurations (n states) are mapped bijectively to sequences of states of length n at each node. Said differently, it gives a protocol to transform a random initial configuration to a temporal random sequence of states at each node (with the uniform distribution in both cases). Such expansive networks with optimal constant T exist as we show below.

Our main contributions. First, in section 3, we study the existence of expansive networks depending on the interaction graph. We characterize the graphs that admit an expansive network over some alphabet (Theorem 3.7): those are the graphs that are strongly connected (there is a path from any vertex to any other vertex) and coverable (the vertices can be covered by disjoint cycles). We show in particular that for such graphs, almost all linear networks over sufficiently large fields are expansive (Corollary 3.12). Second, in section 4, we focus on the non-existence of expansive networks over small alphabets. We show that for any fixed alphabet size q, there exist strongly connected and coverable graphs that do not admit any expansive network over vqw (Theorem 4.1). We also exhibit a graph which admits an expansive network over all alphabets, but does not admit any linear expansive network for an infinite number of alphabet values (Proposition 4.4). Then, in section 5, we focus on the minimum time T (f ), referred to as the expansion time, for which any difference between distinct configurations has been witnessed on all vertices. We notably prove that the expansion time can vary from n to almost q n , and that the minimum of n is achieved by linear networks over fields (Theorem 5.4). In section 6, we consider the average number of differences between two orbits, called expansion frequency. We show that it can be arbitrarily close to 1 (Theorem 6.1) while previous section gave a construction showing that it can be arbitrarily close to 0. In section 7, we consider the decision problem of whether a given network is expansive. We prove that it is a PSPACE-complete problem (Theorem 7.7). Finally, in section 8, we consider a stronger notion of expansivity which asks to recover the initial configuration from any large enough observation of the system (not only the trace at a given node). We show that automata networks with that property yield maximum distance separable codes (Proposition 8.3) and exist on any complete interaction graph (Theorem 8.2), while they require an alphabet quadratic in the number of nodes (Corollary 8.4).

Definitions and preliminary results

Graphs. A (directed) graph is a pair D = (V, E), where E ⊆ V 2 . For concepts about graphs, the reader is referred to the authoritative book [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF]. Let us simply highlight some concepts and their notation in this paper. For any graph D = (V, E) and any set of vertices S ⊆ V , we denote the out-neighbourhood of S as N out (S) = {u ∈ V : ∃s ∈ S s.t. su ∈ E}; the in-neighbourhood is defined similarly and is denoted as N in (S). An arc of the form uu for some u ∈ V is called a loop. A graph is loop-full if there is a loop on each vertex. For any two vertices u, v ∈ V , the distance from u to v in D is the length of a shortest path from u to v in D; it is denoted as d D (u, v). The adjacency matrix of D,

denoted A D is the n × n matrix A D with A D (i, j) = 1 if ij ∈ E and A D (i, j) = 0 otherwise.
Automata networks. Let n be a positive integer and q be an integer no less than 2. We denote [n] = {1, . . . , n} and vqw = {0, . . . , q -1}. In the sequel n will always denote the size of the network and vqw its alphabet. A state is any element x = (x 1 , . . . , x n ) ∈ vqw n . For any S = {s 1 , . . . , s k } ⊆ [n], we denote x S = (x s1 , . . . , x s k ); the order in which these indices occur will not matter usually. We denote the set of functions f : vqw n → vqw n as F(n, q). A network is any element of F(n, q). We can view f as f = (f 1 , . . . , f n ), where each f v is a function vqw n → vqw. We can then use the same shorthand notation as for states, and define f S for instance. We also often use the notation

f t v = (f t ) v .
The interaction graph of f ∈ F(n, q) has vertex set V = [n] and has an arc from u to v if and only if f v depends essentially on u, i.e. there exists a, b ∈ vqw n such that a

[n]\u = b [n]\u and f v (a) = f v (b).
If the interaction graph of f is D, we then say that D admits f . For any digraph D with n nodes, we denote the set of networks in F(n, q) with interaction graph D as F[D, q]. Linear networks. To obtain some results, we shall focus on networks of a special kind that can be analyzed through classical algebra; we give them in decreasing order of generality. A network is abelian if vqw is endowed with the structure of a finite abelian group A and f is an endomorphism of the group A n . More concretely, we have f v (x) = j∈[n] e v,j (x j ), where the e v,j are endomorphisms of A. A network is linear if vqw is endowed with a ring structure R and f is defined by some matrix M as f (x) = xM , where M ∈ R n×n . A network is field linear if it is linear over the finite field GF(q) of order q. The XOR network on D is f ∈ F[D, 2], defined by f (x) = xA D , where A D is the adjacency matrix of D. This is the only abelian network with interaction graph D for q = 2. Note that from the perspective of both positive expansivity in cellular automata and control theory, the restriction to linear (or even abelian) system is common in the literature.

Trace and expansive networks

Fix f ∈ F(n, q). Then for any x and v, the trace of x at v is the infinite (ultimately periodic) sequence

ρ v (x) = (f v (x), f 2 v (x), . . . ). We also denote ρ (T ) v (x) = (f v (x), . . . , f T v (x))
as the first T elements in the trace.

Definition 2.1. A network f is expansive if for any distinct x, y ∈ vqw n and any v ∈ [n], there exists t ≥ 1 such that f t v (x) = f t v (y). Equivalently, f is expansive if and only if for any v, there exists T ≥ 1 such that the trace function ρ

(T ) v is injective.
When f is abelian, the function (f v , f 2 v , . . . , f T v ) : vqw n → vqw T is also abelian. Therefore, if f is abelian then f is expansive if and only if for all x ∈ vqw n \ {(0, . . . , 0)} and all v ∈ [n], there exists t ≥ 1 such that f t v (x) = f t v (0, . . . , 0). Let f be a linear network, i.e. f (x) = xM . From M , construct the powers of M : M 0 = I, M 1 = M, M 2 , . . . ; denote the u-th column of M i as M i u . For any t ≥ 0 and any u ∈ [n], construct the matrix

N (t) u = M t u M t+1 u . . . M t+n-1 u .
The matrices

N (t)
u then determine whether f is expansive when f is field linear.

Lemma 2.2. The following are equivalent for a field linear network f (x) = xM .

1. f is expansive.

2. M is nonsingular and

N (0) u is nonsingular for all u ∈ [n].

N (t)

u is nonsingular for all u ∈ [n] and t ≥ 1.

4. There exists t ≥ 1 such that N (t)

u is nonsigular for all u ∈ [n].
Proof. We prove 2 implies 3. Since

M t+k u = M t M k u , we have N (t) u = M t N (0)
u . Thus, if M and N (0) u are nonsingular, then so is N (t) u . Clearly, 3 implies 4. We prove 4 implies 1. Suppose 4 holds, and let y = (f t u (x), . . . , f t+n-1 u

(x)) = xN (t) u . Then x = y(N (t)
u ) -1 can be recovered from y and f is expansive. We prove 1 implies 2. Clearly, if f is expansive, then it is bijective, thus M is nonsingular. Suppose that f is expansive, but N (0) u is singular for some u. By expansivity, there exists s > n such that the matrix

Ñ (s) u = M 0 u M 1 u . . . M s-1 u
has full rank (i.e. rank n). However, because

N (0) u = Ñ (n)
u is singular, there exists j < n such that M j u is in the column span of Ñ (j) u . Say M j u = j-1 i=0 y i M i u , then we have for all k ≥ 0

M j+k u = M k M j u = M k j-1 i=0 y i M i u = j-1 i=0 y i M i+k u .
Thus, rk(

Ñ (s) u ) = rk( Ñ (j) u ) ≤ rk(N (0) u ) < n, which is the desired contradiction.
Since computing the determinant is no harder than multiplying matrices [15, Theorem 6.6], Property 2 yields an efficient algorithm to determine the expansivity of a field linear network.

Corollary 2.3. Determining whether a field linear network is expansive can be done in O(n • M (n)), where M (n) is the running time of an n × n matrix multiplication algorithm.

Links with expansivity in cellular automata

A topological dynamical system [START_REF] Kůrka | Topological and symbolic dynamics[END_REF] is a pair (F, X) where X is a compact metric space with distance d and F a continuous map. F is said positively expansive if there is a real constant > 0 such that: ∀x, y ∈ X : x = y ⇒ ∃t ≥ 0, d(F t (x), F t (y) ≥ .

Note that the original setting in [START_REF] Utz | Unstable homeomorphisms[END_REF] assumes that F is bijective and defines the weaker notion of expansivity where t might be chosen negative.

A (one-dimensional) cellular automaton is a topological dynamical system (F, Q Z ) where Q is a finite alphabet and F is defined through a local rule f :

Q V → Q with V = [-r, . . . , r] called neighborhood as follows: ∀x ∈ Q Z , ∀z ∈ Z, F (x) z = f (x |z+V )
where x |z+V denotes the map: i ∈ V → x z+i . F is positively expansive if and only if the following trace map is bijective [8, Proposition 5.48]:

x → (x |V , F (x) |V , F 2 (x) |V , . . .)
or equivalently if and only if

∀x, y ∈ X, x = y ⇒ ∃t : F t (x) |V = F t (y) |V .
Expansivity (positive or not) in cellular automata has received a lot of attention [START_REF] Blanchard | Dynamical properties of expansive one-sided cellular automata[END_REF][START_REF] Pivato | Positive expansiveness versus network dimension in symbolic dynamical systems[END_REF][START_REF] Nasu | Nondegenerate q-biresolving textile systems and expansive cellular automata of onesided full shifts[END_REF] and is still an active direction of research [START_REF] Jalonen | On dynamical complexity of surjective ultimately rightexpansive cellular automata[END_REF], one of the main open problem being the decidability of the property (see [START_REF] Boyle | Open problems in symbolic dynamics[END_REF]Problem 19] or [START_REF] Kari | Theory of cellular automata: A survey[END_REF]Problem 7]).

The link between expansive cellular automata and automata networks can be made more explicit through the notion of quasi-expansivity. Definition 2.4. A network f is quasi-expansive if for all x = y and all v, there exists t ≥ 0 such that f t Nin(v) (x) = f t Nin(v) (y).

Note that the main notion of expansivity of the current paper (definition 2.1) is stronger than quasi-expansivity. We can then establish a correspondence between cellular automata and automata networks in two ways (to simplify exposition and stick exactly to the definition of dependency graph we suppose that the local map f : Q V → Q essentially depends on all its variables):

1. we can see a cellular automaton F as an automata network on the infinite graph (Z, E) where (i, j) ∈ E if and only if |i -j| ≤ r (taking the notation above). Note that this graph is always strongly connected and can be covered by disjoint cycles (see Theorem 3.7) and F as a cellular automaton is positively expansive if and only if it is quasi-expansive as an (infinite) automata network. In particular expansivity of F as an automata network implies positive expansivity of F as a cellular automaton.

2. we can also restrict a cellular automaton F to periodic configurations of period n. In this case it can be seen as a standard automata network F n on the finite graph (Z/nZ, E) where (i, j) ∈ E if and only if |i -j| ≤ r.

If F as a cellular automaton is positively expansive, then for any n, the automata network F n is quasi-expansive. The converse is false as the shift cellular automaton F (x) z = x z+1 is not positively expansive while all its restrictions F n are quasi-expansive.

Interaction graphs of expansive networks

In this section, we are interested in determining for which interaction graphs D there exists an expansive network in F[D, q]. Some graphs admit expansive network for any alphabet (subsection 3.2), some admit no expansive network whatever the alphabet. The main result of this section is a characterization of graphs admitting an expansive network for some alphabet (subsection 3.3).

Bijective networks

Since an expansive network is bijective, we first derive a result about the existence of bijective networks. A cycle decomposition of a graph D is a set of vertex-disjoint cycles that partition the vertex set of D. Say a graph D is coverable if it has a cycle decomposition. A digraph is coverable if and only if |N out (S)| ≥ |S| for all S ⊆ V [14, Proposition 3.11.6]. These graphs can be characterized through existence of bijective networks.

Theorem 3.1 ([5]

). D is coverable if and only if F[D, q] contains a bijection for all q ≥ 3.

We first give a similar result on bijections in the linear case. Let M[D, q] denote the set of matrices over Z q and with interaction graph equal to D, i.e. matrices M such that:

M i,j = 0 ⇐⇒ ij ∈ E(D). Theorem 3.2. If D is coverable, then M[D,
q] contains a nonsingular matrix for any q ≥ 3.

Proof. Let us first settle the case where D is loop-full. We shall prove that there exists a matrix M ∈ M[D, q] with determinant equal to 1. The result is clear for n = 1, so suppose it holds for n -

1. Let M ∈ M[D \ n, q] have determinant 1. Then let A ∈ M[D, q] such that A i,j =          M i,j if i, j = n 1 if i = n and j = n and ij ∈ E, or if i = n and j = n and ij ∈ E, 1 if i = j = n 0 otherwise, If det(A) = 2, then consider M ∈ M[D, q] such that M i,j = 2 -det(A) if i = j = n, A i,j otherwise. Then det(M ) = det(A) + (M n,n -1) det(M ) = 1. If det(A) = 2, then let M ∈ M[D, q] such that M i,j =      2 if i = j = n, -A i,j if j = n, i = n, A i,j
otherwise.

We then have det(M ) = det(A) -det(M ) = 1 which shows the induction step for n and settles the case where D is loop-full.

In the general case, let D be coverable, then the mapping v → π(v), where π(v) is the successor of v on a cycle in the cycle partition is a permutation. Denoting the permutation matrix of π by P , define the graph D with adjacency matrix A D = P -1 A D . Then D is loop-full, thus there exists M ∈ M[D , q] with determinant sign(π). Finally, the matrix M := P M belongs to M[D, q] and has determinant 1.

Recall that the term rank of a matrix is the maximum number of non-zero entries which are not in the same row or column. By the max-flow min-cut theorem, this is equal to the number of lines (rows and columns) necessary to cover all non-zero entries of the matrix. The term rank of the adjacency matrix of a graph is equal to the maximum number of pairwise independent arcs, where uv, u v are independent if and only if u = u and v = v ; it is denoted as α 1 (D) in [START_REF] Gadouleau | On the rank and periodic rank of finite dynamical systems[END_REF].

Corollary 3.3 (Edmonds's theorem [START_REF] Edmonds | Systems of distinct representatives and linear algebra[END_REF]). The maximum possible rank of a real matrix with interaction graph D is equal to α 1 (D). Moreover, the maximum is achieved by a matrix with entries in Z.

Corollary 3.4 ([5]

). The maximum possible rank of a network in F[D, q] is equal to q α1(D) for all q ≥ 3. Moreover, the maximum is achieved by a linear function over Z q .

Families of graphs with expansive networks over all alphabets

We exhibit two families of graphs which generalise the cycle, in the sense that the cycle belongs to either family and that every member of the family admits an expansive network over any alphabet (apart from one exception).

The first family is that of cycles with loops.

Say D = (V = vnw, E) is a cycle with loops if there exists S ⊆ vnw such that E = {(i, i + 1 mod n) : 0 ≤ i < n} ∪ {(s, s) : s ∈ S}. Say a cycle with loops is proper if S = V .
We shall repeatedly use the following facts, whose proofs are obvious and hence omitted. Firstly, the following are equivalent:

1. The XOR network on D is bijective.

2. The adjacency matrix A D is nonsingular over GF(2).

D has an odd number of cycle decompositions.

Secondly, if D has a unique cycle decomposition, then the adjacency matrix A D has determinant one over all rings Z q . Proposition 3.5. If D is a cycle with loops, then D admits an expansive linear network for any q ≥ 2, unless D is an improper cycle with loops and q = 2.

Proof. We recall that a linear network f (x) = xM is expansive if for all u ∈ vnw, the matrix M and the matrix

N (0) u = I u M u . . . M n-1 u are nonsingular. If D is a proper cycle with loops, then let M = A D . Since D has a unique cycle decomposition, A D is nonsigular. Also, up to a permutation of columns, N (0)
u is upper triangular with all ones on the diagonal, hence its determinant is equal to one and N (0) u is nonsingular. If D is an improper cycle with loops, we see that it has exactly two cycle decompositions. As such, the XOR network is not bijective and D does not admit an expansive linear network for q = 2. For q = 3, let a ∈ Z q \ {0, 1} be invertible, b = 1 -a if n is odd and b = a + 1 if n is even, and

M =        b a 0 • • • 0 0 1 1 • • • 0 . . . . . . . . . . . . . . . 0 0 • • • 1 1 1 0 • • • 0 1        , then det(M ) = 1. Once again, N (0)
u is upper triangular, and det(N

(0) u ) is a power of a, which shows that N (0) u is nonsingular.
The second family is that of cycles of cycles. Say D is a cycle of cycles if either it is a cycle or it is a union of k ≥ 2 disjoint cycles C 1 , . . . , C k , linked as follows: for each cycle C i there are two vertices u i , v i (which may be equal) such that u i v i+1 ∈ E for all 1 ≤ i ≤ k (computed cyclically). Say a cycle of cycles is proper if there exists i such that u i v i / ∈ E.

Proposition 3.6. If D is a cycle of cycles, then D admits a linear expansive network for all q ≥ 2 unless D is an improper cycle of cycles and q = 2.

Proof. Let D be a proper cycle of cycles. Firstly, we verify that D has a unique cycle decomposition. This is true when D is a cycle. Otherwise, let i such that u i v i / ∈ E, then the successor w i of u i belongs to only one cycle, namely C i . Once C i is removed, it is then clear that v i+1 only belongs to one cycle, namely C i+1 , and so on. Thus, the XOR network on D is bijective. Conversely, if D is an improper cycle of cycles, then it has exactly two cycle decompositions, and hence the XOR network is not bijective. For q ≥ 3, there always exists a linear bijective network by Theorem 3.2.

Let f be a linear bijective network on D. Suppose, for the sake of contradiction, that f is not expansive. Let x and v such that for all t ≥ 0, f t v (x) = 0. We consider two cases. Firstly, suppose that for all 1 ≤ i ≤ k, there exists t i ≥ 0 such that f ti ui (x) = 0. Let v be any vertex, say it belongs to C i ; denote the vertices of C i as u i , u i + 1, . . . u i + l i -1 and in particular v = u i + b. We then have f ti+a ui+a (x) = 0 for all 0 ≤ a ≤ l i -1 and in particular f ti+b v (x) = 0, which is the desired contradiction.

Secondly, suppose that there exists 1 ≤ j ≤ k such that f t uj (x) = 0 for all t ≥ 0. Then for all t ≥ l j , f t Cj (x) = 0. (Justify.) For any t ≥ l j , we have

0 = f t+1 vj (x) = f t uj-1 (x),
thus by a similar reasoning, f t Cj-1 (x) = 0 for all t ≥ l j + l j-1 . By obvious induction, we obtain that f n (x) = 0, which contradicts the fact that f is bijective.

Characterization of graphs admitting expansive networks for some alphabet

We now characterize the graphs D which admit an expansive network over some alphabet. We can actually be more precise, and consider variations of our main definition without affecting the characterization. A network f is said to be weakly expansive if for all x = y and all v, there exists t ≥ 0 such that

f t v (x) = f t v (y)
. Note that a weakly expansive f does not have to be bijective. Recall that a network f is quasi-expansive (Definition 2.4) if for all x = y and all v, there exists t ≥ 0 such that f t Nin(v) (x) = f t Nin(v) (y). It is not difficult to see that these definitions are not equivalent. However, the interaction graphs they characterize are the same as shown in the following theorem.

Theorem 3.7. The following are equivalent for a graph D on n ≥ 2 vertices.

1. D is strongly connected and coverable.

2. D admits an expansive network over some q.

3. D admits a quasi-expansive network over some q.

4. D admits a weakly expansive network over some q.

5. D admits a linear expansive network over any large enough finite field.

Clearly, an expansive network is quasi-expansive and weakly expansive. Therefore this theorem follows from the next three results. Lemma 3.8. If D admits a quasi-expansive network, then D is strongly connected and coverable (or D has a single node).

Proof. Let f ∈ F[D, q] for some q ≥ 2. If D is not strongly connected, then let u and v such that there is no path from u to v in D. There is no path from u to N in (v) either. Then it is clear that for any t ≥ 0, f t W does not depend on

x u , where W = N in (v). In particular, if x, y ∈ vqw n only differ in position u, we have f t W (x) = f t W (y) for all t ≥ 0. Therefore, f cannot be quasi-expansive. Suppose D is not coverable, then by [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF]Proposition 3.11.6] there exists S ⊆ V such that |N out (S)| < |S|. Choose any vertex v ∈ N out (S) (v may be in S or not). By the pigeonhole principle there must exist two distinct configurations x, y ∈ vqw n such that x and y differ only on S and f (x) Nout(S) = f (y) Nout(S) . But it also holds that f (x

) i = f (y) i for any i ∈ N out (S) because x Nin(i) = y Nin(i) since N in (i) ∩ S = ∅. We deduce that f t (x) = f t (y) for all t ≥ 1 and x Nin(v) = y Nin(v)
which proves that f is not quasi-expansive. Lemma 3.9. If D admits a weakly expansive network, then D is strongly connected and coverable (or

D = K 1 ).
Proof. The proof is similar to that of Lemma 3.8. Again, it is clear that D must be strongly connected. If D is not coverable, then let S ⊆ V such that |N out (S)| < |S|. If S = V , then some vertex has no outgoing edge so the graph is not strongly connected. If S = V , then there exist distinct configurations x, y such that x S = y S and x V \S = y V \S and f (x) = f (y). Thus, for any v / ∈ S and any t ≥ 0,

f t v (x) = f t v (y).
We have no constructive method to produce an expansive network on a given strongly connected and coverable digraph. The next theorem shows their existence by a counting argument based on the Schwartz-Zippel Lemma. The hard part of the proof is to establish that some determinants are non-zero using the structure of the considered digraphs. Theorem 3.10. Any strongly connected and coverable graph D on n vertices admits an expansive linear network over GF(q) for any prime power q ≥ 1 2 (n 3 + n 2 + 4).

Proof. We recall that by Lemma 2.2 a linear function f (x) = xM is expansive if and only if for all u ∈ [n], the matrix

N := N (1) u = M u M 2 u . . . M n u is nonsingular.
Our proof is nonconstructive: we shall see the nonzero coefficients of the matrix M as variables, then the determinant of N is a polynomial of these variables; if the field is large enough, then we can always evaluate that polynomial to something other than zero, provided it is not the null polynomial.

Let C1 , . . . , Cs be a decomposition of the vertex set of D into cycles. We let X(e) = ᾱk if e is one of the arcs in Ck ; otherwise, we give a different variable X(e) = βe for any other arc e (and in particular for the chords of the cycles C1 , . . . , Cs ). For any walk W = e 1 , . . . , e L on D, we denote the monomial X(W ) = X(e 1 )X(e 2 ) • • • X(e L ). (The sum and the product of variables commute.)

We fix a vertex u, say it belongs to Cσ . Let T be a spanning "tree of cycles" rooted at Cσ . More precisely, T is a spanning subgraph of D which contains all the cycles C1 , . . . , Cs and for any k = σ, there is exactly one arc leaving Ck . (Such a tree of cycles can be easily constructed by contracting every cycle to a vertex and then building a spanning in-tree rooted at the vertex corresponding to Cσ .) It will be convenient to re-order the cycles according to the topological order in T . We then have C 1 = Cσ , C 2 , . . . , C s . We similarly re-define the variables: α k is the variable for all the arcs in C k (1 ≤ k ≤ s), while β k is the variable corresponding to the arc leaving

C k in T (2 ≤ k ≤ s).
Recall that the determinant det(N

u ) is a sum over all permutations of products of terms. The main point of the proof is to show that det(N (1) u ) is not the null polynomial by exhibiting a monomial Y that appears only in the product corresponding to a particular permutation, hence no cancellation can occur in the sum over permutation defining det(N u ). This monomial is obtained from canonical paths of particular lengths in the structure of tree of cycles above: they each consist in making a number of turns around some cycle and then taking the shortest path to u. Their precise description follows.

For 1

≤ k ≤ s, let L k be the length of C k and Λ k := L 1 + • • • + L k-1 (Λ 1 = 0)
. We also denote the shortest path from C k to u in T as W k and we denote its length as λ k and its monomial as

X k = X(W k ); for k = 1, W 1 is the empty path thus λ 1 = 0 and X 1 = 1. It is easily seen that Λ k ≥ λ k for all k. We remark that for any distinct v, v ∈ C k , d T (v, u) ≡ d T (v , u) mod L k ,
where d T denotes the distance in T . We can then denote the vertices of C k according to their distance to u as follows: let the vertices in

C k be v j k for j = 1, . . . , L k , where d T (v j k , u) ≡ Λ k + j mod L k . From this definition we have Λ k + j ≥ d T (v j k , u) because 0 ≤ d T (v j k , u) -λ k < L k and Λ k + j -λ k ≥ 0 and Λ k + j -λ k ≡ d T (v j k , u) -λ k mod L k .
For any row (vertex) v and column (time) t, we have N (v, t) = W X(W ), where the sum is taken over all walks from v to u of length t. Let us consider v = v j k and t = Λ k + j. There is a canonical walk from v to u of time t: going round the cycle C k as many times as possible and then take the shortest path from C k to u, which yields the term α t-λ k k X k . All the other walks either remain in T , but if so do not use α k as many times, or leave T .

This yields:

N (v j k , Λ k + j) = α Λ k +j-λ k k X k + Γ + ∆
, where all the terms in Γ contain a variable outside of those of T , and the degree of α k in ∆ is at most Λ k + j -1. Therefore, the product

1≤k≤s 1≤j≤L k N (v j k , Λ k + j) contains the monomial Y := s k=1 α d k k X L k k , where d k := L k 1 2 (L k + 1) + Λ k -λ k .
The term Y contributes to the determinant of N , for the permutation ρ of [n], defined as ρ(v j k ) = Λ k + j. We now prove that Y does not appear in any other product of entries that contribute to the determinant of N . More precisely, we prove by induction on k from s down to 1 that if any permutation π of [n] produces for every k a term only involving variables from T where α k has degree

d k , then π(v) = ρ(v) for all v ∈ C k .
Let us prove the case k = s. Let π(C s ) = {t 1 , . . . , t Ls } with t 1 < • • • < t Ls . Clearly, we only need to consider walks in T . According to the topological order of cycles in T , there is no path from C i to C j if i < j. In particular, the rows of N corresponding to a vertex outside of C s does not contain α s . Thus, the degree of α s is at most (t

1 -λ s ) + • • • + (t Ls -λ s ). We then have t 1 + • • • + t Ls -L s λ s ≥ d s = L s 1 2 (L s + 1) + Λ s -L s λ s ,
which implies t j = Λ s + j for j = 1, . . . , L s . Moreover, the degree of α s in N (v i s , Λ s + j) is equal to Λ s + j -λ s if and only if i = j. This implies that π(v j s ) = Λ s + j for all j. The inductive step is similar and hence omitted.

We have thus shown that det(N

u ) is a nonzero polynomial in the variables {X(e) : e ∈ E}. Its degree is clearly d := n(n + 1)/2. By the Schwartz-Zippel Lemma [START_REF] Mullen | Handbook of Finite Fields[END_REF]Theorem 7.1.4], there are at most d(q -1) |E|-1 choices for the values of X(e) for which det(N

u ) = 0. Thus, there are at most nd(q -1) |E|-1 choices for the values of X(e) for which det(N

u ) = 0 for some u ∈ [n]. Since q -1 > nd, we have (q -1) |E| > nd(q -1) |E|-1 , and hence there exists a choice of values for all the variables X(e) such that det(N

u ) = 0 for all u.

We highlight two consequences of our result. Firstly, we comment on the alphabets for which a strongly connected and coverable D admits a linear expansive network. The cartesian product of two networks f ∈ F(n, q) and g ∈ F(n, r) is defined as follows. We view vqrw

∼ = vqw × vrw = {(a 1 , a 2 ) : a 1 ∈ vqw, a 2 ∈ vrw}, then f × g = h ∈ F(n, qr) with h(x 1 , x 2 ) = (f (x 1 ), g(x 2
)). Many properties are preserved by cartesian products: if f and g are expansive, then so is f × g; if f and g are linear, then so is f × g; if f and g have interaction graph D, then so does f × g. In particular, if D admits a linear expansive network over alphabets of size q and r, then it admits a linear expansive network over an alphabet of size qr.

Corollary 3.11. For any strongly connected and coverable D, the set of alphabet sizes q for which there exists a linear expansive network in F[D, q] has positive density.

Proof. Denote the prime numbers as p 1 < p 2 < . . . . Say p j is the largest prime no greater than q := 1 2 (n 3 + n 2 + 4), then let d i = log pi q for all i ≤ j. Then D admits an expansive network on any multiple of Q := j i=1 p di i . We actually conjecture that for any strongly connected and coverable D, there exists q such that D admits an expansive network over all alphabets of size greater than q.

A corollary of Theorem 3.10 is that choosing a linear network at random will almost surely yield an expansive network when q is large enough. Even more strikingly, we can define the following strategy to construct entire families of expansive networks. For a given n and prime power q, the Random-Linear-Strategy first chooses a random matrix M ∈ GF(q) n×n whose entries are all nonzero. Then for a given graph D on [n], the strategy yields the linear network f M,D (x) = x(M A D ) and denotes the Hadamard product of matrices. The following corollary shows that the probability to get an expansive network for all strongly connected and coverable graphs goes to 1 as the alphabet size goes to infinity.

Corollary 3.12. The Random-Linear-Strategy produces from a single random matrix M an expansive network f M,D for all strongly connected and coverable graph D on n vertices with probability at least 1 -∆/(q -1), where ∆ = 2 n 2 -1 n 2 (n + 1).

Proof. Let α = {α ij : i, j ∈ vnw} be an outcome of the Random-Linear-Strategy, where α ij is a nonzero element of GF(q) for all q. For any strongly connected and coverable graph D on n vertices, there are at most n•n(n + 1)/2•(q -1) n 2 -1 choices for α which do not yield an expansive network on D. Since there are at most 2 n 2 choices for D, there are at most ∆(q -1) n 2 -1 choices of α which do not produce an expansive network for all D. Thus, the probability of success is at least 1 -∆(q -1) n 2 -1 /(q -1) n 2 .

Alphabet size and nonexistence of expansive networks

We only consider strongly connected and coverable graphs from now on. For any graph D, we denote the set of expansive (abelian expansive, respectively) networks in F[D, q] as E[D, q] (EA[D, q], respectively). Our nonexistence results are based on the following family of graphs. Consider for any n ≥ 2 the graph

G n = (V n = {0, 1, . . . , n}, E n ) where E n = {(0, i), (i, 0), (i, i) : 0 ≤ i ≤ n}.
Any network with a small enough alphabet and with interaction graph G n must have symmetries in its local functions f i for i = 0 (counting argument). The following theorem uses this idea to show that expansivity is impossible with small alphabets on graphs G n . Theorem 4.1. For all q, there exists n 0 (triply exponential in q) such that, for all n ≥ n 0 , E[G n , q] = ∅.

Proof. We first show that any f ∈ F[G n , q] has a lot of initial configurations reaching cycles of constant size in constant time (i.e. independent of n). To make a precise statement, denote for any φ ∈ vqw vqw 2 the set of automata in f whose local update map is φ: V φ = {i : 0 < i ≤ n and ∀x, f i (x) = φ(x i , x 0 )}. Choose any φ, any V ⊆ V φ and define the configuration c φ,V ∈ vqw [n] by:

c φ,V (j) = 0 if j ∈ V 1 else.
We claim that the orbit under f of any such c φ,V has length at most p = q q q 2 +2 . Indeed, by induction on t, it holds that

f t (c φ,V ) i = f t (c φ,V ) j if {i, j} ⊆ V φ for φ = φ, or {i, j} ⊆ V , or {i, j} ⊆ V φ \ V (it
is true at t = 0 and preserved because two automata {i, j} ⊆ V φ apply the same update map φ ). It follows that there are at most q q q 2 +2 different configurations in the orbit of c φ,V , which proves the claim. Now fix q, let p = q q q 2 +2 and l > log 2 (q 2p ) and choose n ≥ lq q 2 . By choice of n there must be φ ∈ vqw vqw 2 such that |V φ | ≥ l. Thus, there are 2 l choices of V ⊆ V φ yielding 2 l distinct configurations of the form c φ,V . For any configuration c, define ρ(c) := ρ (2p) 0 (c) the trace of length 2p at node 0. By choice of l there must be V, V ⊆ V φ with V = V such that ρ(c φ,V ) = ρ(c φ,V ) (because ρ can take only q 2p different values). We thus have two distinct configurations x = c φ,V and y = c φ,V such that ρ (lx+ly) 0 (x) = ρ (lx+ly) 0 (y) where l x and l y are the lengths of the orbit of x and y respectively. This contradicts expansivity of f as shown in the proof of Theorem 5.4.

We now prove that the bound on the smallest n such that there exists G on n vertices with no expansive networks over vqw can be significantly lowered if we only consider linear networks. We give a proof that actually holds for abelian networks with a quasi-polynomial bound. Theorem 4.2. For any q ≥ 2 and any n > q 2 log(q) it holds EA[G n , q] = ∅.

Proof. Let N q denote the maximum number of endomorphisms of an abelian group of order q. By the decomposition theorem of Abelian groups into products of cyclic groups, one sees that an endomorphism is determined by its value on at most log(q) elements (elements equal to the generator on one component of the product and 0 on the others), thus N q ≤ q log(q) . Let n > q 2 log(q) ≥ N 2 q . Let A be an abelian group of order q and f ∈ F[G n , q] be an endomorphism of A n+1 . Then there exist i and j such that f i (x) = g(x i ) + h(x 0 ), f j (x) = g(x j ) + h (x 0 ) and f 0 (x) = e(x i ) + e(x j ) + h (x {0,...,n}\{i,j} ) for some endomorphisms g, e, h, h and h . Consider a nonzero configuration x such that x i + x j = 0 and x u = 0 for any other vertex u, we then have

f i (x) + f j (x) = g(x i + x j ) + h(x 0 ) + h (x 0 ) = 0, f 0 (x) = e(x i + x j ) + h (x {0,...,n}\{i,j} ) = 0.
By induction, we have f t 0 (x) = 0, thus f is not expansive.

The proof can be easily adapted for linear networks, thus yielding a polynomial bound on the smallest n for which G n admits no linear network over an alphabet of size q.

Corollary 4.3. The graph G n admits no linear expansive network for q whenever n > (q -1) 2 .

We conjecture that in fact, there is a sharp distinction between admitting an expansive network and admitting an abelian expansive network: for all q, there exists D such that E[D, q] = ∅ but EA[D, q] = ∅. We make some progress towards this conjecture by showing that it holds for all q ≡ 2 mod 4. Let G be the graph on four vertices displayed below:

1 2 0 3 Proposition 4.4.
We have E[G, q] = ∅ for all q ≥ 2. However, EA[G, q] = ∅ if and only if q ≡ 2 mod 4.

Proof. Firstly, we verify that G admits no abelian expansive network for q = 2. For q = 2, the only abelian network is the XOR network f (x) = xA G . The configuration x = (0, 1, 1, 0) is a fixed point of the XOR network, thus the latter is not expansive. More generally, for any q = 2k for k odd, any abelian network h ∈ F(n, 2k) decomposes as h = f × g, where f ∈ F(n, 2) and g ∈ F(n, k) are both abelian. We thus obtain that G admits no abelian expansive network for any q ≡ 2 mod 4.

Secondly, we show that there exists an abelian expansive over G for all q ≡ 2 mod 4. We only need to prove the case for non-binary finite fields, the general case following by cartesian product. Let q = 2 be a prime power and let α = {0, 1} be an element of GF(q). Let f (x) = xM , where

M =     0 1 1 1 1 1 0 0 1 0 α 0 1 0 0 0     .
Clearly, det(M ) = -α and hence f is bijective. After some straightforward calculations, we obtain

N 0 =     1 0 3 α + 1 0 1 1 4 0 1 α α 2 + 3 0 1 0 3     , det(N 0 ) = α 2 -α; N 1 =     0 1 1 4 1 1 2 3 0 0 1 α + 1 0 0 1 1     , det(N 1 ) = α; N 2 =     0 1 α α 2 + 3 0 0 1 α + 1 1 α α 2 + 1 α 3 + 2α 0 0 1 α     , det(N 2 ) = -1; N 3 =     0 1 0 3 0 0 1 1 0 0 1 α 1 0 1 0     , det(N 3 ) = 1 -α.
All determinants are nonzero, thus f is expansive. Thirdly, for q = 2, it is straightforward to check that the following network is indeed expansive.

f 0 (x) = x 1 x 2 + x 3 + 1 f 1 (x) = x 0 + x 1 f 2 (x) = x 0 + x 2 + 1 f 3 (x) = x 0 .
Again, combining our previous results and using the cartesian product, we conclude that G admits an expansive network for all q ≥ 2.

Expansion time

Consider some expansive network f . For any node v and any configuration x, it is clear that the trace ρ v (x) is periodic. In particular, let O x = {f t (x) : t ≥ 1} be the orbit of x, then the period of the trace of x is equal to the size l x = |O x | of its orbit (if it were shorter of length l, then x and f l (x) would be two distinct configurations of same trace).

For any expansive network f ∈ F(n, q), any different x, y ∈ vqw n and any y). This is the shortest time for which the temporal evolution of x v determines x completely, for any x and any v. For any v, it is clear that if the function ρ (T ) v is injective, then T ≥ n, thus T (f ) ≥ n. Say f is strongly expansive if it is expansive and T (f ) = n. Lemma 2.2 then shows that any expansive field linear network is strongly expansive. Strongly expansive networks can be viewed as follows. For any x ∈ vqw n , consider the matrix

v ∈ [n], let τ v (x, y) = min t ≥ 1 : f t v (x) = f t v (y) . The expansion time of f is then T (f ) := max x =y∈vqw n ,v∈[n] τ v (x,
M x =      f 1 (x) f 2 (x) . . . f n (x) f 2 1 (x) f 2 2 (x) . . . f 2 n (x) . . . . . . . . . . . . f n 1 (x) f n 2 (x) . . . f n n (x)      .
Then f is bijective if and only if we can recover x from any row of M x , while f is strongly expansive if and only if we can recover x from any column of M x . The expansion time is the minimum value of T such that one can recover any x from the first T time steps of its trace at v. For a given x and a given v, that particular time may be smaller than n. as shown in the following example. It can be checked that f is indeed expansive, with expansion time T (f ) = 4 (and hence f is not strongly expansive). In the traces at vertex v = 1 shown above (the part of the trace that allows to recover the initial state is highlighted), it appears that the states 011 and 110 could be recovered after only two time steps.

However, the expansion time is "universal" for strongly expansive networks: for any v and any x, one must wait n time steps before being able to recover x. Proposition 5.2. If f is strongly expansive, then for any v ∈ [n] and x ∈ vqw n , there exists y = x such that τ v (x, y) = n.

Proof. If f is strongly expansive, then for any v, the function ρ

(n) v is surjective.
Suppose, for the sake of contradiction, that there exists x such that for any y = x, ρ

(n-1) v (x) = ρ (n-1) v (y). Let a = f n v (x)
, then there is no y such that ρ In order to highlight the specificity of strongly expansive networks, we now show that the maximum possible expansion time for expansive network is almost q n . Example 5.3 (Expansive counter). We construct an expansive network f in F(n, q) with expansion time T (f ) ≥ q n -q -1. Intuitively, this network is the successor function of a particular enumeration of vqw n , which can be viewed as a "twisted lexicographic order." More formally, for any integer 0 ≤ a ≤ q n -1, say a = a 1 + a 2 q + • • • + a n q n-1 , let x a = (x a 1 , . . . , x a n ) ∈ vqw n be defined as x a n = a n and for 1 ≤ i ≤ n -1,

x a i =      q -2 if a i+1 = • • • = a n = q -1 and a i = q -1 q -1 if a i+1 = • • • = a n = q -1 and a i = q -2 a i otherwise.
Then let f (x a ) = x a+1 mod q n . Since the maps a → a + 1 mod q n and a → x a are bijective, f is well-defined by the previous formula and also bijective.

The next theorem establishes precise bounds on the maximum possible expansion time. The upper bound uses the theorem of Fine and Wilf on periods of words [START_REF] Fine | Uniqueness theorems for periodic functions[END_REF].

Theorem 5.4. For all n and q, the maximum T (f ) over all expansive f ∈ F(n, q) is between q n -q -1 and q n -1. The lower-bound is granted by Example 5.3 which verifies T (f ) ≥ q n -q -1.

Proof. Upper bound. Let x = y with l x ≤ l y ; denote τ = τ v (x, y).

Case 1: l x | l y . We first prove that τ ≤ l y . Suppose that this is not the case, i.e. f t v (x) = f t v (y) for all 1 ≤ t ≤ l y . Then ρ v (x) = ρ v (y), which contradicts the expansivity of f . Thus, τ ≤ l y ≤ q n . Suppose that τ = l y = q n , then f is a cyclic permutation of vqw n and the trace ρ v (x) is a cyclic shift of ρ v (y), and their only difference is in position q n , i.e

x v = a = y v = b. Let N = |{t : 1 ≤ t ≤ q n -1, f t v (x) =
a}| denote the number of times the trace of x is equal to a until time q n -1. We then have N = q n-1 -1. However, N also counts the number of times the trace of y is equal to a until time q n -1; we obtain N = q n-1 , which is the desired contradiction.

Case 2: l x | l y . We prove that τ ≤ l x + l y -gcd(l x , l y ) -1 which is sufficient to get the upper bound of the theorem since in this case x and y have disjoint orbits and therefore l x + l y ≤ q n . Suppose, for the sake of contradiction, that τ ≥ l x + l y -gcd(l x , l y ). Then ρ v (x) and ρ v (y) are (infinite) periodic words of period l x and l y respectively as said earlier, and they share the same prefix of length l x + l y -gcd(l x , l y ). By Fine and Wilf's theorem [START_REF] Fine | Uniqueness theorems for periodic functions[END_REF] we deduce that ρ v (x) = ρ v (y) which contradicts expansivity of f . Lower bound. Let f be the network of Example 5.3. As already said, f is bijective. We now prove that f is expansive. We only need to show that for any 1 ≤ e ≤ q n /2 and any v ∈ [n], there exists 0 ≤ t ≤ q n -1 such that x t v = x e+t v . Let k be the largest number such that q k divides e. For 1 ≤ v ≤ k, we have x q n -1-e v = q -1 and x q n -1 v = q -2, while for k + 1 ≤ v ≤ n, we have x q v-1 -1 v = 0 and x q v-1 -1+e v = 0. Finally, it is easily verified that τ 1 (x q n -1 , x q-1 ) = q n -q -1.

Expansion frequency

In the previous section, we have shown that we may have to wait until n time steps in order to differentiate a particular pair x, y of distinct states. However, that difference may occur frequently after its first occurrence. In this section, we are then interested at how often we see a difference between the orbits of x and y at some given node v.

For all distinct x, y ∈ vqw n and all v ∈ [n], let φ v (x, y) := dH(ρv(x) (lx ly ) ,ρ(y) (lx ly ) )

lxly

, where d H denotes the Hamming distance. We then define the expansion frequency of f as Φ(f ) = min

x =y∈vqw n ,v∈[n] φ v (x, y).
It is clear that 1 T (f ) ≤ Φ(f ) ≤ 1. However, Φ(f ) itself can be as close to 1 as possible.

The upper bound in the following theorem is obtained through Berlekamp's generalisation of the Plotkin bound applied to the set of (long) traces at a given node seen as a code. Another link between variants of expansivity and codes is presented in section 8. Theorem 6.1. For any expansive network f , Φ(f ) ≤ q n -q n-1 q n -1 . Equality is achieved for all n and all prime powers q by some field linear network.

Proof. Upper bound. Let N be the product of all the orbit lengths under f , and consider the code C = {ρ

(N ) v (x) : x ∈ vqw n } of length N over vqw. Since T (f ) ≤ N ,
all traces are distinct and hence |C| = q n . Claim 6.2. The minimum distance of C is bounded by: d min (C) ≤ δ := (q-1)N q n-1

q n -1
Proof. Berlekamp's generalisation of the Plotkin bound in [START_REF] Berlekamp | Algebraic Coding Theory[END_REF] shows that for any code C of length N over vqw and minimum distance d, we have |C| ≤ dq dq-N (q-1) , provided the denominator is positive. Since δq > N (q-1), we can use Berlekamp's generalisation of the Plotkin bound. In particular, if

d min (C) = d > δ, then |C| ≤ dq dq-N (q-1) < δq δq-N (q-1) = q n , which is a contradiction. Thus, d ≤ δ.
By definition, there exists a pair x, y ∈ vqw n such that d H (ρ

(N ) v (x), ρ (N ) v (y)) = d min (C). We obtain φ v (x, y) ≤ δ N = (q-1)q n-1 q n -1
. Achievability. Consider the q-ary image of the mapping ξ → αξ in GF(q n ), where α is a primitive element of the field. This is a linear function in F(n, q), with 0 as its unique fixed point. For any nonzero x ∈ GF(q n ), the orbit of x contains all q n -1 nonzero elements of GF(q) n . Therefore, for any x = 0 and v, φ v (x, 0) = (q-1)q n-1 q n -1 .

On the other extreme, example 5.3 yields a network with expansion frequency of 2/q n .

PSPACE-completeness

In this section, we are interested in the problem of deciding whether a given network is expansive or not. Formally, we define the decision problem expan as follows:

• Input : a triple (q, n, f ) where f : vqw n → vqw n is given by circuits computing f i for each i.

• Question : is f expansive?

The goal of this section is to prove that problem expan is PSPACE-complete. Our proof proceeds by reduction from problem QBF (quantified Boolean formula) which is PSPACE-complete [START_REF] Stockmeyer | Word problems requiring exponential time[END_REF]. The simplest expansive network is the rotation map: (q 1 , . . . , q n ) → (q 2 , . . . , q n , q 1 ) (see section 3.2). The simplest nonexpansive network is the identity map. The rough idea of our reduction is to construct an automata network with a special component of states (called cycle configuration below) and with the following behavior: repeatedly test by a brute force algorithm whether the QBF is true, and each time the test concludes 'true' do a rotation on the special component, otherwise let the special component unchanged. Thus, if the QBF is false, the constructed network is certainly not expansive (identity map on the special component). If, on the contrary, the QBF is true, then the network will repeatedly apply a rotation on the special component, ensuring that if two initial configurations differ on this component then their traces at any node will also differ. This is of course not enough to conclude: firstly, a pair of initial configurations might differ only outside the special component, and secondly the conclusion of the QBF test cannot be trusted if the algorithm was not initialized correctly. To ensure that the network is globally expansive in the case where the QBF is true, two additional properties will be granted:

1. the component of states used to perform the QBF test will itself be "expansive" (differences in the initial configurations in these components must be visible in the trace at any node) ;

2. the QBF test will self-detect bad initialization and, in this case, a rotation on the special component will be applied repeatedly.

The first key ingredient of our construction is the existence of expansive networks which implement counters (Lemma 7.1): using such expansive counters as a primitive everywhere will essentially ensure the first property above. The second key ingredient is the QBF test algorithm. It is a brute force algorithm with as many nested loops as variables in the QBF. At each level it counts how many valuation of a variable makes a subformula true to deduce truth at the upper level depending on the corresponding quantifier (we want two correct valuations for a ∀ quantifier and at least one for a ∃ quantifier). Each level is implemented using two variables: a loop counter acting like an instruction counter, and a truth counter with is used to count the number of correct valuations. Loop counters have a completely rigid behavior independent of the QBF, they just indicate the progression of the test in the nested loops. Truth counters however depend on the QBF and their initialization is critical for the algorithm to give a correct answer. The self-detection for bad initialization will consist in double counting in each loop: increment the counter for each correct valuation, then use counter value to decide truth, then decrement the counter for each correct valuation, then test if counter value is zero (good initialization) or not and act correspondingly. To give a more concrete intuition before entering into the detailed construction, suppose the QBF is ∀x 1 , ∃x 2 , ∀x 3 , φ(x 1 , x 2 , x 3 ) where φ is quantifier-free. Then the algorithm looks roughly like this1 : algorithm: do forever level1() level1(): (test truth of the whole QBF)

1. if level2(0) then increment TruthCounter1 2. if level2(1) then increment TruthCounter1 3. if TruthCounter1= 2 then do rotation (QBF considered true) 4. if level2(0) then decrement TruthCounter1 5. if level2(1) then decrement TruthCounter1 6. if TruthCounter1 = 0 then do rotation (bad initialization detected) level2(x 1 ): (test truth of subformula ∃x 2 , ∀x 3 , φ(x 1 , x 2 , x 3 )) 1. if level3(x 1 , 0) then increment TruthCounter2 2. if level3(x 1 , 1) then increment TruthCounter2 3. if TruthCounter2≥ 1 then test2=true else test2=false 4. if level3(x 1 , 0) then decrement TruthCounter2 5. if level3(x 1 , 1) then decrement TruthCounter2 6. if TruthCounter2 = 0 then do rotation (bad initialization detected) 7. return test2(truth of subformula) level3(x 1 , x 2 ): (test truth of subformula ∀x 3 , φ(x 1 , x 2 , x 3 )) 1. if φ(x 1 , x 2 , 0) is true then increment TruthCounter3 2. if φ(x 1 , x 2 , 1) is true then increment TruthCounter3 3. if TruthCounter3= 2 then test3=true else test3=false 4. if φ(x 1 , x 2 , 0) is true then decrement TruthCounter3 5. if φ(x 1 , x 2 , 1
) is true then decrement TruthCounter3 6. if TruthCounter3 = 0 then do rotation (bad initialization detected)

return test3(truth of subformula)

We now proceed to the detailed description of our construction, starting from expansive counters. Lemma 7.1 (Expansive counters). For any q and any n there exists χ q,n : vqw n → vqw n an expansive network for which all configurations belong to the same cyclcic orbit and with an ordering map ν q,n : vqw n → vq n w verifying ∀x ∈ vqw n : ν q,n (χ q,n (x)) = ν q,n (x)+1 mod q n . χ q,n has an expansion time of at most q n . Moreover, for any fixed q, ν q,n is computable by circuits of size polynomial in n, and there is an algorithm that given n compute in time polynomial in n the circuits representing χ q,n and ν q,n .

Proof. The lemma follows from Example 5.3 which is expansive as shown in Theorem 5.4. Let χ q,n the network of the example and denote by φ the map a → x a used in its definition, and let ρ be the map a → a + 1 mod q n on vq n w. The orbits of ρ obviously consist in a single cycle. The example shows that χ q,n is actually conjugated to ρ, meaning that φ -1 • χ q,n • φ = ρ. So the map ν q,n = φ -1 verifies the property stated in the lemma. It also follows that the orbits of χ q,n consist in a single cycle. It is clear that φ and φ -1 and ρ have polynomial size circuits. Therefore it is also the case for χ q,n which is a composition of these maps. Finally, one should be easily convinced that there is an algorithm that given n computes the circuits we are speaking about.

Equipped with such expansive counters, we can now construct a network that implement the brute force algorithm to test a quantified Boolean formula. More precisely, given any quantified Boolean formula

Ψ = Q 0 x 0 , Q 1 x 1 , ..., Q n-1 x n-1 φ(x 0 , ..., x n-1 )
(where each Q i is either ∃ or ∀ and φ is quantifier-free) we build f Ψ : vqw n → vqw n where q = 2 3n+1 as follows.

To simplify notations, we see any x ∈ vqw n as a n × (3n + 1) array of elements of v2w and use the notation x i,j with i ∈ vnw and j ∈ v3n + 1w so that node i of the automata network in configuration x holds the vector of states (x i,0 , . . . , x i,3n ) ∈ vqw.

We want to interpret any configuration x ∈ vqw n as 2n + 1 configurations distributed over the network: n configurations of v4w n called loop counters, n configurations of v2w n called truth counters and a single configuration of v2w n called the cycle configuration. Intuitively, to each variable of the formula Ψ is attached a loop counter and a truth counter, whose role is to implement the brute force algorithm sketched above. More precisely, for any 0 ≤ k < n we define the following maps:

• the k th loop counter map L k : vqw n → v4w n verifying L k (x) = (2x 0,3k + x 0,3k+1 , . . . , 2x n-1,3k + x n-1,3k+1 ) ∈ v4w n ,

• the k th truth counter map T k : vqw n → v2w n verifying T k (x) = (x 0,3k+2 , . . . , x n-1,3k+2 ) ∈ v2w n ,

• the cycle configuration map C : vqw n → v2w n verifying C(x) = (x 0,3n , . . . , x n-1,3n ).

If λ denotes either L k or T k or C, then for any i ∈ vnw and for any x, x ∈ vqw n we have λ(x) i = λ(x ) i implies x i = x i .

Let σ : v2w n → v2w n be the rotation map, i.e. σ(x) i = x i+1 mod n . Let χ 4 = χ 4,n , ν 4 = ν 4,n , χ 2 = χ 2,n , ν 2 = ν 2,n . The behavior of f Ψ consists in applying either χ 4 or the identity map on loop counters (i.e. incrementing or not the counter), either χ 2 or χ -1

1. L k (y) = χ 4 (L k (x)) if k = n -1 or, when k < n -1, if ν 4 (L k+1 ) = 2 and
ν 4 (L j (x)) = 0 for all j, k < j ≤ n -1. In any other case L k (y) = L k (x).

2. We define the subformula of level k by

Ψ k (x 0 , . . . , x k-1 ) = Q k x k , . . . , Q n-1 x n-1 φ(x 0 , . . . , x n-1 )
and the Boolean value τ k (x) which is true if and only if ν 4 (L k (x)) = 2 and ν 4 (L j (x)) = 0 for all j, k < j ≤ n -1, and

ν 2 (T k ) > 0 when Q k = ∃ (resp. ν 2 (T k ) = 2 when Q k = ∀).
We say that x raises the truth flag at level k when τ k (x) is true. We define the current valuation of variable k as v k (x) = ν 4 (L k (x)) mod 2 and we also define τ n (x) as the truth of the expression φ(v 0 (x), . . . , v n-1 (x)).

3. Then T k (y) is defined as:

(a) χ 2 (T k (x)) if τ k+1 (x) and 0 ≤ ν 4 (L k (x)) < 2, (b) χ -1 2 (T k (x)) if τ k+1 (x) and 2 ≤ ν 4 (L k (x)) < 4, (c) χ 2 (T k (x)) if 4 ≤ ν 4 (L k (x)) < 4 + 2 n and ν 4 (L j (x)) = 0 for all j, k < j ≤ n -1, (d) T k (x) else.
4. we define the Boolean value β(x) which is true if and only if for some k it holds ν 4 (L j (x)) = 0 for all j ≥ k and ν 2 (T k (x)) = 0. We say that the bad counter flag is raised if β(x) is true.

5. Then C(y) = σ(C(x)) if either β(x) or τ 0 (x), and C(x) in any other case.

The behavior of f Ψ can be intuitively understood as follows:

1. counter L k is incremented once during each cycle of counter L k+1 so that they form n nested loops that run independently of Ψ and the rest of the configuration;

2. at each level k the truth flag can be raised only at a precise moment in the cycle of the k th loop counter, and if at least one valuation of variable x k made the subformula Ψ k+1 "true", then the subformula Ψ k is considered "true" when Q k is an ∃ quantifier, and similarly when the two possible valuations of variable x k made Ψ k+1 "true", then Ψ k is considered "true" when Q k = ∀; the cycle. Concretely, if the counter started the cycle with value a then it must again be in value a at step 4 and at the first step of the next cycle, and between step 4 and 4 + 2 n it must take all possible values. The sequence of incrementations/decrementations of the counter during the cycle is independent of its initial value a;

4. a bad counter flag is raised if some truth counter was not initialized to 0 at the beginning of its cycle and therefore cannot be trusted;

5. the cycle configuration is rotated regularly if either a counter cannot be trusted or the formula Ψ is true, otherwise it is left unchanged.

Lemma 7.2.

There is an algorithm working in polynomial time that, given a quantified Boolean formula Ψ, builds circuits that compute f Ψ (these circuits are of polynomial size).

Proof. The construction above gives a polynomial time algorithm to build f Ψ from Ψ, which is a collection of 3n 2 + n Boolean circuits which are themselves finite combinations of L k , T k , C, χ q and ν q (for q = 2 or 4), τ k and β, all being circuits that can be generated in polynomial time (by Lemma 7.1 for χ q and ν q , and by straightforward verification for the rest).

From the description above, the intended behavior of f Ψ is a brute-force algorithm to test the truth of formula Ψ and make the evolution of the cycle configuration component depend on it. However this only works on well initialized configurations, while expansivity is a global property about all possible pairs of configurations. The next three lemmas show that badly initialized configurations are never a problem. First, the following lemma shows some regularity of the cycle of each counter: they always go back to their initial value after one cycle, whatever there initial value and whatever the context.

∈ vnw, if ν 4 (L j (f Ψ (z))) = 0 for all j ≥ k then T k (f 4 n(n-k) Ψ (z)) = T k (z).
Proof. We proceed by downward induction on k starting from k = n -1. For t ∈ {0, 1} we have that T

n-1 (f t+1 Ψ (z)) = χ 2 (T n-1 (f t Ψ (z))) if and only if T n-1 (f t+3 Ψ (z)) = χ -1 2 (T n-1 (f t+2 Ψ (z))), because v i (f t+2 Ψ (z)) = v i (f t Ψ (z)) for all i ∈ vnw and therefore τ n (f t+2 Ψ (z)) = τ n (f t Ψ (z)). We deduce that T n-1 (f 4 Ψ (z)) = T n-1 (z). We also have T n-1 (f 4 n Ψ (z)) = χ 2 n 2 (f 4 Ψ (z)) by definition of f Ψ . Since χ 2 n
2 is the identity map we deduce T n-1 (f 4 n Ψ (z)) = T n-1 (z) which proves the induction hypothesis for k = n -1. Suppose now that the hypothesis holds for all levels j ≥ k + 1 (k ≤ n -2) and consider some z ∈ vqw n such that ν 4 (L j (f t0 Ψ (z))) = 0 for all j ≥ k. Denote z t = f t Ψ (z) for any t ≥ 0. Let ∆ = 4 n(n-1-k) so that ν 4 (L k (z i•∆ )) = i for 0 ≤ i < 4 n . By induction hypothesis and for all k + 1 ≤ j < n we have T j (z 2∆ ) = T j (z 0 ). We also have

L j (z 2∆ ) = L j (z 0 ) for all k + 1 ≤ j < n and v j (z 2∆ ) = v j (z 0 ) for all j ∈ vnw (because ν 4 (L k (z 2∆ )) = ν 4 (L k (z 0 )) mod 2 and L j (z 2∆ ) = L j (z 0 ) for j = k).
The same equalities of counters and valuations hold between z 2∆+1 and z 1 because the action of f Ψ on the counters T j , k + 1 ≤ j < n, only depends on actually infinite. Indeed, by hypothesis a bad counter flag is raised at some step t 0 in the orbit of x (equivalently of x ), which means that for some k we have ν 4 (L j (f t0 Ψ (x))) = 0 for all j ≥ k and ν 2 (T k (f t0 Ψ (x))) = 0. The claim implies that ν 2 (T k (f t0+m•4 n(n-k) Ψ (x))) = 0 for any m ≥ 0 (note that m • 4 n(n-k) is a multiple of the period of all counters L j for j ≥ k). The sequence (t n ) is such that for any n ≥ 0 we have both

C(f 1+tn Ψ (x)) = σ n (C(x)) and C(f 1+tn Ψ (x )) = σ n (C(x )).
Finally, consider j ∈ vnw such that C(x) j = C(x ) j and any i ∈ vnw, so that σ i-j mod n (C(x)) i = σ i-j mod n (C(x )) i . We deduce that f

1+t i-j mod n Ψ (x) i = f 1+t i-j mod n Ψ (x ) i .
The next lemma shows the link between the truth of Ψ and the behavior of f Ψ on "good" pairs of configuration. Lemma 7.6. If a pair of configuration x = x agrees on all counters and no bad counter flag is raised in their orbits, then the pair is expansive if the formula Ψ is true. Moreover, if Ψ is false and x i = x i for some i ∈ vnw then the pair is not expansive at node i.

Proof. First, as said in the proof of Lemma 7.5, equality of counters is preserved under iteration and therefore predicate τ 0 is true at step t in the orbit of x if and only if τ 0 is true at step t in the orbit of x . This implies that for all t there is t such that C(f

t Ψ (x)) = σ t (C(x)) and C(f t Ψ (x )) = σ t (C(x )) and in particular it is always the case that C(f t Ψ (x)) = C(f t Ψ (x )
). So we can suppose without loss of generality that ν 4 (L k (x)) = ν 4 (L k (x )) = 0 for all k ∈ vnw (otherwise we consider configurations at the same time step in both orbits for which it is the case). We must also have ν 2 (T k (x)) = ν 2 (T k (x )) = 0 for all k ∈ vnw because no bad counter flag is raised by hypothesis. We show by downward induction on k starting from k = n -1 that for any y in the orbit of x such that ν 4 (L k (y)) = 2 and ν 4 (L j (y)) = 0 for all k < j ≤ n -1, then τ k (y) holds if and only if Ψ k (v 0 (y), . . . , v k-1 (y)) is true. Take any configuration y = f t Ψ (x) in the orbit of x with ν 4 (L n-1 (y)) = 2, and let y -1 = f t-1 Ψ (x) and y -2 = f t-2 Ψ (x) (t must be greater than 2 because ν 4 (L n-1 (x)) = 0 by hypothesis). We have ν 4 (L n-1 (y -2 )) = 0 and ν 2 (T n-1 (y -2 )) = 0 (no bad counter flag hypothesis). Therefore ν 2 (T n-1 (y

-1 )) = 1 if and only if τ n is true, i.e. if φ(v 0 (y -2 ), . . . , v n-1 (y -2 )) is true. Similarly ν 2 (T n-1 (y)) = ν 2 (T n-1 (y -1 )) + δ where δ = 1 is φ(v 0 (y -1 ), . . . , v n-1 (y -1 )) is true and 0 otherwise. Said dif- ferently, since v n-1 (y -2 ) = 0 and v n-1 (y -2 ) = 1 and v j (y -2 ) = v j (y -1 ) for 0 ≤ j < n -1, ν 2 (T n-1 (y)) = # v ∈ {0, 1} : φ(v 0 (y), . . . , v n-1 (y)) . Thus, τ n-1 (y) is true if and only if # v ∈ {0, 1} : φ(v 0 (y), . . . , v n-1 (y)) ≥ 1 when Q n-1 = ∃ and if and only if # v ∈ {0, 1} : φ(v 0 (y), . . . , v n-1 (y)) = 2 when Q n-1 = ∀.
This exactly means that τ n-1 (y). The induction step is similar and hence omitted. We have shown in particular that if y verifies ν 4 (L 0 (y)) = 2 and ν 4 (L j (y)) = 0 for all 0 < j ≤ n -1, then τ 0 (y) holds if and only if Ψ 0 = Ψ is true. We deduce that if Ψ is false then C(y) = C(x) for any y in the orbit of x, and therefore if the pair x, x is such that C(x) = C(x ) but C(x) i = C(x ) i , then it is not expansive at node i. On the contrary, if Ψ is true, then for any t there is t such that C(f t Ψ (x)) = σ t (C(x)) so any pair satisfying the hypothesis of the lemma is expansive at any node. Theorem 7.7. Problem EXPAN is PSPACE-complete.

Proof. It is straightforward to check expansivity in polynomial space (for each node and each pair of configurations test if their orbits differ at the node at some time step bounded by q n where n is the size of the network and q the state set). PSPACE-hardness follows from the lemmas and the fact that deciding whether a quantified Boolean formula is true is a PSPACE-complete problem.

Note that our construction actually shows that it is PSPACE-complete to separate networks which are expansive (the trace ρ v is injective for any node v) from networks which are not expansive at any single node (for all v, the trace ρ v is not injective). It also shows that it is PSPACE-complete to decide whether a network is quasi-expansive because the constructed network is either expansive, or acts as the identity on the cycle configuration and thus cannot be quasi-expansive. Moreover, our result actually improves the co-NP-hardness of observability proven in [START_REF] Laschov | Observability of boolean networks: A graph-theoretic approach[END_REF] because, as said in the introduction, expansivity can be seen as a particular form of observability (where the output of the system is the trace at some node). Finally, the alphabet size in our construction only depend on the number of quantifiers in the formula, so we actually show Σ phardness for each level p of the polynomial hierarchy with a fixed alphabet size.

Stronger form of expansivity

The notion of expansivity considered so far asks to determine the initial configuration from the trace at any given node. Here, we strengthen the notion by asking to determine the initial configuration from any large enough 'observation' of the network during the first n time steps. Let f ∈ F(n, q). Consider any sequence ω of n pairs (vertex, time step): ω = v 1 , t 1 ), . . . , (v n , t n ) where v i ∈ vnw and t i ∈ vnw for all i such that 1 ≤ i ≤ n. The associated observation is the map τ ω : vqw n → vqw n given by τ ω (x) = f t1 (x) v1 , f t2 (x) v2 , . . . , f tn (x) vn . We say f is super-expansive if for any ω, the map τ ω is injective. Looking again at matrix M x defined previously, f is super-expansive if x can be determined from any set of n entries in this matrix. Proposition 8.1. Let D be a graph with n nodes. If f ∈ F[D, q] is superexpansive, then D is the complete graph (the graph with n 2 arcs).

Proof. Suppose that D does not contain the arc ij and consider any f ∈ F[D, q]. Let ω = (1, 1), . . . , (i -1, 1), (j, 2), (i + 1, 1), . . . , (n, 1) , then the interaction graph of τ ω has a source (namely i) and hence is not coverable. Thus, by [START_REF] Gadouleau | On the rank and periodic rank of finite dynamical systems[END_REF]Corollary 6], τ ω is not bijective.

Using a similar technique as in the proof of Theorem 3.10 we can show the existence of super-expansive networks.

preserved by permutation of ω). Since q > n 2 n 2 n , we have q n 2 > n 2 n 2 n q n 2 -1 , and hence there exists a choice of values for all the variables X e such that M is super-expansive.

As an application, we shall see that any super-expansive (linear) network naturally gives rise to a (linear) orthogonal array and a maximum distance separable code. This can be formalized as follows (see [START_REF] Hedayat | Orthogonal Arrays[END_REF][START_REF] Macwilliams | The Theory of Error-Correcting Codes[END_REF] for an overview of the topic).

An orthogonal array of strength s over alphabet vqw and of index 1 is a N × M array A of elements of vqw with s ≤ N and such that for any set of s columns of A no s-tuple appears two times. When q is a prime power, we say the orthogonal array A is linear if the set of rows is a vector space over GF(q). A code C is a set of words from vqw N and its minimal distance d(C) is the minimal Hamming distance between two distinct elements of C. When q is a prime power, a code C is linear if it forms a sub-vector space of GF(q) N . A maximum distance separable (MDS) code is a code verifying the equality in the so-called Singleton bound [START_REF] Macwilliams | The Theory of Error-Correcting Codes[END_REF], i.e. such that |C| = q N -d(C)+1 .

The link between these combinatorial objects and super-expansive networks is as follows. Given any f ∈ F(n, q) let A f be the n 2 × q n array whose set of rows is {L x : x ∈ vqw n } where L x = (f (x) 1 , f (x) 2 , . . . , f (x) n , f 2 (x) 1 , . . . , f 2 (x) n , . . . , f n (x) 1 , . . . , f n (x) n ). Proposition 8.3. If f ∈ F(n, q) is super-expansive then A f is an orthogonal array of strength n and index 1, and its set of rows is an MDS code of minimum distance n 2 -n + 1. If moreover q is a prime power and f is linear, then A f is linear and its set of rows is an MDS linear code. Proof. To any set of n columns of A f is naturally associated ω = v 1 , t 1 ), . . . , (v n , t n ). The fact that τ ω is injective (by super-expansivity of f ) exactly means that no pair of distinct lines L x can coincide on this set of columns. Hence, A f is an orthogonal array of strength n. The fact that it also correspond to a MDS code is well-known and general [START_REF] Hedayat | Orthogonal Arrays[END_REF]Theorem 4.21]. Finally, it is straightforward to see that when f is linear then A f is a linear and the corresponding code also.

Using the classical bound of K. A. Bush on MDS codes [START_REF] Bush | Orthogonal arrays of index unity[END_REF], we get a lower bound on the alphabet of a super-expansive network.

Corollary 8.4.

There is no super-expansive network with n nodes over the alphabet vqw if q ≤ n 2 -n.

Proof. This follows immediately from the Bush bound [START_REF] Bush | Orthogonal arrays of index unity[END_REF], which states that any orthogonal array of index 1, strength t over alphabet vqw of size N × M verifies: N ≤ t + q -1. The corollary follows from the previous proposition with N = n 2 and t = n.

Perspectives

The results presented above leave us with a contrasted global picture: on one hand, expansivity is easy to characterize and ubiquitous on linear systems as soon as simple graph theoretical constraints on the network are satisfied, and, on the other hand, the general (non-linear) case provides behaviors that are impossible in the linear case (e.g. exponential expansion time) but is PSPACEhard to decide. Among the possible future research directions, we would like to put forward the following:

• When making the parallel with cellular automata, it is striking that we obtained a hardness result for expansivity in automata networks, while decidability of positive expansivity in cellular automata is still a major open problem (see [START_REF] Boyle | Open problems in symbolic dynamics[END_REF]Problem 19] or [START_REF] Kari | Theory of cellular automata: A survey[END_REF]Problem 7]). To that extent, we think that two restrictions on the possible inputs of the expan problem are important to study: bounded degree networks and uniformity of the local rules (like in cellular automata).

• Several results above gave some hints on the crucial role of the alphabet. We are far from understanding to property of expansivity for fixed alphabet, starting from the characterization of their of interaction graph. In particular, we left open this simple question: do strongly connected and coverable graphs of degree d admit expansive networks of alphabet bounded by d?

• Beyond expansivity, we think that many classical properties of topological dynamics [START_REF] Kůrka | Topological and symbolic dynamics[END_REF] can be adapted to automata networks through the notion of trace which is central in this paper. For instance, one can imagine meaningful notions of mixingness, transitivity or equicontinuity points for automata networks, and study there relations to expansivity. We also think that studying the traces of automata networks from a formal language point of view is promising.

  , a), thus contradicting surjectivity.

Lemma 7 . 3 .

 73 For any z ∈ vqw n and any k

To help readability we use pseudo-code with call/return of subroutines instead of loops with global variables. Not that local variables test2 and test3 are artifacts of the pseudo-code and are not present in the real construction.

or the identity map on truth counters (i.e. either incrementing, decrementing or not changing the counter) and either σ or the identity map on the cycle configuration, all choices depending on the context. Precisely y = f Ψ (x) is defined by:

to implement this idea, the truth counter at level k is updated according to the following cycle governed by the loop counter of level k (one step of the cycle is executed at each value change of L k ): it is incremented when the truth flag at level k+1 is raised, for each valuation of x k during the two first steps of the cycle, then decremented when the truth flag at level k + 1 is raised, for each valuation of x k during the two next steps, then incremented 2 n times, then left unchanged until the end of

$ This work was partially funded by the CNRS and Royal Society joint research project PRC1861 and the French ANR project FANs ANR-18-CE40-0002.

the values of the L j and T j (k + 1 ≤ j < n) and the valuations v j for all j ∈ vnw. By a direct induction we have the same equalities between counters of z t+2∆ and z t for 0 ≤ t ≤ 2∆, in particular τ k+1 (z t ) holds if and only if τ k+1 (z t+2∆ ) holds. We deduce that T k (z t+1 ) = χ 2 (T k (z t )) if and only if T k (z t+∆+1 ) = χ -1 2 (T k (z t+∆ )) for 0 ≤ t ≤ 2∆. It follows that T k (z 4∆ ) = T k (z 0 ) and since T k (z 4 n(n-k) ) = χ 2 n 2 (T k (z 4∆ )) by definition of f Ψ we finally deduce

2 is the identity map).

The next two lemmas show that "bad" pairs of configurations always comply with expansivity. Given i ∈ vnw, we say that a pair of configurations x, x ∈ vqw n is expansive at node i if there is t > 0 such that f t Ψ (x) i = f t Ψ (x ) i . Lemma 7.4. If a pair of configurations x, x differ in some loop counter ( i.e. L k (x) = L k (x ) for some k ∈ vnw) or in some truth counter ( i.e. T k (x) = T k (x ) for some k ∈ vnw) then it is expansive at node i for any i ∈ vnw.

Proof. Suppose first that L k (x) = L k (x ) for some k. By a simple downward induction on k (from k = n -1 to k = 0) and for any configuration y ∈ vqw n we have

for some k and take the largest such k. Case 3 of the definition of f Ψ ensures for any z ∈ vqw n that:

where λ is either the identity, χ 2 or χ -1 2 and the choice of λ only depends on the values L j (z) (for j ∈ vnw) and T k+1 (z) (if k¡n-1).

if ν

)) = 4 (it exists because x and x agree on all loop counters) and consider z = f t0 Ψ (x) and z = f t0 Ψ (x ). By point 1 above and because T k (x) = T k (x ) we must have T k (z) = T k (z ). Applying expansivity at node i of χ 2 we know there exists 0

) i so the pair x, x is expansive at node i.

Lemma 7.5. If a pair of configurations x = x agrees on all counters ( i.e. L k (x) = L k (x ) and T k (x) = T k (x ) for all k) but a bad counter flag is raised in either orbit, then this pair is expansive at any node i ∈ vnw.

Proof. The equality of all counters (L k (x) = L k (x ) and T k (x) = T k (x ) for all k) is preserved under iteration by definition of f Ψ , therefore for any t it holds that β(

). Denote by (t n ) the ordered sequence of time steps t for which either β(f t Ψ (x)) or τ 0 (f t Ψ (x)) holds. From the claim above we deduce that the sequence (t n ) defined above is Theorem 8.2. For any n and any prime power q > n 2 n 2 n there exists a super-expansive linear network with n nodes over GF(q). Proof. The proof technique is similar to that of Theorem 3.10. First for any linear function f (x) = xM and any ω = v 1 , t 1 ), . . . , (v n , t n ), the observation τ ω is injective if and only if the matrix

. . . M tn vn is nonsingular (straightforward adaptation of Lemma 2.2). Since injectivity of τ ω is preserved by permutation of ω, we suppose that

Like for Theorem 3.10 our proof is nonconstructive: we shall see the nonzero coefficients of the matrix M as variables (X ij ) i,j∈vnw , then the determinant of N ω is a polynomial of these variables; if the field is large enough, then we can always evaluate that polynomial to something other than zero, provided it is not the null polynomial. Using the correspondence between walks on the complete graph and monomials, the determinant of N ω can be expressed as:

where each monomial appearing in P σ is of the form

) is a walk of length t i from node σ(i) to node v i . We shall now choose a specific permutation σ and a specific monomial appearing in P σ , and show that it does not appear in any other P σ for σ = σ . Let A = {v 1 , . . . , v n } and choose v 1 , . . . , v n distinct nodes verifying:

Our permutation is σ = i → v i , and we consider the monomial M = i X ti-1 v i v i X v i vi which clearly appears in P σ . Consider any permutation σ and suppose that M appears in P σ , i.e. M = n i=1 ti k=1 X wi(k) where w i (1)

{i} is a singleton then we must have σ(i) = v i because in this case no other edge than v i v i arrives at v i and appears in M . If not, let k = max I v . Since v k ∈ A and since in M there is no edge arriving at v k other that v k v k and no edge starting from v k other than v k v i , then the only walk that can contain edge v k v k is a walk starting from v k , arriving at v and it must be of length t k to exhaust the power of X v k v k in M . Therefore, we must have σ (k) = v k . Continuing with the same reasoning we show that σ and σ are equal on I v for all v, which means σ = σ. This shows that det(N ω ) = 0.

The degree of N ω is clearly at most n 2 . By the Schwartz-Zippel Lemma [START_REF] Mullen | Handbook of Finite Fields[END_REF]Theorem 7.1.4], there are at most n 2 q n 2 -1 choices for the values of X e for which det(N ω ) = 0. Thus, there are at most n 2 n 2 n q n 2 -1 choices for the values of X e for which some observation τ ω fails to be injective (recall that injectivity of τ ω is