Abhijin Adiga
email: abhijin@vbi.vt.edu

Chris J Kuhlman
email: ckuhlman@vbi.vt.edu

Henning S Mortveit
email: hmortvei@vbi.vt.edu

Sichao Wu
email: sichao@vbi.vt.edu

Effect of Graph Structure on the Limit Sets of Threshold Dynamical Systems

Keywords: graph dynamical systems, generalized cellular automata, threshold functions, block decomposition

 showed the existence of block-sequential threshold systems that have arbitrarily long limit cycles. Motivated by this result, we study how the underlying graph structure influences the limit cycle structure of block-sequential systems. We derive a sufficient condition on the graph structure so that the system has only fixed points as limit cycles. We also identify several well-known graph families that satisfy this condition.

Introduction

In this paper, we study Boolean graph dynamical systems or automata networks induced by threshold functions. Such systems are a natural choice to model various biological and sociological phenomena (see [START_REF] Kauffman | Metabolic stability and epigenesis in randomly constructed genetic nets[END_REF][START_REF] Karaoz | Whole-genome annotation by using evidence integration in functional-linkage networks[END_REF][START_REF] Granovetter | Threshold models of collective behavior[END_REF][START_REF] Macy | Chains of cooperation: Threshold effects in collective action[END_REF] for example). We consider standard Boolean threshold functions where, each vertex v is associated with a threshold T v , and the vertex function of v evaluates to 1 if and only if at least T v vertices in its closed neighborhood (v and its distance-1 neighbors) are in state 1. These systems have been extensively studied [START_REF] Goles | Neural and automata networks[END_REF][START_REF] Goles | Comportement périodique des fonctions à seuil binaires et applications[END_REF][START_REF] Barrett | Complexity of reachability problems for finite discrete dynamical systems[END_REF]. Several generalizations of standard threshold functions have been considered in the past. For example in [START_REF] Kuhlman | Bifurcations in boolean networks[END_REF], bi-threshold systems were studied where the thresholds for the 0 to 1 and 1 to 0 transitions can be different. Multi-threshold systems with more than 2 possible vertex states were considered in [START_REF] Kuhlman | Limit sets of generalized, multi-threshold networks[END_REF][START_REF] Goles | Neural and automata networks[END_REF]. In [START_REF] Wu | Limit cycle structure for dynamic bi-threshold systems[END_REF], systems with dynamic thresholds were considered where the vertex thresholds vary with time. Another popular variant of the standard threshold function are Hopfield networks, where only the open neighborhood is considered while evaluating the next state, i.e., the state of the vertex itself is ignored. Our focus is on the limit set or the attractor structure of these systems which captures their "long-term" behavior. The update scheme, i.e., the order in which the vertex functions are evaluated, influences the attractor structure and in general the phase space. Two update schemes (i) synchronous or parallel and (ii) sequential are well-studied. In the synchronous update scheme, every vertex function is applied simultaneously, while in a sequential update scheme, vertices are updated one by one according to a total order defined on the vertex set. A generalization of these schemes is the block-sequential update. Here, the vertices are partitioned into blocks, and vertices within the blocks are updated synchronously while the blocks themselves are updated sequentially. A more general sequential scheme is the word update which is a generalization of the sequential systems. Here, a vertex can be updated more than once in a single time step [START_REF] Mortveit | An introduction to sequential dynamical systems[END_REF].

Two interesting questions which have been repeatedly addressed in the past are: given a graph dynamical system, (i) what is the maximum possible length of a limit cycle? (ii) what conditions lead to only fixed points as limit sets? There are some notable results in the case of standard threshold systems. Goles and Olivos [START_REF] Goles | Comportement périodique des fonctions à seuil binaires et applications[END_REF] and Barrett et al. [START_REF] Barrett | Complexity of reachability problems for finite discrete dynamical systems[END_REF] independently, using different methods, showed that sequential threshold systems exhibit only fixed points as limit cycles. In [START_REF] Goles | Neural and automata networks[END_REF][START_REF] Goles | Comportement périodique des fonctions à seuil binaires et applications[END_REF], it was shown that for synchronous update there can be limit cycles of length at most two. Their result is applicable for the more general case of weighted threshold functions. Kuhlman et al. [START_REF] Kuhlman | Bifurcations in boolean networks[END_REF] considered these questions regarding bi-threshold systems. They showed that, while synchronous systems can have limit cycles of length at most two, sequential systems can have arbitrarily long limit cycles.

In this paper, we consider standard threshold systems with block-sequential update. Mortveit [START_REF] Mortveit | Limit cycle structure for block-sequential threshold systems[END_REF] showed that if the blocks are of size at most 3, then there will be only fixed points. The author also conjectured that the limit cycle length can be at most two for arbitrary block size. However, this was disproved recently by Goles and Montealegre [START_REF] Goles | Computational complexity of threshold automata networks under different updating schemes[END_REF]. Unlike the sequential or synchronous cases, these systems can have arbitrarily long limit cycles. In [START_REF] Goles | Neural and automata networks[END_REF], the more general setting of weighted threshold functions was studied. They gave a sufficient condition for the system to have only fixed points. In this work, we examine standard threshold systems systems from a structural perspective. Our main objective was to identify conditions on the underlying graph structure which lead to only fixed points. Our main result is given below. Theorem 1. Let X be a simple graph with vertex set V [X] and edge set E[X]. Let B be a block partition of V [X]. If every block B ∈ B satisfies Condition (1) below, then, any block-sequential standard threshold system induced by B for any update order on the blocks has only fixed points as limit sets. Also, the transient length is at most (1) An interesting feature of Theorem 1 is that Condition (1) only applies to the individual blocks and is independent of the connections between the blocks. The proof uses the potential function argument introduced in [START_REF] Barrett | Complexity of reachability problems for finite discrete dynamical systems[END_REF]. We build on the framework provided by [START_REF] Mortveit | Limit cycle structure for block-sequential threshold systems[END_REF] and extend the results of that paper. We also show that simple graph classes such as trees and complete graphs satisfy Condition [START_REF] Barrett | Complexity of reachability problems for finite discrete dynamical systems[END_REF]. In addition, we show that any graph which can be block-decomposed into subgraphs which satisfy Condition (1), also satisfies this condition.

(|E[X]| + |V [X]| + 1)/2.
We note that Condition (1) is not a necessary condition. Consider any graph with arbitrary block partition where each vertex has threshold 1. This is a progressive threshold system, i.e., a vertex will never transition from 1 to 0. Hence, it has only fixed points even though the blocks may not satisfy Condition [START_REF] Barrett | Complexity of reachability problems for finite discrete dynamical systems[END_REF].

The organization of the paper is as follows. We introduce the notation and basic definitions in the next section. In Section 3, we prove Theorem 1. In Section 4, we derive the block-decomposition result. In Section 5, we demonstrate some graph classes which satisfy Condition (1) before we conclude in Section 6.

Preliminaries

Let X be a simple undirected graph on n vertices with vertex set V [X] and edge Every vertex is assigned a threshold function f v : {0, 1} deg(v)+1 -→ {0, 1} defined as follows:

set E[X]. Let B = {B 1 , B 2 , . . . , B m } be a block partition of V [X]. For S ⊆ V [X], let deg S (v)
f v x[v] = 1, if w∈n[v] x w ≥ T v , 0, otherwise, (2)
where

T v ∈ N with T v ≥ 1 is the threshold of v.
For a block B and system state x, the map F B (x) : {0, 1} n -→ {0, 1} n is given by

F B (x) v = f v x[v] , if v ∈ B, x v , otherwise. (3)
The block-sequential map F : {0, 1} n -→ {0, 1} n is defined as

F = F Bm • F Bm-1 • • • • • F B1 . (4)
The two special cases of the block-sequential update scheme are sequential and parallel update schemes. The sequential update corresponds to each vertex belonging to a distinct block, i.e., for i = 1, . . . , n, |B i | = 1 and therefore, m = n. In parallel update, there is only one block, i.e., m = 1 and

B 1 = V [X].
3 Sufficient condition for fixed points

Potential function method

For v ∈ V [X], let T 0 (v) denote the smallest number of vertices in n[v] that must be in state 0 for x v to be mapped to zero. By the definition of threshold function in (2), we have

T 0 (v) + T (v) = deg(v) + 2.
With each vertex and edge, we associate a potential. The vertex potential for vertex v and system state x is

P (x, v) = T (v), x v = 1, T 0 (v), x v = 0 . (5)
The edge potential for edge e = {v, v } is

P (x, e) = 1, x v = x v , 0, otherwise. (6)
The system potential function P : {0, 1} n → N for state x is defined as

P (x) = v∈V [X] P (x, v) + e∈E[X] P (x, e) . (7)
For sequential threshold systems, Barrett et al. [START_REF] Barrett | Complexity of reachability problems for finite discrete dynamical systems[END_REF] showed that for any x = F (x) where x = x , P (x ) < P (x). Since P (x) ≥ 0 for all x, it follows that the limit set is comprised of only fixed points. They also showed that the transient length

is at most (|E[X]| + |V [X]| + 1
)/2 as a consequence of this result. The same argument was applied by Mortveit [START_REF] Mortveit | Limit cycle structure for block-sequential threshold systems[END_REF] for block-sequential systems with blocks of size at most three.

Proof of Theorem 1

Suppose the system transitions from state x to x when a block B is updated, i.e.

x = F B (x). Let ∆P = P (x ) -P (x). Let P v (x) = P (x, v) + e∈Ev[X] P (x, e), where E v [X] is the set of edges incident with v. Let ∆P v = P v (x )-P v (x) denote the change in potential at vertex v. Note that since only block B is updated, ∀v / ∈ B, x v = x v . Let B(x, x ) ⊆ B denote the set of vertices such that x v = x v .
We use the following result from Mortveit [START_REF] Mortveit | Limit cycle structure for block-sequential threshold systems[END_REF].

Lemma 2 (Mortveit [START_REF] Mortveit | Limit cycle structure for block-sequential threshold systems[END_REF]). ∆P = v∈B(x,x ) ∆P v .

The lemma below gives an upper bound for ∆P v . Lemma 3. For any v ∈ B(x, x ), let γ v denote the number of neighbors of v in B(x, x ) which have the same state as v in x (and therefore, in x ). Applying

F B , ∆P v ≤ deg B(x,x ) (v) -2γ v -2.
Proof. In [START_REF] Mortveit | Limit cycle structure for block-sequential threshold systems[END_REF], ∆P v is bounded as a function of deg B (v) and the number of vertices in state 1 in x. We apply the same approach here, but obtain a more compact result. Let n 1 (x, v) and n 0 (x, v) denote the number of neighbors of v in state 1 and 0 respectively. There are two possible cases: v transitions either from 0 to 1 or 1 to 0. We consider these cases separately.

Transition 0 → 1. Note that n 1 (x) ≥ T (v). We recall that T (v) + T 0 (v) = deg(v) + 2. Also, since only vertices in B(x, x ) change state,

n 0 (x , v) = n 0 (x, v) + (number of neighbors of v in B(x, x ) in state 1 in x) -(number of neighbors of v in B(x, x ) in state 0 in x) = n 0 (x, v) + (deg B(x,x ) (v) -γ v ) -γ v = deg(v) -n 1 (x, v) + deg B(x,x ) (v) -2γ v . (8)
Now we compute ∆P v .

∆P v = T (v) + n 0 (x , v) -T 0 (v) + n 1 (x, v) = T (v) + deg(v) -n 1 (x, v) + deg B(x,x ) (v) -2γ v -deg(v) + 2 -T (v) + n 1 (x, v) = 2 T (v) -n 1 (x, v) + deg B(x,x ) (v) -2γ v -2 ≤ deg B(x,x ) (v) -2γ v -2 .
Transition 1 → 0. In this case, we have n 1 (x) ≤ T (v) -2. Following a similar approach as in [START_REF] Kauffman | Metabolic stability and epigenesis in randomly constructed genetic nets[END_REF], it can be shown that

n 1 (x , v) = n 1 (x, v)+deg B(x,x ) (v)-2γ v . ∆P v = T 0 (v) + n 1 (x , v) -T (v) + n 0 (x, v) = deg(v) + 2 -T (v) + n 1 (x, v) + deg B(x,x ) (v) -2γ v -T (v) -deg(v) -n 1 (x, v) = 2 n 1 (x, v) -T (v) + 2 + deg B(x,x ) (v) -2γ v ≤ deg B(x,x ) (v) -2γ v -2 .
For a set of vertices S ⊆ V [X], let S denote the number of edges in X[S], the subgraph induced by S. For a state vector x, let Λ S (x) = (u, v) | u, v ∈ S, x u = x v and {u, v} ∈ E[X] , i.e., the set of all pairs of adjacent vertices in S which have the same state.

Lemma 4. ∆P = P (x ) -P (x) ≤ 2 B(x, x ) -2|Λ B(x,x ) (x)| -|B(x, x )| .
Proof. From Lemma 2, P (x ) -P (x) = v∈B(x,x ) ∆P v . Applying Lemma 3,

P (x ) -P (x) ≤ 2( B(x, x ) -v∈B(x,x ) γ v -|B(x, x )|). Note that for each (u, v) ∈ Λ B(x,x ) (x), v contributes 1 to γ u and u contributes 1 to γ v . More- over, if (u, v) / ∈ Λ B(x,x ) (x)
, then, it does not contribute to the sum. Therefore,

v∈B(x,x ) γ v = (u,v)∈Λ B(x,x ) (x) 2 = 2|Λ B(x,x ) (x)|. Hence proved.
Lemma 5. Let block B satisfy Condition (1). Then, for any x = F B (x) such that x = x, P (x ) < P (x).

Proof. From Lemma 4, ∆P ≤ 2( B(x, x ) -2|Λ B(x,x ) (x)| -|B(x, x )|). Let B = B(x, x ) and y be the state vector restricted to B(x, x ). Since x = x, B is not empty. Therefore, by Condition (1), B -2|Λ B (y)| -|B | < 0.

From Lemma 5, we note that if every block satisfies Condition (1), then, whenever a block is updated and some vertices change states, the system potential decreases. Since the potential cannot be negative by definition, it follows that there can be only fixed points as limit sets. Hence, we have proved Theorem 1.

Block decomposition

In the graph theory literature, a block is a maximal connected subgraph without a cut vertex [START_REF] Diestel | Graph Theory[END_REF]. Every block can either be a maximal 2-connected subgraph, an edge, or an isolated vertex. Since the term "block" has already been used to mean something else in this paper, we will henceforth refer to maximal connected subgraphs as subblocks. Every graph can be decomposed into subblocks. Since they satisfy maximality, any two subblocks overlap in at most one vertex, which, if it exists, is a cut vertex of the graph. This is illustrated with an example in Figure 1 Theorem 6. Let block B be such that all of its subblocks satisfy Condition (1).

Then, B satisfies Condition (1) too.

Proof. Let {S 1 , . . . , S k } be the vertex partition of B where each S i induces a subblock of B. From the block graph representation, it is easy to see that there exists an ordering of the subblocks such that every subblock has at most one cut vertex in common with its previous subblocks. We will assume that the current ordering satisfies this property, i.e.,

∪ j<i S j ∩ S i = 1, ∀i = 1, . . . , k . (9)
Let D ⊆ B and D i = D ∩ S i . From ( 9), we have

|D| ≥ |D 1 | + k i=2 |D i | -1 .
For a subset of vertices S, let E S denote the edge set of the graph induced by S. We observe that the edge sets E S i partition E B . This implies that E D i are mutually disjoint. Since Λ D i (x) ⊆ E Di , they are mutually disjoint too. we have

D -2Λ D (x) -|D| ≤ k i=1 D i -2Λ D i (x) -|D 1 | + k i=2 |D i | -1 = D 1 -2Λ D 1 (x) -|D 1 | + k i=2 D i -2Λ D i (x) -|D i | + 1 .
Since all the subblocks satisfy the Condition (1), the first term in the above expression is negative while the second term is at most 0. Hence, D -2Λ D (x)-|D| < 0.

Simple graph classes which satisfy Condition (1)

We will show that some graph classes such as trees, odd cycles, and complete graphs satisfy Condition [START_REF] Barrett | Complexity of reachability problems for finite discrete dynamical systems[END_REF]. Even though these are very simple graphs, to the best of our knowledge, these results have not been obtained before using any other method. Throughout this section, B corresponds to a block in X and B ⊆ B. Proposition 7. If B induces a tree in X, then, it satisfies Condition (1).

Proof. Suppose B ⊆ B. If the graph induced by B is connected, then it still corresponds to a tree. If not, then, each connected component (which is also a tree) in the graph can be considered independent of the rest of the block. In that case, effectively we are working with a smaller tree. Hence, without loss of generality, we will assume that B is connected (and can be the same as B).

Since B = |B | -1, it implies that B satisfies Condition (1).
Alternatively, we could have used Theorem 6 to prove the above proposition. Proposition 8. If B induces an odd cycle in X, then, it satisfies Condition (1).

Proof. If B ⊂ B, then it corresponds to a collection of disconnected paths. Then, we can apply Proposition 7 to show that B satisfies the condition. Therefore, we will assume that B = B. We first note that B = |B|. Since the cycle is odd, there exists by the pigeonhole principle, at least one pair of vertices in Λ B (y) for any state vector y. Hence, for all B ⊆ B, B -2Λ B (y) -|B| < 0.

Remark 11. Note that one can configure an example corresponding to a 4-cycle (C 4 ) for which not satisfies Condition (1) (See Figure 3(a)). Moreover, this configuration corresponds to a limit cycle of length 2. So, a natural question to ask is whether graphs which do not have a C 4 as a vertex-induced subgraph not satisfies Condition (1) for all x. Unfortunately, the answer is no. Proof. A wheel graph is formed by connecting a single vertex to all vertices of a cycle. see Figure 4 (a) as an illustration. Let B ⊆ B and y be the state vector restricted to B . There are three cases that need to be considered. Without loss of generality, we will assume that the state of the center vertex is 0. Let Q denote the remaining set of vertices and of these, let k be in state 0. It is clear that the rest n -1 -k vertices are in state 1. We have

|Λ B (y)| = k + |Λ Q (y)| . (10)
If k ≥ n-2 2 , (11) trivially holds. Thus, we will assume that k < n-2 2 . Note that each edge on Q contributes 1 to |Λ Q (y)| if and only if the two vertices associated with the edge are in the same state. Therefore, |Λ Q (y)| will achieve its minimum value when all vertices in state 0 have their neighbors in state 1. And since k < n-2 2 , it is guaranteed that such a configuration exists. In this case, n -2 -2k edges will contribute to |Λ Q (y)|, i.e. we have, |Λ

Q (y)| ≥ n -2 -2k . This yields, |Λ B (y)| = k + |Λ Q (y)| ≥ n -2 -k > n-2
2 . Hence, (11) holds, which in turn implies that

B -2|Λ B (y)| -|B | ≤ 2n -3 -2 • n -2 2 -n ≤ -1 .
Hence, proved. Hence, (12) holds. We have,

B -2|Λ B (y)| -|B| ≤ 2n -2 -2 • n -1 2 -n ≤ -1 .
Hence, proved.

Remark 13. Note that there exists a wheel graph with an even cycle corresponding to a limit cycle of length 2, see Figure 5. In this example, suppose the threshold value of the central vertex is 3 and all other vertices have threshold value 2. Then, one can verify that the central vertex will remain 0 and the other vertices will change states alternatively in pairs, i.e. this configuration leads to a length 2 limit cycle.

Conclusion

In this paper, we studied the limit cycle structure of standard threshold dynamical systems with block-sequential update. We identified a sufficient condition for the system to have only fixed points as limit sets. There are several possibilities to consider for the future. Even though the condition depends only on the blocks and not the graph as a whole, it seems to be restrictive. One direction to explore is to find more general conditions which take into account edges between the blocks too. Another direction would be to study bi-threshold block-sequential systems.

For

  any non-empty B ⊆ B and any assignment y of vertex states for B , B -2|Λ B (y)| -|B | < 0, where, B is the number of edges in the subgraph induced by B and Λ B (y) = {u, v} ∈ E[X] | u, v ∈ B , and y u = y v .

  denote the number of neighbors of v in the graph induced by S, and let deg(v) be its degree in X. x v denotes the vertex state of v. Since we are considering Boolean systems, x v ∈ {0, 1}. Let x = (x 1 , x 2 , . . . , x n ) be the system state. Let n[v] denote the sorted sequence of the closed neighborhood of v, and let x[v] denote the restriction of x to n[v].

  (a). Let C be the set of cut vertices and S be the set of subblocks. The block graph is the bipartite graph on the vertex set C ∪ S where for c ∈ C and S ∈ S, {c, S} is an edge if and only if c ∈ S. It can be easily shown that the block graph is a tree. See Figure1(b) for the block graph of the example.

Fig. 1 .

 1 Fig. 1. An example of (a) a block decomposition and (b) the corresponding block graph.

Figure 3 (Fig. 3 .

 33 Fig. 3. Configurations which lead to limit cycles of length two: if the black vertices are in state 0, then the white are in 1, and vice versa. (a) Block C4 where all vertices have threshold 2 and (b) an induced-C4-free graph with the black vertices having threshold 2 and white vertices 3.

  (a) B does not contain the center vertex. In this case, B induces either an odd cycle or a collection of paths. Then, from Propositions 7 and 8, B -2|Λ B (y)-|B | < 0. (b) B ⊂ B and contains the center vertex. In this case, the central vertex corresponds to a cut vertex (see Figure 4 (b)). Therefore, block decomposition of B yields subblocks, all of which have the following structure: a path graph where each vertex is connected to a central vertex. Let B be such a subblock (illustrated in Figure 4 (b)). We only need to show that B -2Λ B (y)-|B | < 0. The rest follows from Theorem 6. Let n = |B |. We have B = 2n -3.

Fig. 4 .

 4 Fig. 4. (a) An exemplary wheel graph. (b) Induced sub-graph B of a wheel graph by removing multiple vertices from the cycle

(-1 2 . ( 12 )

 212 c) B = B, i.e. we consider the whole wheel graph. In this case, |B| = n and B = 2n -2. Now, we will show that B -2|Λ B (y)| -|B| < 0. The argument is similar to the previous case. Let Q denote the set of vertices in the cycle. Now, we will claim that|Λ B (y)| ≥ n Since |Λ B (y)| = k + |Λ Q (y)|, if k ≥ n-1 2, the above inequality holds. We can thus assume k < n-1 2 . There are n-1 edges on the cycle. Using the same arguments as in the previous case, at most 2k edges do not contribute to the value of|Λ Q (y)|, which means |Λ Q (y)| ≥ n -1 -2k. It follows that |Λ B (y)| = k + |Λ Q (y)| ≥ n -1 -k > n -1 2 .

Fig. 5 .

 5 Fig. 5. Configuration over a wheel graph with an even cycle which leads to limit cycle of length 2. Black vertices are in state 0 and white are in state 1. The threshold value for the central vertex is 3, and 2 for other vertices.

Proposition 9. If B induces a clique in X, then, it satisfies Condition [START_REF] Barrett | Complexity of reachability problems for finite discrete dynamical systems[END_REF].

Proof. If B ⊂ B, then it still induces a clique. Hence, we will assume that B = B. Let y be the state vector restricted to B. Let n 0 denote the number of vertices of B in state 0 and let n

The next result concerns systems with block size at most 4. This is an extension of the result by Mortveit [START_REF] Mortveit | Limit cycle structure for block-sequential threshold systems[END_REF].

Proposition 10. Any block B of size 4 other than the 4-cycle, satisfies Condition (1).

Proof. If B ⊂ B, then it corresponds to a block of size 3 or less, for which the result follows from [START_REF] Mortveit | Limit cycle structure for block-sequential threshold systems[END_REF]. Hence, we will assume that B = B. If B is a tree or clique, then, by Propositions 7 and 9, the statement is true. The remaining possibilities excluding the 4-cycle are isomorphic to one of the graphs illustrated in Figure 2. We consider them one by one and in each case show that B -2|Λ B (x)| -|B| < 0 and the rest follows from Lemma 4.

Graph (a)

Graph (c)

The argument is similar to the previous case.


Kari Eloranta
email: kari.v.eloranta@gmail.com

Hard Core via PCA: entropy bounds

Keywords: hard core model, independent sets, topological entropy

We establish bounds for the entropy of the Hard Core Model/ Independent Sets on a few 2-d lattices. Our PCA-based sequential fill-in method yields an increasing sequence of lower bounds for the topological entropy. Additionally the procedure gives some insight on the support of the measure of maximal entropy. The method also applies to other lattices and models with appropriate sublattice splitting.

Introduction

The Hard Core Model/Golden Mean Subshift/Independent Sets is a highly useful model in various disciplines as witnessed by its many appearances under distinct names in fields like Statistical Mechanics/Symbolic Dynamics/Theoretical Computer Science respectively. Simply described, one distributes 0's and 1's on each vertex of a given graph and requires an exclusion rule to hold everywhere: no two 1's can be nearest graph neighbors ( [START_REF] Baxter | Exactly solvable models in statistical mechanics[END_REF]).

On a k-partite graph it is natural to associate with it a probabilistic cellular automaton (PCA) which updates each of the k subgraphs from the others with a local rule as follows: in an all-0 neighborhood update the center vertex to 1 with probability u ∈ (0, 1), otherwise update to 0. Running a sequential update with the PCA (from any input) through the subgraphs yields eventually any Hard Core configuration with positive probability (and no others).

The PCA behavior is of interest for different u-values. If u is near 1, we are in the high density regime and the characterization of the allowed Hard Core configurations is essentially a packing problem (studied e.g. in an earlier paper [START_REF] Eloranta | Dense packing on uniform lattices[END_REF]). In the dilute case i.e. u is near 0, the configurations are essentially Bernoulli(ũ)-fields (sometimes called Hard Square Gas), 0 < ũ < u.

Here we concentrate on the intermediate entropic regime. The outstanding open question near u = 1/2 is the exponential size of the configuration space. In almost all two or higher dimensional set-ups the exact answer is unknown. We try to alleviate the situation a little bit by establishing a procedure to estimate the entropy from below and to characterize the typical configurations. For simplicity we restrict here the graphs to be 2-d lattices. This facilitates comparison to entropy approximations elsewhere via different methods (e.g. [START_REF] Baxter | Planar lattice gasses with nearest-neighbor exclusion[END_REF], [START_REF] Calkin | The number of independent sets in a grid graph[END_REF], [START_REF] Engel | On the Fibonacci number of an M × N lattice[END_REF], [START_REF] Forchhammer | Entropy bounds for constrained two-dimensonal random fields[END_REF], [START_REF] Milosevic | Towards finding exact residual entropies of the Ising ferromagnets[END_REF]). Our ideas also generalize to more complicated and higher dimensional set-ups. For a general percolation approach to Hard Core see e.g. [START_REF] Van Den Berg | Percolation and the hard-core lattice gas model[END_REF].

Set-up

Let L be a 2-dimensional lattice. Subsequently we will consider mostly one of the regular lattices (square (Z 2 ), honeycomb (H) or triangular (T)). In a few cases we illustrate the principles developed on more exotic stages like square lattice with the Moore neighborhood (Z 2 M, eight nearest Euclidean neighbors, a non-planar graph) or the Kagomé lattice (K). Our method is not intrinsically 2-d but for understanding the clear geometry of 2-d serves best.

A configuration on L satisfying the Hard Core Rule is an element in X = {0, 1} L where no two 1's can be nearest neighbors. This rule can naturally be viewed as a zero range infinite repulsive potential i.e. a hard exclusion rule not unlike that in hard sphere packing. Call the collection of configurations X hc L . The exclusion rule naturally imposes a sublattice split on L if it is a kpartite graph. For example on Z 2 , a bipartite graph, one can man all sites on 2Z 2 (Z 2 rescaled by √ 2 and rotated by 45 • ) with 1's and the rest of Z 2 must then be all 0's. Call the former the even sublattice, L e and the latter the odd sublattice, L o (it is a (1/2, 1/2)-shifted copy of the former). In rendering these we will present the even/odd sublattices as circle/dot sublattices. In a similar fashion H splits into two identical sublattices and T (a tripartite graph) into three "thinned" copies of T. Both in the dense packing regime of [START_REF] Eloranta | Dense packing on uniform lattices[END_REF] and in the the entropic regime of this paper, this splitting will be highly relevant. Remark. For the full shift on any lattice h top X = ln 2 (indicating two independent choices per lattice site). If L = Z the Hard Core model is explicitly solvable and a standard transfer matrix argument implies that h top = ln

Let X 0 ⊂ X = {0, 1} L . | • |
( 1+ √ 5 2
) (e.g. [START_REF] Walters | Ergodic theory[END_REF]). For two and higher dimensional lattices the matrix argument breaks down and the exact value of the Hard Core topological entropy remains an unsolved problem except for T (see [START_REF] Baxter | Exactly solvable models in statistical mechanics[END_REF]). In this paper we try to approach and in particular approximate it in a novel way.

From the general theory of lattice dynamical systems ( [START_REF] Walters | Ergodic theory[END_REF]) it is known that shift invariant probability measures on a space of configurations, M, satisfy the maximum principle, h top = sup M h µ , where h µ is the measure-entropy. The special measures yielding the equality are measures of maximal entropy. For two and higher dimensional systems they are in general not unique. In all our cases they are believed to be so, but we do not actually need to know this.

For the idea of our approach recall that given the entropy function H(P) = -∑ µ(P i ) ln µ(P i ) for a partition P, it holds H(P ∨ P ′ ) = H(P) + H(P ′ |P). In the case of Z let P (e) = {{x|x 0 = i}} and P (o) = {{x|x 1 = i}} be the (generating) partitions for the even/odd sublattice for the left shift σ. P = P (e) ∨ P (o) generates on Z and the conditional entropy formula above implies

h µ (σ) = 1 2 h µ (σ 2 |P) = 1 2 h (e) µ + inf n 1 2n H µ ( n-1 ∨ k=0 σ -2k P (o) n-1 ∨ k=0 σ -2k P (e)
)

.

(1.1)

The formula readily generalizes to Z d -actions, to multiple sublattices etc. The last expression is trivial only in the independent case (equals 1 2 h

(o) µ ). It codes the additional entropy to be gained from the odd sublattice, given the even. In the case of Hard Core it is manageable since 1. the rule is of range one and 2. the hard exclusion greatly simplifies the computation of the conditional probabilities involved. This will become much more transparent in the subsequent analysis.

Lower bounds

We now proceed to establish lower bounds for the topological entropy using the sublattice partition representation (1.1) and a sequential fill-in scheme to circumvent the dependencies. To keep the ideas clear we first present them in the bipartite the case and then comment on the k-partite cases.

Let N e denote an all-0 nearest neighbor neighborhood of a site on the odd lattice in the even lattice. In the case of Z 2 lattice the sites in N e form the vertices of an even unit diamond, ♢ e (♢ o ). On the honeycomb and triangular lattices these sites form triangular arrangements, △ or ▽ or a hexagon.

It will become quite useful to think the fill-in in terms of forming a tiling. The pieces are 0/1-tiles which in Z 2 case are either 0/1-diamonds (as above) depending on whether the center site carries 0 or 1. On the hexagonal and triangular lattices the tiles are 0/1-(unit) hexes. Once a sublattice is chosen, one can tile the plane using any combination of 0/1-tiles centered on the sublattice.

Recall that the Bernoulli measure with parameter p, B(p), assigns 1's independently with probability p to each (sub)lattice site and 0's otherwise. Its entropy, denoted by h B (p), is -p ln p -(1 -p) ln (1 -p).

Proposition 1. The topological entropy of the hard core model on a lattice with a two-way sublattice split is given by

h top = 1 2 { h (e) + P (N e ) ln 2 } , ( 2.1)
where h (e) is the entropy of the measure of maximal entropy computed from the even sublattice alone.

Proof. We attain the maximum entropy by first assigning the marginal of the measure of maximal entropy to the even lattice and then filling in the nonblocked sites on the odd lattice. These are centered at the even unit diamonds, which have probability P (N e ). B(1/2) is the maximal entropy measure among B(p), hence this on the allowed odd sites and the factor h B (1/2) = ln 2. QED

The principle in the Proposition can be directly applied to square and honeycomb lattices. A further argument is required to cover all regular lattices. In the following result we present these arguments and further extend to Kagomé lattice, K (a tripartite graph), as well as to the square lattice with Moore neighborhood, Z 2 M (eight nearest neighbors in Euclidean metric, a 4-partite graph).

Theorem 1. The topological entropy of the hard core model is bounded from below on the square (m = 4) and honeycomb (m = 3) lattices by

h Z 2 /H (p) = 1 2 { h B (p) + (1 -p) m ln 2 } , (2.2)
on triangular (m ′ = 3) and Kagomé (m ′ = 2) lattices by

h T/K (p, q) = 1 3 { h B (p) + (1 -p) m ′ [ h B (q) + [1 -(1 -p)q] 2 ln 2 ] } (2.3)
and on Z 2 M lattice by

h Z 2 M (p, q, r) = 1 4 { h B (p) + (1 -p) 2 [ h B (q) + [1 -(1 -p)q] 4 h B (r) + (1 -p) 2 (1 -q) 2 [ 1 -(1 -(1 -p)q) 2 r ] 2 ln 2 ]}
(2.4) where p, q and r ∈ (0, 1).

Proof. The lower bounds (2.2) follow simply from (2.1) by assigning B(p) to the even sublattice since then P (N e ) = (1-p) |Ne| where the exponent is the number of elements in N e in Z 2 and H respectively.

On the triangular lattice the sublattice partition is three-way. We call the parts the dot, circle and triangle sublattices. They are filled in three stages in the order • → • → ◃. See Figure 1a and b for the notation and arrangement of the sublattices in a neighborhood of a triangle site.

Suppose the three sublattices are initially all empty. First fill-in the circle lattice with B(p), hence the entropy contribution 1 3 h B(p) . Then fill-in all dot sites centered at ▽ with B(q), this implies the entropy increase 1 3 (1 -p) 3 h B(p) from the dot lattice.

To update the center site which is a triangle we need to know that its value is not forced. Hence P(center triangle not forced by nearest neighbor circle or dot) = P(no 1 ′ s in the hexagon of nearest neighbors of the triangle) = P(△ = 0 and

▽ = 0) = P(c 2 = c 4 = c 5 = 0 and d 1 = d 2 = d 3 = 0) = P(d 1 = d 2 = d 3 = 0 | c 2 = c 4 = c 5 = 0) P(c 2 = c 4 = c 5 = 0) = P(d 1 = d 2 = d 3 = 0 | c 2 = c 4 = c 5 = 0) (1 -p) 3 = [ P(d 1 = 0 | c 2 = c 4 = c 5 = 0) ] 3 (1 -p) 3 = [ P (c 1 = 1 or {c 1 = 0 and d 1 = 0} | c 2 = c 4 = c 5 = 0) ] 3 (1 -p) 3 = [p + (1 -p)(1 -q)] 3 (1 -p) 3 (2.5)
which together with the choice B(1/2) on the non-blocked dots gives (2.3). The Kagomé lattice argument is similar to the triangular one. There are three sublattices involved, all identical copies of the Kagomé, only thinned and reoriented. For the nearest neighbors of a triangle-site see Figure 1c. Again we fill in the order • → • → ◃. In the last stage the probability of the triangle site being unforced is now

P(c 2 = c 4 = 0 and d 1 = d 2 = 0) = [ P (c 1 = 1 or {d 1 = 0 and c 1 = 0} | c 2 = c 4 = 0) ] 2 (1 -p) 2 = [p + (1 -p)(1 -q)] 2 (1 -p) 2
In the case of the square lattice with Moore neighborhood there is a four-way sublattice partitioning. We denote and fill them as follows:

• → • → ◃ → ⋄ (see Fig. 1d).
The two first terms of the formula (2.4) are straightforward since circles are laid independently and each dot has exactly two circle neighbors. Furthermore as above we can show that

P(◃ unforced) = (1 -p) 2 [p + (1 -p)(1 -q)] 4 .
For the diamond site at the center of Fig. 1d to contribute to the entropy we need to know the probability that it is unforced i.e. all entries in the punctured square S rendered with dotted line in Fig 1d. are 0's:

P ( S = 0 ) = P ( all ◃, • ∈ S are 0 | all • ∈ S are 0 ) (1 -p) 4 =P ( ◃ ∈ S are 0 | •, • ∈ S are 0 ) (1 -p) 4 (1 -q) 2 =P ( d 1 = 1 or {d 1 = d 2 = 0 and t 1 = 0} | •, • ∈ S are 0 ) (1 -p) 4 (1 -q) 2 = [ P ( d 1 = 1 | •, • ∈ S are 0 ) + P ( d 1 = d 2 = 0 and t 1 = 0) | •, • ∈ S are 0 )] 2 (1 -p) 4 (1 -q) 2
(2.6) One can compute the two probabilities in the last expression to be

2p(1 -p)q + (1 -p) 2 (2 -q)q and [ p 2 + 2p(1 -p)(1 -q) + (1 -p) 2 (1 -q) 2 ]
(1 -r) respectively. From these the formula in the square brackets in (2.6) can finally be simplified to the form 1

-[1 -(1 -p)q] 2 r. QED
The entropy bounds in (2.2) -(2.4) can be maximized with respect to the parameters using standard optimization routines in a desktop machine.

In the square lattice case the topological entropy has been computed to a great accuracy (e.g. in [START_REF] Baxter | Planar lattice gasses with nearest-neighbor exclusion[END_REF] to some 40 decimal places) using the corner transfer matrix methods. These numerical studies attack the problem in a very different way. Our aim is not to compete in decimal count but rather present an alternative method applicable in many lattice set-ups to estimate the entropy which simultaneously yields some explicit information on the generic configurations/the measure of maximal entropy. The measure of maximal entropy doesn't need to be unique for a 2-d lattice model but in the case of hard square gas it is. This follows from the Dobrushin criterion ( [START_REF] Dobrushin | Statistical Physics and Dynamical System[END_REF], [START_REF] Radulescu | The Dobrushin-Shlosman Phase Uniqueness Criterion and Applications to Hard Squares[END_REF]). Using this knowledge and the results above we now establish bounds for the density of 1's in the generic configurations. The exact value of the upper bound in the following result is in the Proof but we prefer to give the statement in this more explicit form.

Proposition 2. In the square lattice case the density of 1's at the equilibrium is in the interval (0.21367, 0.25806).

Proof. Let ρ e be the density of 1's on the even lattice and let c denote the expected number of 0's that a 1 forces on the odd lattice. Since exactly half of the non-forced sites will be 1's it must by the uniqueness of the measure of maximal entropy hold that (2 + c)ρ e = 1. Hence under it

P(x i = 0) = 1 + c 2 + c , P(x i = 1) = 1 2 + c
and P (♢ e ) = 2 2 + c on both lattices. The last one is due to exactly half of ♢ e giving rise to all the 1's on the other sublattice. (0-diamond as defined in the beginning of the section).

The entropy of any distribution on the even lattice with 1-density ρ e is bounded from above by the entropy of the Bernoulli distribution with parameter ρ e . Hence the total entropy at that 1-density is bounded from above by 1 2

( h B ( 1 2 + c ) + 2 2 + c ln 2
) .

This expression bounded by h top of Table 1 ( [START_REF] Baxter | Planar lattice gasses with nearest-neighbor exclusion[END_REF] or [START_REF] Milosevic | Towards finding exact residual entropies of the Ising ferromagnets[END_REF]) yields an upper bound for c, 2.6801 which in turn gives the lower bound for ρ e . The upper bound for ρ e follows from a lower bound for c which we establish using a monotonicity argument. The 1's on say the even lattice are B(1/2)distributed on the non-forced sites. Call this set F. Pick a site in it which has symbol 1. How many sites will this entry block? Let F ′ be a superset of F.

Then clearly E(c| F ) ≥ E(c| F ′ ) as in a bigger domain the 1 is more likely to share the blocking with a nearest neighbor 1 on the same sublattice. Hence a lower bound is obtained by calculating the blocking for a 1 with its eight nearest neighbors also in F . Enumerating the 2 8 possible neighborhood configurations and weighting them uniformly according to the B(1/2)-distribution we get the lower bound for c: 15/8. This in turn implies the upper bound for ρ e , 8/31. QED Since our first estimate for the lower bound on Z 2 is associated with densities incompatible with Proposition 2 we will try out a symmetric variant of the theme. The (near) equality of the densities on the sublattices should be a natural property of a measure corresponding to a good lower bound since the measure of maximal density is believed to be unique in all our cases. In the last three cases in Table 1. the non-equality of the densities isn't far off but for the first two we present an "equalization".

Proposition 3. To achieve equal densities of 1's on each of the sublattices one needs to replace the B(1/2) distribution in the last stage of the measure construction by B(p ′ ) and thereby ln 2 in (2.2) by h B(p ′ )

, where p ′ = p(1 -p) -|Ne| .

Proof. In the case of two sublattices after B(p) distribution of 1's on the even lattice there are a density of (1 -p) |Ne| unforcing neighborhoods on this sublattice. These have to produce the correct density of 1's on the odd lattice, hence we need the even lattice flip probability p ′ to satisfy p ′ (1 -p) |Ne| = p. QED Using Proposition 3 one can optimize the square lattice topological entropy bound to (a slightly worse value) 0.3921 at common density level 0.2015. In view of Proposition 2 this indicates that the entropy generating 1's are not yet packed in densely enough. In the case of the honeycomb lattice the corresponding values are 0.427875 at 0.2284.

Higher order blocks

To improve the entropy bounds and more importantly to get some insight into the character of the measure of maximal entropy we now consider more complicated optimization schemes involving Bernoulli-distributed blocks on sublattices.

We first illustrate the ideas on hexagonal and triangular lattices.

A three-hex is obtained by gluing together three unit hexes so that each has two joint sides. Figure 2a. illustrates three such three-hexes next to each other (for reference lattice edges are indicated as thin dotted lines in one of the unit hexes). Note that the unit tiles on each of them are all centered on the same sublattice, the circle lattice in this case (call the tile a circle three-hex). The dots of the other sublattice are all in the centers of the three-hexes or on their extremities (three of them are indicated). Three-hexes of the same orientation obviously tile the plane. Let B(p), p = (p 0 , p 1 , p 2 , p 3 ) be the Bernoulli distribution on circle three-hexes with the probability that the three-hex has exactly k 1-tiles in it in a given orientation being p k (so p 0 + 3p 1 + 3p 2 + p 3 = 1). Its entropy is then h

H (p) = 1 6 { h (3) B (p) + [ p 0 + 2a(p) 3 ] ln 2 } (3.1)
and for the triangular lattice a corresponding bound is

h (3) T (p, q) = 1 9 { h (3) B (p) + [ p 0 + 2a(p) 3 ] h B (q) + 3 [p 1 + p 0 (1 -q)] a(p) 3 (2 -q) 2 ln 2 } (3.2)
where p i , q ∈ (0, 1).

Proof. For the construction of the measure we will fill in the lattice in the order • → •. If the circle three-hexes are distributed Bernoulli with parameter p the entropy contribution from the circle lattice will be 1

[ p 0 + 2 (p 0 + 2p 1 + p 2 ) 3 ]
where the coefficient 2 and the power 3 follow from the fact that at two of the three dot sites three adjacent three-hexes coincide. These formulas combined and simplified yield (3.1).

On the triangular lattice a third sublattice enters and the fill-in order is then • → • → ◃. The entropy contribution from the Bernoulli circle three-hexes is now 1 3 1 3 h B (p) since each sublattice is identical, hence of density 1/3. In the second stage the unforced dot sites are filled with B(q) distribution. Their density is computed as above to be 1 3

[ p 0 + 2 (p 0 + 2p 1 + p 2 ) 3 ]
, hence the entropy contribution from dot lattice will be this expression multiplied by 1 3 B(q). In the final stage the unforced triangle sites are filled by B(1/2). Their density in the full lattice is

1 3 P(nearest neighbor • and • sites all 0 ′ s) = 1 3 { p 1 (p 0 + 2p 1 + p 2 ) [(p 1 + 2p 2 + p 3 ) + (p 0 + 2p 1 + p 2 )(1 -q)] 2 +p 0 (p 0 + 2p 1 + p 2 )(1 -q) [(p 1 + 2p 2 + p 3 ) + (p 0 + 2p 1 + p 2 )(1 -q)] 2 } , (3.3)
which results from considering the two different arrangements of four neighboring three-hexes as shown in Fig. 2c. (top and bottom cases for the top and bottom expressions in (3.3)). The formulas merged and simplified result in (3.2). QED Remarks. 1. The Kagomé lattice case is treated in an analogous fashion to T.

2. Note that apart from improvements in the entropy bounds, almost all of the sublattice densities have increased (in comparison to values in Table 1) indicating a better packing of the 1's on the sublattices. Moreover they have significantly less variation which is to be expected since the densities are equal for the measure of maximal entropy.

Let us now return to our original motivation, the Hard Core on the square lattice.

Compounding the principles above and some further ideas we will implement an increasing sequence of lower bounds converging to the topological entropy. Along the way we'll get more explicit information on the configurations favored by the measure of maximal entropy. 1-tiles in the Z 2 case are diamonds of side length √ 2 centered on either of the two sublattices. k-omino is formed by gluing together k such 1-tiles along edges. If k = n 2 and the 1-tiles are in a diamond formation we call them a n × n -blocks. There are 2 n 2 of them. The optimization results in Section 2 were for the 1 × 1-blocks.

Consider next 2×2 -blocks. There are 16 of them, but after assuming isotropy for them i.e. that blocks that are rotations of each other are distributed with equal probability (inevitable when measure of maximal entropy is unique), there are only five free parameters for Bernoulli distribution B(p) on them (p = (p 0 , p 1 , p 21 , p 22 , p 3 , p 4 ), p 0 + 4p 1 + 4p 21 + 2p 22 + 4p 3 + p 4 = 1. Here the first subindex of p refers to the number of 1's in the block and p 22 and p 21 denote the two different arrangement of two 1's in the block (side by side and across)).

The entropy contribution from the even lattice (on which we distribute first the 1's using B(p) is now

- 1 4
{ p 0 ln p 0 + 4p The density of the unforced sites on the odd lattice can be computed from the three cases indicated in Figure 3a. and results in 1 4

{ p 0 + 2 (p 0 + 2p 1 + p 21 ) 2 + (p 0 + 3p 1 + 2p 21 + p 22 + p 3 ) 4 } . ( 3.5)
These combined yield a lower bound for h top , which is optimized in Table 3 (second row). In the block size 3 × 3 there are initially 511 free block probabilities to optimize. When rotational invariance is imposed the variable number is reduced and additionally we will expect blocks that are reflections of each other to have equal probabilities at the optimum. After these two types of symmetries are accounted the number of free variables will be 101. In this size and in larger blocks another feature appears which enables further variable weeding. Consider the block in Figure 3c. The symbol assignments in sites x, y and z are irrelevant in the sense that the existing 1's in the 3 × 3 -block already force all the odd sites (to carry 0's) that x, y and z might force if any of them were 1's. Hence there are 2 3 blocks of equal probability. This combined with the symmetry assumptions above yield the total of 64 blocks with identical probabilities at the optimum (this is actually the maximum reduction achievable in this block size). Combing through the set of all blocks for this feature will result in reduction by a factor about 11 to the final set of 46 variables. Their optimal values have been computed and the results are in Table 3.

Subsequently we call sites like x, y and z above weak with respect to the rest of the given block. Only the corner sites of a block cannot ever be weak.

The procedure of variable reduction is highly useful since the above rotational and reflection symmetry search as well as the weak site identification can be automated. Moreover the reduction improves significantly at every stage: for example in the next block size of 4 × 4 the initial variable number of 65.536 shrinks 66-fold to 991 final free variables.

Note also that the optima in block size n × n can be utilized as indicated in Figure 3d to initiate the search in the next larger block size. Once e.g. the 3 × 3 subblock optimum probability is known, the added half frame (e 1 , . . . , e 7 ) should be assigned B(p) entries with p computed from 3 × 3 blocks. With tailored optimization routines one should be able to deal with several thousands of variables in the larger block sizes. All the optimizations here were done with non-specialized code using Mathematica.

The optimal block probabilities satisfy a useful monotonicity property, that we establish next. For this let B i , i = 1, 2 be n × n -blocks, whose subsets of 1's we refer to as B [START_REF] Baxter | Exactly solvable models in statistical mechanics[END_REF] i . There is a partial order on the blocks via B

(1) i using the ordinary set inclusion:

B i ≺ B j if B (1) i ⊂ B (1)
j . Let the optimal probabilities for the blocks be p = (p 0 , p 1 , p 2 , p 3 , . . . , p l ), l = 2 n 2 (no reductions done yet and no particular order in the coordinates). The correlation structure inside the measure of maximal entropy gradually presents itself in the Bernoulli approximations when we consider higher order blocks. Correlations between the blocks are zero because of independence, but within the blocks it is worth making comparisons.

Theorem 3. Given two blocks

By adding the optimum probabilities of all 3 × 3 blocks at a given density level k/9 = 0, 1/9, . . . , 1 we obtain the "density profile" of this measure (here k is the number of 1's in the block).

Suppose next that we generate the 3 × 3 blocks from 1 × 1 Bernoulli entries with the appropriate optimal p for 1's (as found above). By adding these up we again obtain a density profile, this time for the 1 × 1 optimal Bernoulli measure at the resolution level of the block size 3 × 3. The 3 × 3 blocks can of course be generated using the optimal 2 × 2 blocks as well and yet another density profile results. These three discrete plots are rendered as curves in Figure 5. Perhaps the most notable feature here is the flattening of the distributions, as the block size increases i.e. the total block probabilities move towards the tails (while their means stay constant around 0.22). The curves cross between density levels 1/3 -4/9: below this cross over the shorter range Bernoulli measures favor light 3 × 3 blocks, above it they discount heavier blocks in comparison to the optimal 3 × 3 Bernoulli measure.

When examined closer one will see that the total probability of 3 × 3 blocks at a given density level essentially comes from at most three different kinds of local configurations (up to reductions above that is). These seem to be "grown": when moving from density level d to level d + 1/9 the high probability blocks are generated by adding a (contiguous) 1 into an existing high probability block. This mechanism cannot prevail when the 3 × 3 blocks are generated independently from smaller blocks. Consequently the small block curves in Figure 5. have suppressed tails. We expect this phenomenon to prevail in the higher order Bernoulli blocks as well and thereby to be a significant feature in the long range correlations of the measure of maximal entropy.

1 . 1 n

 11 means the cardinality and x| A means the restriction of x to the set A. The standard measure of richness of the configuration set is Definition The topological entropy of the set X 0 is h top X0 = lim n→∞ ln |{x| An | x ∈ X 0 }| where |A n | = n and the sequence {A n } grows in a sufficiently regular fashion.

Fig. 1 :

 1 Fig. 1: Tiling of the triangular lattice with hexagonal 1-tiles and neighborhoods in triangular, Kagomé and Z 2 M cases.

Fig. 2 : 3 -

 23 Fig. 2: 3-hex arrangements in hexagonal and triangular cases.

( 3 )Theorem 2 .

 32 B (p) = -p 0 ln p 0 -3p 1 ln p 1 -3p 2 ln p 2 -p 3 ln p 3 . Let a(p) = p 0 + 2p 1 + p 2 . For the hexagonal lattice the Hard Core entropy is bounded from below by h[START_REF] Van Den Berg | Percolation and the hard-core lattice gas model[END_REF]

2 1 3 h

 23 B (p) where the factors result from the sublattice density and the fact that we distribute triples. As in Proposition 1. in the next stage the maximal entropy choice for the unforced sites on the dot lattice is the B(1/2) distribution. The total density of sites available is computed at two different types of dot sites (as in Fig.2a, the three dots indicated) and is1 3

Fig. 3 :

 3 Fig.3: n × n -blocks and update window in Z 2 case. Reductions in a 3 × 3 -block and the extension.

Fig. 4 :

 4 Fig.4: Prevalent 3 × 3 -blocks with optimal probabilities without multiplicities.

Fig. 5 :

 5 Fig.5: 3 × 3 -block occupation probabilities from Bernoulli blocks of size 3 × 3 (diamond), 2 × 2 (square) and 1 × 1 (star). k ∈ {0, 1, . . . , 9} is the number of 1's in the block.

Table 1 :

 1 First lower bounds for Hard Core topological entropy and the corresponding sublattice densities for some 2-d lattices. To the right we have indicated the best numerical estimates for the entropy and corresponding density (in parenthesis) found in the literature.

	L	max h L	sublattice densities	best estimates
	Z 2	0.3924	(0.1702, 0.2370)	0.4075 (0.2266) [9],[2]
	H	0.4279	(0.2202, 0.2371)	0.4360 (0.2424) [2]
	T	0.3253	(0.1457, 0.1559, 0.1517)	0.3332 (0.1624) [2]
	K	0.3826	(0.1944, 0.1948, 0.1866)
	Z 2 M	0.2858	(0.119, 0.127, 0.130, 0.126)

Table 2 :

 2 Optimized lower bounds and densities for three-hex Bernoulli blocks.

	L	max h L	(p0, p1, p2, p3), q	sublattice densities
	H	0.4304	(0.504, 0.110, 0.048, 0.021)	(0.2276, 0.2376)
	T	0.3265	(0.64, 0.092, 0, 025, 0.010), 0.25	(0.153, 0.155, 0.151)

  1 ln p 1 + 4p 21 ln p 21 + 2p 22 ln p 22 + 4p 3 ln p 3 + p 4 ln p 4

	}
	. (3.4)

Table 3 :

 3 Optimized lower bounds and densities for a Bernoulli blocks on Z 2 .

	block size	max h Z 2	sublattice densities	final/initial variables
	1 × 1	0.392421	(0.1702, 0.2370)	1/1
	2 × 2	0.39877	(0.1993, 0.2254)	5/15
	3 × 3	0.4014	(0.2073, 0.2254)	46/511

  B 1 and B 2 with optimal lower bound probabilities p 1 and p 2 , if B = p 2 , otherwise p 1 > p 2 .Remarks. 1. Intuitively the result says that if neither of two even blocks gives more subsequent choice on the odd lattice, for maximum entropy one should weight them equally. Otherwise one should favor the one giving more choice on the odd lattice. 2. One can readily see some chains imposed by the order in Figure4: 0 ≺ 12 ≺ 23 ≺ 31 or 0 ≺ 11 ≺ 21/22 ≺ 33 etc. The monotonicity can be utilized in limiting the number of n × n -blocks optimized for larger values of n (dropping blocks with least probability as dictated by the Theorem and with least multiplicity (most symmetric)).

	(1) 1 with respect to B (1) ⊂ B 2 (1) 1 0.236 0.0336 0.0238 then p 1 11 then p 1 ≥ p 2 . If B 2 \ B (1) 0.01069 0.00337 0.00597 12 0 21 22 23	(1) 1 31 0.00262 contains only weak sites 0.00479 0.00215 32 33

Acknowledgments

The author would like to thank the referees for valuable suggestions that led to the improvement of the exposition.

Proof. The optimal lower bound is given by h(p) = 1 n 2 {-∑ i p i ln p i + P(N e ) ln 2} where N e is the even 2 × 2 -diamond of all 0's as in Section 2. Let B i be such that B

(1) 1

⊂ B

(1) 2 and let p 1 = p + ϵ, p 2 = p -ϵ, 0 ≤ |ϵ| < p. Denote by h ϵ (p) the lower bound with the given p 1 and p 2 . To prove the result we will consider the entropy variation under the probability change of the two blocks: where P k,ϵ (N e ) and P k (N e ) are the N e -diamond probabilities computed from the different arrangements involving k = 1, 2 or 4 n × n -blocks as in Figures 3a andb, for the block probability choices p ± ϵ or p for both.

By ln (1 + x) ≈ x the first square bracket behaves for small ϵ like

contains only weak sites with respect to B

(1) 1

then the blocks B i allow exactly the same sites to flip on the odd lattice hence each of the three last lines in (3.6) vanishes. The sole contribution to ∆h ϵ (p) then comes from the first square bracket and since this is negative for small but nonzero ϵ, it must be that p 1 = p 2 at the optimum.

If

1 contains non-weak sites with respect to B

(1)

1 let us first assume that they force k odd interior sites (recall that the odd sites are the vertices of the grids in Figure 3. There are (n -1) 2 such interior sites in a n × n -block). Let m be the number non-forced odd interior sites over block B 1 . Then

where the dots refer to the contributions from the other blocks. All these terms cancel out, since the other block probabilities are identical.

If non-weak sites only force odd interior sites then by geometry of the set-up the two last lines in (3.6)


P Ginisty
email: pascal.ginisty@ifts-sls.com

B Legoff

J Olivier
email: jeremy.olivier@univ-pau.fr

J Vaxelaire

H Tabuteau
email: herve.tabuteau@univ-rennes1.fr

J Paixao

Measurement of adhesion strengths and energy between calcium carbonate cake and filter cloth

Keywords: cake discharge; filtration cycle, filter cloth, adhesion strength, shearing, calcium carbonate

Various devices in liquid-solid separation require mechanical cake discharge using different technologies. An incomplete cake discharge causes yield losses, cycle time increase, irregular cake formation, high mechanical constraints which decrease medium life time, excess consumption of cleaning liquors….Currently, cake discharge is only assessed qualitatively by observations of filter cloth after discharge or quantitatively by weighing recovered solids. A prototype has been developed to carry out reliable and repeatable measurements by removing filter cloth from filter cake by shearing. This study presents results of experiments performed with calcium carbonate (which forms sticky cakes) and discusses the conditions of cake formation and cake detachment from filter cloth. It highlights the role of two main parameters : filter cloth characteristics and pressure.

Introduction

In liquid solid separation, cake discharge contributes in the same manner as cake filtration, washing or deliquoring in the process cycle time. Various devices in liquid-solid separation (filter press, belt filter, leaf filter, candle filter, rotary drum filter, Nustche filter, filtering centrifuge…) require a mechanical cake discharge. Different techniques can be used: gravity discharge, vibrations, scraping, traction, shearing, centrifugation, chocks,… This key step is often underestimated in the process cycle time. An incomplete cake discharge causes yield losses, cycle time increase, irregular cake formation, high mechanical constraints. The choice of adapted operating conditions such as filter cloth characteristics, sludge pretreatment, cake thickness, pressure….is necessary to decrease discharge time to a minimum. Industrial feedback shows that cakes which are stuck to filter cloth and difficult to discharge, cause usually important productivity losses and require higher cleaning liquor volumes. Moreover, a poor discharge leads to a decrease of the filter cloth efficiency (which is a key point of filtration success) owing to phenomena as blinding, clogging [START_REF] Weigert | Effect of filter fabric blinding on cake filtration. 7th World Filtration Congress[END_REF].

The parameter which may be associated to cake discharge is the adhesion force (or energy). It represents the mechanical force required to separate particles from a solid surface (Dutschk, 2000). In the field of liquid separation, cake detachment is usually assessed qualitatively by observing the cake fall from a vertical filter cloth and the remaining particles trapped at its surface. Only few researches were carried out to quantify adhesion forces between a filtration cake and a filter cloth and no devices are commercially available to carry out this measurement. Different methods were tested in the eighties to separate cake from filter cloth and to measure the corresponding forces by centrifugation [START_REF] Muller | Adhesive Forces between filter Cloth end Cake[END_REF][START_REF] Salazar-Banda | Determination of the adhesive forcebetween particles and a flat surface, using the centrifuge technique[END_REF] or by shearing [START_REF] Ward | Cake Filtration -The Adhesion of Cake to the Filtercloth[END_REF]. The measurement of cake adhesion has been more specifically studied in other fields like in dust and gas filtration using air jet pulses, or in food products using impulse or centrifugal techniques for cake removal [START_REF] Morris | Adhesion of Cakes to Filter Media[END_REF][START_REF] Tanabe | Experimental investigation of deposition and removal of particles during gas filtration with various fabric filters[END_REF]. In these cases, the measurements were conducted by combination of atomic force microscopy and angle contact measurement angle with a glass surface [START_REF] Handojo | Measurement of adhesion strengths between various milk products on glass surfaces using contact angle measurement and atomic force microscopy[END_REF][START_REF] Shimada | Development of an apparatus for measuring adhesive force between fine particles[END_REF], by probe "Tack tests" for mortars [START_REF] Bouras | Adhesive and rheologlocial properties of fiber reinforced joint mortars[END_REF] or by different standardized methods for adhesives [START_REF] Roche | A study of mechanical and adhesive properties of six structural adhesives. Adhesive and Consolidants for conservation : Research and Applications[END_REF]. These methods remain difficult to apply and other specific techniques have to be developed to assess the magnitude of the adhesion forces between filter cakes and filter clothes.

The study aims at studying the formation and discharge of a calcium carbonate cake from the filter cloth and its detachment from the filter cloth with a prototype recently developed to perform repeatable measurement of the adhesion force and energy between filter cake and filter cloth. The influence of filter cloth characteristics and pressure on cake detachment was studied.

Material and Methods

Cake formation

Cakes were formed by filtration of a 250 g/L calcium carbonate suspension on a filter cloth under pressure applied by a piston in a filtration-compression cell of 70 mm diameter. The calcium carbonate was provided by OMYA supplier (reference : Réf : F38052, d 10 (µm) : 0.7 µm, d 50 (µm) : 2.5 µm, d 90 (µm) : 6.5 µm, d 98 (µm) : 10 µm).

Complementary studies were carried out with a specific transparent cell equipped either a with piece of filter cloth (filtering surface 5x0.6 mm 2 ) or with a circular piece of filter cloth (radius 1.5mm thickness 0.6 mm) to observe the deposit of the first layers of calcium carbonate on the filter cloth.

Cake discharge

A prototype device has been developed to remove the filter cake from the filter cloth by a perpendicular traction, a tangential shearing or a combined traction (in an oblique direction), respectively. In the present study, only the shearing mode was studied according the principle scheme presented in figure 1. The system cake + filter cloth is located in a bracket and fixed on the prototype base. A specific plier grabs the filter cloth to a part of its periphery and removes it form the cake in the horizontal direction with a speed of 2 mm/s. The figure 2 enables us to determine the maximal force and the corresponding shear stress by dividing the force by the contact surface between the cake and the filter cloth required to initiate the detachment. The global energy required to achieve a complete detachment is the product of the force and the corresponding displacement. Further measurements such as the mass of residual solids (retained on the filter cloth) and the loss of permeability (of the filter cloth) were also conducted. Tests were carried out at least 3 times and highlighted a satisfying repeatability with a standard deviation below 10%. .

Results and Discussion

Calcium carbonate cake formation The cake formation was also studied in another configuration (figure 4, left) completely saturated with water, with a greater filtering area (7.1 vs 3 mm 2 ), still fed with a suspension of 33 g/L concentration but with a lower initial pressure (0.1 bar). In this case, the particles settle within the tubing at the beginning of the experiment. As a result a dense suspension pocket is formed very close to the inlet of the cell (figure 4a) and then it flows towards the filter cloth. In the following, this dense pocket clogs the filter. It's worth noting that until the end of the test the concentration of the feeding suspension remains constant, i.e., no other dense suspension pocket is formed anymore. The cake formed on the filter is compacted over time in a linear manner (figure 4, graph on the right) under constant pressure of 0.1 bar. When the height of the cake stops to grow, the applied pressure is increased up to 0.2 bar which leads to slightly steeper compaction rate. Finally, another increase of the pressure, up to 0.4 bar, ends the squeezing process. We get a cake compression of around 400 % from the cake formation up to the end of the test.

These observations are a help for the understanding of the physical mechanisms of the cake formation. For the same cake thickness, the manner the layers of solids are deposited on the filter cloth may contribute to the behavior of the cake during its discharge. Results of filtration-compression tests obtained in a vertical filtration-compression cell with the same filter cloth (REF 1, polypropylene, monofilament/staple, bubble point : 6 µm) at different pressures are presented in table 1. The results highlight that the calcium carbonate cake has a medium specific resistance to filtration and a low compressibility. The increase of pressure between 5 and 10 bar allows a decrease of filtration time and fouling of the filter cloth without any significant change of the cake thickness and dryness.

Discharge of calcium carbonate cakes obtained different pressures

The cakes, obtained at different pressures (table 1), were discharged from the filter cloth (ref 1) with the prototype device (figure 1). Results are presented in table 2. The increase of pressure between 5-8 and 10-13 bar during filtration-compression involved a higher stress to initiate the cake detachment (that means that the cake discharge by gravity may need assistance by mechanical means) but a lower energy to achieve the complete cake discharge. This behaviour can be explained by the fact that the filter cloth contained less solids (and was consequently less clogged). The rupture of bridges between particle layers and filter cloth were more complete and total at 13 bar than at 5 bar. Consequently, the quantity of cleaning liquid might be lower in this situation.

Discharge of calcium carbonate cakes formed at 10 bar from different filter clothes

Series of experiments were carried out for monofilament filter clothes manufactured with different textile material. The other parameters such as the thread diameter, the weaving type and the permeability were similar. Results are presented in table 3. Results show that polyamide material allows an easier cake discharge than polypropylene material even if a higher quantity of solids remains trapped in the filter cloth. The main advantage of special polypropylene comparing to standard propylene was the decrease of the detachment energy and of residual solids (even if a higher shear stress was necessary to initiate cake detachment).

Another series of tests were carried out with two polypropylene monofilament filter clothes woven in the same time with the same thread and with the same bubble point (18 µm). They just differed with regard to their pattern : twill (weft thread passing over or under 2 or more warp yarns) or satin (smooth surface). Results are presented in table 4. Results show that filter cloth with satin surface treatment lead to a lower shear stress to initiate cake detachment comparing to twill filter cloth. This behavior may be due to a lower quantity of solids trapped inside the filtering medium as spacings between points of interlacing are wider.

Conclusions

An experimental method has been developed to quantify the adhesion of filter cakes on filter clothes. Some works are still under progress to improve the reliability and the repeatability of the measurement. The paper presented the influence of two important parameters (pressure and filter cloth properties) which contribute to cake stickiness to the filter cloth and modify its discharge behavior. In order to better understand the interaction between particles and filter cloth, a filtering medium of controlled characteristics will be manufactured by lithography. This work will help to optimize cake discharge time by choosing the most adapted operating conditions for a fast cake discharge in industrial devices. The development of a cake discharge index is foreseen to ease the comparisons between suspensions of different origins and different operating conditions.

Figure 1 :Figure 2 :

 12 Figure 1 : Principle of filter cloth detachment from cake by shearing A typical curve obtained during the measurement is illustrated figure 2.

Figure 3 :

 3 Figure 3: Calcium carbonate cake formation in a horizontal transparent glass cell. The dark scale bar corresponds to 5mm.

Figure 4 :

 4 Figure 4: (left) Calcium carbonate cake formation in a vertical transparent glass cell (inner diameter 3mm). (middle) consecutive images (a to f) of the cake formation. In image a, a dense pocket of suspension flows towards the filter and get into contact with it few seconds later (image b) and delayed the initial time of cake formation. This event corresponds to the highest point in the graph on the right. Evolution of the height of the cake (delimited by the arrow) with time for three consecutive pressure step (100, 200 and 400 mbar).The two red lines correspond to linear fits of the data.

Table 1 :

 1 Results of filtration-compression tests of calcium carbonate (50 g at 250 g/L) at different pressures with filter cloth (ref 1).

	Pressure (bar)	5	8	10	13
	Filtration time (min)	20	13	11	9
	Specific resistance (10 11 m/kg)	5.4	5.7	6	6.4
	Cake thickness (mm)	9	8	8	8
	Cake dryness (%)	80.6	80.6	80.8	81.3
	Ratio of filter cloth
	permeability before and after	0.062	0.112	0.221	0.250
	test (%)

Table 2 :

 2 Results of filter cloth (ref 1) detachment from calcium carbonate cakes formed at different pressures

	Pressure (bar)	5	8	10	13
	Maximal shear stress (Pa)	4025±330	4050±170	4980±440	7050±440
	Detachment energy (J/mm 2 )	28.6±8.96	35.4±6.14	21.0±1.21	14.4±1.87
	Solids loss on filter cloth (%)	1.45±0.12	1.52±0.13	1.00±0.17	1.07±0.18

Table 3 :

 3 Results of carbonate calcium detachment from equivalent filter clothes only differing by the textile material

	Textile material	Polyamide 12	Polypropylene standard	Polypropylene special
	Maximal shear stress (Pa)	2225±140	4338±720	6026±245
	Detachment energy (J/mm 2 )	14.5±0.85	40.6±4.48	30.9±4.79
	Solids loss on filter cloth (%)	0.883±0.061	0.573±0.087	0.293±0.030

Table 4 :

 4 Results of carbonate calcium detachment from equivalent polypropylene filter clothes only differing by the surface treatment

	Surface treatment	Satin	Twill
	Maximal shear stress (Pa)	4957±342	6346±367
	Detachment energy (J/mm 2 )	19.6±2.13	18.2±1.1
	Solids loss on filter cloth (%)	0.320±0.04	0.56±0.06


Marie-Agathe Charpagne

Thomas Billot

Jean-Michel Franchet

Nathalie Bozzolo

HETEROEPITAXIAL RECRYSTALLIZATION, A NEW RECRYSTALLIZATION MECHANISM IN SUB-SOLVUS FORGED -' NICKEL-BASED SUPERALLOYS WITH LOW LATTICE MISMATCH

Keywords: dynamic recrystallization, γ-γ' polycrystalline Nickel base superalloy, inverse precipitation

A new dynamic recrystallization mechanism has recently been reported in -' Nickelbased superalloys after hot-forging in the sub-solvus domain. The mechanism leads to recrystallized grains encompassing a primary ' precipitate having the same crystallographic orientation. The nucleation of those grains actually occurs before deformation by inverse precipitation of coherent  phase at the rim of the primary ' precipitates. This makes the specificity of that recrystallization process. Once the matrix starts being deformed, the coherent  phase particles grow under the conventional stored-energy-consumption driving force. A detailed study of this new mechanism in the René65 TM alloy has recently been published by the authors. Heteroepitaxially recristallized grains grow first, at low strain levels; then discontinuous dynamic recrystallization takes place, through classical necklace nucleation. Contrary to the usual trends for dynamic recrystallization kinetics, heteroepitaxial recrystallization goes faster with increasing strain rate and at lower temperatures. In the present paper, hot-forging experiments have been designed to demonstrate that the same mechanism can be triggered in other -' nickel base superalloys (Udimet 720 and RR1000).

Introduction

Dynamic recrystallization mechanisms and kinetics in polycrystalline Nickel base superalloys have been extensively studied in the past decades, notably because the grain size control is of utmost importance for high-technology hot-forged component made of those materials. Discontinuous recrystallization with nucleation on serrated grain boundaries has been established as the main mechanism governing microstructure evolution during deformation at high temperature [START_REF] Shen | Modeling microstructural development during the forging of Waspaloy[END_REF][START_REF] Medeiros | Microstructural modeling of metadynamic recrystallization in hot working of IN 718 superalloy[END_REF][START_REF] Guo | The effect of deformation temperature on the microstructure evolution of Inconel 625 superalloy[END_REF][START_REF] Mitsche | Assessment of dynamic softening mechanisms in Allvac® 718Plus TM by EBSD analysis[END_REF][START_REF] Lindsley | Sub-solvus recrystallization mechanisms in UDIMET (R) alloy 720LI[END_REF][START_REF] Zhang | Dynamic recrystallization behavior of a γ′-hardened nickelbased superalloy during hot deformation[END_REF][START_REF] Lin | EBSD study of a hot deformed nickel-based superalloy[END_REF]. If the alloy is forged in the γ' sub-solvus domain, primary γ' precipitates interact with grain boundaries of the recrystallized grains and limit their growth by the so-called Smith-Zener pinning phenomenon [START_REF] Ashby | INTERACTION OF CRYSTAL BOUNDARIES WITH SECOND-PHASE PARTICLES[END_REF][START_REF] Smith | Zener pinning[END_REF]. Consequently, the recrystallized grain boundaries typically end on those particles in the recrystallized microstructures. The present authors have recently reported the existence of another recrystallization mechanism referred to as heteroepitaxial recrystallization, which takes place in addition to conventional necklace discontinuous dynamic recrystallization in the René65 TM superalloy. This new mechanism drastically contrasts with conventional ones by its nucleation process [START_REF] Charpagne | Hereroepitaxial recrystallization: a new mechanism simultaneous to conventional discontinuous dynamic recrystallizaton, discovered in a polycristalline γ-γ' nickel-based superalloy[END_REF], its kinetics and its dependence on temperature and strain rate [START_REF] Charpagne | Hereroepitaxial recrystallization: a new mechanism simultaneous to conventional discontinuous dynamic recrystallizaton, discovered in a polycristalline γ-γ' nickel-based superalloy[END_REF][START_REF] Charpagne | Heteroepitaxial recrystallization observed in René 65 and Udimet 720: a new recrystallization mechanism possibly occuring also in other low lattice mismatch γ/γ' Nickel-based superalloys[END_REF]. In the René65 TM alloy, the nucleation of such grains occurs when the material is slowly cooled from high temperature, typically at 5°C per minute. During slow cooling a complete or partial coherent γ shell forms around each γ' precipitate by inverse precipitation (γ'→γ). When such microstructure is further deformed at high temperature, the γ shells grow under the difference in stored energy with the surrounding matrix, and become heteroepitaxially recrystallized grains. This mechanism is the dominant recrystallization mechanism at low strain levels (typically ε<0.6). Since a low lattice mismatch between γ and γ' phases is a necessary condition for the development of such large heteroepitaxial features [START_REF] Charpagne | Evidence of multimicrometric coherent γ' precipitates in a γ-γ' Nickel-based superalloy[END_REF], the possible occurrence of heteroepitaxial recrystallization in other γ-γ' superalloys with low lattice mismatch is investigated in the present article.

Materials and processes

Two industrial γ-γ' superalloys have been selected for this study: Udimet 720 and RR1000 (composition given in Table 1). They both exhibit a low lattice mismatch : 0.02% for RR1000 [START_REF] Grant | The Effect of Lattice Misfit on Deformation Mechanisms at High Temperature[END_REF], or even smaller for Udimet 720 [START_REF] Ricks | The growth of γ′ precipitates in nickel-base superalloys[END_REF]. Both of them initially presented a fine grain size of about 10 µm and contained primary γ' precipitates with a size in the range 1-3 µm. They were first submitted to a sub-solvus annealing treatment aiming at triggering the formation of γ shells around primary γ' precipitates. This treatment consists in a two-hours holding at a temperature T1 and slow cooling down to a temperature T2 at 5°C.min -1 and then air cooling from T2 to room temperature. The temperatures T1 and T2 (given in Table 2) were adjusted relative to the γ'-solvus temperature of each alloy. Following this thermal treatment, cylindrical Udimet 720 samples (6 mm in diameter, 9 mm in height) were deformed by hot-compression up to a height reduction of 2:1 under the following conditions: 1000°C-0.1s -1 ; 1040°C-0.1s -1 and 1040°C-0.01s -1 . All samples were mechanically polished using diamond suspensions down to 1 µm in size and characterized using the coupled EDS-EBSD method described in [START_REF] Charpagne | Evidence of multimicrometric coherent γ' precipitates in a γ-γ' Nickel-based superalloy[END_REF] that allows for separating primary γ' precipitates from the γ matrix . Microstructure was characterized at the center of the deformed samples, where the strain level is the highest.

Results and discussion

1. Annealed samples Fig. 1 presents the microstructure of the annealed RR1000 sample within various imaging modes. The Forward Scattered Electron (FSE) image of Fig. 1-a reveals both topographic and crystallographic contrasts [START_REF] Day | Developments in the EBSP technique and their application to grain imaging[END_REF], and thus allows for highlighting the location of γ' precipitates as they were slightly dug during polishing. 1-b), but a γ grain boundary encircles each precipitate. Fig. 1-c confirms the presence of a γ shell around the precipitates, having the same crystallographic orientation as the precipitate. No significant orientation variation can indeed be revealed either at the γ-γ' interface on the Kernel Average Misorientation (KAM) map of Fig. 1-d. The FSE image of the annealed Udimet 720 sample (Fig. 2) shows similarities with Fig. 1-a. The primary γ' precipitates numbered 1 to 4 are surrounded by a coherent γ shell.

The microstructures of Figs. 1 and2 are actually typical of materials having undergone the inverse precipitation process originally described in [START_REF] Charpagne | Hereroepitaxial recrystallization: a new mechanism simultaneous to conventional discontinuous dynamic recrystallizaton, discovered in a polycristalline γ-γ' nickel-based superalloy[END_REF][START_REF] Charpagne | Heteroepitaxial recrystallization observed in René 65 and Udimet 720: a new recrystallization mechanism possibly occuring also in other low lattice mismatch γ/γ' Nickel-based superalloys[END_REF] for the René65 TM alloy. In order to check whether those coherent γ shells can lead to hetero-epitaxial recrystallization in those alloys as well, three Udimet 720 samples have been deformed in the sub-solvus domain, as presented below.

Udimet 720 samples after hot-compression

An EBSD map of the sample deformed at 1000°C and 0.1s -1 , color coded according to the Grain Orientation Spread (GOS) value, is presented on Fig. 3. The black areas correspond to the primary γ' precipitates, filtered out thanks to the use of EDS combined with EBSD [START_REF] Charpagne | Evidence of multimicrometric coherent γ' precipitates in a γ-γ' Nickel-based superalloy[END_REF]. The dominant population appears in blue color (GOS<1.2°, Fig. 3-c). Those grains have the lowest internal misorientations in the microstructure, i.e. those are the grains with the lowest dislocation content. From this observation, one can conclude that those grains have formed late in the dynamic recrystallization process. A second population with higher internal misorientations is highlighted on Fig. 3-d (1.2° < GOS < 4.2°). Those grains have a shape of rings, or parts of rings, as they embed a primary γ' precipitate. Their higher GOS value suggests that they have formed before the former population of Fig. 3-c and have been subsequently deformed, storing dislocations before deformation ended. Finally, few grains with significantly higher internal misorientations (thus higher dislocation density) also remain in the microstructure (red grains of Figs. 3-a and3-e). Those are matrix grains which were present in the initial microstructure and have not recrystallized yet. By using a double thresholding on the GOS distribution and considering the shape and size of the recrystallized grains, two recrystallized populations could thus be identified, and their apparition relatively to each other in the recrystallization process could be deduced from their average GOS value, indicative for the dislocation content. The nature of those recrystallized populations can be further detailed by analyzing their orientation and location in the microstructure. Fig. 4 presents the deformed microstructure of Fig. 3 within other imaging modes. From the comparison of Fig. 4-a and Fig. 4-b, among the recrystallized grains, those with the highest internal misorientations appear to be heteroepitaxially recrystallized grains. As clearly visible on Fig. 4-a and 4-dc and confirmed on the BackScattered Electron (BSE) image of Fig. 4-d, they embed a primary γ' precipitate having the same crystallographic orientation (see the typical example highlighted on all images). Those grains arise from the coherent γ shell, which has formed during the cooling stage of the annealing treatment performed prior to deformation. On the other hand, the other population of recrystallized grains, small equiaxed grains with low internal misorientations shown of Fig. 3-d, has no specific orientation. It arose from the conventional necklace dynamic recrystallization mechanism.

. In order to check whether the evolution trends of the heteroepitaxially recrystallized grains with temperature and strain rate are similar to those obtained in the René65 TM superalloy [START_REF] Charpagne | Hereroepitaxial recrystallization: a new mechanism simultaneous to conventional discontinuous dynamic recrystallizaton, discovered in a polycristalline γ-γ' nickel-based superalloy[END_REF], the microstructure of two other samples deformed under different conditions was investigated using similar GOS thresholding. Table 3 displays the obtained area fraction and average grain size for all three grain populations depicted in Fig. The recrystallized grain size slightly increases with temperature both types of recrystallized grains (see both samples deformed at 0.1s -1 ). The area fraction of heteroepitaxially recrystallized grains is higher: at 0.1s -1 (the highest strain rate) at 1040°C, and at 1000°C (the lowest temperature) at 0.1s -1 . Those results are fully consistent with the tendencies observed in the René 65 superalloy [START_REF] Charpagne | Hereroepitaxial recrystallization: a new mechanism simultaneous to conventional discontinuous dynamic recrystallizaton, discovered in a polycristalline γ-γ' nickel-based superalloy[END_REF][START_REF] Charpagne | Heteroepitaxial recrystallization observed in René 65 and Udimet 720: a new recrystallization mechanism possibly occuring also in other low lattice mismatch γ/γ' Nickel-based superalloys[END_REF] and can be explained by the balance between two opposite driving forces: first the difference in stored energy which promotes the growth of the heteroepitaxially recrystallized grains against the surrounding matrix ; second, the difference in chemical potential of the γ-gene elements across the γ'-γ interface, which tends to dissolve the γ shells back into the precipitates since the deformation temperature is higher than the temperature at which inverse precipitation occurred during the former cooling stage.

Conclusion

This article demonstrates that heteroepitaxial recrystallization, observed first in René 65 superalloy, also occurs in at least two other superalloys with a low lattice mismatch: RR1000 and Udimet 720. A rough investigation of the deformation conditions promoting hetero-epitaxial recrystallization in Udimet 720 leads to the same conclusions than in the René 65 alloy. This mechanism is intensified at low temperatures and high strain rates, which is opposite to the tendencies of classical discontinuous dynamic recrystallization. Taking this mechanism into account is crucial when aiming at describing accurately the softening processes which take place during forging and the resulting microstructures.

  Fig. 1-b to Fig. 1-d are different plots of the corresponding EBSD map: the trace of the precipitates itself is hardly visible on the Pattern Quality (PQ) map (Fig.

Figure 1 :

 1 Figure 1: Annealed RR1000 superalloy. a) FSE image; b-d) corresponding EBSD maps of the same area (step size: 37 nm): b) PQ map; c) Orientation map within a color code indicating which crystallographic direction is parallel to the normal to the scanned section; d) KAM map (average misorientation angle between each pixel and its first neighbours, excluding disorientations higher than 5°).

Figure 2 :

 2 Figure 2: FSE image of the annealed Udimet 720 sample.

Figure 3 :

 3 Figure 3: Udimet 720 sample after annealing treatment and subsequent deformation at 1000°C and 0.1s -1 , followed by water quenching. a) GOS map of the γ matrix with primary γ' precipitates plotted black, b) GOS distribution histogram, c) grains appeared by discontinuous dynamic recrystallization (GOS<1.2°), d) heteroepitaxially recrystallized grains (1.2°<GOS<4.1°), e) non-recrystallized matrix grains (GOS>4.1°).Grain boundaries (>10°) in black and twin boundaries (60°<111>, with a tolerance of 5°) in red.

Fig. 3 -

 3 Fig.3-a enables to identify three populations of grains, reported on the associated GOS distribution of Fig.3-b, and shown separately on Figs.3-c to 3-e. The dominant population appears in blue color (GOS<1.2°, Fig.3-c). Those grains have the lowest internal misorientations in the microstructure, i.e. those are the grains with the lowest dislocation content. From this observation, one can conclude that those grains have formed late in the dynamic recrystallization process. A second population with higher internal misorientations is highlighted on Fig.3-d(1.2° < GOS < 4.2°). Those grains have a shape of rings, or parts of rings, as they embed a primary γ' precipitate. Their higher GOS value suggests that they have formed before the former population of Fig.3-cand have been subsequently deformed, storing dislocations before deformation ended. Finally, few grains with significantly higher internal misorientations (thus higher dislocation density) also remain in the microstructure (red grains of Figs.3-a and 3-e). Those are matrix grains which were present in the initial microstructure and have not recrystallized yet. By using a double thresholding on the GOS distribution and considering the shape and size of the recrystallized grains, two recrystallized populations could thus be identified, and their apparition relatively to each other in the recrystallization process could be deduced from their average GOS value, indicative for the dislocation content. The nature of those recrystallized populations can be further detailed by analyzing their orientation and location in the microstructure. Fig. 4 presents the deformed microstructure of Fig. 3 within other imaging modes. From the comparison of Fig.4-a and Fig.4-b, among the recrystallized grains, those with the highest internal misorientations appear to be heteroepitaxially recrystallized grains. As clearly visible on Fig.4-a and 4-dc and confirmed on the BackScattered Electron (BSE) image of Fig.4-d, they

Figure 4 :

 4 Figure 4: Same sample as Fig.3. a) GOS map of the γ matrix with primary γ' precipitates plotted black, b) Orientation map within a color code indicating which crystallographic direction is parallel to the normal to the scanned section, c) pattern quality superimposed with EDX-resolved phase map (primary γ' precipitates in blue color), d) BSE image

Table 1 : Nominal composition of RR1000 and Udimet 720 alloys

 1

	Alloy	T1 (°C) T2 (°C)
	Udimet 720	1050	600
	RR1000	1095	745

Table 2 : Temperatures of the annealing treatment for each superalloy

 2

Table 3 : Area fraction f and equivalent circle diameter (µm) of the two types of recrystallized grains and of the non-recrystallized grains in Udimet 720 after annealing and compression under different conditions

 3 3.

		1000°C 0.1s -1	1040°C 0.1s -1	1040°C 0.01s -1
	Classical dynamically recrystallized grains 0.67 -1.0 µm	0.68 -1.3 µm	0.65 -2.3 µm
	Hetero-epitaxially recrystallized grains	0.30 -1.3 µm	0.24 -1.5 µm	0.21 -2.3 µm
	Deformed matrix grains	0.03 -2.1 µm	0.08 -1.9 µm	0.14 -5.0 µm