Ioannis Giotis
email: igiotis@cs.upc.edu

Lefteris Kirousis
email: lkirousis@math.uoa.gr

Kostas I Psaromiligkos
email: kostaspsa@gmail.com

Dimitrios M Thilikos

Acyclic Edge Coloring through the Lovász Local Lemma ✩

Keywords: Acyclic edge coloring, Algorithmic proof of the Lovász Local Lemma 2010 MSC: 05D40, 05C15

We give a probabilistic analysis of a Moser-type algorithm for the Lovász Local Lemma (LLL), adjusted to search for acyclic edge colorings of a graph. We thus improve the best known upper bound to acyclic chromatic index, also obtained by analyzing a similar algorithm, but through the entropic method (basically counting argument). Specifically we show that a graph with maximum degree ∆ has an acyclic proper edge coloring with at most ⌈3.74(∆ -1)⌉ + 1 colors, whereas, previously, the best bound was 4(∆ -1). The main contribution of this work is that it comprises a probabilistic analysis of a Moser-type algorithm applied to events pertaining to dependent variables.

Introduction and the basic algorithm

Let G = (V, E) be a (simple) graph with l vertices and m edges. The chromatic index of G is the least number of colors needed to properly color its edges, i.e., to color them so that no adjacent edges get the same color. If ∆ is the maximum degree of G, it is known that its chromatic index is either ∆ or ∆ + 1 (Vizing [START_REF] Vizing | Critical graphs with a given chromatic class[END_REF]).

A cycle of G of length s is a sequence v i , i = 0, . . . , s-1 of distinct vertices so that ∀i = 0, . . . s -1, v i and v i+1 (mod s) are connected by an edge. The acyclic chromatic index of G (ACI) is defined as the least number of colors needed to properly color the edges of G so that no cycle is bichromatic, i.e., so that there is no cycle whose edges are properly colored with only two colors. Notice that in any properly colored graph, any cycle of odd length is necessarily at least trichromatic, i.e., its edges have three or more colors. It has been conjectured (J. Fiamčik [START_REF] Fiamčik | The acyclic chromatic class of a graph (in Russian)[END_REF] and Alon et al. [START_REF] Alon | Acyclic edge colorings of graphs[END_REF]) that the acyclic chromatic index of any graph with maximum degree ∆ is at most ∆ + 2. A number of successively tighter upper bounds to the acyclic chromatic index have been provided in the literature. Most recently, Esperet and Parreau [START_REF] Esperet | Acyclic edge-coloring using entropy compression[END_REF] proved that the acyclic chromatic index is at most 4(∆ -1). Their proof makes use of the technique of Moser and Tardos [START_REF] Moser | A constructive proof of the general Lovász Local Lemma[END_REF] that constructively proves the Lóvasz Local Lemma (a technique which became known as the "entropy compression method" [START_REF] Tao | Mosers entropy compression argumentAvailable[END_REF]). An approach using the entropy compression method was also used for the vertex analogue of the edge chromatic number by Gonçalves et al. [START_REF] Gonçalves | Entropy compression method applied to graph colorings[END_REF].

In this work, we modify the technique used by Esperet and Parreau [START_REF] Esperet | Acyclic edge-coloring using entropy compression[END_REF] in that for a Moser-type edge coloring algorithm, we use as tool of analysis the approach we described in Section 2 of [START_REF] Giotis | On the algorithmic Lovász local lemma and acyclic edge coloring[END_REF]. Namely, instead of an essentially counting argument as used in the entropy compression method, we give a probabilistic analysis that yields an upper bound of ⌈3.74(∆-1)⌉+1 for the acyclic chromatic index, improving over 4(∆ -1) in [START_REF] Esperet | Acyclic edge-coloring using entropy compression[END_REF] (in contrast to the paper by Moser and Tardos [START_REF] Moser | A constructive proof of the general Lovász Local Lemma[END_REF], a probabilistic analysis was used in the original paper of Moser [START_REF] Moser | A constructive proof of the Lovász Local Lemma[END_REF]; see the elegant exposition by Spencer in [START_REF] Spencer | Robin Moser makes Lovász Local Lemma algorithmic[END_REF]). The present paper can be read independently of [START_REF] Giotis | On the algorithmic Lovász local lemma and acyclic edge coloring[END_REF].

An interesting aspect of this application is that the edge colors to which the "undesirable" events of LLL refer to are not probabilistically independent. This dependence introduces certain conceptual difficulties, some of which are, we believe, non-trivial (see the proof of Lemma 5 and the preceding remarks). The randomized algorithm that we deal with allows the freedom, when coloring an edge, to make a selection, uniformly at random, from a guaranteed minimum number of available colors. However, the "guarantee" of a minimum number of available colors is valid only if any conditioning refers only to colors previously assigned. To handle the probabilistic analysis of such a randomized algorithm without introducing posterior probabilities, which would render the analysis unmanageable, we put all events referring to colors that edges have in chronological order according to the instant these edges got their current color. We consider this approach of handling dependent events in constructive proofs of LLL, rather than just the improvement of the coefficient of the upper bound from 4 to 3.74, as the essential aspect of the contribution of this work (nevertheless, see the discussion in Section 3 for possible further numerical improvement). We also get improved numerical results with respect to graphs with bounded girth, some specific values of which are sampled in Figure 1. Below, to facilitate notation, we call a proper edge-coloring s-acyclic if it contains no bichromatic cycle of length s or less. We call the corresponding graph parameter the s-acyclic chromatic index.

Girth Number of colors Previously known

[4] - 3.731(∆ -1) + 1 4(∆ -1) 7 3.326(∆ -1) + 1 3.737(∆ -1) 53 2.494(∆ -1) + 1 3.135(∆ -1) 219 2.323(∆ -1) + 1 3.043(∆ -1)
We start by mentioning the following fact, proved in Esperet and Parreau [START_REF] Esperet | Acyclic edge-coloring using entropy compression[END_REF]:

Lemma 1 (Esperet and Parreau [START_REF] Esperet | Acyclic edge-coloring using entropy compression[END_REF]). At any step of any successive coloring of the edges of a graph, there are at most 2(∆ -1) colors that should be avoided in order to produce a 4-acyclic coloring.

Proof Sketch. Notice that for each edge e, one has to avoid the colors of all edges adjacent to e, and moreover for each pair of homochromatic (of the same color) edges e 1 , e 2 adjacent to e at different endpoints (which contribute one to the count of colors to be avoided), one has also to avoid the color of the at most one edge e 3 that together with e, e 1 , e 2 define a cycle of length 4. So the total count of colors to be avoided adds up to 2(∆ -1).

Assume now that we have K = ⌈(2 + γ)(∆ -1)⌉ + 1 colors, where γ is a nonnegative constant to be computed.

We assume below that the edges of the graph, and its cycles, are ordered according to fixed a priori orderings.

Notice that for each cycle of the graph there are two consecutive traversals of its edges. It does not matter which we use, but for concreteness when we start the traversal from an edge e, the next edge to be traversed is the least one from the two adjacent to e. We call this traversal "positive".

Also in an even length cycle, the edges can be partitioned into two subsets of equal cardinality, the elements of each of which have pairwise odd distance. These sets are called equal parity sets. If we color such a cycle with two colors so that no adjacent edges get the same color, then the equal parity sets are the monochromatic sets, i.e. the sets whose respective elements get the same color.

Consider now the algorithm given in Figure 2.

Color

1:
Color all edges following their ordering and choosing at each step a color uniformly at random among those that retain 4-acyclicity. 2: while an edge belonging to a bichromatic cycle exists, let e be the least such and let C be the least bichromatic cycle that contains e and do

3:

Recolor(e, C) 4: end while 5: Output current coloring.

Recolor(e, C) 1: Recolor, in their ordering, all edges of C, choosing at each step a color uniformly at random among those that retain 4-acyclicity. 2: while an edge of C belonging to a bichromatic cycle exists, let e ′ be the least such and let C ′ be the least bichromatic cycle that contains e ′ and do

3:

Recolor(e ′ ; C ′ ) 4: end while A root call of Recolor is a call invoked in line 3 of Color. A phase is the collection of steps involved in the execution of a call of Recolor (root or not) or the collection of steps executed in line 1 of Color. The latter phase is called the initial phase (phases are nested). The time complexity of Color is expressed in terms of the number of invocations (root or not) of Recolor, i.e. the number of phases.

Notice that in this algorithm, each non-root invocation of Recolor chooses a cycle sharing an edge with the cycle of the calling Recolor. So this algorithm is in the spirit of the algorithm in the original paper by Moser [START_REF] Moser | A constructive proof of the Lovász Local Lemma[END_REF]; in the subsequent algorithm by Moser and Tardos [START_REF] Moser | A constructive proof of the general Lovász Local Lemma[END_REF], the event chosen at the end of each phase does not necessarily share a variable with the event of the previous phase.

The following follows easily from line 2 of Color.

Lemma 2. Color outputs an acyclic edge coloring if it ever stops.

The main result of this paper, Theorem 2, states that if there are at least 3.74(∆ -1) + 1 available colors, then the probability that Color lasts for at least n phases is < 1 for sufficiently large n (actually, Theorem 2 states that this probability is subexponential), therefore there is an acyclic edge coloring. Lemma 3. Consider an arbitrary call of Recolor(e, C). Let E be the set of edges that do not belong to a bichromatic cycle at the beginning of this call together with the set of edges of C. Then, if the call terminates, the edges in E do not belong to any bichromatic cycle at the end of Recolor(e, C).

Proof. Consider an edge e ′ ∈ E. Assume first that e ′ does not belong to C. Then, if e ′ is in a bichromatic cycle C ′ after the execution of Recolor(e, C), that cycle must have become bichromatic during the execution. Therefore there is a cycle C -and an edge of it e -such that the process Recolor(e -; C -) was called as a recursive call of Recolor(e, C) and C ′ and C -share an edge and C ′ became bichromatic during Recolor(e -; C -). But the call Recolor(e -; C -) will not terminate until all edges in C -do not belong to a bichromatic cycle. Assuming Recolor(e, C) terminates, Recolor(e -; C -) must have also terminated. So C ′ cannot be bichromatic at the end of Recolor(e -; C -). The same argument can be reapplied every time e changes color and becomes an element of a bichromatic cycle during Recolor(e, C).

If, on the other hand, e ′ ∈ C, then by definition e ′ does not belong to any bichromatic cycle at the end of Recolor(e, C).

As an immediate corollary we get:

Corollary 1. The cycles of root calls of Recolor have pairwise distinct sets of edges. Therefore the number of root phases is at most m, the number of edges of the graph.

We define labeled forests to be rooted forests whose nodes are labeled with pairs (e, C), where e is an edge, called the edge-label, and C is an even cycle of half-length ≥ 3 that contains e, called the cycle-label. We consider such labeled forests as ordered by ordering the set of roots and each set of siblings (children of the same parent) according to the order of their respective edge-label. We also define:

Definition 1. A labeled forest is called feasible if i.
Pairwise, the cycle-labels of the roots of the trees do not share an edge, ii. pairwise the cycle-labels of the children of every node do not share an edge, iii. if C is the cycle-label of a node u, the edge-label of any child of u belongs to C.

Feasible forests are intended to represent the structure of recursive calls to Recolor. For technical reasons, we add to a feasible forest some new leaves to which we assign just an edge-label (their cycle-label can be taken to be an empty cycle): First we add new trees comprised of a root only, so that the set of edge-labels of all the roots of the trees of forest becomes equal to the set of edges of the graph; second, we hang from each original leaf v of F as many new leaves as the edges of the cycle-label of v, and we label them so that the set of their edge-labels coincides with the set of edges of the cycle-label of v. So we assume in the sequel that there are exactly m roots whose edge-labels comprise the set of all edges, and that any internal node with a cycle-label C of halflength k has exactly 2k children whose edge-labels comprise the set of all edges in C. Traversing the internal nodes of each tree of a feasible forest in pre-order (depth-first), and visiting the trees in the order of their roots' edge-labels, we obtain the forest's label-sequence L = (e 1 , C 1 ), . . . , (e n , C n ) (labels of leaves are not included in the label-sequence).

Definition 2. The n-witness forest (or just the witness forest, when n is clear from the context) of an execution of Color with at least n phases is the feasible forest that results by creating one node per each of the n invocations of Recolor, labeling it by its argument, and structuring the trees of the forest as the calls of Recolor appear in the recursion stack of each root phase, i.e. a node labeled with (e 2 , C 2 ) is a progeny of a node labeled with (e 1 , C 1 ) if Recolor(e 2 , C 2 ) is called while Recolor(e 1 , C 1 ) is executed (additional leaves as described in the previous paragraph are also added).

A Bound for the Acyclic Chromatic Index

Towards finding an upper bound that Color lasts for at least n phases, we consider the algorithm ColorVal in Figure 3 that takes as input an arbitrary sequence S = (e 1 1 , e 2 1 , k 1 ), . . . , (e 1 n , e 2 n , k n ), such that for all s = 1, . . . , n, e 1 s and e 2 s are adjacent edges contained in some cycle of half-length k s ≥ 3, and appear in this order in the cycle's positive traversal, when we start from e 1 s . We call such sequences admissible sequences. Observe that ColorVal on input an arbitrary admissible sequence S, with |S| = n, always produces as output a uniquely defined sequence of cycles C = C 1 , . . . , C n (but, alas, may end up with success = false). The notion of "phases" for ColorVal is defined in analogy to Color, i.e. phases are comprised of the number of steps that are involved with the execution of line 1 (initial phase) or with the execution of a loop of line 3 of ColorVal (phase s).

ColorVal (S admissible sequence (e 1

s , e 2 s , k s ), s = 1, . . . , n)

1: Color all edges of the graph, following their ordering, choosing at each step uniformly at random a color that retains 4-acyclicity. Recolor all edges of C s , in their ordering, choosing at each step a color uniformly at random among those that retain 4-acyclicity 9: end for Proof. We prove first that the probability P for at least one F ∈ F S being a witness forest of Color is bounded from above by the probability that Color-Val is successful on input S. For this it is sufficient to notice that if the random choices made by an execution of Color that produces an arbitrary F ∈ F S are made by ColorVal on input S F = S, then ColorVal is successful. The result now follows by observing the the events that F is a witness forest of Color for various F ∈ F S are mutually exclusive, therefore P can be written as the sum in the lhs of (1).

Given an admissible sequence S = (e 1 1 , e Call the color an edge has immediately before the s'th repetition of loop 3 the edges's color at phase s. Also call an edge's color at phase 1 the edge's initial color. Given an edge e and a phase number s, let time(s; e) be the latest instant before phase s starts that e was assigned the color it has at phase s, and let χ(s; e) be this color.

Remark 1. Notice that in general it is possible to have two distinct phases s ′ , s and an edge e so that time(s ′ ; e) = time(s; e), because an edge may not be assigned a color for the duration of several phases; however if C s ′ is the cycle produced by an execution of ColorVal at phase s ′ , s ′ < s, and e belongs to C s ′ then time(s ′ ; e) < time(s; e), because the cycles of the output cycle-sequence are recolored at each repetition of loop 3.

Let c 1

s , c 2 s be the colors that the early edges e ), j = 1, 2. Remark 2. To avoid a possible misinterpretation, let us stress here that we do not assume that c 1 s , c 2 s are a priori fixed and that the executions considered are conditioned on the early edges of C s taking the colors c 1 s , c 2 s , respectively. Rather, given an arbitrary execution, c 1 s , c 2 s denote the colors the early edges will have at phase s. Much like the Monty Hall problem [START_REF] Selvin | A problem in probability (letters to the editor)[END_REF], where the assumption that

Monty Hall opens box A does not mean that the choice of the contestant is conditioned on Monty Hall always opening box A. "Box A" is just a "name" for whatever box Monty Hall will open. Its actual value depends on the box selected by the contestant.

Given a phase number s a color c and an edge e (belonging to C s or not), the event of assignment of color c for phase s (CA-event, in short), notationally CA(s, c; e), is the event that occurs if the color assigned to e by ColorVal at instant t = time(s; e) is c. If e belongs to the cycle C s , i.e. if e = e i s for some i, then the CA-event CA(s, c; e) for c = c ((i+1) mod 2)+1 s is called the the correct color assignment event (CCA-event, in short), notationally CCA(C s ; e). In other words, a CCA-event occurs when the edge of its argument takes the color of the corresponding early edge of the cycle of its argument. We refer to the color c ((i+1) mod 2)+1 s for the edge e i s as e i s 's "correct" color for phase s. The chronological order of the edges e i s of a cycle sequence C is the order induced by the ordering of time(s; e i s ) (recall Remark 1).

Definition 3. An anterior conditional for an event CA(s, c; e) is any conjunction of events CA(s ′ , c ′ ; e ′ ), or negations of them, such that time(s ′ ; e ′ ) < time(s; e).

Lemma 4. The probability of any CA-event, not referring to a cycle's early edge and its correct color, given any anterior conditional, is at most

1 γ(∆ -1) + 1 .
Proof. It follows immediately from the fact that ColorVal assigns a color chosen uniformly at random from the set of colors that do not presently destroy 4-acyclicity and that this set, by Lemma 1, has cardinality at least γ(∆ -1) + 1, independently of past assignments (recall that the total number of available colors is K = ⌈(2 + γ)(∆ -1)⌉ + 1).

Remark 3. [Identifying the pivotal edges with their corresponding early edges]

Observe that by definition, the CCA-events corresponding to the early edges of cycles occur with probability 1. To keep the notation simple, we will consider CCA-events CCA(C s ; e i s ) for all i ≥ 3 but with the notational convention that for j = 1, 2, CCA(C s ; e l j s s ) stands for CCA(C s ; e j s ), i.e. the CCA-event of an early edge is, by convention, just the CCA-event of the corresponding pivotal edge.

Lemma 5. Given an admissible sequence S = (e 1

s , e 2 s , k s ), s = 1, . . . , n, then for the probability of success of ColorVal on input S we have that:

Pr [ColorVal is successful on S] ≤ 1 γ(∆ -1) + 1 n n s=1 1 -1 - 1 γ(∆ -1) + 1 ∆-1 2ks-3 . (2)
Proof. Given a cycle-sequence C associated with S, the edges incident on v i s other than e i-1 s are called these edges stemming out v i s . Let these edges in chronological order be o 1 , . . . , o δ i s , where δ i s denotes their cardinality (the o l 's themselves depend on s and i, however for brevity we omit the corresponding indices). Obviously δ i s ≤ ∆ -1, where ∆ is the max degree of the underlying graph G. When e i-1 s is the previous to last edge of C s in its positive traversal, we set δ i s = 1. Also, let the parity of a non-pivotal edge e i s of C s be 1 or 2 depending on whether e i s is at odd distance from e 1 s or e 2 s . Let E 1 C , . . . , E 2 k C denote the CCA-events CCA(C s ; e i s ), 1 ≤ s ≤ n, i = 3, . . . , 2k s of C in chronological order (by Remark 1, we may assume that these events correspond to distinct time instants). Let A t denote the conditional that the chronologically first t -1 CCA-events of C hold (A t depends on the execution).

The geometric order of the edges of C is the one where the edges in each cycle are ordered as they are traversed in its positive traversal, whereas the cycles are ordered by their index (corresponding phase number). Assume that the CCAevent for the k'th such edge (k = 1, . . . , 2 k) in the geometric order is E t k C . In other words, E t k C , t = 1, . . . , 2 k is a reordering, in the sense of the geometric order, of the chronological order E C , t = 1, . . . , 2 k (the reordering depends on the execution).

We now define a random variable, denoted by C, over the random colorchoices of ColorVal. C is the unique cycle-sequence such that for every cycle C s of C, every non-pivotal edge e i s is either the (unique) edge stemming out of v i s that, at the beginning of phase s, has the same color as the pivotal edge of C s of the same parity, if there is such one, or is the first edge stemming out of v i s in some predetermined order of all edges of the underlying graph, otherwise. This is a well defined function over the space of random color-choices of ColorVal because we cannot have two homochromatic edges incident onto the same vertex. It is admittedly somewhat confusing that until now the notation C referred to an arbitrary but fixed cycle-sequence, whereas in the sequel it denotes a random variable depending on the random choices of ColorVal, yet we believe that we thus avoid overloading the notation. Once C is seen as an well-defined random variable, all the parameters defined up to now in terms of a fixed arbitrary C, like e i s (the i-th edge in the positive traversal of the s-th cycle of C), δ i s (the number of edges stemming out of the v i s ), o l (the chronologically l-th edge stemming out of v i s ) etc. become well-defined random variables, depending only on the random choices of ColorVal and its input S. Also the events previously described remain meaningful with C being the random variable defined above instead of arbitrary and fixed. Now, observe that:

Pr [ColorVal is successful on S] = Pr [C is bichromatic] = 2 k t=1 Pr E t C | A t = 2 k k=1 Pr E t k C | A t k . (3)
Indeed, we obviously have that the event "ColorVal is successful on S" is implied by the event "C is bichromatic" (C is said to be bichromatic if for all s, C s is bichromatic at the beginning of phase s). Also because no two homochromatic edges can be incident to the same vertex, we have that the latter event is implied by the former, so we get the first equality of Equation 3. The second equality follows by Remark 3 and the third one is trivial.

In order to find an upper bound for Pr E t k C | A t k , first assume that for some s = 1, . . . , n, i = 3, . . . , 2k s , the event E t k C is the event CCA(C s ; e i s ). For brevity let δ k denote δ i s and c k the correct color for e i s . Let now E l be the event "(e i s = o l ) ∧ CA(s; c k , o l )", l = 1, . . . , δ k . Intuitively, E l means that e i s is the chronologically l'th edge stemming out of v i s and it gets the correct color. In case e i s is a non-pivotal early edge of a cycle C s (i.e. the earliest edge among the same parity edges of C s ), then E l stands for "(e i s = o l ) ∧ CA(s; c k , e)", where e is the pivotal edge e 1 s or e 2 s of the same parity as e i s and c k is e i s 's color (recall Remark 3). We have:

Pr E t k C | A t k = Pr CA(s, c k ; e i s ) | A t k = Pr δ k l=1 E l | A t k , (4)
because always (deterministically) e i s is one of the edges that stem out of v i s . Intuitively, Pr δ k l=1 E l | A t k denotes the probability that one of the edges stemming out of e i s gets the correct color.

Observe that:

Pr

δ k l=1 E l | A t k = 1 -Pr δ k l=1 (¬E l ) | A t k = 1 - δ k l=1 Pr ¬E l | l-1 m=1 ¬E m ∧ A t k . (5)
Intuitively, the expression Pr

δ k l=1 (¬E l ) | A t k
denotes the probability that none of the possible instantiations of e i s (i.e. the edges that stem out of the v i s ) gets the correct color. Now observe that:

(i) for an l's for which e i s = o l , it holds that Pr ¬E l | l m=1 ¬E m ∧ A t k = 1, whereas (ii) for an l for which e i s = o l , it holds that

Pr ¬E l | l-1 m=1 ¬E m ∧ A t k ≥ 1 - 1 γ(∆ -1) + 1 ,
because when e i s = o l , the event E l is equivalent to CA(s, c k ; o l ) and the conditional

l-1 m=1 ¬E m ∧ A t k is equivalent to A t k ,
which is anterior to CA(s, c k ; o l ), because e i s = o l . Therefore for all l, we have that

Pr ¬E l | l-1 m=1 ¬E m ∧ A t k ≥ 1 - 1 γ(∆ -1) + 1 , Therefore: Pr δ k l=1 (¬E l ) | A t k ≥ 1 - 1 γ(∆ -1) + 1 d k ,
where d k = 1 if k corresponds to the last (in the geometric order) edge e i s of C s , and

d k = ∆ -1 otherwise (d k is not random).
Therefore, from ( 4) and ( 5) we get that:

Pr E t k C | A t k ≤ 1 -1 - 1 γ(∆ -1) + 1 d k .
Observe that among the k = 1, . . . , 2 k there are n values of k for which d k = 1 (the k's for which e i s is the closing edge of C s ), whereas for the remaining n s=1 (2k s -3) values of k, we have d k = ∆ -1. So we can conclude from (3) that that Pr [ColorVal is successful on S] is bounded from above by:

1 γ(∆ -1) + 1 n n s=1 1 -1 - 1 γ(∆ -1) + 1 ∆-1 2ks-3 .
Remark 4. The fact that no two homochromatic edges can be incident onto the same vertex is essential for the correctness of the above proof. For example in the case of vertex coloring, where we can have more than one homochromatic vertices neighboring with the same vertex, the proof does not go through. Indeed, even if we define the random variable C to be the unique cycle-sequence such that for every cycle C s of C, every non-pivotal edge e i s is either the first edge stemming out v i s that has the same color as the pivotal edge of C s of the same parity, if there is one, or is the first edge stemming out of v i s , if there is none, still Equation 3 can only take the form:

Pr [ColorVal is successful on S] ≥ Pr [C becomes bichromatic] = 2 k t=1 Pr E t C | A t = 2 k k=1 Pr E t k C | A t k . ( 6
)
Corollary 2. If S is as in Lemma 5 then

Pr [ColorVal is successful on S] ≤ 1 ∆ -1 n n i=1 1 γ 1 -e -1 γ 2ki-3 . (7)
Proof. Use the inequality

1 -x > e -x 1-x , ∀x < 1, x = 0
(see e.g. [12, inequality (4.5.7)]) for x = 1 γ(∆-1)+1 , which implies, after elementary operations, that 1 -

1 γ(∆-1)+1 ∆-1
is at least e -1 γ .

We now turn to the estimation of the probability, call it Pn , that Color lasts for at least n phases.

Theorem 1. The expression P n defined as

P n = n1+•••+nm=n n1,...,nm≥0 Q n1 • • • Q nm , (8)
where Q n is defined by the recursion:

Q n = k≥3 1 γ 1 -e -1 γ 2k-3 • n1+•••+n 2k =n-1 n1,...,n 2k ≥0 Q n1 • • • Q n 2k , (9)
with Q 0 = 1, is an upper bound of Pn .

Proof. Let f be an unlabeled ordered forest with m trees (recall, m is the number of edges of G) and with n internal nodes, each, considered in their pre-order, having an even degree 2k s , s = 1, . . . , n (k s ≥ 3). Let p f be the probability that the witness forest of an execution of Color on G has underlying unlabeled forest f . Obviously Pn =

f p f , (10)
where the sum above ranges over unlabeled forests as described.

With each internal node of f with half-degree k s , we associate weight

1 γ 1 -e -1 γ 2ks-3
, and we associate weight 1 with the leaves of f . We define:

f = n i=1 1 γ 1 -e -1 γ 2ki-3 . ( 11
)
We now prove:

Claim. p f ≤ f .
Proof of Claim. Let L = (e 1 1 , C 1 ), . . . , (e 1 n , C n ) be a sequence which if considered as label-sequence of f leads to an n-witness forest for Color. We will examine what the possibilities for L are and thus bound the probability that at least one such label-sequence, together with f , comprises a witness of Color.

First observe that the lengths of the cycles C s should coincide with the positive degrees 2k s of f , therefore the lengths of the C s of L are uniquely determined. Then observe that the edge-label e 1 1 of L, which is to be assigned to the first r root of f that is not a leaf, is uniquely determined to be the k'th edge of G, where k -1 is the number of leaf-roots that precede r (recall the definition of a witness forest, the way it is defined by Color and the fact that we introduced isolated roots for feasible forests in order to cover all edges of G). There are at most (∆ -1) choices for e 2 1 , the second pivotal edge of C 1 . This introduces a factor of (∆-1) for the sought after upper bound of p f . Once e 1 1 , e 2 1 of L are determined, the event that f , together with such an L, gives a witness for Color necessitates that some C 1 with pivotal edges e 1 1 , e 2 1 and length 2k 1 is bichromatic. For each such possibility for C 1 , the second edge-label e 1 2 of L is determined to be the first edge of C 1 that does not correspond to a leaf of f (recall again the definition of a witness forest, the way it is defined by Color and the fact that we introduced isolated leaves for feasible forests in order to cover all edges of each cycle-label of each internal node). Again there are at most (∆ -1) possibilities for e 2 2 , thus introducing a factor of (∆ -1) to the sought after upper bound. And again, it becomes necessary that some C 2 with with pivotal edges e 1 2 , e 2 2 and length 2k 2 is bichromatic. We continue in this fashion, following the structure of f : when a leaf is reached, we go back to the last internal node (in a depth-first fashion), then the next edge of this internal node's cycle-label should be the next edge-label in L; when a tree of the forest f is exhausted, we go to the next root, then the next edge of G should be the next edge-label L. Now from Proposition 1, which bounds the probability that at least one forest with labels (e 1 s , C s ) s is a witness for Color, and Corollary 2, which bounds the probability that ColorVal is successful on input (e 1 s , e 2 s , k s ) s , and taking into account the n factors (∆ -1), which correspond to the possible choices of e 2 s , we conclude that p f is bounded from above by the product of the weights:

f = n i=1 1 γ 1 -e -1 γ 2ki-3 .
This concludes the proof of the Claim and we now return to the proof of Theorem 1.

Consider unlabeled ordered forests with m ordered trees with n internal nodes in total, whose out-degrees are even and ≥ 6; assign weight w 2k to all internal nodes of out-degree 2k; also assign weight 1 to all leaves and let the weight of such a tree be the product of the weight assigned to all its nodes. Then by distributivity of multiplication over addition it follows that the sum f n of the weights of all such weighted unlabeled ordered forests is given by:

f n = n1+•••+nm=n n1,...,nm≥0 t n1 • • • t nm , (12)
where t n , the sum of the weights of weighted unlabeled ordered rooted trees with n internal nodes, is given by the recurrence:

t n = k≥3 w 2k n1+•••+n 2k =n-1 n1,...,n 2k ≥0 t n1 • • • t n 2k , (13)
with t 0 = 1. By the Claim above we get that:

f p f ≤ f f = f n i=1 1 γ 1 -e -1 γ 2ki-3 . (14)
The required follows from ( 10) and ( 14) making use of the recurrence given by ( 12) and (13).

Asymptotic analysis of the recurrence

We will asymptotically analyze the coefficients of the OGF Q(z) of Q n . Towards this end, multiply both sides of equality (9) by z n and sum for n = 1, . . . , ∞ to get

Q(z) -1 = k≥3 1 γ 1 -e -1 γ 2k-3 zQ(z) 2k , (15)
with Q(0) = 1. Setting W (z) = Q(z) -1 we get

W (z) = k≥3 1 γ 1 -e -1 γ 2k-3 z(W (z) + 1) 2k , (16)
with W (0) = 0. For notational convenience, set W = W (z). Then from (16) we get:

W = z 1 γ • 1 -e -1
to get from (17):

W = zφ(W ). ( 19
)
Let now R =

By [13, Proposition IV.5] (it is trivial to check that the hypotheses in that Theorem are satisfied for γ > 0), we get [z n ]Q ⊲⊳ (1/ρ) n , i.e. lim sup ([z n ]Q) 1/n = 1/ρ (see [START_REF] Flajolet | Analytic Combinatorics[END_REF]IV.3.2]). Now by a simple search (through Maple, for the code see [START_REF] Giotis | Maple code[END_REF]) we found that for γ = 1.73095, the unique positive solution of (20) in the radius of convergence is τ = 0.1747094762, and this value of τ gives 1/ρ = 0.9999789027 < 1. Therefore by making use of (8), we get: Theorem 2. Assuming ∆, the maximum degree of the graph G, is constant, and given the availability of at least 3.74(∆-1)+1 colors, there exists an integer N , which depends linearly on m, the number of edges of G, and a constant ρ > 1 such that if n/ log n ≥ N then the probability that Color executes at least n calls of Recolor is < (1/ρ) n ; therefore the graph has an acyclic edge coloring. Now if the graph has girth 2r -1 for r ≥ 4, the previous arguments carry over with minimal changes. Namely, equation (9) becomes:

Q n = k≥r 1 γ 1 -e -1 γ 2k-3 • n1+•••+n 2k =n-1 n1,...,n 2k ≥0 Q n1 • • • Q n 2k , Q 0 = 1. ( 22
)
Also in [START_REF] Giotis | Acyclic edge coloring through the lovász local lemma[END_REF] and ( 16), the starting point of the summation is changed from 3 to r. Moreover, equation (17) becomes:

W = z 1 γ • 1 -e -1 γ 2r-3 (W + 1) 2r 1 -1 -e -1 γ 2 (W + 1) 2 , ( 23
)
and equation (18) becomes:

φ(x) = 1 γ • 1 -e -1 γ 2r-3 (x + 1) 2r 1 -1 -e -1 γ 2 (x + 1) 2 . ( 24
)
Working as before, we get numerical results depicted in Figure 4 with sample specific values explicitly given in Figure 1.

Discussion

There are several conceivable possibilities for improvement of the ⌈3.74(∆ -1)⌉ + 1 bound. For example, in Color we can recolor not all edges of C s but all but two consecutive of them (because it is only those that determine bichromaticity). Also in Theorem 1, we can conceivably improve the bound provided by claiming that for each execution, there is only one k s so that the cycle C s of half-length k s is bichromatic. Nevertheless we opted not to consider these possible improvements, as our aim was only to present a probabilistic analysis of a Moser-type algorithm with dependent variables.

Figure 1 :

 1 Figure 1: Our results

Figure 2 :

 2 Figure 2: The coloring algorithm

Figure 3 :

 3 Figure 3: The coloring validation algorithm

l 1 s s , e l 2 ss

 12 , respectively, of a cycle C s have at phase s i.e. c j s = χ(s; e l j s s

γ 3 (W + 1) 6 1 - 1 -e -1 γ 2 (W + 1) 2 . 6 1 - 1 -e -1 γ 2 (x + 1) 2 ,

 361226122

- 1

 1 be the radius of convergence of the series representing φ at 0. Let also τ be the (necessarily unique) solution in the interval (0, R) of the characteristic equation (in τ ):φ(τ ) -τ φ ′ (τ )

Figure 4 :

 4 Figure 4: γ as a function of girth

  2: success := true 3: for s = 1, . . . , n do then let C s be the unique such cycle /*the uniqueness is due to the fact that no distinct homochromatic edges can be coincident to the same vertex*/

	4:	if there is a cycle C s that:
		(a) has length 2k s and contains e 1 s , e 2 s in this order in its positive
		traversal,
		(b) is bichromatic under the current coloring
	5:
		first) cycle
		that contains e 1 s , e 2 s in this order in its positive traversal, starting from e 1 s
	7:	end if
	8:

6:

else success := false; let C s be an arbitrary (e.g. the

  2 1 , k 1 ), . . . , (e1 n , e 2 n , k n ), an arbitrary sequence C = C 1 , . . . , C n of cycles such that C s , s = 1, . . . , n, has length 2k s and contains e1 s , e 2 s , in this order in its positive traversal, starting from e 1 s , is called a cycle-sequence associated with the admissible S (a cycle-sequence C associated with S need not necessarily be the cycle-sequence produced by ColorVal).Given a cycle-sequence C = (C s ) s associated with an admissible sequence S = (e1 s , e 2 s , k s ) s , let the other edges of C s in its positive traversal be e 3 s , . . . e 2ks s and let v i s , i = 1, . . . , 2k s , be the vertices of C s with v i s , v i+1 mod 2ks For linguistic convenience, we call the edges e 1 s , e 2 s the first and second pivotal edges of C s , respectively (these are common to all C). Let e ) be the edge of C s that gets the color it has at phase s of ColorVal earliest among the edges of C s that have equal parity with e 1 the early edges of C s .We call instants of an execution of ColorVal the discrete successive values t = 1, 2, . . . of a time parameter at which ColorVal assigns a color to an edge. Reassigning the same color is assumed to take place at a new instant.

	endpoints of e i s . Finally let 2 k =	n s=1 (2k s -2).	s	being the
	call e	l 1 s s , e	l 2 s		l 1 s s (respectively, e s s (e 2 l 2 s s , respectively). We

s

Acknowledgements

We are grateful to Juanjo Rué for showing to us how to deal with the asymptotics of the coefficients of inverse generating functions. We are grateful to Dieter Mitsche on one hand and to Dimitris Achlioptas and Fotis Iliopoulos, on the other, for pointing out errors in previous versions of this paper; the second and fourth authors are also indebted to the latter two for initiating them to this line of research. The contributions of the undergraduate students Rafail Kartsioukas, Georgios Kontogeorgiou, Stavros Messaris and Zoi Terzopoulou at various stages of this work were crucial. We sincerely thank them all. We are also much indebted to Gwenaël Joret for pointing out the incompleteness of the proof of [15, Lemma 5] and for the illuminating for us exchange of messages that followed. John Livieratos' remarks at the last phases of this work were very helpful.

✩ Research co-financed by the European Union (European Social Fund ESF) and Greek national funds through the Operational Program "Education and Lifelong Learning" of the National Strategic Reference Framework (NSRF) Research Funding Program: ARISTEIA II.


Nicolas Lyotard

Woodrow L Shew

Lydéric Bocquet

Jean-François Pinton

Polymer and surface roughness effects on the drag crisis for falling spheres

Keywords: 47, 85, lb Drag reduction -47, 32, Ff Separated flows -47, 63, mc High Reynolds number motions

We make time resolved velocity measurements of steel spheres in free fall through liquid using a continuous ultrasound technique. We explore two different ways to induce large changes in drag on the spheres: 1) a small quantity of viscoelastic polymer added to water and 2) altering the surface of the sphere. Low concentration polymer solutions and/or a pattern of grooves in the sphere surface induce an early drag crisis, which may reduce drag by more than 50 percent compared to smooth spheres in pure water. On the other hand, random surface roughness and/or high concentration polymer solutions reduce drag progressively and suppress the drag crisis. We also present a qualititative argument which ties the drag reduction observed in low concentration polymer solutions to the Weissenberg number and normal stress difference.

Introduction

Reduction of drag in turbulent flows due to a small quantity of viscoelastic polymer added to the fluid has been the subject of intense research for more than 50 years (e.g. [1,2]). For example, the addition of as little as 5 parts per million (ppm) of polyacrylamide to turbulent pipe flow can result in an increase in flow speed of 80 percent for a given imposed pressure drop [START_REF] Toms | Proc. Int. Congress. Rheology[END_REF]. Similar flows with rough or structured wall surfaces have also been shown to exhibit reduction in drag (e.g. [START_REF] Vlachogiannis | [END_REF]5]). Our experiments address drag reduction by similar mechanisms for bluff bodies, which has received far less attention in spite of the potential impact on a broad range of phenomena and applications (aircraft, underwater vehicles and ballistics, predicting hail damage, sports ball aerodynamics, fuel pellets, etc.).

The aim of our work is to explore the influence of polymer additives in the fluid as well as sphere surface structure on the drag experienced by free falling spheres. Before we review the literature on these topics, let us first recall the main characteristics and terminology of high Reynolds number flow around spheres. (Reynolds number is defined as Re = U D/ν where U is sphere speed, D is sphere diameter, and ν is the kinematic viscosity of the fluid.) In the range 10 4 < Re < 10 7 , two basic phenomena are responsible for the most prominent flow features: flow separation and the transition to turbulence in the sphere boundary layer. For 200 < Re < Re * w ≈ 3 × 10 5 flow separation oc-curs. (The w subscript distinguishes the value for smooth spheres in pure water from the different cases discussed later.) In this regime, laminar flow extends from the upstream stagnation point to slightly downstream of the flow separation point, i.e. the turbulence develops downstream from the separation point. In contrast, at Re just above Re * w , the boundary layer becomes turbulent upstream of the flow separation point. The resulting change in the velocity profile abruptly moves the separation point downstream. Since the drag on the sphere is dominated by pressure drag (form drag), this jump in the separation location results in a severe drop in drag, the so-called drag crisis [6,7,8,9]. In this range of Re, friction drag contributes not more than 12 percent to the total drag on a smooth sphere [6]. Although indirectly, our investigation is essentially exploring the effects of polymer additives and sphere surface structure on the dynamics of boundary layer separation and transition to turbulence. We now briefly review studies which directly address these issues. Both Ruszczycky [10] and D. A. White [11] measured drag on a falling sphere in aqueous polymer solutions at Re < Re * w . Ruszczycky studied relatively high concentrations between 2500 and 15000 ppm (by weight) of poly(ethylene oxide) (4 × 10 6 molecular weight (MW)) and guar gum (unknown MW) for a range of sphere sizes from 9.5 to 25.4 mm in diameter. Maximum drag reduction of 28 percent was found for a 25.4 mm sphere in 5000 ppm guar gum solution. For higher concentrations (15000 ppm) the drag was found to increase compared to water, probably because such high concentrations tend to be rather viscous. D. A. White used the same polymer at smaller concentrations with a similar range of sphere sizes and found a 45 percent maximum reduction in drag for a 75 ppm solution. A. White [12] and more recently Watanabe et al. [13] investigated a range of Re spanning the drag crisis. Their work suggests that at polymer concentrations above about 30 ppm, the drag crisis is replaced by a gradual decrease in drag which manifests as drag reduction for Re < Re * w and drag enhancement for supercritical Re > Re * w . This is consistent with the observations of D. A. White and Ruszczycky below the drag crisis, as well as water tunnel measurements with circular cylinders [14]. At smaller polymer concentrations (5 to 10 ppm) the situation is less clear. A. White's measurements show erratic variation of drag as Re is increased, while Watanabe et al. report no change in behavior compared to water. Cylinder studies, in contrast, show a more sharply defined drag crisis at low polymer concentration [14]. One of the goals of our work is to better understand the nature of low concentration polymer effects near the drag crisis.

Concerning free falling rough spheres, to our knowledge, only one experimental work exists in the literature. In this short, qualitative study, A. White explored the combined effects of surface roughness and polymer additives [15]. He found that roughening the sphere surface shifts the wake separation point downstream, reducing drag, but with both a rough surface and polymers added the separation point shifts back upstream, increasing drag. Our observations add to White's intriguing results.

Wind tunnel measurements for both spheres [16] and cylinders [17] indicate that the drag crisis is shifted to lower Re when the surface is roughened. The roughened surface triggers an early transition to turbulence in the boundary layer. Golf balls are made with surface dimples in order to reduce drag by a very similar mechanism [18]. Furthermore, Maxworthy showed that adding a trip on the upstream surface of a smooth sphere induces a turbulent boundary layer and early drag crisis [8]. We are aware of no fixed sphere studies addressing roughness and polymer effects together. We add a note of caution to the reader that fixed (wind tunnel) and free-falling spheres may not behave the same. The first case corresponds to a fixed velocity of the upstream flow, while the second corresponds to a constant force driving the motion. Unlike the fixed sphere, a falling sphere cannot exist in a steady state with Re very close to Re * w ; it is not a stable solution. Furthermore, even at terminal fall speed the wake is never truly steady. It is dynamically active with long-lived non-axisymmetric spatial structure. As a result, the "terminal" fall velocity of a sphere fluctuates in both direction and magnitude, which may lead to small discrepancies in comparing to wind tunnel data or to other free-fall experiments.

This paper is organized as follows. The next section presents the experimental procedures and equipment. In section 3 we present our measurements for the free fall of smooth or roughened spheres in water and in solutions containing small polymer amounts. We discuss our results in terms of changes in drag with varying Reynolds number, polymer concentration and surface conditions. In the last section, we link our results at low polymer concentrations to the effects of a coil-stretch transition [27].

Measurement system and technique

We measure the fall velocity of steel spheres (ball bearings with density ρ = 7.8 g/cm 3 ) with diameters ranging from 3 mm to 80 mm. Two types of sphere surfaces are investigated in addition to the polished smooth surface (see photos in fig. 1). The first type, grooved spheres, have have a regular pattern of grooves machined into the surface. The grooves are 500 µm deep, 1 mm wide. The second type corresponds to roughened surface, produced either by sanding the smooth polished spheres or by gluing onto the surface a single layer beads. In the first case, changes in the surface height are of the order of 10 microns. In the second case, we have used spherical glass beads 700 µm in diameter. The fluid vessel is 2 m tall and 30 × 30 cm in lateral dimension with walls made of 2 cm thick acrylic plate. The tank is filled with either tap water or a dilute aqueous solution of polyacrylamide (MW 5×10 6 , granulated form, Sigma-Aldrich). The polymer solutions range in concentration between 5 and 200 ppm by weight. The polymers are mixed first with 2 liters of water with a magnetic stirrer for at least 8 hours and then mixed with another 180 liters of water for 5 minutes in the experimental vessel. Tests with colored dye in the fluid confirm that this procedure effectively mixes the fluid. These polymer concentrations are in the dilute regime, significantly below the estimated overlap concentration of 1200 ppm. The Weissenberg number W i, defined as the ratio of polymer relaxation time τ R ∼ 10 -4 to flow time scale (see section 4.2 for details), ranges between 0.8 and 2.3.

The spheres are released at the top of the vessel using an electromagnet. The speed of the ball is obtained using a continuous ultrasound technique. This technique is described in more detail in previous publications [20,21], but we briefly describe it here. One ultrasound transducer positioned at the top of the vessel emits sound at 2.8 MHz into the fluid. As the sphere falls it scatters sound at a Doppler shifted frequency which is measured with a second ultrasound transducer located near the emitter. The recorded signal is processed to recover the vertical component of the sphere velocity. The processing entails mixing the recorded signal with a 2.8 MHz sinusoid, low pass filtering, decimating to a lower sample rate, and finally using a parametric time-frequency analysis algorithm (MVA, see ref. [21]) to recover the time varying Doppler shifted frequency. The resulting absolute precision for the velocity measurement is about 2 cm/s with a relative precision in mm/s. With typical fall speeds of several m/s, this is better than 1% precision. At such high Reynolds numbers (10 4 -10 6 ), the flow in the wake contains significant nonaxisymmetric flow structures [7], which often cause some lateral motion of the sphere. We present data only from trajectories that remained at least one sphere diameter away from the vessel walls throughout the fall. Based on studies of tunnel blockage effects for fixed spheres, we expect that walls have less than 5% influence on measured drag coefficients [16]. Furthermore, any wall influence is similar for the different polymer solutions and sphere surfaces allowing for meaningful comparisons between the different cases.

Experimental results

In this section, we present our observations in the form of either drag coefficient estimates or velocity time series. Each presented measurement is the result of averaging over several trajectories under the same conditions. We find that each drop is reproducible up to instantaneous differences of a several percent. We first discuss our measurements of smooth spheres falling in water, which provide a baseline for comparisons to the results from our experiments with polymer solutions and rough spheres. Next, we present measurements of smooth sphere behavior in polymer solutions. Then we explore the consequences of surface grooves or roughness in water. And finally, we address the combined case of altered-surface spheres in polymer solutions.

Water

We show in fig. 2(a) the fall velocity time series for the spheres with diameter D varying between 6 mm and 80 mm. As the spheres are released from rest, they accelerate until a terminal velocity U T is reached -although for the larger spheres the water tank is not sufficiently tall for this steady state to be reached. The dynamics at the onset of motion is quite complex. Added mass effects, as well as wake-induced lift forces and history forces play a role [19,20]. However when the Reynolds number is large the dominant forces at work during the vertical fall of the sphere are the gravitational force F B = 1/6(ρ S -ρ F )πD 3 g and an effective drag force

F D = 1/8C D πρ F D 2 U 2 T
, where C D is the usual drag coefficient; ρ F and ρ S are the fluid and sphere densities. In the steady state, these forces balance and one may then compute the drag coefficient as

C D = 4 3 (ρ S /ρ F -1)Dg U 2 T . (1)
We note here that, unlike wind tunnel experiments, the velocity is not prescribed so that both C D and Re are empirically computed from the data -the equation above may be viewed as an implicit relationship for C D (Re)Re 2 as a function of the control parameters of the experiment. We observe that during the approach to terminal speed, the trajectories for different sphere sizes are fully characterized by one time scale τ and the terminal speed U T . We may extract τ and U T from each velocity time series by fitting the data to an exponential of the form, u(t) = U T (1 -e -t/τ ). In agreement with previous observations [20], the exponential is simply an effective tool used to extract τ and U T and does not accurately represent the more complex dynamics of the true trajectory. When scaled by τ and U T , all the time series in Fig. 2(a) collapse onto one curve, verifying the importance of these two characteristic quantities. Using the exponential fit on the entire time series, we take advantage of our good resolution in both time and velocity magnitude to obtain accurate measurements of U T even though the fall distance is only 2 m. Since this method integrates the whole time record of the fall, it also avoids possible errors incurred by taking single point measurements as has been done in past studies. Furthermore, inspection of the entire velocity time series is often very instructive, clearly revealing the drag crisis in some cases -see for instance the inset of fig. 2(a), where a 60 mm sphere is shown to accelerate again as its Reynolds number exceeds Re * w . We compare in fig. 3 our measurements of drag coefficients for smooth spheres in water to the free fall measurements of A. White [12] as well as the wind tunnel measurements of Achenbach [6]. We find an excellent agreement with White's data. In particular, we find that the critical Reynolds for the drag crisis is Re * w = 2.8 10 5 , a value that serves as a reference for comparison with the fall of spheres with modified surfaces and in water with additives. We also note that both White's data and ours suggest that the value of the drag coefficient just after the drag crisis for the free fall of spheres (imposed force case) is twice that observed in wind tunnel experiments (imposed velocity case).

Polymer solution

We first present velocity time series for a 40 mm sphere falling in a range of polymer concentrations in fig. 4(a). We observe that at all concentrations the sphere terminal velocity is larger than in pure water; drag is reduced. This effect is greatest at small polymer concentrations, as demonstrated in fig. 4(b): drag reductions over 30% have been observed for polymer concentration less than 20 ppm, while at higher concentrations the change is 10-25%. In the 5 and 10 ppm solutions, one observes a sudden acceleration of the sphere once it achieves a velocity of about 2.5 m/s; this is the drag crisis. Examining the data for a range of sphere sizes in the 10 ppm solution (see Fig. 5(a)), we see that the critical Reynolds number is then Re * polymer ∼ 1.0 10 5 , almost a third of the value Re * w ∼ 2.8 10 5 in pure water. On the other hand, at higher polymer concentrations, we do not observe a jump in the velocity time series and their is no discontinuity in the drag C D (Re) curve. One observes that for high polymer concentrations, the drag is reduced at Re < Re * w , but enhanced for Re > Re * : in pure water a drag crisis would have occured and dramatically reduced C D but this does not happen when the polymer concentration exceeds about 100ppm as shown in Fig. 5(b). Instead the value of drag decreases continuously. These observations are consistent with the experiments of previous investigations using poly(ethylene oxide) in a similar range of concentrations [12,13]. We have not been able to reach Reynolds numbers high enough to determine whether the drag would reach a common asymptotic limit.

Rough and grooved surfaces in water

In exploring surface structure effects, we concentrate our attention on 30 and 40 mm spheres, whose Re in pure water lies just below the drag crisis. The time series in fig. 6 illustrate the different behaviors for the different surfaces we studied. In pure water, both the 30 mm grooved sphere and rough sphere behaves the same as the 30 mm smooth sphere -cf. Fig. 6(a). In contrast, adding grooves to the 40 mm sphere induces a drag crisis, as shown in Fig. 6(b). The 40 mm rough sphere showed moderate drag reduction, but not a well defined crisis. Indeed, the dynamics in Fig. 6(c) shows that the terminal velocity is increased compared to the smooth sphere, but there is no clear change in the acceleration as in the case of the grooved sphere, Fig. 6(b).

Grooves are thus able to shift the drag crisis from Re * w ∼ 2.8 10 5 to Re * grooves ∼ 0.8 10 5 . In the case of the 40 mm sphere, the terminal velocity increases from 2.5 m/s to 3.4 m/s, corresponding to a drag reduction of 46%. For the rough sphere, a drag reduction is also observed but it is limited to a 20% gain. This difference in behavior is not yet understood. One may note that a rough surface destabilizes the boundary layer but also increases friction and dissipation. Finally, we have observed that sanded spheres (rugosity of the order of 10 µm) with a diamater of 30 and 40 mm showed no change compared to smooth spheres. This indicates that surfaces modifications must exceed the thickness of the viscous sub-layer in order to produced measurable effects on the dynamics.

Rough and grooved surfaces in polymer solution

We now examine the changes in the above described behavior when polymer is added to the water. We find that the two regimes of low and high concentration -section 3.2 -are affected differently by adding grooves to the sphere surface. Results for the grooved spheres are presented in fig. 7. At low concentration the shift of the drag crisis to lower Re due to polymer is exaggerated by adding grooves to the sphere; Re * w is shifted even lower. Indeed, in a 5 ppm solution, the 30 mm grooved sphere experiences the drag crisis, whereas the same sphere in water as well as the smooth 30 mm sphere in 5 ppm solution do not. We find that the Re * grooved+poly ∼ 6 10 4 , a further gain of 20% compared to polymers alone. The same behavior is observed for the 40 mm grooved sphere at low polymer concentration. At higher polymer concentration, the spheres behave identically with or without grooves.

The rough sphere did not exhibit the same behavior. Rather, the surface roughness seems to suppress the drag crisis, in agreement with the observations of A. White [15]. Our results are presented in Fig. 8, for a 40 mm sphere. When the surface is smooth, one observes as before the shift in the drag crisis and a very large terminal velocity at low polymer concentration (10 ppm), as well as a reduced drag at high concentration (200 ppm). However, for the rough sphere all dynamical v(t) curves are very close. The rough spheres experience no further decrease in drag in the polymer solutions, compared to what is already induced by the surface roughness. In fact, there even may be a slight increase in drag (of the order of 5%) when the rough sphere falls in the water and polymer solution, at any concentration.

Discussion

Experimental summary

We have conducted a series of experiments using precise and time resolved ultrasound velocity measurements to compare the behavior of rough and smooth steel spheres falling through water or dilute aqueous polymer solutions.

Remarkably, we find that in low concentration polymer solutions (5 to 20 ppm) the drag crisis happens at a lower Reynolds number than in water. By adding a pattern of shallow grooves to the sphere surface, we shift the drag crisis to even lower Re. Adding grooves to a sphere in pure water also shifts the drag crisis to lower Re. On the other hand, a sphere roughened with a layer of 700 µm beads glued to its surface never experiences a drag crisis, exhibiting nearly the same drag with or without polymers. The drag on a rough sphere is slightly less than that on a smooth sphere. For higher concentration polymer solutions (100 -200 ppm) and smooth spheres the drag crisis is suppressed and replaced by a more gradual decrease in drag as Re is increased. This high concentration behavior is largely unchanged by adding grooves to the sphere surface.

Our measurements seem to indicate that for low concentrations the polymers are able to induce the transition to turbulence but have little effect on the location of flow separation whether laminar or turbulent. That is, low polymer concentrations induce an early drag crisis, but do not greatly change the drag before and after the crisis, so that we may conclude that the location of the separation points have not been significantly changed. In fact, we have observed that the dynamical behavior v(t) is quite well modelled by a simple shift in the C D (Re) curve, coupled to a simple dynamical equation in which only the drag force is accounted for.

At high concentration and Re < Re * w (i.e. laminar flow separation), drag is reduced, which implies that the separation location is pushed downstream on the sphere surface. On the other hand, for the case of turbulent flow separation (Re > Re * w ), θ s apparently shifts upstream, which manifests as an increase in drag.

Surface roughness is commonly understood to induce an early transition to boundary layer turbulence [8], which may explain the shift in Re * w observed for the grooved sphere. On the other hand, it is difficult to explain in the same context our observation of rather weak drag reduction and apparent suppression of the drag crisis for the rough sphere. Perhaps friction drag is significant in this case. Further investigation of this curious behavior is left for future work.

Drag crisis and normal stress difference

In this section we try to rationalize the effect of the polymers on the observed drag reduction. We follow ideas proposed for drag reduction in pipes [START_REF] Lumley | [END_REF] and much devloped since (see for instance [28]). Specifically, a change of conformation of the polymer is argued to be the source of the modification of the drag crisis.

As discussed above, the drag crisis is the result of the destabilization of the laminar boundary layer [START_REF] Schlichting | Boundary layer theory[END_REF]. At a critical Reynolds number the boundary layer becomes turbulent, shifting the separation line downstream and reducing accordingly the drag on the sphere. The polymer has a priori little effect on the parameters influencing this boundary layer transition, like the viscosity η. Indeed the polymer concentration is smaller than the overlap concentration ξ ⋆ , separating the dilute from the semi-dilute regime [START_REF] Doi | The theory of polymer dynamics[END_REF] -for the polymers under consideration, this is estimated to be ξ ⋆ ≃ 1200 ppm. The shear viscosity of the polymer solutions in water, η P , is related to the polymer density according to η P = η w (1 + 1.49ξ/ξ ⋆ ) with η w the water viscosity [START_REF] Doi | The theory of polymer dynamics[END_REF]. Thus for the low concentrations under consideration here, ξ ≪ ξ ⋆ , the viscosity is close to that of water η ∼ η w .

However this estimate assumes that the polymers' structure is not affected by the flow. Velocity gradients may locally induce a stretching of the polymer, which can be quantified by the Weissenberg number defined as W i = γτ R , with γ a deformation rate and τ R the polymer relaxation time. Typically, for W i < 1 the polymer is in a coil state, while for W i > 1 stetching occurs. Let us estimate W i in our geometry. The relaxation time is typically τ R ∼ η w R 3 g /k B T , with R g the radius of gyration of the polymer, R g ∼ bN νF (b the monomer size and ν F ≃ 3/5 the Flory exponent). For the polymers under investigation, τ R ∼ 10 -4 s. On the other hand the deformation rate is estimated as the shear rate in the boundary layer, i.e. γ ∼ U/δ, with U the sphere velocity and δ ∼ νD/U the typical thickness of the boundary layer (a the diameter of the sphere). This gives

W i ∼ U 3/2 τ R √ νD , (2)
which can be rewritten

W i ∼ Re Re c 3/2 , (3)
with a critical Reynolds number Re c defined as

Re c = D 2 ντ R 2/3 . (4)
At Re c the polymer is thus expected to undergo -within the boundary layer -a coil-stretched transition and the drag will be accordingly be affected (as we discuss hereafter). This point is confirmed experimentally in Fig. 9 where the drag coefficient is plotted versus the reduced Reynolds number Re/Re c : the 'drag-crisis' is always found to occur for Re ∼ Re c for the different cases investigated. While a full rescaling is not expected in this plot, this figure points to the relevance of the Weissenberg number as a key parameter to the polymer induced drag crisis: it does show that the drag crisis transition with polymers, i.e. when the drag coefficient strongly decreases, occurs at a Reynolds number of the order of the critical Reynolds number, Re ∼ Re c . This indicates that the drag crisis criterion with polymers corresponds to W i ∼ 1, as also observed in earlier works.

At this level, the previous discussion suggests that the polymer effect on the drag crisis is associated with a conformation change. The question of the polymer-flow coupling however remains, and in particular the origin of an earlier destabilisation of the boundary layer. First, as the polymers in the boundary layer become stretched, most of the properties of the polymer solution in this region will change dramatically : the typical size of the polymer increases indeed from the radius of gyration to the much larger contour length of the polymer, L ≫ R g . This affects the relaxation time which now becomes τ R ∼ η w L 3 /k B T , and therefore the viscosity which increases typically by a factor (L/R g ) 3 = N 3(1-νF ) ≫ 1. However, increasing the viscosity in the boundary layer amounts to a decrease in the local Reynolds number : this would lead to a re-stabilisation of the laminar boundary layer, an effect which is opposite to the experimental observation.

Another origin has therefore to be found. We suggest that the destabilisation of the boundary layer originates in a very large normal stress difference occuring when the polymer is in its strechted state. Normal stress difference is a non-newtonian effect which is commonly observed in polymeric solutions [START_REF] Doi | The theory of polymer dynamics[END_REF]. This is known to lead for example to the Weissenberg (rod-climbing) effect. In our geometry, the normal stress difference is expected to be proportional to the square of the shear-rate according to ∆σ = σ xx -σ yy = Ψ P γ2 (5) with Ψ P a transport coefficient ; σ xx , σ yy are the normal components of the stress tensor in the x and y directions, with {x, y} local coordinates respectively parallel and perpendicular to the sphere surface (curvature effects are neglected).

Let us show that this term does destabilize the boundary layer. Classically, the boundary layer is destabilized by a negative pressure gradient term due to a decrease of the fluid velocity U e (x) in the outer layer [START_REF] Schlichting | Boundary layer theory[END_REF] : -∇P e = ρU e (x)∇U e (x), with U e (x) the fluid velocity outside the boundary layer. A stability analysis of the boundary layer with such a pressure gradient leads to a destabilization at a reduced Reynolds number [START_REF] Schlichting | Boundary layer theory[END_REF] Re δ = U δ/ν ∼ 600, corresponding to Re ∼ 10 5 . The normal stress difference adds a contribution to this term, leading to an supplementary effective pressure gradient term -∇P eff = ρU e (x)∇U e (x) + Ψ P ∇ γ2 ,

where γ ≃ U e (x)/δ(x) and δ(x) ≃ νx/U e (x) the local thickness of the boundary layer. It is easy to verify that this supplementary contribution to the effective pressure gradient will be negative -and therefore destabilizing -, before the classical contribution ρU e (x)∇U e (x). Moreover in the stretched state -for W i > 1-, one may verify that this contribution is dominant as compared to the classical one. The ratio ∆ between these two terms is of order ∆ ∼ Ψ P γ2 /ρU 2 e . Using Ψ P ∼ η P τ P with η P the polymer contribution to the viscosity and τ P the polymer relaxation time [START_REF] Doi | The theory of polymer dynamics[END_REF], one deduces ∆ ∼ U τ P /D ∼ (L/R g ) 3 / √ Re c (for Re = Re c ). In our case, with Re c ∼ 10 5 , (L/R g ) 3 = N 3(1-νF ) ∼ 2.10 5 (N ≃ 35.10 3 ), one has ∆ ∼ 10 3 ≫ 1. This term thus leads to a strong destabilization as soon as the polymer is stretched.

To summarize, for Re ≥ Re c the coil-stretched transition occurs for the polymer in the boundary layer, and the existence of a normal stress difference induces a strong destabilization of the laminar boundary layer. This scenario gives the trends of the underlying mechanisms leading to a shift of the drag crisis even for very small amounts of polymers. For the polymer additive to have an effect, the critical Reynolds number has to be lower than the critical Reynolds number for the drag crisis in pure water, < Re ⋆ w . This provides a condition in terms of the size of the falling object but also a minimal polymer weight (since τ R ∝ N 3ν ). To go further, a more detailed stability analysis of the boundary layer with the supplementary normal stress difference is needed. We leave this point for further studies.

Fig. 1 .

 1 Fig. 1. SETUP: the vertical velocity of falling steel spheres is measured with an ultrasound device. The fluid is tap water, pure or with small amounts of pomymer additives. Smooth, grooved, and rough spheres are tested.

Fig. 2 .

 2 Fig. 2. WATER & SMOOTH SPHERES: (a) Time series of the spheres vertical velocity u(t) during their free fall. The inset shows the drop -with a non zero initial velocity -of a 60 mm sphere: as its velocity reaches 3.5 m/s it meets the drag crisis. (b) Comparison of the experimental data with a model u(t) = UT (1 -exp(-t/τ )) exponential evolution. The parameters (τ, UT ) are obtained using a multidimensional unconstrained nonlinear minimization (Nelder-Mead) with MAT-LAB. The inset shows the evolution of the characteristic time τ with the Reynolds number. Note the sharp change in behavior near the drag crisis.

Fig. 3 .

 3 Fig.3. DRAG COEFFICIENT measurements for smooth spheres in water. Red Circles -our data; solid circles -Achenbach (wind tunnel)[16].

Fig. 4 .

 4 Fig. 4. POLYMERS : (a) Fall velocity time series of a 40 mm sphere in water, and polymer solutions with concentration increasing from 5 to 200 ppm. In the 5 and 10 ppm solutions the sphere undergoes a drag crisis where none existed for the pure water case. (b) Percentage change of terminal velocity UT for increasing polymer concentration compared to pure water case for 40 mm sphere.

Fig. 5 .

 5 Fig. 5. POLYMERS : Drag coefficient measurements for smooth spheres in water (solid circles) compared to polymer solution (open circles). (a) In 10 ppm solution the drag crisis is shifted to lower Re. (b) In 200 ppm solution the drag crisis is replaced by a gradual decrease in drag.

Fig. 6 .

 6 Fig.6. ROUGH & GROOVED SPHERES: velocity time series for grooved (dashed line) and rough spheres (dahs-dotted line) compared to smooth spheres (solid line) in pure water. The grooved surface induces an early drag crisis.

Fig. 7 .Fig. 8 .

 78 Fig. 7. GROOVED SPHERES & POLYMERS: At low polymer concentration (left column) adding grooves to the sphere induces an even earlier drag crisis compared to the smooth sphere. At high concentration (right column) grooves do not change the observed dynamics.

Fig. 9 .

 9 Fig. 9. Drag coefficient versus the reduced Reynolds number Re/Rec. The different symbols correspond to various concentrations of polymers: (•) 10ppm; (square) 25ppm; (⋄) 50ppm; (△) 100ppm; (▽) 200ppm. Lines are a guide to the eye. For a given polymer concentration, the different experimental points correspond to different size of the falling sphere (from left to right, D = 3, 6, 10, 20, 30, 40, 50, 60mm).

Re ⋆ w : Re c = D 2 ντR 2 / 3

 223


D Wagner

N Roubier

C Prioul

Keywords: Dynamic strain aging, C-Mn steels, Internal friction tests, Tensile tests, Strain rate sensitivity tests

Measurement of sensitivity to dynamic strain aging in C-Mn steels by internal friction experiments

Introduction

Carbon-manganese steels, in the form of pipes, plates and forgings, and associated welds are commonly used for pressurised water reactor secondary systems (feedwater line and steam line). Nevertheless, if they are insufficiently killed, these steels are well known to be sensitive to dynamic strain aging (DSA). This phenomenon, [START_REF] Baird | The inhomogeneity of plastic deformation[END_REF][START_REF] Cuddy | [END_REF][3][START_REF] Strudel | Dislocations et de ´formation plastique[END_REF][START_REF] Neuha | Plastic deformation and fracture of materials[END_REF][START_REF] Estrin | Continuum models for materials with microstructure[END_REF][START_REF] Wagner | [END_REF][8] induces an increase in flow stress, ultimate tensile strength and work hardening coefficient, as well as a decrease in ductility (elongation, reduction of area) and fracture toughness. DSA is due to the presence of solute atoms, which are able to diffuse over short distances and pin mobile dislocations. Therefore, the temperature range (mobility of solute atoms) and the strain rate (dislocation velocity) required to observe these interactions between mobile dislocations and diffusing atoms, are strongly dependent on the composition and thermomechanical treatment of the materials. The physical models 3,[START_REF] Estrin | Continuum models for materials with microstructure[END_REF] usually proposed to interpret the experimental results are based on a discontinuous motion of the dislocations, which are temporarily arrested on localised obstacles. During this waiting time, the solute atoms diffuse to dislocations and increase the strength of these obstacles. Within the DSA range, where the strain rate sensitivity coefficient S~L s L ln :

e becomes negative, well known localised deformation bands [9][START_REF] Rodriguez | Encyclopedia of materials science and engineering[END_REF][START_REF] Mccormick | [END_REF][12] (called Portevin-Le Chatelier bands) occur during the tensile test. On the stress-strain curve, these features produce serrated yielding.

In C-Mn steels, it is well established that the diffusing species are interstitial carbon and nitrogen atoms. Moreover, according to its greater solubility limit [START_REF] Leslie | Encyclopedia of materials science and engineering[END_REF][START_REF] Marschall | [END_REF] nitrogen seems to exert a more pronounced influence on strain aging than carbon does. Depending on the diffusion coefficients, the chemical composition of the steels and the strain rate, the temperature range over which DSA occurs can vary from 200 to 350uC. [START_REF] Wagner | [END_REF]8 This coincidence with the operating temperature range of the secondary lines of pressurised water reactors (PWR), leads to the necessity for a good estimation of the sensitivity to DSA of the in service steels.

To measure the sensitivity to DSA, tensile tests and more accurate strain rate sensitivity tests are needed in the temperature domain where DSA occurs. This means that the sensitivity to DSA can only be characterised through a large number of tests. The internal friction technique allows an evaluation of the balance between carbon and nitrogen atoms free in the lattice and carbon and nitrogen atoms interacting with mobile dislocations. So, it seems interesting to correlate this technique with tensile and strain rate sensitivity tests in order to characterise the sensitivity of a material to DSA (from an engineering point of view) with a unique test.

The objective of this study is to demonstrate the pertinence of this hypothesis with a view to measuring the DSA sensitivity of C-Mn steels with a single test.

Thus, tensile and strain rate sensitivity tests as well as internal friction tests were performed on two C-Mn steels exhibiting large differences in their sensitivity to DSA.

Materials

The materials studied are two C-Mn steels of AFNOR (French standard) NFA 36205 grade A48 and A42, which were received as 40 mm thick plates. The chemical compositions are reported in Table 1. The plates were submitted to a prior normalisation thermal treatment consisting of austenitising at 870uC followed by air cooling, thus leading to a microstructure composed of banded ferrite and pearlite.

The A48 grade material is a silicon semikilled steel containing a very low aluminium content (0 . 004%). This amount is too small to allow full precipitation of nitrogen atoms by aluminium nitride (AlN) formation during cooling from the austenitic region. Consequently, for this heat treatment, a large amount of free nitrogen is still present in the lattice, making this alloy sensitive to DSA. The A42 grade material is a fully killed steel containing a larger aluminium content (0 . 045%) so that almost all the nitrogen atoms are precipitated as aluminium nitrides, thus making this alloy relatively insensitive to DSA.

Experimental techniques Tensile tests

Tensile tests were carried out with a strain rate of 2 . 4610 24 s 21 in the 20-300uC temperature range for the A48 steel or 20-350uC temperature range for the A42 steel. Cylindrical specimens (10 mm diameter) were machined in the quarter thickness longitudinal direction of the plates. Conventional and true stress-strain curves were plotted. The yield strength (s YS ), the ultimate tensile strength (s UTS ), the uniform and total elongation, the reduction of area as well as the work hardening coefficient were determined as functions of temperature.

Strain rate sensitivity tests

Internal friction experiments

Internal friction experiments were performed in the 20-300uC temperature range on an inverted torsion pendulum 15 with an applied strain of 5610 26 and a heating rate of 130 K h -1 . The samples (3 mm diameter, 50 mm gauge length) were also machined in the quarter thickness transverse direction of the plates. This sample geometry leads to a resonant frequency of the apparatus close to 1 . 5 Hz. The internal friction parameter Q -1 was recorded as a function of test temperature.

Results

Tensile tests

On the conventional tensile curves (nominal stress versus elongation DL/L 0 ), the Portevin-Le Chatelier effect (PLC) is clearly exhibited at both 100 and 200uC for the A48 steel, whereas for the A42 steel, no serrations resulting from the PLC effect were visible. The variations of ultimate tensile strength s UTS and total elongation are plotted against temperature on Figs. 1 and 2, respectively, for the two steels. In the temperature range tested, the two steels display ultimate tensile stress maxima associated with elongation minima, but the maximum and the minimum are more pronounced in the A48 steel than in the A42 steel. According to the larger manganese content of the A42 steel, the UTS maximum and elongation minimum are shifted to higher temperature: 250-300uC for the UTS of A42 compared to 200uC for A48, and 200uC for the elongation of A42 compared to 150uC for A48. The interaction existing between manganese atoms and nitrogen (or carbon) atoms [START_REF] Wagner | [END_REF] reduces the mobility of the nitrogen and carbon atoms thus causing the appearance of dynamic strain aging to occur at higher temperatures.

Strain rate sensitivity tests

Figure 3 shows the evolution of the strain rate sensitivity coefficient S versus temperature for the two steels.

According to the tensile tests, for the silicon semikilled A48 steel, S shows a sharp minimum in the temperature range tested, whereas, for the aluminium killed A42 steel, this minimum is less pronounced. As expected, the minimum of S occurs at the same temperature as that observed for elongation (200uC for A42 and 150uC for A48).

Internal friction tests

As shown in Fig. 4, the internal friction spectrum measured on the A48 grade reveals two main peaks in the 20-300uC temperature range (curve 1). The first one, which presents a maximum at about 20uC, can be associated with the Snoek peak (SP) resulting from carbon and nitrogen redistribution between octahedral sites in the ferritic lattice. Due to the complex interactions between nitrogen and manganese previously mentioned, the Snoek peak height is not directly proportional to C and N interstitial content in the lattice, as observed in pure iron. The second peak, observed in the 150 to 250uC temperature range, corresponds to the cold work peak (CWP) and is due 2 Total elongation versus temperature for semi-killed A48 steel and fully killed A42 steel to the interaction between dislocations and interstitials such as carbon and nitrogen. The CWP height is related to both the density of mobile dislocations and the interstitial content in the vicinity of dislocations. This classical interpretation of the internal friction spectrum in steels is confirmed by curve 2 which represents the internal friction variation measured on this A48 grade steel after 8% cold working and one month room temperature aging. In this case, an increase of the CWP with dislocation density is observed, associated with a corresponding SP decrease, in agreement with the classical balance of interstitial atoms between lattice and dislocations. [START_REF]Fast: Me ´taux-Corros[END_REF] The internal friction spectrum measured on the A42 grade (curve 3) reveals no peak (neither SP peak nor CWP peak), in agreement with the very low nitrogen content of the ferritic lattice.

Discussion

In good agreement with their different free nitrogen content (resulting from their different aluminium content), these two carbon-manganese steels are very different regarding their sensitivity to DSA. For the A48 semikilled steel the increase in UTS is 143 MPa and the drop in elongation 14%. For the A42 fully killed steel, these values are 45 MPa and 8%, respectively.

According to these tensile tests, the strain rate sensitivity tests indicate a drop of the strain rate sensitivity coefficient S of about 10 MPa for the A48 and 3 . 5 MPa for the A42 steel.

In the internal friction spectrum, the Snoek peak due to free carbon and nitrogen redistribution between equivalent octahedral sites in the lattice, which appears at 20uC, reveals a more complex shape than in pure iron. As discussed by Koiwa, 17 the SP dissymmetry in these industrial materials results from overlapping of the C peak (located around 39uC in a-Fe 18,19 ) and N peak (around 24-25uC in a-Fe [18][19][20] ) and essentially from the presence of substitutional manganese, which modifies the jump process of nitrogen atoms. [START_REF] Wagner | [END_REF] The cold work peak (also known as the Snoek-Ko ¨ster peak) observed between 150 and 200uC is due to mobility of the interstitial atoms in the dislocations stress field. The exact mechanism of this relaxation is still controversial. 21,22 In the simplest model, the dislocation line pinned between two points, drags solute atoms as it bows out under the oscillating stress. At low temperature, the interstitial atom mobility is not sufficient to follow dislocations, whereas at high temperature, this mobility is too important and, in both cases, no energy dissipation is involved. At intermediate temperatures, dragging of the interstitial atoms by the dislocations is effective and results in the energy loss measured by internal friction.

Room temperature aging and tempering of Fe-C and Fe-C-N have been studied extensively by many authors. [START_REF] Fergusson | Proc. Heat Treatment Conf[END_REF][START_REF] Borrely | [END_REF][25][26][27] From these studies it appears that, after room temperature aging, the interstitial atoms are distributed through various sites:

1. Most of the nitrogen and carbon atoms are clustered in a local enriched zone which, after a sufficient time leads (in Fe-N and Fe-C ferrites) to a0 Fe 16 N 2 or Fe 16 (C,N) 2 carbonitrides precipitation.

2. A noticeable part of the interstitial atoms are trapped in the vicinity of lattice defects such as dislocations.

3. The remaining part of the interstitial atoms are randomly distributed between the octahedral sites of the solid solution. Internal friction results by Fergusson and Jack [START_REF] Fergusson | Proc. Heat Treatment Conf[END_REF] showed that these atoms contribute to the Snoek peak observed in these structures. Therefore, the peak height can give a measure of the nitrogen (and carbon) content in the lattice.

For the A48 semi-killed steel, the nitrogen content near the dislocations or randomly distributed between the octahedral sites of the lattice is important in agreement with the observation of both a Snoek peak and a cold work peak. On the other hand, for the A42 fully killed steel, the internal friction spectrum is flat showing neither Snoek peak nor cold work peak, and the free nitrogen content is very low. Furthermore, the weak DSA observed for the A42 steel, in the absence of any corresponding Snoek peak or cold work peak, can be attributed partly to the insufficient resolution of our internal friction measurements, since only a few ppm of nitrogen atoms are needed to give rise to DSA. 28 Nevertheless, a single internal friction test allows one to estimate the sensitivity of the steel to DSA.This method is very useful when the material is only available in small quantities as in welded metals or heat affected zones. Results (tensile and internal friction tests) on other materials 6 (base metals, deposited weld metals by manual metal arc welding (MMAW) or submerged arc welding (SAW) in as welded or post-weld heat treated (PWHT) condition) have been used to quantify this possible estimation. In pure b.c.c. metals, the Snoek peak height is proportional to C or N atoms in solid solution. Nevertheless, in steels the Snoek peak is more complex, due to overlapping of C and N peaks and also due to nitrogen Snoek peak distortion by nitrogen manganese interaction. [START_REF] Wagner | [END_REF][8][9][START_REF] Rodriguez | Encyclopedia of materials science and engineering[END_REF][START_REF] Mccormick | [END_REF][12][START_REF] Leslie | Encyclopedia of materials science and engineering[END_REF][START_REF] Marschall | [END_REF][15][START_REF]Fast: Me ´taux-Corros[END_REF][17] In this case the deconvolution of the different peaks is doubtful and the quantitative determination of free C and N content in the lattice is not reliable. We have therefore plotted the global Snoek peak height versus two different DSA sensitivity parameters defined from an engineering point of view. The first one, ((DL/L 0 ) 20uC 2(DL/L 0 ) min )/(DL/ L 0 ) 20uC , corresponds to the loss in total elongation over the temperature range tested, relative to the total elongation measured at 20uC. The second one, ((UTS) max 2 (UTS) 20uC )/(UTS) 20uC, corresponds to the relative increase of the ultimate tensile strength. As reported in Figs. 5 and6, a linear relationship can be plotted between the Snoek peak height and these two DSA sensitivity indexes defined above, so a single internal friction test allows estimation of the sensitivity to DSA of the steels. If the cold work peak height is plotted versus these two DSA sensitivity parameters, no correlation can be found. This result shows that it is the diffusion of interstitial solutes randomly distributed between the octahedral sites of the solid solution that is predominantly responsible for the DSA phenomenon. Contrary to a possible intuitive interpretation of DSA in steels, the interstitial atoms that are already interacting with the dislocation stress field, and responsible for the CWP, are not predominantly involved in DSA.

Conclusions

Tensile tests and strain rate sensitivity tests have been performed on two C-Mn steels: a semikilled A48 steel very sensitive to DSA and a fully killed A42 steel, relatively insensitive to DSA.

The internal friction tests have shown good correlation between the internal friction spectrum and the sensitivity to DSA. This sensitivity evaluated by the ductility loss or the UTS increase is proportionnal to Snoek peak height. This important result shows that even in industrial materials a single internal friction test can give a good evaluation of the DSA sensitivity. However, to obtain the temperature range associated with the strain rate range in which DSA occurs, tensile and strain rate sensitivity tests are needed.

  Strain rate sensitivity tests were performed on cylindrical specimens (4 mm diameter). The strain rate sensitivity coefficient

	S~D s DLog	: e
	was determined by changing the strain rate	: e during
	tensile tests at constant temperature and for a given plastic deformation. In this study, the drop in : e (from : e 1 52 . 4610 24 s 21 to : e 2 52 . 4610 23 s 21 ) was always
	carried out at a plastic deformation of 4%. These tests
	were conducted at various temperatures from 20 to 300
	or 350uC.

Table 1

 1

		Chemical composition of A48 and A42 steels,
		wt-% (balance Fe)
	Steel C	N	S	P	Si	Mn Al	O
	A48 0 . 198 0 . 0082 0 . 012 0 . 0104 0 . 207 0 . 769 0 . 004 0 . 0006 A42 0 . 140 0 . 0082 0 . 0057 0 . 016 0 . 225 0 . 989 0 . 045 0 . 0049

Internal friction Q 21 versus temperature for A48 (normalised and cold worked conditions) and A42 steels

Acknowledgments

The financial support of Framatome-ANP and EDF is greatly acknowledged. Thanks are due to MM. Houssin, Faure, Frund and Meyzaud for fruitful discussions and for providing the C-Mn steels for this study.