Pablo Arrighi

Amélia Durbec

Pierre Guillon

Graph subshifts

We propose a definition of graph subshifts of finite type that can be seen as extending both the notions of subshifts of finite type from classical symbolic dynamics and finitely presented groups from combinatorial group theory. These are sets of graphs that are defined by forbidding finitely many local patterns. In this paper, we focus on the question whether such local conditions can enforce a specific support graph, and thus relate the model to classical symbolic dynamics. We prove that the subshifts that contain only infinite graphs are either aperiodic, or feature no residual finiteness of their period group, yielding non-trivial examples as well as two natural undecidability theorems.

Graphs

). Let π be a finite set, Π = π 2 , and V some universe of names.

Introduction

Subshifts of finite type are well studied objects in symbolic dynamics [START_REF] Lind | An introduction to symbolic dynamics and coding[END_REF] and ergodic theory. Given an alphabet Σ, a subshift of finite type (SFT) on Z d is a set of configurations Y ⊆ Σ Z d that do not contain a given finite set of forbidden patterns F ⊆ Σ {-n,n} d . In spite of their relatively benign and local definition, SFT have proven to have complex global behaviours. One example of such results is the existence of aperiodic SFTs in dimension 2, but not in dimensional 1. Even some natural problems such as determining whether an SFT contains a periodic configuration at all, are proven to be undecidable [START_REF] Berger | The undecidability of the domino problem[END_REF]. This local-to-global complexity is in fact shared by multiple dynamical systems and most notably with Cellular Automata (CA) [START_REF] Langton | Self-reproduction in cellular automata[END_REF]. However, the two models are deeply connected as CA of dimension d can be seen as subshift of dimension d + 1. This connection as been used to prove multiple theorems on different subclasses of CA [START_REF] Kari | The nilpotency problem of one-dimensional cellular automata[END_REF]. This result is also one of the original motivations of this paper: Graph subshifts ought to be a mean to study a generalization of CA called Causal Graph Dynamics (CGD) [START_REF] Arrighi | Reversibility vs local creation/destruction[END_REF]. CGD extend CA in two complementary ways: first because they are defined on arbitrary graphs of bounded degree m, and second because they allow for the graph itself to evolve, according to a local, shift-invariant rule. Graph subshifts aim to encompass CGD spacetime diagrams as a subclass. Subshifts have already been generalized to configurations over Cayley graphs of finitely presented groups. However this is not enough to simulate CGD as all configurations share the same support graph. In this paper, we provide a formalism which relaxes this constraint, allowing the support of the graphs itself to also be prescribed by set of forbidden patterns. We introduce and formalize the notion of graph subshifts, i.e. sets of graphs that are defined by forbidding finitely many local patterns. The natural question to ask, then, is whether we may enforce, by means of such local constraints only, that the set of graphs be of a particular shape. In particular, notice that a graph subshift may contain a finite or an infinite number of graphs (up to shift), and that the graphs themselves may be of finite or of infinite size. In this first paper we focus on the question whether there exist subshifts whose graphs are all of infinite size. The question is non-trivial; for instance we prove that the problem whether a given set of forbidden patterns induces a graph subshift without finite configuration is undecidable. The problem whether it uniquely fixes the support graph is also shown undecidable. Still, we prove that the graph subshifts that contain only infinite graphs are either aperiodic, or feature no residual finiteness of their period group, yielding us with non-trivial examples and establishing connections with different areas of mathematics : periodicity from symbolic dynamics; residually finite groups from combinatorial group theory [START_REF] Baumslag | Some two-generator one-relator non-hopfian groups[END_REF] [START_REF] Lyndon | Combinatorial Group Theory[END_REF]; and graph covers as used in graph theory and distributed computing.

Graphs. Our graphs are the usual, connected, undirected, possibly infinite, bounded-degree labeled graphs, but with a few added twists:

-Vertices are connected through their ports. An edge is an unordered pair {x : a, y : b} of V × π, or a singleton {x : a} standing for a self-loop, where x, y are vertices and a, b ∈ π are ports. Each port is used at most once per node: if e, e ∈ E(G) intersect, they must be equal. As a consequence the degree of the graph is bounded by |π|. -Each vertex x is given a label σ(x), taken within a finite set Σ, also referred to as an internal state. The set of all graphs having ports π, vertex labels Σ is denoted GΣ,π, or simply G. We single out a vertex as the origin:

Pointed graph non-modulo. A pointed graph is a pair (G, p) with p ∈ V (G). The set of pointed graphs with states in Σ and ports π is written PΣ,π, or simply P.

Here is when graph differ only modulo names of vertices:

Graph Isomorphism. An isomorphism R is a function from G to G which is specified by a bijection R(.) from V to V . The image of a graph G under the isomorphism R is a graph RG having :

-A set of vertices R(V (G)).

-A set of edges { {R(u) : a, R(v) : b}| {u : a, v : b} ∈ E(G)}.

-Internal states given by σ • R -1 . Similarly, the image of a pointed graph P = (G, p) is the pointed graph RP = (RG, R(p)). When P and Q are isomorphic we write P ≈ Q, defining an equivalence relation on the set of pointed graphs. Notice that pointed graph isomorphism rename the pointer in the same way as it renames the vertex upon which it points; which effectively means that the relative position of vertices w.r.t to the pointer is unchanged.

Pointed graphs modulo. The goal of this twists is to work with the set of graphs that is a compact space. Indeed, consider a graph G, a vertex x ∈ V (G), and D = G r

x the disk of radius r around x, i.e. the subgraph of G induced by the r-neighbors of x in G. Now forgetting about G, this D is one amongst the many possible disks of radius r that can appear in G. In order for the set of graphs to form a compact space, one requirement is that the set of disks of radius r be finite. Morally this is the case, since the degree is bounded by |π|. Vertex names x, y, z jeopardize this however; we must get rid of them. Thus, -Graphs are endowed with a privileged pointed vertex p playing the role of an origin.

-These pointed graphs are considered modulo isomorphism, so that only the relative positions of vertices matter. The set of all pointed graphs modulo is denoted XΣ,π, or simply X . Given a graph non-modulo G, and a vertex p ∈ V (G), we write X((G, p)) for the corresponding pointed graph modulo. Additionally the set of disks of radius r with states Σ and ports π is written X r .

Paths and vertices.

Over graphs modulo isomorphism without pointer, vertices no longer have a unique identifier, which makes designating a vertex a daunting task. Fortunately, our graphs are pointed, so that any vertex û can always be designated by some sequence of ports u that leads to it, starting from the origin. Given a pointed graph modulo X, its set of paths, starting from the origin, forms a subset L(X) of Π * with Π = π 2 . Whenever two paths u and v lead to the same vertex, we write u ≡X v. Thus vertex û is really the ≡X -equivalence class of u, hence the hat notation. The set of these equivalence classes, a.k.a vertices, is denoted V (X). Notice that, starting from origin, following path v = (ab) • • • (cd) and then path v = (dc) • • • (ba), leads back to the vertex at the origin, namely ε.

Remark 1 Notice that two paths u, u designate the same vertex û = u if and only if for every v ∈ L(X), uv = u v.

Remark 2 A reduced path is a path that does not go through the same edge twice consecutively in opposite directions, i.e. u.abba.v is not simple as it can be reduced to u.v. The language up to this reduction equivalence is a groupoid for concatenation (and inversion), i.e. alike a group but its law is partially defined. The set of (centered) cycles, i.e. reduced paths from the pointer back to it, is a subgroup of it (concatenation and inversion are always defined among them). The set of vertices is the quotient of the set of reduced paths by the following equivalence relation: u ≡X v if and only if there exists a cycle c such that u = c.v. Indeed, whenever they designate the same vertex û = v, we have u = (uv)v, where uv is a cycle. Nevertheless, concatenation, does not induce a semigroup at the level of vertices, since we may have û = v and yet wu = wv.

Operations over pointed Graphs modulo

Shift. Let X ∈ X be a pointed graph modulo and G its associated graph. Consider u ∈ L(X). Then Xu is X((G(X), û)). The pointed graph modulo Xu is referred to as X shifted by u.

Back to graphs non-modulo. Sometimes we still need to manipulate usual graphs, where vertices do have names. For this purpose we use a canonical naming function X ∈ X → G(X) ∈ G, which names each vertex of X by the set of paths that lead to it, starting from ε. This G(X) is referred to as 'the associated graph'. One has X(G(X), ε) = X.

Topology on pointed graphs modulo

Having a well-defined notion of disks allows us to define a topology upon X , which is the natural generalization of the well-studied Cantor metric upon CA configurations [START_REF] Hedlund | Endomorphisms and automorphisms of the shift dynamical system[END_REF].

Definition 1 (Gromov-Hausdorff-Cantor metrics) Consider the function

d : X × X -→ R + (X, Y ) → d(X, Y ) = 0 if X = Y (X, Y ) → d(X, Y ) = 1/2 r otherwise
where r is the minimal radius such that X r = Y r . The function d(., .) is such that for > 0 we have (with r = -log 2 ( ) ):

d(X, Y ) < ⇐⇒ X r = Y r .
Remark 3 This defines an ultrametric distance, and the topology can be seen as a product of discrete topologies over the (unions of finitely many) discs of each radius.

Subshifts

Given a pointed graph modulo X, a word in Π * designates a vertex, and a language L ⊆ Π * designates a finite set of vertices. If, moreover, L is stable under taking the prefix, then the designated vertices induce a connected subgraph of X which we refer to as 'cut'. For instance, a cut could represent a spacelike surface within a spacetime diagram. Given a set Z of graphs, one may be interested in selecting those whose cut according to L equals some graph Z, which we refer to as 'cylinder'. This could be, for instance, because Z represents the set of every possible spacetime diagram, and Z a particular initial condition.

Definition 2 (Cuts and cylinders) Consider L ⊆ Π * a prefix-stable language, i.e. such that uv ∈ L implies u ∈ L. The L-cut of a graph X ∈ X is the subgraph induced by the vertices

{ û| u ∈ L ∩ L(X)}. It is denoted X |L . Consider Z ⊆ X , we write Z |L for X |L X ∈ Z . Consider Z ∈ Z |L , the cylinder of Z within Z is X ∈ Z X |L = Z . It is denoted [Z] Z .
Definition 3 (Subshift) Let F be a set of tuples (F, L), where each F is a finite graph and each L a finite prefix-stable language. The subshift forbidding F is

Z = X ∈ GΣ,π ∀v ∈ L(X), ∀(F, L) ∈ F , (Xv) |L = F .
It is of finite type if F can be chosen finite.

Remark 4

The following are equivalent.

1. Z is a subshift of finite type. 2. Z is the subshift forbidding some F × {M } where F is a finite set of finite graphs and M a single finite prefix-stable language. 3. Z is the set of graphs allowing some finite set A of tuples (A, L), where A is a finite graph and L a finite prefix-stable language-in the sense that:

Z = X ∈ GΣ,π ∀v ∈ L(X), ∃(A, L) ∈ A, (Xv) |L = A .
4. Z is the set of graphs allowing A × {M } where A is a finite set of finite graphs and M a single finite prefix-stable language.

Proof. 1 =⇒ 2 For every F, define M = (F,L)∈F L and F = (X \ Z) |M . F × {M } defines the same subshift as F. ⇐⇒ 4 Similarly, for every A, define M = (F,L)∈F L and A = Z |M . A × {M } defines the same subshift as A. ⇐⇒ 4 The subshift Z obtained by forbidding F × M is the same as that obtained from allowing

A × M = (X |M \ F ) × M . Note that X |M is finite. =⇒ 1; 4 =⇒ 3 Obvious.

Definition 4

The prefix-stable language M is the same in Conditions 2 and 4 of Remark 4. It is called a defining window for Z. We can assume that it is the minimal possible one.

Remark 5

The duality between forbidding and allowing no longer holds in general when the subshifts are not of finite type. For example we can think about the set of graphs authorizing exactly those finite graphs which have exactly one red vertex. This set however is not closed topologically (cf. [START_REF] Arrighi | Cellular automata over generalized cayley graphs[END_REF] as summarized by the Appendix) and hence it is not a subshift. Its closure is the so-called one-dimensional sunny-side-up subshift, as defined by forbidding those finite graphs having two red vertices.

Remark 6 In the pairs (F, L), L cannot always be assumed to be the language labelling the paths of F . For example, requiring every vertex to have an edge with port a ∈ Σ is a very natural finite-type condition, but this SFT is not of the form X ∈ GΣ,π ∀v ∈ L(X), ∀F ∈ F , (Xv) |L F = F as the LF do not contain a and hence cannot tell that it is absent. The same remark holds for the dual definitions, i.e. through allowed patterns: think of the SFT consisting of those graphs having no port a ∈ Σ.

The equivalent definitions all capture the concept of local constraint, and in the following sections we often define our SFTs by describing some conditions that graphs must locally satisfy. Among these conditions, nearest-neighbor constraints are those defined with a single edge between two vertices, that is L ∈ Π.

Examples

Example 1. A directed 2-regular SFT is an SFT with ports π = {a, a , b, b } obtained by imposing constraints: 1/ enforcing that edges be of the form pp ; 2/ enforcing that all ports be occupied. It contains, amongst many others, the Cayley graph of the free group over two generators (a tree), as well as those of all of its quotients. . The SFT is defined by forbidding all but these patterns, on their corresponding languages.

Example 2 (Locally grid-like SFT). We can define a graph SFT with ports π = {a, a , b, b } corresponding to the monochromatic fullshift on a, b|aba -1 b -1 = ε , by imposing three families of constraints: 1. enforcing that edges be of the form pp ; 2. enforcing that all ports be occupied; 3. enforcing that the subgraph induced by {ε, aa , bb , aa bb , bb aa } obeys the relation i.e. form a square as in Fig. 2). This graph SFT obviously contains the Cayley graph of a, b|aba -1 b -1 = ε , but also the Cayley graphs of most quotient subgroups (excluding really small groups such as the trivial group).

A similar construction can be performed for any finitely presented group, and via a more precise third constraint, get a cleaner statement (with all possible quotients).

Example 3. Consider a finitely presented group Γ = J |R , that is, a group generated by the abstract finite set J , and R represents a minimal set of relations, that is words over J J -1 that represent the identity element (and from which all such words can be derived). For example Z 2 = a, b|aba -1 b -1 (it will always be implicitly given by this canonical presentation) and F2 = a, b| . For every alphabet Σ, there is a canonical way to associate a Cayley SFT Z Γ Σ to this group. Define π = J J -1 and the following constraints: 1. each edge involves two inverse ports; 2. every vertex must have all possible ports; 3. for every word u ∈ R and L its language of prefixes, one forbids the pair (Y, L) for every graph Y supported by L in which path u is not a cycle back to the origin. This SFT obviously contains the Cayley graph of Γ , but also all of the Cayley graphs of its quotient subgroups, as will be seen in the next section. For example, Z Z 2 Σ contains the infinite grid as well as tori and cylinders, and Z F 2 Σ actually contains all Cayley graphs of all groups with two generators. Let Γ be a finitely presented group. A SFT is defined by Γ -NN constraints if they include precisely the forbidden patterns defining Z Γ and some additional nearest-neighbor forbidden patterns. Note that if Γ = F k , then F k -NN constraints are simply constraints on the edges, provided the correct regularity of the graph.

Example 4 (Hard-square model). The hard-square model SFT is defined by Z 2 -NN constraints: Z ⊆ X {0,1},a,a ,b,b such that for every configuration X and edge {u : a, v : b} ∈ E(X), one has that σx(u) = 0 or σx(v) = 0. This can be expressed as an SFT by forbidding the black/white coloured versions of Fig. 2 that have two adjacent black vertices. This is a direct generalization of a well-known SFT on Z 2 and other subgroup that go by the same name. As a graph SFT, it not only contains all the configuration that are already present on Z 2 such as in Fig. 3, but also new infinite configurations such as the cylinder of Fig. 4, and even finite configuration such as tori only containing 0.

Besides finitely presented groups, the notion of quotient of a group can be extended to periodic graphs, which is the subject of the following section.

Example 5. Given any subshift Z, one can define the subshift of its infinite graphs, by additionnally forbidding (F, Lπ 2 ) for every prefix-stable language L ∈ Π * and every graph F such that F |L = F . Indeed this condition exactly means that L was already describing all possible vertices in F , and longer paths do not add any. Nevertheless, this subshift is very rarely of finite type, as we will see in the following section.

On the contrary, all SFTs presented so far contain finite graphs. It is not obvious a priori whether some SFTs contain only finite graphs, or even whether they are homogeneous, i.e. all the graphs share a common support. We will discuss these properties in the next sections.

5 Periodicity and finiteness

Quotient and Periods

Definition 5 (Period) Any word u ∈ L(X) such that X = Xu is called a path-period. The corresponding vertex û is called a period. The stabilizer of X is its set of periods; it is denoted by S(X). X is called weakly periodic if S(X) {ε}, strongly aperiodic otherwise.

Notice that if X is weakly periodic, then either S(X) is infinite or every period û is torsion, i.e. u n = ε for some n ≥ 2.

Remark 7

The set of reduced path-periods is a subgroup of the groupoid of reduced paths defined in Remark 2. The set of cycles is a normal subgroup of the group of path-periods (since if u is a period and v is a cycle, then uvu is still a cycle). Like in Remark 2, the stabilizer is the quotient of the group of reduced path-periods by the normal subgroup of cycles (since if u and v are paths to the same vertex, then u = (uv)v, where uv is a cycle).

All the statements in Remark 7 are easy to prove, but we concentrate on proving the next proposition, which will be useful for the rest of the paper.

Proposition 1 Let X be a graph. For û, v in S(X), the concatenation operation ûv → uv, and the reverse operation û → u are well-defined, and endow S(X) with a group structure.

Proof.

-Let u ≡X u and v ≡X v . Remark 1 already gives that uv ≡X u v. Now from X u = X, one can deduce that v ≡X u v , which means that u v ≡X u v . We have proven that uv ≡X u v , so that the concatenation operation is well defined over vertices. -Remark 1 gives that u u = ε = uu ≡X u u. This means that u ≡X u u, and since X = X u , u ≡X u. We have proven that the inversion is well defined over vertices. -Neutral element: the origin ε is a period, because Xε = X.

-Concatenation: If û, v ∈ S(X), then (Xuv) = (Xu)v = Xv = X. It follows that uv is a period.

-Inversion: If û ∈ S(X), then since X = Xuu = (Xu)u = Xu. It follows that u is a period. This period provides a right and left inverse for û, since uu = ε = uu = uu.

Remark 8 If H is a stabilizer subgroup of X, then for every vertex û ∈ V (X), ûH û is a stabilizer subgroup of Xu. (Xu)/uHu is well-defined and turns out to be equal to (X/H)u.

Notice that monochromatic Cayley graphs are exactly the graphs whose all vertices are periods. As we have seen in our Cayley SFT examples, periodic graphs can typically be "folded into smaller graphs" that also belong in the graph SFT. The following formalizes the idea of a graph folding into another one.

Definition 6 (Homomorphism) A homomorphism from graph X ∈ X to graph X ∈ X is a function ϕ from V (X) to V (X ) such that for all u ∈ L(X), ϕ(û) = û (in particular L(X) = L(X )) and σX (u) = σ X (u).

When it is surjective, we say that X covers X and that ϕ is a covering.

Remark 9 A homomorphism sends cycles to cycles and preserves exactly the set of path-periods. Hence if û is a period of X, ϕ(û) is a period of ϕ(X).

Consider X ∈ X and a stabilizer subgroup H. We can define a quotient graph X/H to be X((G, p)) where:

-V (G) = { H û| û ∈ V (X)}, i.e. each vertex is labelled by a set H û.

p = H, i.e. the pointer is the vertex labeled by H.

-

E(G) = (H û : a, H uab : b) uab ∈ L(X) . -σG(H û) = σX (u).
Proposition 2 (Quotient graph) X/H is a well-defined graph, and û → H û is a homomorphism.

Proof. First of all, notice that H û = H û implies that there exists ĥ ∈ H such that û = ĥû, so that X u = (X h )u = Xu. Let us prove that σ X/H is well-defined. Let û, û ∈ V (X) such that H û = H û . From the remark above, Xu = X u , and therefore σX (u) = σX (u ). Now let us prove that if there is an edge {H û : a, H v : b} in G(X/H), then there is an edge {û : a, h v : b} in G(X). Indeed, by definition and the remark above, there is an edge { ĥû : a, ĥ v : b} in G(X) for some ĥ, ĥ ∈ H. Since Xu = X hu , there is also an edge {û : a, ĥ ĥ v : b}. Thus H û inheritates from û the absence of port conflict. The function ϕ satisfies trivially the two homomorphism conditions.

We say that a set of vertices

H is M -separated in graph X if for every û ∈ V (X), H ∩ (Xu) |M = {ε}. If U, V ⊂ Σ * , then we note U V = { uv| u ∈ U, v ∈ V }, and U = { u| u ∈ U }.
Proposition 3 Let X be a graph and H ≤ S(X) a stabilizer subgroup. If H is M M -separated in X, then the covering preserves the language of support M in the sense that for all u ∈ L(X), (Xu

) |M = (X/H u ) |M (modulo isomorphism).
In particular, if X belongs in some SFT X with defining window M , then X/H also belongs in X .

Proof. By definition, if u is a valid path in X, then it is also a valid path in X/H, and the internal state σX (u) = σ X/H (u) is the same. It remains to prove that if v, w designate distinct vertices in (Xu) |M , then they still designate distinct vertices in (X/H u ) |M . Assume on the contrary that v ≡ (X/H u ) |M w.

By the fact that concatenation is well defined (Proposition 2), there exists h such that ĥ ∈ H and hv ≡X u w, i.e. h ≡X u wv. Since wv ∈ (Xu) |MM and ĥ ∈ H, separation gives that wv ≡X u h ≡X u ε.

This means that w ≡X u v. This proves that the homomorphism induces an isomorphism over (Xu) |M . By definition, this homomorphism does not change the labeling alphabet, so that (modulo isomorphism) (Xu) |M = (X/H u ) |M . If X has defining window M , then by definition X ∈ X ⇐⇒ X/H ∈ X .

Strong periodicity

Definition 7 (Strong periodicity) A language L ∈ Π * is said to be dense in X if there exists a finite prefix-stable language M Σ * (we say that L is M -dense) such that for all û ∈ V (X), ûM ∩L = ∅.

A graph X is said to be strongly periodic if its stabilizer S(X) is dense in X. Equivalently, there are only finitely many distinct (modulo isomorphisms) graphs Xu, for u ∈ L(X).

Note that finite graphs are strongly periodic, but may not always be weakly periodic. Apart from this degenerate case, strongly periodic graphs are weakly periodic. Notice also that strong periodicity is almost equivalent to being a Cayley graph, up to replacement of each vertex by a fixed finite graph (with possible edges between them). This replacement (factor map) corresponds somehow to the application of a causal graph dynamics [START_REF] Arrighi | Cellular automata over generalized cayley graphs[END_REF] to the Cayley graph.

Corollary 1 A graph X is strongly periodic if and only if X/H is finite for some stabilizer subgroup H.

Proof. First, assume that H = S(X) is M -dense for some M Σ * : For every u ∈ L(X), there exist ĥ ∈ S(X) and v ∈ M such that û can be written ĥv. Now for every ĥ ∈ H, ĥ û = ĥ ĥv ∈ H v, so H û ⊆ H v and ĥ v = ĥ ĥĥ v = ĥ ĥû ∈ H û, so

H v ⊆ H û. Thus H û = H v. Hence, the set { H û| û ∈ V (X)} = { H v| v ∈ M ∩ L(X)} of vertices of X/H is finite. We conclude by Proposition 2. Conversely, if X admits a finite quotient X/H, there exists M such that { H û| u ∈ L(X)} = { H v| v ∈ M ∩ L(X)}.
For all û ∈ V (X), since û ∈ H û, we get that û ∈ H v for some v ∈ M . Therefore, û = ĥv with ĥ ∈ S(X) and v ∈ M , so that H is M -dense.

The following result establishes a surprising connection between the SFT that admit finite graphs, and the well-established notion (see for instance [START_REF] Ceccherini-Silberstein | Cellular Automata and Groups[END_REF]Chap. 2]) of residual finiteness from group theory: Definition 8 (Residually finite group) A group S is residually finite if and only if for any nonidentity element û ∈ S, there exists a normal subgroup H S of finite index such that û / ∈ H.

This notion is very robust. In particular, the property extends to finite sets of non-identity elements I, i.e. there exists a normal subgroup H S of finite index such that H ∩ I ⊆ {ε}, simply because any finite intersection of finite-index subgroups is a finite-index subgroup.

Let us relate residual finiteness to quotient graphs, at the intuitive level first. Say X belongs in some SFT Y and let û1, . . . , ûn be distinct elements of V (X). We have that H(û1, . . . , ûn) ⊆ S(X) is a subgroup of its stabilizer group, and thus that X/H(û1, . . . , ûn) is a possible quotient graph; one which maintains that û1, . . . ûn are distinct. The correct choice of û1, . . . , ûn will help us make sure that X/H(û1, . . . , ûn) still belongs in SFT Y.

Theorem 1 Let Y be a SFT. Y contains a finite graph if and only if Y contains a strongly periodic graph X such that S(X) is residually finite.

Proof. The right-to-left implication directly comes from the fact that finite graphs are strongly periodic and finite groups are residually finite. Now, suppose that Y has defining window M and admits a strongly periodic graph X such that S(X) is residually finite. Since X is strongly periodic, û∈V (X) V ((Xu) |MM ) is a finite union of finite subgraphs.

Since S(X) is residually finite, there exists a subgroup H ≤ S(X) of finite index which does not intersect

û∈V (X) V ((Xu) |MM ) \ {ε} ⊆ Σ M M .
Hence, H is M M -separated, so that we can use Proposition 3: for all û ∈ V (X) we have that (X/H u ) |M = (Xu) |M . Given that Y has defining window M , we get that X/H ∈ Y.

Thus there are two complementary ways in which a nonempty SFT may have only infinite configurations: either by preventing strongly periodic configurations, or by forcing them to have stabilizers that are not residually finite. In the non-residually-finite case (like the Tarski monster groups, see for instance [START_REF] Ol | Geometry of defining relations in groups[END_REF]), one can build SFTs with strongly periodic configurations that do not fold uniformly onto finite graphs.

Remark 10 Γ is not residually finite if and only if Z Γ {0} includes an SFT containing the Cayley graph of Γ but no finite quotient of it. Indeed, one can consider the SFT Z included in Z Γ {0} defined by the additional constraint that u is never a cycle, where u is a noncyclic path that witnesses that Γ is not residually finite, in the sense that all finite quotients of Γ map u to ε.

Quotients in Cayley SFTs

We have seen that the notions of quotients and SFTs are linked, because finite-type constraints cannot easily tell a graph from some of its quotients. On the opposite point of view, it is noticeable that some SFTs admit a maximal support with respect to coverings.

Proposition 4 Let Γ be a finitely presented group, X a graph, and Z some SFT defined by Γ -NN constraints. The following are equivalent:

1. X ∈ Z.

2. X is covered by some colored Cayley graph Y of Γ which is in Z.

Proof. 1 =⇒ 2 Suppose that the support of X is in Z. We note that paths designating vertex û in Y all designate the same vertex in X: indeed, if v also designates û in Y , then it can be obtained from û by iteratively applying the reduction rules from the presentation. Then thanks to the third condition in the definition of Z Γ Σ , it also designates the same vertex as û in X. Hence one can simply define φ(û) = û ∈ V (X) for every û ∈ V (Y ), and σY (û) = σX (û). This clearly satisfies the conditions of Definition 6. 2 =⇒ 1 Conversely, consider a graph X covered by some Cayley graph Y of Γ which is in Z. Consider a cycle constraint of Z, that is: every path labeled by some u (in the group presentation of Γ ) must be a cycle. This constraint is satisfied in X because loops are preserved by homomorphism. Now consider an edge constraint of Z. These are also preserved by homomorphism, by definition. We have proven that X satisfies all constraints defining Z.

In graphs of Z Z 2 Σ , all stabilizers are subgroups of the grid generated by {hh , vv }, which makes many properties easier.

Proposition 5 Let Z be an SFT defined by Z 2 -NN constraints. Then exactly one of the following occurs:

1. Every graph in Z is supported by the infinite grid, and is strongly aperiodic. 2. Z contains a finite graph and a strongly periodic infinite grid.

Proof. Assume that Condition 1 is not satisfied. A classical pumping argument from multidimensional symbolic dynamics (see for instance [START_REF] Ballier | Propriétés structurelles, combinatoires et logiques des pavages[END_REF]Lemma 1.16]) shows that Z then contains a strongly periodic configuration. In that case, its stabilizer, as a subgroup of Z 2 , is residually finite (see for example [7, Prop.2.2.1]). Theorem 1 then implies that Z contains a finite graph. On the other hand, it is clear that both conditions cannot be satisfied simultaneously, so that they indeed form a dichotomy.

It is already interesting to note that the dichotomy from Proposition 5 is nontrivial, directly from the existence of strongly aperiodic SFTs over the grid (and other ones). But the next subsection will show a stronger result.

In contrast with Z Z 2 Σ , Z F 2 Σ is much less rigid in the sense of the following statement, because it can be related to tilings over small-square surfaces, as studied in [START_REF] Chazottes | Tilings of the plane and Thurston semi-norm[END_REF][START_REF] Monteil | Down with hierarchy ![END_REF], and formalized in [13,

Undecidability

Theorem 2 The dichotomy from Proposition 5 is undecidable, given a list of Z 2 -NN constraints.

Proof. Every set F of Z 2 -NN constraints defines both a (graph) SFT Z, and a classical SFT Z over the infinite grid (which is included in Z). If Z is strongly aperiodic, then Z is in Class 1, whereas if it contains a weakly periodic configuration, then Z is in Class 2. The dichotomy is then directly equivalent to strong aperiodicity of Z , which is known to be undecidable [START_REF] Gurevich | A remark on berger's paper on the domino problem[END_REF].

Consequently, the class of homogeneous graph SFTs that contains only finite graphs is computably unseparable from the class of graph SFTs containing both finite and infinite graphs. This means the undecidability of any property that is implied by one of the two classes, and which implies the negation of the other one.

Corollary 2

The problem whether a graph SFT contains only finite graphs, and the problem whether a graph SFT is homogeneous, are both undecidable.

More precisely, the reduction directly gives that the dichotomy is Σ 0 1 -complete, so that all general properties separating it are Σ 0 1 -hard. The encoding of Cayley graphs into graph SFTs also, more directly, implies the following undecidability result.

Theorem 3 There exists a Cayley SFT Z Γ {0} such that the problem whether, given a word u ∈ Π * , u represents a cycle from the origin back to itself in every graph of Z Γ {0} , is undecidable.

It is actually Σ 0 1 -complete.

Proof. From Proposition 4, u represents a cycle from the origin back to itself in every graph of ZΓ if and only if it represents the identity element in Γ , which means that it is in the language of the word problem. It is known that there exists a finitely presented group Γ whose word problem is undecidable.

Conclusion

To sum up, we provided a formalism generalizing SFTs on Cayley graphs by allowing the support graph to be determined by forbidden subgraphs. The generalization also allows the SFT to have finite configurations and we provided examples of such SFT. By defining quotient graphs, we have shown that the only way for an SFT to not have finite configurations is to only have configurations that are either aperiodic, or with a stabilizer that is not residually finite. Similarly, we have shown that having only one support graph requires configurations to have finite stabilizers. We used both results to prove that the finite configuration problem and the support graph unicity problem are undecidable.

In the future, we wish to study determinism and study directly the relation between causal graph dynamics and graph subshifts, and use this connection to prove structure and complexity results on causal graph dynamics. Moreover, graph subshifts could provide a new point of view for studying group subshifts. On the other hand, many notions and results known upon group subshifts such as sofic subshifts, determinism or entropy, would be interesting to lift to graph subshift. We have seen that graph subshifts could generalize both classical symbolic dynamics and finite-type group geometry. They could be used to simulate a larger class of objects; let us discuss one example. Let T be a finite set of tiles, i.e. polygons of the plane R 2 . A tiling is then a covering of R 2 by translated copies of tiles from T , the intersection of any two of them being either empty, or a vertex, or a whole edge, or the whole tile. Now let us define subshift ZT with Σ = T , π as the set of tile edges up to translation, and the following constraints: each vertex labeled t ∈ T must have exactly those ports which correspond to the edges of t, and every simple cycle must correspond to a valid vertex in a tiling of the plane by T (i.e. it involves tiles that can be put next to each other around this vertex).

The fact that the latter condition can be forced by finitely many constraints (so that ZT be an SFT) is equivalent to the classical finite-local-complexity property of T . With this construction, there is a one-to-one correspondence between tilings by T of the plane and of all surfaces and graphs in ZT . Now if one is interested in the shift-orbit closure of a single tiling of the plane (i.e. the Penrose tiling), it is an interesting question whether this corresponds to an SFT in ZT . Some work has been devoted to understanding for which tilings one can force locally tilings of the plane to be in the shift-orbit closure [START_REF] Fernique | Weak colored local rules for planar tilings[END_REF][START_REF] Bédaride | When periodicities enforce aperiodicity[END_REF]; one says that the tilings admits local rules. Additionnally forbidding (via finite constraints) all possible graphs which represent tilings on surfaces but not on the plane is a new question. Our work shows that if the tiles are rectangles and if we allow for some decorations (that could also be encoded locally as small hanging subgraphs), then this is possible. It is tempting to think that this is still true in the case of general strongly aperiodic tilings, but the proofs would require a new formalism, because the support is no longer a Cayley graph. The same could be done in the tridimensional space, or in the hyperbolic plane.

Let us make a final remark. Graph theorists are used to considering families of graphs defined by forbidden finite graph minors. Of course, seen as including possibly infinite graphs, these families are subshifts, but they are a priori not SFTs (not even sofic). However, even if the minor operation involves vertices at possibly unbounded distance, it is known to have some kind of representation as local constraints [START_REF] Kuske | Logical aspects of Cayley-graphs: the group case[END_REF] (involving a nondeterministic coloring). The relation with our setting could be investigated.

Fig. 1 .

 1 Fig. 1. The different types of graphs. (a) A graph G. (b) A pointed graph (G, 1). (c) A pointed graph modulo X.

LFig. 2 .

 2 Fig.2. Locally grid-like SFT corresponding to the Cayley graph of a, b|aba -1 b -1 . The SFT is defined by forbidding all but these patterns, on their corresponding languages.

Fig. 3 .

 3 Fig. 3. Configuration of the hard-square model that is present in Z 2 . The colours represent the 0/1 internal states of the vertices.

Fig. 4 .

 4 Fig.[START_REF] Baumslag | Some two-generator one-relator non-hopfian groups[END_REF]. Configuration of the hard-square model whose support graph is not Z 2 . In order to preserve clarity, only half of the ports are written and some edges have been dashed.

  Subsection 1.3.3]. Proposition 6 Let Z be an SFT defined by F2-NN constraints. Then the following are equivalent: 1. Z is nonempty. 2. Z contains a weakly periodic Cayley graph of F2. 3. Z contains a Cayley graph of a group different from F2. Besides, the following are equivalent: 4. Z contains a finite graph. 5. Z contains a finite Cayley graph. 6. Z contains a strongly periodic Cayley graph of F2. 7. Z contains an amenable Cayley graph. Nevertheless, there exist nonempty SFTs containing only finite graphs and defined by F2-NN constraints.The second equivalence is very close to the main result of[START_REF] Hellouin De Menibus | Tiling an arbitrary amenable group is decidable[END_REF], about how tilesets tile Cayley graphs. They also show the equivalence with containing a cylindric graph, i.e. with having an infinite cyclic dense stabilizer. If Z is nonempty, then by Proposition 4, it contains a Cayley graph of F2. It is known that every SFT over F2 contains a periodic configuration (see for instance [21, Theorem 2.2]). =⇒ 3 Let X be a weakly periodic Cayley graph of F2 and û be a nontrivial period. Then the infinite cyclic group û is a residually finite stabilizer subgroup: if M is a defining window for Z, then there exists an infinite (cyclic) subgroup H < û which is M M -separated. By Proposition 3, X/H belongs in Z. =⇒ 1 This is trivial. =⇒ 4 This is trivial. =⇒ 5 This is due to Theorem 1. =⇒ 6 If Z contains a finite graph X, then from Proposition 4, it also contains a colored Cayley cover Y of X. All preimages of ε by the homomorphism are period in Y (because they are periods in X), and their set is M -dense, where M is a finite language representing all possible paths in X. 5 ⇐⇒ 7 This is trivial because finite groups are amenable.

	Proof.
	=⇒ 2

=⇒ 4

This is remarked in

[START_REF] Monteil | Down with hierarchy ![END_REF]

, based on

[START_REF] Chazottes | Tilings of the plane and Thurston semi-norm[END_REF]

.

-The last statement is also inherited from symbolic dynamics over groups

[START_REF] Piantadosi | Symbolic dynamics on free groups[END_REF] Example 4.1]

.

Acknowledgements

We are indebted to Nicolas Schabanel who ecouraged us to study graph subshifts and contributed to the first four definitions. This publication was made possible through the support of the ID# 62312 grant from the John Templeton Foundation, as part of the 'The Quantum Information Structure of Spacetime' Project (QISS) . The opinions expressed in this publication are those of the author(s) and do not necessarily reflect the views of the John Templeton Foundation.


J B Vaney

J Carreaud

G Delaizir

A Piarristeguy

A Pradel

E Alleno

J Monnier

E B Lopes

A P Gonçalves

A Dauscher

C Candolfi

B Lenoir

High Thermoelectric Performance in Sn-Substituted α-As2Te3

Lead chalcogenides PbX (X = Te, Se, S) have been the materials of choice for thermoelectric power generation at mid-range temperatures (500 -700 K). Here, we report on a new family of chalcogenides -As2Te3 that exhibits similar thermoelectric performances near 500 K. Sn doping in p-type polycrystalline -As2-xSnxTe3 (x ≤ 0.075) provides an efficient control parameter to tune the carrier concentration leading to thermopower values that exceed 300 V K -1 at 500 K. Combined with the structural complexity of the monoclinic lattice that results in extremely low thermal conductivity (0.55 W m -1 K -1 at 523 K), a peak ZT value of 0.8 is achieved at 523 K for x = 0.05. A single-parabolic band model is found to capture well the variations in the transport properties with the Sn concentration and suggests that higher ZT values could be achieved through band structure engineering. These results surpass those obtained in the sister compounds -As2-xSnxTe3 and further show that -As2Te3 based materials are competitive with other chalcogenides for thermoelectric applications at intermediate temperatures.

Electronic Supplementary Information (ESI

) available: Rietveld refinements of the PXRD patterns of the α-As2-xSnxTe3 samples; BSE images and X-ray mapping; DSC traces; Electrical resistivity data plotted as ln r versus T -1 ; High-temperature transport properties of a second specimen of α-As2Te3; Pisarenko plot; Temperature dependence of the specific heat; Crystallographic parameters of the α-As2-xSnxTe3 samples.

Introduction

The thermoelectric potential of a given material is evaluated through its dimensionless figure of merit ZT defined as ZT = a 2 T / r(k L +k e ). [START_REF] Goldsmid | Thermoelectric Refrigeration[END_REF][START_REF]Thermoelectrics and Its Energy Harvesting[END_REF] High ZT values are achieved at an absolute temperature T in materials that show an unusual combination of large thermopower a , low electrical resistivity r and low lattice and electronic thermal conductivities k L and k e , respectively. Narrow-band-gap semiconductors are usually the best materials that enable achieving a fine balance between these conflicting requirements. [START_REF] Goldsmid | Thermoelectric Refrigeration[END_REF][START_REF]Thermoelectrics and Its Energy Harvesting[END_REF] In particular, several families of semiconductors investigated over the last years crystallize in a complex unit cell that leads to extremely low lattice thermal conductivity. High ZT values then emerge when the electronic properties are properly optimized either through chemical substitutions or by filling

the voids in open-framework structures. Among others, Zintl phases, Mo-based cluster compounds, clathrates or sulfosalt minerals are prominent examples of materials in which such a combination of transport properties was demonstrated. [START_REF] Brown | [END_REF][4][5][6][7][8][9][10][11][12][13][14][15][16][17][18][19][20] All these families share the common characteristic of exhibiting their maximum ZT at high temperatures, typically between 700 and 1000 K. Near room temperature, however, the state-of the-art solid solutions (Bi,Sb)2(Se,Te)3 still represent the best known thermoelectric materials to date. [START_REF] Goldsmid | Thermoelectric Refrigeration[END_REF][START_REF]Thermoelectrics and Its Energy Harvesting[END_REF] The As-based analogue -As2Te3 represents another member of this family that was recently proposed to harbor topologically-protected surface states when a uniaxial strain is applied along the c axis of the rhombohedral crystal structure (Figure 1). 21 The  nomenclature refers to the fact that this binary compound also crystallizes with a monoclinic unit cell referred to as the  form. [22][23][24][25] The crystal structure of -As2Te3, shown in Figure 1, consists of zig-zag chains where As atoms are either trigonally or octahedrally coordinated to the Te atoms yielding two As and three Te sites. Yet, in spite of first-principles calculations suggesting that ZT values of up to 0.75 at 300 K might be achieved in both compounds, 25 their transport properties remain so far largely unexplored. 26 In agreement with these calculations, our recent preliminary study of the thermoelectric properties of -As2-xSnxTe3 above room temperature revealed a favorable combination of semiconducting-like electronic properties and extremely low thermal conductivity values. 27 Substituting Sn for As offered an effective control parameter of the carrier concentration, thereby significantly improving the ZT values up to 0.65 at 423 K for x = 0.015. These results motivated us to investigate Sn substitution in its monoclinic derivative -As2Te3.

Here, we explore the transport properties of polycrystalline -As2-xSnxTe3 (0.0  x  0.075) in a wide range of temperatures (2 -523 K) with the aim of assessing its thermoelectric potential relative to -As2Te3. Our results show that the carrier concentration can be tuned to achieve a maximum ZT of 0.8 at 523 K for x = 0.05. Additionally, we used a single parabolic-band model to identify the basic material parameters that govern the transport and from which strategies to achieve higher ZT values may be developed.

Experimental Section

Synthesis

According to the binary As-Te phase diagram, α-As2Te3 decomposes peritectically at 654 K.

This low temperature along with the fact that the boiling point of As is below its melting point makes it difficult a direct synthesis using elemental As and Te. Because the  analogue transforms into the α form when annealed above 473 K, 28 α-As2-xSnxTe3 specimens were synthesized by annealing -As2-xSnxTe3 samples at 573 K for 3 days. In a first step, polycrystalline samples of -As2-xSnxTe3 with x = 0.0, 0.025, 0.050 and 0.075 were synthesized by direct reaction of stoichiometric amounts of pure elements (As (Goodfellow, 99.99%), Te (5N+, 99.999%) and Sn (Strem Chemicals, 99.999%)) in silica tubes sealed under secondary vacuum. All manipulations were carried out in dry, argon-filled glove boxes.

The tubes were subsequently heated in a vertical furnace up to 923 K with a heating rate of 10 K h -1 , held at this temperature for 2 hours and eventually quenched in a salt-ice-water mixture.

The annealing step was realized by placing directly the quenched ampules in a furnace. The annealed ingots were ground into micron-sized powders before being consolidated by spark plasma sintering (SPS, Dr. Sinter 515S Syntex) at 618 and 573 K (temperatures selected from the sintering window) for the undoped and doped samples, respectively, under 50 MPa of pressure for 2 min. using a graphite die of 10 mm inner diameter. A second sample of α-As2Te3 has been prepared in order to probe for possible off-stoichiometry. For this reason, the synthesis conditions were slightly changed. In a first step, -As2Te3 was synthesized by heating the initial mixture of As and Te powders placed in sealed silica tubes up to 1123 K at a rate of 9 K h -1 . This temperature was maintained for 2 h before being quenched in a salt-icewater mixture. The resulting ingot was crushed into micron-sized powders, introduced in another silica tube and annealed at 618 for 3 days to obtain the targeted α-As2Te3 phase.

Structural and Chemical Characterizations

Phase purity and crystallization were verified by powder X-ray diffraction (PXRD) with a Bruker D8 Advance diffractometer (Cu Kα1 radiation) in reflection mode. The lattice parameters were determined by Rietveld analyses of the collected spectra using the Fullprof software. Chemical homogeneity was probed by scanning electron microscopy (SEM) in backscattering electron mode (BSE) and energy dispersive X-ray spectroscopy (EDXS) elemental mapping using a Quanta 600 FEG (FEI). These experiments were carried out on polished surfaces of bulk pieces of the consolidated samples.

Electron Probe Microanalysis

Bulk pieces of the densified samples were carefully polished down to 1 μm with alumina powder to obtain appropriate surfaces for analysis. Electron probe microanalysis (EPMA) was performed with a JEOL JXA 8530F equipped with wavelength-dispersive spectrometers.

Backscattered electrons were used for imaging the surface of the samples. In order to minimize matrix effects, X-ray intensities of As and Te were compared with those of a calibrated β-As2Te3 standard for quantitative analysis. The calibration of this sample was carried out with the isostructural compound Bi2Te3 whose deviations from the ideal stoichiometry are below the resolution of the instrument. [START_REF]Thermoelectrics and Its Energy Harvesting[END_REF] Thus, an exact stoichiometry of two Bi atoms and three Te atoms per formula unit was assumed. The chemical compositions of the α-As2-xSnxTe3 specimens were determined from analysis of a set of at least 90 different points for each sample.

Differential scanning calorimetry (DSC)

Differential scanning calorimetry (DSC) measurements were performed on small pieces of the consolidated pellets (30 mg) loaded into closed-stainless steel crucibles with a DSC121

(Setaram) apparatus. The data were collected under an argon flow from 300 to 673 K. A low heating rate of 2 K min -1 was applied in order to ensure a good thermal equilibrium between the sample and the crucible owing to the low thermal conductivity of these compounds in this temperature range.

Optical absorption

Optical absorption spectra of disk-shaped samples were measured at room temperature by a Thermo Scientific Nicolet 6700 FTIR spectrophotometer equipped with an integrated sphere.

The electronic band gaps E g were determined by applying the Kubelka-Munk theory that relates the measured reflectance R to a value proportional to the absorption coefficient

F(R) = (1- R) 2 / 2R. 29

Low-Temperature Transport Properties Measurements

To probe possible anisotropy, the polycrystalline samples were cut both parallel and perpendicular to the pressing direction with a diamond-wire saw. Bar-shaped samples (~3×2.5×8 mm 3 ) were used to measure simultaneously the thermopower, electrical resistivity and thermal conductivity between 5 and 300 K using the thermal transport option (TTO) of a physical property measurement system (PPMS, Quantum Design). These measurements were carried out by brazing four copper leads onto the surface of the samples with a low melting point braze. The same samples were used to determine the Hall resistivity r H from measurements of the transverse electrical resistivity r xy with the AC transport option of a PPMS. To this end, a five-wire configuration was utilized by soldering five copper wires onto the samples using the same braze as for the TTO measurements. m 0 H ® 0. Note that for some samples (x = 0.0 and x = 0.025), the high electrical resistivity measured below 100 K did not allow using a five-wire configuration.

We stress here that the anisotropic crystal structure described in the C2/m space group leads to a galvanomagnetic tensor with a maximum of five independent Hall coefficients. 30 Hence, the Specific heat measurements were carried out between 2 and 300 K on a small bulk piece of the x = 0.0 sample (20 mg) using the dedicated option of the PPMS. Apiezon N grease was used to ensure a good thermal coupling between the sample and the platform of the sample holder.

Ultrasonic measurements were performed at 300 K to obtain the longitudinal and transverse sound velocities. Honey was used to improve the contact between the piezoelectric transducers and the samples ( 0.5 mm in thickness).

High-Temperature Transport Properties Measurements

Another set of bar-shaped samples (typical dimensions ~ 1×1×8 mm 3 ) were also cut in the two directions to probe the electrical resistivity and the thermopower between 300 and 523 K.

These two measurements were carried out simultaneously with a ZEM-3 apparatus (Ulvac-Riko). Thermal conductivity was determined from 300 up to 523 K via thermal diffusivity measurements performed under argon flow on disk-shaped samples (~ 10 mm in diameter) for the parallel direction and on prism-shaped (~ 6×6×1 mm 3 ) for the perpendicular direction using a LFA 427 (Netzsch) equipment. Prior to these measurements, the samples were spraycoated with a thin layer of graphite to ensure a homogeneous signal absorption and emission on the respective surfaces. The thermal diffusivity a is related to the thermal conductivity by the relation k = aC P r V where C p is the isobaric specific heat and V  is the density. Specific heat measurements (DSC 403 F3, Netzsch) were performed on the x = 0.0 and 0.05 samples in the same temperature range by the continuous scanning method under argon flow. Because of nearly identical values, a linear fit of the high-temperature data of the x = 0.0 sample was used for calculating the thermal conductivity of the α-As2-xSnxTe3 series. The combined uncertainty in the determination of the ZT values is estimated to 17% in the temperature range investigated. 31 The Hall coefficient was also determined on samples cut in both directions with a home-made apparatus using the van der Pauw configuration. These measurements were performed between 300 and 420 K under dynamic vacuum on thin square samples (~1×6×6 mm 3 ) under applied magnetic fields ranging between -1 and +1T.

Results and discussion

Phase purity, chemical homogeneity and thermal behavior

All the polycrystalline samples show experimental densities higher than 98% of the theoretical densities. Unlike the -As2-xSnxTe3 compounds for which a preferred orientation was noticeable, the PXRD data did not reveal any significant degree of anisotropy. The PXRD patterns, shown in Figure S1 to S4 (Electronic Supplementary Information), demonstrate that the monoclinic phase was obtained as the main phase in all samples. In addition to the reflections of α-As2Te3 that were indexed with the monoclinic space group C2/m, weak additional peaks are present for some compositions that can be attributed to the cubic AsTe compound and elemental Te. Attempts at synthesizing samples with a higher Sn content (x = 0.1) led to an increased amount of secondary phases suggesting that the solubility limit of Sn in α-As2Te3 is close to 0.075. SEM images collected in backscattering electron mode (Figure S5 in Electronic Supplementary Information) further corroborated the presence of minute amounts of elemental Te. Elemental mapping images taken on the Sn-doped samples indicate that Sn is homogeneously distributed. This conclusion is further corroborated by the EPMA results that did not reveal any Sn-containing impurities regardless of the nominal composition. Average compositions from EPMA are listed in Table 1. An excellent agreement between the nominal and actual compositions is observed for all samples.

The lattice parameters, derived from Rietveld refinements against the PXRD data and summarized in Table S1 (Electronic Supplementary Information), indicate that the unit cell volume expands in a nearly linear manner up to x = 0.075 as a result of the larger ionic radius of Sn relative to As. Owing to the presence of two distinct crystallographic As sites, the exact location of the Sn atoms in the unit cell could not be unequivocally determined from these refinements.

The binary phase α-As2Te3 has no melting or decomposition behavior below 600 K as evidenced by the DSC curve shown in Figure S6 (Electronic Supplementary Information).

Above this temperature, two well-defined endothermal peaks are observed at 638 and 650 K.

Both temperatures agree very well with the reported As-Te binary phase diagram indicating that a mixture of α-As2Te3 and Te should evolve with increasing temperature in a two-step process: a first partial melting at 636 K, above which α-As2Te3 and liquid coexist, followed by the melting of the binary compound at 654 K. The change of slope in the DSC signal around 612 K might correspond to a third event, although it remains unclear whether this change is intrinsic to α-As2Te3.

Optical Band Gap

Figure 2 presents the absorption spectra against photon energy hn , where h is the Planck constant and n is the wave frequency, shown as a Tauc-plot assuming direct transitions for all samples. The signal recorded for the x = 0.0 sample shows a steep rise for energies above 0.43 eV. This value is coherent with prior optical absorption measurements (0.46 eV) and with first-principles calculations (0.48 eV) and can thus be attributed to direct transitions across the band gap located along the Γ -Y direction according to electronic band structure calculations. The optical spectra of all Sn-doped samples differ from that of the undoped sample since they feature a shallow rise below 0.4 eV followed by a steeper rise around 0.41 -0.42 eV. The slow rise at low energies might be either due to impurity states in the band gap or intraband transitions while the second increase in absorption may be attributed to interband transitions across the band gap. This interpretation seems further justified by the thermopower data which feature a broad maximum corresponding to thermal excitations across a band gap of around 0.35 eV in the Sn-substituted samples. These data further show that the optical band gap decreases upon Sn substitution.

Electronic and galvanomagnetic properties

Figure 3a shows the temperature dependence of the r(T ) data of the series α-As2- xSnxTe3. Except for the x = 0.0 sample below 150 K, no significant difference between measurements parallel and perpendicular to the pressing direction is discernable within the experimental uncertainty, in agreement with the PXRD data. From electronic band structure calculations, α-As2Te3 is expected to show a semiconducting behavior. In agreement with this expectation, the electrical resistivity of α-As2Te3 is characteristic of lightly-doped semiconductors, with values varying by several orders of magnitude upon cooling to 5 K. 26 The substitution of Sn for As does not alter the semiconducting behavior although r decreases by one order of magnitude at 300 K on going from x = 0.0 to 0.025. Further increasing x then leads to a slight but noticeable increase in r above  200 K. At high temperatures, the slow decrease in r observed in the x = 0.050 and 0.075 samples is likely due to the excitations of minority carriers across the band gap, which decreases with x as revealed by IR absorption spectroscopy.

The low-temperature behavior of r(T

)can be further understood by considering the electrical transport in non-degenerate semiconductors that can be usually well described by an Consistent with the semiconducting nature of these samples, the thermopower steadily increases with temperature in a nonlinear manner in the Sn-substituted specimen (Figure 3b).

In contrast, a(T ) does not monotonically vary in α-As2Te3 but shows a maximum near 250 K, temperature above which a decreases. Above 395 K, a approaches zero in the parallel is very large or very small (where m is the mobility of the majority and minority carriers). 33 For instance, a similar situation occurs in the Half-Heusler compounds ZrNiSn for which a five-fold difference between the band gaps estimated in n-and p-type samples using the Goldsmid-Sharp relation has been underlined. 34 In the Sn-substituted samples, a ranges between 250 and 300 V.K -1 at 300 K and rises cm -3 at 300 K. We note that due to the strong influence of electrons above 250 K, this value is only an upper limit of the actual hole and electron concentrations in this sample. This carrier density is at least one order of magnitude lower than that calculated (3.125×10 19 cm -3 at 300 K, see Table 2) from electronic band structure calculations in Ref. 25 where no disorder and 300 K = 253.8 V K -1 were assumed, indicating that both electrons and holes contribute to the electrical transport. This difference likely originate from electrically-charged native defects due to slight off-stoichiometry, as already observed in the related Bi2Te3-based alloys and suggested in -As2Te3. 27 The presence of defects in α-As2Te3 is further corroborated by measurements of the transport properties of a second sample prepared under slightly different synthetic conditions (Figure S8 in Electronic Supplementary Information) for which, n-type electrical conduction is observed. The α-As2Te3 thus behaves similarly to Bi2Te3 where either p-or n-type conduction can be achieved depending on the synthesis conditions. [START_REF] Goldsmid | Thermoelectric Refrigeration[END_REF][START_REF]Thermoelectrics and Its Energy Harvesting[END_REF] In Bi2Te3, electrically active charged defects, is, antisite defects (BiTe and TeBi) and vacancies (on the Te or Bi sites), play a central role in determining the carrier concentration and hence, the thermoelectric performances. Antisite defects originate supposedly from the small difference in Pauling electronegativity (PE) between Bi and Te (PE = 2.02 and 2.10, respectively). Because BiTe (TeBi) defects and Bi (Te) vacancies act as hole dopants and electron donors, respectively, the type of electrical conduction largely depends on deviations from the ideal stoichiometry. 35 Hence, Bi-rich compounds harbor a p-type conduction (the main defects are believed to be TeBi) while Te-rich samples exhibit an n-type conduction (the main defects are believed to be BiTe). 36 The similar electronegativity difference between As and Te (PE = 2.18 for As) suggests that antistructure defects equally play a significant role in α-As2Te3. The competition between these two types of defects in samples close to the ideal stoichiometry would naturally explain the presence of holes and electrons in α-As2Te3. This scenario seems consistent with the results obtained on the second sample (Figure S8 in Electronic Supplementary Information) which features similar r(T ) but thermopower values as high as -550 V K -1 at 300 K. Slight differences in the subtle balance between the concentration of both types of defects due to different synthetic conditions provide a simple explanation for such stark contrast in a(T ).

Upon substituting Sn for As, p H increases by almost one order of magnitude to 1.35×10 19 cm -3 for x = 0.025 and then smoothly decreases down to 8.1×10 18 cm -3 for x = 0.075. This decrease in the hole concentration naturally explains the increase in both r and a with x above 300 K. The complex trend observed in Co1-xNixSb3 (0  x  0.01) and in lightly-doped p-type CoSb3. [37][38][39] These data were recently reanalyzed and successfully described by a multiband model in the presence of both acoustic phonon and ionized impurity scattering. This model was found to describe remarkably well m H (T ) between 5 and 300 K in both skutterudite systems, providing a consistent interpretation of the nearly constant The trend in the a values with the hole concentration has been further analyzed within a single-parabolic-band model (SPB) as a first approximation. This analysis has been performed at 400 K i.e. at a temperature where a single carrier type and a well-identified scattering mechanism dominate and below the threshold of the intrinsic regime of conduction.

For these reasons, the undoped sample was not included in the present analysis. In the SPB model, the thermopower and hole concentration are expressed as 40

a = k B e (2 + r)F 1+r (h) (1+ r)F r (h) -h ae è ç ö ø ÷ (1)
p = 4p 2m * k B T h 2 ae è ç ö ø ÷ 3/2 F 1/2 (h) (2)
where k B is the Boltzmann constant, e is the elementary charge, h is the Planck constant, m * is the hole density of states effective mass, r is the scattering parameter ( r = 0 for acoustic phonon scattering and r = 2 for ionized impurities), h is the reduced chemical potential and

F i (h) is the Fermi integral of order i defined as F i (h) = z i dz 1+
e z -h 0 ¥ ò with z the reduced carrier energy. As shown in Figure S9 (Electronic Supplementary Information), this simple approach describes quite well the a(p) relationship in the hole concentration range covered using a constant m * value of 1.3 m e . T increases. The results also evidence a significant degree of anisotropy in α- As2Te3 that disappears upon Sn doping. The magnitude of the low-temperature maximum decreases concomitantly with increasing the Sn content, a behavior consistent with enhanced point-defect scattering, as typically observed in solid solutions. Remarkably, very low thermal conductivity values are achieved at 300 K that further decrease at higher temperatures to reach  0.55 W.m -1 .K -1 at 520 K in the x = 0.050 and 0.075 samples. These values are nearly identical in α-As2-xSnxTe3 and -As2-xSnxTe3 and close to those observed in some Se-based chalcogenides. [START_REF] Sassi | [END_REF][42][43][44][45][46][47][48] We further compared k L to the minimum lattice thermal conductivity calculated from the transverse and longitudinal speeds of sound

Thermal transport properties

k B V - 2 3 v i T q i ae è ç ö ø ÷ 2 x 3 e x (e x -1) 2 dx 0 q i /T ò i å (3)
In Equation (3), V is the average atomic volume, In Figure 6b, the experimental hole concentration dependence of the ZT values is compared to a theoretical curve calculated within the SPB model. The materials properties required in this calculation were obtained using Equations ( 1) and ( 2) in addition to the following equations giving the Lorenz number L and the Hall mobility m H 40

3 / 1 2 ) / 6 )( / ( V k v B i i    =
L = k B 2 e 2 (1+ r)(3+ r)F r (h)F 2+r (h) -(2 + r) 2 F 1+r (h) 2 (1+ r) 2 F r (h) 2 (4)
m H = m 0 p F r (h) 2G(1+ r)F 1/2 (h) (5)
where m 0 is the intrinsic hole mobility and G(x) is the gamma function. The dependence of ZT on the carrier concentration is then obtained from Equation ( 6) to ( 8)

ZT = a 2 L + (yb) -1 (6) b
= m 0 (m * / m e ) 3/2 T 5/2 k L (7) y = 2e 2pk B m e h 2 ae è ç ö ø ÷ 3/2 F r (h) G(1+ r) (8)
This analysis has also been restricted to 400 K for the same aforementioned reasons. In Equation ( 7), constant k L and m 0 values of 0.60 W m -1 K -1 and 27 cm 2 V -1 s -1 , respectively, were used. The experimental hole concentration of 1.3×10 19 cm -3 is close to the optimum concentration of 4.3×10 19 cm -3 predicted by the SPB model at 400 K. Yet, this is not to say that further control of the hole concentration may not lead to further optimization of ZT. The limitations of this model are tied to the underlying hypothesis made i.e. a constant effective mass and the presence of a single carrier type and single parabolic band. In the present case, the maximum ZT occurs at higher temperatures where the samples experience minority carrier activation. Since this effect is not taken into account in this model, the optimum hole concentration predicted at 400 K is likely underestimated when considering ZT values at higher temperatures. Further, electronic band structure calculations revealed the presence of weakly-dispersive, heavy hole bands located slightly below the Fermi level. 21,25 Higher hole concentration may allow probing deeper into the valence bands possibly resulting in nonparabolic effects and larger effective masses. These two properties might help maintain high thermopower values despite higher hole concentrations and thus, might contribute to achieve higher ZT values.

Conclusion

Our exploration of the transport properties of α-As2Te3 revealed that interesting thermoelectric properties may be achieved through a proper control of the carrier concentration. Here, the hole concentration was effectively tuned by Sn alloying leading to a maximum ZT of 0.8 at 22 523 K for x = 0.05. This reasonably high value arises from a favorable combination of high thermopower in a broad temperature range, despite activation of minority carriers, and very low thermal conductivity that approaches the minimum thermal conductivity at high temperatures. The transport properties above 300 K can be fairly well described within a single parabolic band model, which provides guidance for further optimization of α-As2Te3.

This analysis, combined with the reported electronic band structure of α-As2Te3, suggests the possibility to achieve higher ZT values at higher hole concentrations. The similarities between α-As2Te3 and the related compounds -As2Te3 and Bi2Te3-based alloys further suggest that other elements on both the As and Te sites may help optimize the ZT values making this material competitive with other chalcogenides operating around 500 K.

Tables

r xy was measured under magnetic fields m 0 HH

 0 ranging between -1 and +1 T. The data were corrected for slight misalignment of the contacts by applying the formula r was determined from the slope of the r H (m 0 H) data in the limit

RH

  values will depend on the orientation of the sample, making it challenging to analyze in detail the galvanomagnetic properties. Although the anisotropy as seen by PXRD and transport properties measurements remains moderate (except for the high-temperature thermopower of the binary compound), the R H values measured show some anisotropy. The difference between the values measured parallel and perpendicular to the pressing direction evolves with the Sn content from 6% for x = 0.0 and 0.025 up to 15% in the x = 0.075 sample. Keeping this in mind, we shall use the Hall carrier concentration ( p ) and Hall mobility ( m H )values inferred in the parallel direction within a single-band approximation ( analyze the transport as a first approximation. Note that using the values obtained in the perpendicular direction would neither change the analysis nor our general conclusions.

B

  is the activation energy, E g is the band gap and k B is the Boltzmann constant. When the r(T ) data are plotted as ln r versus T -1 , (FigureS7, Electronic Supplementary Information) several distinct regimes can be distinguished. For all samples, r levels off below 40 K in a manner typical of extrinsic conduction mechanisms with D < 10 -3 meV suggesting that impurity band conduction dominates the electrical transport. The samples enter a different regime of conduction at higher temperatures with activation energies of 0.13 (130 -520 K), 0.11 (75 -200 K), 0.045 (80 -170 K) and 0.040 (80 -170 K) meV for the x = 0.0, 0.025, 0.050 and 0.075 samples, respectively. The temperature range where this regime dominates clearly decreases with increasing x and may be related to charge carriers thermally excited into an impurity band formed by Sn atoms. As we shall see below, Hall effect data provide further experimental evidence in favor of this scenario.

  direction and become negative in the perpendicular direction. Another trait that marks the binary compound as distinct among this series is the anisotropy observed between the parallel and perpendicular directions above  200 K that vanishes upon Sn alloying to within experimental uncertainty. The maximum in a(T ), the sign change at high temperatures and the anisotropy are all signatures of mixed conduction that develops in α-As2Te3. The anisotropy further suggests that a large asymmetry in the electron-hole density of states effective masses ( m * ) exists owing to asymmetry in the dispersion of the valence and conduction bands. A large difference in m * between electrons and holes seems further supported by the breakdown of the Goldsmid-Sharp relation E g » 2ea max T max that relates the energy band gap E g to the maximum thermopower value a max reached at the temperature T max . 32 In the present case, this relation would imply a very narrow band gap (75 meV) in contradiction with the value inferred from absorption measurements (0.43 eV, see Figure 2).This simple formula is no longer valid either when the material is degenerate or when the majority-to-minority carrier ratio defined as A = m maj

  with temperature before starting to fall near 450 K and 500 K in the x = 0.050 and x = 0.025 samples, respectively. The maximum reached marks the onset of electron-hole pairs excitation across the energy band gap. The Goldsmid-Sharp relation yields E g  0.35 eV for x = 0.025 and 0.30 eV in the x = 0.050 and 0.075 samples, in reasonable agreement with the values inferred from absorption spectroscopy. The absence of anisotropy in a(T ) in Sn-substituted specimen further suggests that the closer agreement between the Goldsmid-Sharp relation and the experimental band gaps is mainly due to changes in the above-mentioned A ratio. The galvanomagnetic properties of the series α-As2-xSnxTe3 provide valuable insights into the compositional dependence of r and a . Hall effect data indicate that all samples exhibit a positive and linear field dependence (not shown) indicative of holes as the dominant carriers, in agreement with the thermopower data. In contrast to a(T ), the Hall data of the binary compound are nearly isotropic with an effective hole concentration p H of 3.4×10 18

HB

  p H (x) suggests a non-rigid-like evolution of the band structure and makes it difficult to draw a definitive conclusion about the donor or acceptor nature of Sn, a situation reminiscent to that observed in -As2Te3. 27 This complexity could originate from the amphoteric character of Sn and/or from a change in the intrinsic defect concentration upon substituting Sn for As. The larger difference in electronegativity between As and Sn (PE = 1.96) with respect to As and Te may indeed decrease the antisite defect concentration. The temperature dependence of the Hall mobility m H , shown in Figure 4, reveals that above 300 K m H decreases with temperature in all samples with an approximately T -3/2 behavior indicative of acoustic phonon scattering. Below room-temperature, the m H values increase with increasing x thereby explaining the decrease in r observed below 200 K when x varies from 0.025 to 0.050. Further, m H sharply decreases before tending to level off below 50 K in the x = 0.050 and 0.075 samples. Although this low-temperature decrease suggests that scattering by ionized Sn impurities is also present, m H rises more steeply than the expected T 3/2 dependence. In the x = 0.025 specimen, the slope approaches T 3 and reduces to T 2 in the other two doped compounds. In this series, grain boundary scattering can be ruled out since the m H (T ) data do not follow the expected relation in any temperature range m is the energy barrier at the grain boundaries. Interestingly, such deviations from the T 3/2 law were observed in a series of n-type polycrystalline skutterudite

mH

  values at low temperatures and the sharp increase mimicking that of ionized impurity scattering. These analyses demonstrated that an impurity band formed by Ni atoms dominates transport at low temperatures explaining the very low and nearly constant m H values. Furthermore, the steep increase in m H was shown to be due to the thermal excitation of carriers from the impurity band to the first valley of the band structure (i.e. minimum of the conduction band). The m H (T ) data measured in α-As2-xSnxTe3 share strong similarities with those collected in CoSb3 and Co1-xNixSb3. In the latter, besides the low-temperature dependence of m H , increasing the Ni content leads to a shift of the onset of the sharp decrease towards lower temperatures, as tend to do the present m H data on going from x = 0.025 to 0.050. In addition, impurity band conduction prevailing at low temperatures and extrinsic carrier conduction dominating at moderate temperatures are consistent with the r(T ) data. All these clues point to the presence of a Sn impurity band above the valence band maximum at the origin of the anomalous temperature dependence of m H in α-As2-xSnxTe3.

Figure 5

 5 Figure5shows the total thermal conductivity of the α-As2-xSnxTe3 series. The temperature

3 . 5

 35 sound velocity, respectively, of the ith mode. Here, the sum is performed over one longitudinal and two transverse modes. Within this approach, k m is attained when the phonon mean free path reaches l = l / 2 which stands for the shortest physically meaningful distance for a phonon of wavelength l . Measurements of the sound velocities carried out on the x = 0.0 sample yielded v T = 1798 m s -1 and v L = 3062 m s -1 . Both values are consistent with those determined recently by first-principles calculations. 50 As shown in Figure 5, k L approaches k m ( 0.4 W m -1 K -1 ) at high temperatures indicating that the thermal transport is intrinsically optimized in α-As2Te3 with respect to thermoelectric performances. Dimensionless thermoelectric figure of merit ZT The dimensionless figure of merit ZT is shown in Figure 6a as a function of temperature. The combination of intrinsic semiconducting behavior leads to very low ZT values in the undoped sample. Upon substituting Sn for As, the ZT values are significantly improved with a peak value of 0.8 at 523 K in the 0.05 sample. This relatively high value is comparable to those achieved in other thermoelectric chalcogenides such as PbSe or PbS at similar temperatures, 51- 53 making α-As2Te3 an interesting playground to reach high ZT values.

Figure 1 .

 1 Figure Captions

Figure 2 .

 2 Figure 2. Optical absorption spectra of the series α-As2-xSnxTe3 with x = 0.0, 0.025, 0.050 and

Figure 3 .

 3 Figure 3. a) Temperature dependence of the electrical resistivity r and b) thermopower  as

Figure 4 .

 4 Figure 4. Hall mobility m H across the α-As2-xSnxTe3 series from Hall effect measurements in

Figure 5 .

 5 Figure 5. Temperature dependence of the total thermal conductivity for α-As2-xSnxTe3 with x

Figure 6 .

 6 Figure 6. a) High-temperature dimensionless thermoelectric figure of merit ZT of the α-As2-

Table 1 .

 1 Nominal and actual compositions measured by EPMA on the polycrystalline series α-As2-xSnxTe3. The compositions have been normalized to five atoms per formula unit.

	Nominal composition	EPMA
	As2Te3	As1.985Te3.015
	As1.975Sn0.025Te3	As1.990Sn0.024Te2.986
	As1.95Sn0.05Te3	As1.929Sn0.047Te3.024
	As1.925Sn0.075Te3	As1.906Sn0.075Te3.019

Table 2 .

 2 Comparison between the experimental and theoretical room-temperature values of

Acknowledgements

The authors would like to thank financial support from the French National Agency (ANR) in the frame of its programme "PROGELEC" (Verre Thermo-Générateur "VTG"). C. C., J.-B.

V. and B. L. thank C. Gendarme for the EPMA experiments.

Conflict of Interest

The authors declare no competing financial interest.


Dr Diane Frankel
email: diane.frankel@univ-amu.fr

Question 4

Concerning the etiology (primary tumour) of malignant pleural effusions, classify the following malignancies in order of frequency: Comments: For the patient, the V600E mutation in BRAF was positive on sentinel node at diagnosis. The mutation was detected for a second time at the relapse in the 11R mediastinal node. In France, BRAF V600E is found in 34.7% of malignant melanoma (www.e-cancer.fr). This mutation is not specific for malignant melanoma and can also be found in other malignant tumours such as lung cancer (2% of cases) or Hairy cell leukemia (79 to 97% of cases) for example.

A

  Figure 1. Cytology of pleural effusion: Papanicolaou stain, x40 (panels A, B); May-Grünwald-Giemsa stain, x40 (Panel C); Fontana-Masson stain, x40 (Panel D). Scale bar: 10μm

Figure 2 .Answers

 2 Figure 2. Immunocytochemistry (peroxidase staining, x40) using antibodies against cytokeratins (clones AE1/AE3/PCK26), vimentin (clone V9), EpCAM (clone MOC31), S-100 protein (rabbit polyclonal), HMB45 (clone HMB45) and melan A (clone A103). Mouse IgG and polyclonal rabbit IgG were used as isotypic controls. Scale bar: 10μm

Morphology quiz: Identification of metastatic cells in pleural effusion

Summary "Inside this month's Cytopathology » Quiz related to cytological examination of pleural effusion in a patient with history of laterothoracic malignant melanoma

Case history

• 46-year-old man.

• Diagnosed with a melanoma on the right lateral thoracic wall (SSM, Clarck level IV, Breslow thickness 1.72 mm).

• Treated with local surgery and resection of sentinel lymph nodes.

• Presenting with a pleural effusion, 19 months after initial diagnosis, which was collected and sent for cytology.

See images page 5.

Question 1

Based on the images provided on the following page (Figure 1), the pleural effusion contains: