Slim Ouni

Sara Dahmani

Vincent Colotte

On the quality of an expressive audiovisual corpus: a case study of acted speech

Keywords: expressive audiovisual speech, facial expressions, acted speech, audiovisual perception

In the context of developing an expressive audiovisual speech synthesis system, the quality of the audiovisual corpus from which the 3D visual data will be extracted is important. In this paper, we present a perceptive case study on the quality of the expressiveness of a set of emotions acted by a semi-professional actor. We have analyzed the production of this actor pronouncing a set of sentences with acted emotions, during a human emotion-recognition task. We have observed different modalities: audio, real video, 3D-extracted data, as unimodal presentations and bimodal presentations (with audio). The results of this study show the necessity of such perceptive evaluation prior to further exploitation of the data for the synthesis system. The comparison of the modalities shows clearly what the emotions are, that need to be improved during production and how audio and visual components have a strong mutual influence on emotional perception.

Introduction

Within the framework of developing audiovisual speech synthesis techniques, commonly known as the animation of a 3D virtual talking head synchronously with acoustics, providing an expressive talking head can highly increase the naturalness and the intelligibility of the audiovisual speech. These techniques are based on audiovisual corpus that should convey convincing expressive emotions. For this purpose, we are investigating acted speech, uttered by an actor with different emotions. In fact, as our purpose is not to investigate expressions for recognition neither for perception, characterizing speech in this context is valuable. In fact, the virtual talking head is in the same situation as an actor: making an effort to provide convincing and visible expressions, even though with some exaggeration [START_REF] Ouni | Acoustic and Visual Analysis of Expressive Speech: A Case Study of French Acted Speech[END_REF]. In fact, human expressions are not always visible, and in the majority of cases they are subtle and some human speakers are barely expressive [START_REF] Hess | Why the Same Expression May Not Mean the Same When Shown on Different Faces or Seen by Different People[END_REF].

When developing a talking head, our goal is that expressions are easily perceived by the majority of the users. When recording acted speech, we should make sure that this acting is convincing. For this reason, it is reasonable to perform a perceptual evaluation, where during a human recognition task, the quality of the expressivity of an audiovisual corpus is assessed. Several researches have been conducted to study expressive audiovisual speech mainly from perceptive point of view [START_REF] Vatikiotis-Bateson | Characterizing audiovisual information during speech[END_REF][START_REF] Granstrom | Prosodic cues in multimodal speech perception[END_REF][START_REF] Munhall | Visual prosody and speech intelligibility head movement improves auditory speech perception[END_REF][START_REF] Swerts | Facial expression and prosodic prominence: Effects of modality and facial area[END_REF]. The main addressed topic is the correlation between f0 an eyebrow and head movements [START_REF] Cave | About the relationship between eyebrow movements and fo variations[END_REF][START_REF] Munhall | Visual prosody and speech intelligibility head movement improves auditory speech perception[END_REF][START_REF] Beskow | Visual correlates to prominence in several expressive modes[END_REF]. The main purpose of our study is to show the importance of evaluating how an expressive audiovisual speech is perceived to try to quantify the quality of the expressiveness of the expressive audiovisual speech. We have observed different modalities: audio, real video, 3D-extracted data, as unimodal presentations and bimodal presentations (with audio).

In this paper, we present our recent research where we conducted a case study of a semi-professional actor who uttered a set of sentences for 6 different emotions in addition to neutral speech. We have recorded concurrently audio and motion capture data using a multimodal acquisition platform. This platform allows capturing the movement of reflective markers, electromagnetic sensors and the movement of the eyes without any markers. This platform has been designed to acquire 3D data adapted to expressive audiovisual speech. In the following paragraphs, we present the recorded expressive audiovisual speech corpus, then we present the conducted perceptive evaluation.

Expressive audiovisual speech corpus

Corpus Acquisition

Setup

We have used a multimodal acquisition system composed of a motion-capture system (VICON) using optical reflective markers, an articulograph (AG501) using electromagnetic sensors and a markerless motion capture (RealSense) that allows tracking the movement of the face without markers. The Vicon system is based on 4 Vicon cameras (MX3+) using modified optics for near range. The cameras were placed at approx. 150 cm from the speaker. Vicon Nexus software provides the 3D spatial position of each reflective marker at a sampling rate of 100 Hz. Reflective markers of 3 mm in diameter have been glued on the upper part of the actor face. They are aimed to capture facial expressions. The articulograph (EMA) sensors allow tracking mainly the lip movement. The EMA technique allows capturing finely these gestures at a sampling rate of 250 Hz and handle the occlusion problem, in the case of bilabial pronunciation (even hidden, it is always possible to track the sensors). The RealSense system was used to capture mainly the shape and movement of the eyes. As this system is markerless, it is appropriate for this task.

Figure 1 shows the setup where Vicon markers and EMA sensors are placed on the face, and the RealSense is placed in front of the actor. We have placed 5 extra markers on the top of the head to remove the head movement. Figure 2 presents the layout of the markers, sensors and virtual markers on the face of the actor. The audio was acquired simultaneously with the spatial data using a unidirectional microphone. To synchronize the audio channel and the motion capture channel, we have used an in-house electronic device.It triggers simultaneously an infrared lamp captured by the Vicon system and RealSense, and a high-pitched sound generated by a piezoelectric buzzer for audio captured by the articulograph system. We have developed several tools and algorithmic techniques to process and merge the data accurately.

Material

A semi-professional actor has been asked to utter 10 French sentences for 7 different emotions (neutral, joy, surprise, fear, anger, sadness, and disgust). These sentences were 4 to 5 words in length. The actor has used a technique called exercise in style, where he dissociates the semantics of the syntax of the sentences and acts the same sentences in different styles.

The linguistic content of the sentences does not help to identify the expressed emotion (dissociation between semantics and syntax).

The ten sentences were presented one at a time on the screen in front of the actor who uttered them showing the same consistent emotion. In this context, the emotions should be considered as acted ones as they are a bit exaggerated as in the case of a play at the theater.

Perceptual Evaluation

The main question we are investigating here is whether the actor was able to convey the different expressions correctly the human receivers. This is essential to make a decision about how good is the acquired expressive audiovisual corpus. As the final data will be used to develop an expressive audiovisual speech synthesis. This data is based on 3D points (markers/sensors on the face). For this reason, evaluating this presentation is helpful to see whether a minimal presentation of the face is sufficient to model facial expressivity. Similar evaluation technique has been used in the past to evaluate an audiovisual speech synthesis system [START_REF] Bailly | Evaluation of movement generation systems using the point-light technique[END_REF]. When using the 3D facial data, we usually remove head movement to make audiovisual synthesis process smooth and technically easier to concatenate segments. In this evaluation, we observed whether head movement can help to better communicate emotion.

Material and Participants

For each emotion, 10 sentences have been presented to thirteen participants (adults, 3 females, 10 males). They were asked to identify the emotion expressed by the actor. We studied two modalities : unimodal and bimodal. For the unimodal presentation, we considered the following channels : audio, 3D points without head movement, 3D points with head movement and the real video of the actor face. For the bimodal presentation, we combined the audio with different visual channels. The presentations were organized in 3 successive blocks : (1) unimodal audio, (2) unimodal visual only, and (3) bimodal audiovisual. Within each block the sentences of each emotion were presented randomly. For the visual channels during blocks ( 2) and (3), we presented 3D points without head movement, 3D points with head movement and finally, the video of the actor face. We should notice that we used the 3D points instead of a 3D talking head controlled by these 3D points to avoid any bias that might be introduced during the evaluation because of the quality of the 3D model.

The different stimuli were presented via a web application [START_REF] Ouni | Acoustic-visual synthesis technique using bimodal unit-selection[END_REF] where participants were asked to identify each expressed emotion by selecting the right one from a list of 7 emotions. This web application allows controlling the experiment and it makes several verification, to make sure that the experiment was performed in good conditions.

Results

We have analyzed participant answers of each presentation. The results are summarized in Figure 3, Figure 4 and Figure 5. In each figure, a table presents the average recognition rate for each emotion and each presentation.

Figure 3 presents the actor performance. The first presentation is the video with audio of the actor, the second is the video without audio, and the third is the audio alone. In bimodal presentation, which corresponds to the full information conveyed by the actor to express the different emotions, all the expressions were well recognized (recognition rate higher than 70%). This is reassuring that globally the different expressions were acted correctly. The unimodal presentation of the face is still having relatively good recognition rates, but lower than those of bimodal presentation. This shows that the visual modality (the actor face) provides reasonable good information to decode the expressed emotion. The unimodal auditory presentation result shows that some expressions were not well recognized as sadness (25%), disgust (30.77%), joy (41.35%) We recall that when developing the expressive talking head, we are not going to use the video of the actor directly, but the 3D points corresponding to the markers and sensors on the face of the actor. The purpose of this perceptual evaluation is also to see whether the landmarks are sufficient to express the different emotions. Although this information is minimalist, it can give a preview of the quality of the talking head rendering, as it will be based on this data. Figure 4 shows the results of the recognition rates for the different emotions when we only present the 3D points (as presented in Figure 2). We present two modalities (3D points with audio, 3D points without audio) and with or without head movement. Overall, bimodal presentations have higher recognition rate than unimodal 3D point presentations, except that of sadness, which is expected as in the unimodal auditory presentation, the emotion sadness has the lowest recognition rate. The results of unimodal presentations show that some expressions have very low recognition scores as anger (5.77%), fear (21.15%), disgust (17.31%) and to a lesser extent surprise (40.38%). This shows that the 3D points representing the face are not sufficient to convey these expressions, and that the audio channel is an essential complementary modality to convey emotions. We notice that auditory modality increases well for the emotions joy, fear, disgust and surprise.

The impact of the head movement during audiovisual expressive speech is not clear. In fact, during bimodal 3D point presentation, the head movement has improved the recognition rate of a set of expressions (neutral, anger, sadness) but not the others (surprise, disgust, fear, joy). The highest recognition rate improvement (compared to the presentations without head movement) was that of sadness and anger. During the unimodal 3D point presentation (without audio), the result shows that the head movement improved the recognition rate of some expressions (neutral, surprise, fear and anger) but decreased the recognition rate of joy. We notice that head movement improved the recognition of fear during unimodal 3D points (from 21.15% to 46.15%).

Figure 5 helps to compare each channel as a unimodal presentation. Thus, we present the recognition rate per emotion when during the auditory unimodal presentation, the actor-face unimodal presentation, 3D point unimodal presentation with and without head movement. Across all the unimodal presentations, the actor face presented the highest recognition rate (except that of anger). During the 3D point unimodal presentations, performances are lower than during the actor-face presentation. We also notice that unimodal auditory has better performances than 3D point unimodal presentations (except for joy and sadness).

Discussion

The quality of the recorded corpus can influence the quality of the audiovisual speech synthesis. When dealing with expressive audiovisual speech, it is important to make sure that expressivity is well perceived. The results of our current study show the importance of evaluating the quality of the expressive recorded data at an earlier stage. The first benefit is to see how good is the audiovisual acting of the actor. In this case study, and overall, the result seems to be good and the acting is convincing. When combining audio channel and visual channel, this study show improvement in recognition task scores when the two channels were combined. The audio alone does not seem to convey the right expression all the time. In our study the linguistic content of the sentences does not help participants in the perceptive evaluation to identify the expressed emotion, to avoid any bias. Overall, the bimodal presentations are better than unimodal ones. This confirms the importance of considering expressive audiovisual speech as a bimodal signal [START_REF] Ouni | Acoustic-visual synthesis technique using bimodal unit-selection[END_REF]. Since our earlier work in audiovisual speech synthesis, we consider both channels acoustic and visual together [START_REF] Ouni | Acoustic-visual synthesis technique using bimodal unit-selection[END_REF][START_REF] Toutios | Setup for Acoustic-Visual Speech Synthesis by Concatenating Bimodal Units[END_REF]. This case study seems to confirm that this is still the best way to convey emotions correctly.

The bimodal 3D point presentation with head movement seems to provide good results. However, we cannot confirm that head movement helps in improving expressiveness. When

UNIMODAL PRESENTATIONS

Figure 5: Unimodal presentations -Unimodal auditory, unimodal actor faces, Unimodal 3D points with and without head movement. Table presenting recognition rates for each emotion across the different presentations.

observing Figure 3, we may suggest to the actor improving facial expressions to better perform the emotions with lower recognition rates (for instance, anger and surprise) and to improve voice performance for sadness and disgust emotions, for instance. Each low recognition score should help to identify expressivity-related problem. The problematic expressions will be presented to the actor and a debriefing will be held to make the acting more convincing.

In Figure 5, an emotion presented by 3D points (without audio) that has a low recognition rate when compared with the same emotion during actor-face presentation (without audio) indicates that the 3D points were not sufficient to express that given emotion accurately (for instance, anger, disgust and surprise). This may mean that the layout presented in Figure 2 should be improved or modified to better capture facial expressions. We should not forget that the 3D point presentation is an important simplification of the facial information. However, this simplification should allow capturing the important expressive facial features. Currently, we are continuing investigating the results of the analysis. In particular, we are considering studying the confusion of a given expression with another one, and what that can tell us about the expression itself. We also intend to study whether there is a correlation between perceptual results of the experiment and anatomical analysis of the actor face.

Figure 1 :

 1 Figure 1: The positions of the reflective markers, EMA sensors, and RealSense, relatively to the face of the actor.

Figure 2 :

 2 Figure 2: The layout of the markers on the face of the actor.

  Actor performance -3 presentations: Bimodal actor face, unimodal actor face, and unimodal auditory. Table presenting recognition rates for each emotion across the different presentations.

						MOD ALITIES
						ACTOR
	100
		80
	RECOGNITION RATE (%)	40 60
		20
		0	Joy	Sadness	Anger	Fear	Disgust	Surprise	Neutral
	Bimodal Face		97.12	83.65	70.19	92.31	89.42	75	99.04
	Unimodal Face		86.54	72.12	55.77	66.35	72.12	61.54	91.35
	Unimodal Auditory	41.35	25.96	75.96	50.96	30.77	63.46	75.96
	Figure 3: and fear (50.96%). Anger (75.96%) and neutral (75.96%) have
	the highest recognition rate in this presentation. Moreover,
	the recognition rate of anger in unimodal auditory is higher
	than that in unimodal face (55.77%) and even in bimodal face

presentation.This indicates that the actor makes more emphasis on audio to convey anger and less on the face.

  3D point presentations -bimodal 3D points with and without head movement, unimodal 3D points with and without head movement. Table presenting recognition rates for each emotion across the different presentations.

				MOD ALITIES -H EAD MOVEMENT
		100			3D POINTS
		80
	RECOGNITION RATE (%)	40 60
		20
		0	Joy	Sadness	Anger	Fear	Disgust	Surprise	Neutral
	Bimodal w/ head mvt	76.92	75	63.46	71.15	39.42	68.27	92.31
	Bimodal w/o head mvt	84.62	58.65	40.38	75	47.12	77.88	88.46
	Unimodal w/ head mvt	49.04	68.27	14.42	46.15	17.31	46.15	77.88
	Unimodal w/o head mvt	75	69.23	5.77	21.15	17.31	40.38	62.5
	0 20 80 100 Figure 4: Joy 40 60 RECOGNITION RATE (%)	Sadness	Anger	Fear	Disgust	Surprise	Neutral
	Audio		41.35	25.96	75.96	50.96	30.77	63.46	75.96
	Actor-face		86.54	72.12	55.77	66.35	72.12	61.54	91.35
	3D points w/ head mvt	49.04	68.27	14.42	46.15	17.31	46.15	77.88
	3D points w/o head mvt	75	69.23	5.77	21.15	17.31	40.38	62.5

Acknowledgements

This work was supported by Region Lorraine (COREXP Project) and the EQUIPEX Ortolang. We also thank Florian Sietzen for his participation in this work.


Ali Akhavi

C Éline

Moreira Dos
email: cmoreira@math.unicaen.fr

A REWRITE BASED ANALYSIS OF ALGORITHMS

 to the case of the usual Gaussian algorithm. An interesting (but not easy) future application will be lattice reduction in higher dimensions, in order to exhibit a tight upper-bound for the number of iterations of LLL-like reduction algorithms in the worst case. Sorting ordered finite sets are here as a nice esay example to illustrate the purpose of our method. We propose several rewrite systems in the group S of permutations and canonically identify a sorting algorithm with a rewrite system over S. This brings us to exhibit worst-cases of several sorting algorithms.

Introduction

A Euclidean lattice is the set of all integer linear combinations of a set of linearly independent vectors in R p . The independent vectors are called a basis of the lattice. Any lattice can be generated by many bases. All of them have the same cardinality, that is called the dimension of the lattice. If B and B ′ represent matrices of two bases of the same lattice in the canonical basis of R p , then there is a unimodular matrix U such that B ′ = U B. A unimodular matrix is a matrix with integer entries and with determinant equal to ±1. The lattice basis reduction problem is to find bases with good Euclidean properties, that is, with sufficiently short vectors and almost orthogonal.

In two dimensions, the problem is solved by the Gaussian algorithm, that finds in any two-dimensional lattice, a basis formed with the shortest possible vectors. The worst-case complexity of Gauss' algorithm (explained originally in the vocabulary of quadratic forms) was first studied by Lagarias [START_REF] Lagarias | Worst-case complexity bounds for algorithms in the theory of integral quadratic forms[END_REF], who showed that the algorithm is polynomial with respect to its input. The worst-case complexity of Gauss' algorithm was also studied later more precisely by Vallée [START_REF] Vallée | Gauss' algorithm revisited[END_REF].

In 1982, Lenstra, Lenstra and Lovász [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF] gave a powerful approximation reduction algorithm for lattices of arbitrary dimension. Their famous algorithm, called LLL, was an important breakthrough to numerous theoretical and practical problems in computational number theory and cryptography: factoring polynomials with rational coefficients [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF], finding linear Diophantine approximations [START_REF] Lagarias | The computational complexity of simultaneous D iophantine approximation problems[END_REF], breaking various cryptosystems [START_REF] Joux | Lattice reduction: A toolbox for the cryptanalyst[END_REF] and integer linear programming [START_REF] Kannan | Improved algorithm for integer programming and related lattice problems[END_REF][START_REF] Lenstra | Integer programming with a fixed number of variables[END_REF]. The LLL algorithm is a possible generalization of its 2-dimensional version, which is the Gaussian algorithm. The LLL algorithm seems difficult to analyze precisely, both in the worst-case [START_REF] Akhavi | Worst-case complexity of the optimal LLL algorithm[END_REF][START_REF] Lenstra | Flags and lattice basis reduction[END_REF][START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF] and in averagecase [START_REF] Daudé | An average-case analysis of the Gaussian algorithm for lattice reduction[END_REF][START_REF] Daudé | An upper bound on the average number of iterations of the LLL algorithm[END_REF]. In particular when the dimension is higher than two, the problem of the real worst-case of the algorithm is completely open. However, LLL-like reduction algorithms are so widely used in practice that the analyzes are a real challenge, both from a theoretical and practical point of view. The purpose of our paper is a new approach to the worst--case analyze of LLL-like lattice reduction algorithms. For the moment this approach is presented only in two dimensions. We have to observe here that the worst case of some variant of the Gaussian algorithm is already known [START_REF] Vallée | Gauss' algorithm revisited[END_REF]. Even if our paper generalize this knowledge to the case of the usual Gaussian algorithm, we do not consider it as the most important point of this paper. Our aim here is to present this new approach.

An LLL-like lattice reduction algorithm uses some (finite) elementary transforms. We consider the group generated by these basic transforms. Then we exhibit a family of rewriting rules over this group, corresponding to the mechanism of the algorithm. The rewriting rules make some forbidden sequences and the length of a valid word over the set of generators becomes very close to the number of steps of the algorithm. This makes appear the smallest length of input demanding a given number of iterations to the reduction algorithm. From a combinatorial point of view, the group of n-dimensional lattice transformations GL n (Z), i.e. the multiplicative group of n × n matrices with determinant ±1, is the group of automorphisms of the free Abelian group on n free generators 1 . Here we are concerned by GL 2 (Z), which is is well-known and whose presentation in terms of generators and relators is known since the nineteenth century. In this paper we present a rewriting system over GL 2 (Z), that makes us predict how the Gaussian algorithm is running on an arbitrary input. We deduce from this the worst-case configuration of the usual Gaussian algorithm and give an "optimal" maximum for the number of steps of the Gaussian algorithm. Our result generalizes the result of Vallée [START_REF] Vallée | Gauss' algorithm revisited[END_REF]. She studied a variant of the Gaussian algorithm where elementary transforms made by the algorithm are some integer matrices of determinant equal to 1. In the case of the usual Gaussian algorithm, elementary transforms are integer matrices of determinant either 1 or -1.

Il the following we briefly outline the two steps of our method.

1.1. First step. Consider a deterministic algorithm A that run on an input x (the data x is a set X of data). Then by mean of elementary transforms taken in a set F ⊂ X X , the algorithm changes the input step by step (x → f (x) until the modified data satisfies some output condition (x ∈ O ⊂ X. An elementary or atomic transform is a transform that cannot be decomposed by the algorithm:

(1.1) ∀f ∈ F, ∀k ∈ N, k > 1, ∀(f 1 , . . . , f k ) ∈ (F \{id}) k , f = k i=1 f i
This is of course a very general context containing both iterative and recursive algorithms.

Algorithm A : Input: x ∈ X. Output: y ∈ O. Initialization: i := 1; While x / ∈ O do Determine an adequate function f ∈ F by a computation on x and eventually on i.

x:=f(x) i:=i+1 The algorithm A is deterministic. We suppose that the determination of the adequate function f ∈ F at a moment i (which may depend on the history of the execution) has a cost that can be added without ambiguity to the cost of the function f . Considering F as an alphabet, the set F * of finite words on F is then the monoid generated by the set of free generators F . F * contain all (finite) executions of the algorithm. Now fix a sequence of transforms (f

1 , f 2 , . . . , f k ) ∈ F k .
Is the sequence (f 1 , f 2 , . . . , f k ) ∈ F k a possible execution for the algorithm? More precisely, is there (x, y) ∈ X × Y such that the algorithm A outputs y when running on an input x and following the exact sequence of transforms (f 1 , f 2 , . . . , f k )?

Answering this question in such a general context is very difficult and the general problem (formulated more precisely) is likely undecidable. However the answer in restricted class of algorithms bring indeed a strong understanding of the mechanism of the algorithm and we believe that it is interesting by its own with lots of possible applications in program verifying, or program designing.

In this paper, we propose a method to answer this question in the case of Gaussian algorthm and three sorting algorithms. A set (finite in the case of our examples) of rewriting systems encode all possible executions of a given algorithm. All possible executions will be the normal forms (or reduced forms) of these rewriting systems.

1 By the free Abelian group, we mean that the only non trivial relators (i.e. the additional relators compared to the free group) are the commutators.

1.2. second step. Usually when counting the number of steps of an algorithm, one considers all inputs of length less than a fixed bound, say M . Then one estimates the maximum number of steps taken over all these inputs by:

(1.2) f (M ) := max all inputs of length less than M number of steps of the algorithm.

2

Here to exhibit the precise real worst-case, we first proceed in "the opposite way". Consider k a fixed number of steps. We will estimate the minimum length of those inputs demanding at least k steps to be processed by the algorithm:

(1.3) g(k) := min all inputs demanding at least k steps length of the input.

Clearly f (g(k)) = k. Otherwise there would be an input of length less than g(k) demanding more than k steps. But g(k) is by definition the minimal length of such inputs. So by inverting the fuction g , we can compute f .

2. Gaussian algorithm and the new approach to its worst-case analysis Endow R2 with the usual scalar product (, ) and Euclidean length |u| = (u, u) 1/2 . A two-dimensional lattice is a discrete additive subgroup of R 2 . Equivalently, it is the set of all integer linear combinations of two linearly independent vectors. Generally it is given by one of its bases (b 1 , b 2 ). Let (e 1 , e 2 ) be the canonical basis of R 2 . We often associate to a lattice basis (b 1 , b 2 ) a matrix B, such that the vectors of the basis are the rows of the matrix:

(2.1) B = e 1 e 2 b 1 b 1,1 b 1,2 b 2 b 2,1 b 2,2
.

The length L of the previous basis (or the length of the matrix B) is defined here to be the maximum of 2 ) and a lower-triangular matrix M that expresses the system b into the system b *3 . Put m = (b2,b1) (b1,b1) . By construction, the following equalities hold:

(|b 1 |, |b 2
(2.2) b * 1 = b 1 b * 2 = b 2 -m b 1 , M = b * 1 b * 2 b 1 1 0 b 2 m 1 . The ordered basis B = (b 1 , b 2 ) is called proper if the quantity m satisfies (2.3) -1/2 ≤ m < 1/2.
There is a natural and unique representative of all the bases of given two-dimensional lattice. This basis is composed of two shortest vectors generating the whole lattice. It is called the Gauss-reduced basis and the Gaussian algorithm outputs this reduced basis running on any basis of the lattice. Any lattice basis in two dimensions can always be expressed as

(2.4) B = U R,
where R is the so-called Gaussian reduced basis of the same lattice and U is a unimodular matrix, i.e. an element of GL 2 (Z). The goal of a reduction algorithm, the Gaussian algorithm in two dimensions, is to find R given B. The Gaussian algorithm is using two kinds of elementary transforms, explained in the sequel of this paper. The Gaussian algorithm can also be regarded (especially for the analysis purposes) as an algorithm that gives a decomposition of the unimodular matrix U of relation (2.4) by means of some basic transforms:

(2.5) Input:

B = U R. Output: R = T x k+1 ST x k ST x k-1 . . . ST x2 ST x1 B;
where

(2.6) S = 0 1 1 0 and T = 1 0 1 1 .
The matrix T corresponds to an integer translation of b 2 in the direction of b 1 by one. Of course, we have:

T x = x i=1
and T = 1 0

x 1 , for all x ∈ Z.

The matrix S represents a swap. Each step of the algorithm is indeed an integer translation followed by a swap 4 . So each step of the Gaussian algorithm is represented by ST x , x ∈ Z * . Writing the output in this way (2.5) shows not only the output but how precisely the algorithm is working since T and S represent the only elementary transforms made during the execution of the Gaussian algorithm. So when studying the mechanism of a reduction algorithm in two dimensions and for a fixed reduced basis R, the algorithm can be regarded as a decomposition algorithm over GL 2 (Z):

(2.7) Input:

U ∈ GL 2 (Z). Output: a decomposition of U , U := T x k+1 ST x k ST x k-1 . . . ST x2 ST x1 .
The integer k denotes the number of steps. Indeed the algorithm terminates [START_REF] Akhavi | Worst-case complexity of the optimal LLL algorithm[END_REF][START_REF] Lagarias | Worst-case complexity bounds for algorithms in the theory of integral quadratic forms[END_REF][START_REF] Vallée | Gauss' algorithm revisited[END_REF]. In the sequel we will prove that the above mechanism does not depend strongly on the reduced basis R. More precisely there are exactly 4 rewrite systems. (for all reduced bases of R 2 )

The unimodular group in two dimensions GL 2 (Z) has been already studied [START_REF] Magnus | Über n-dimensionale G ittertransformationen[END_REF][START_REF] Magnus | Combinatorial group theory[END_REF][START_REF] Nielsen | Die Gruppe der dreidimensionale G ittertransformationen[END_REF][START_REF] Nielsen | Die Isomorphismengruppe der freien Gruppen[END_REF] and it is wellknown that {S, T } is a possible family of generators for GL 2 (Z). Of course there are relators associated to these generators and there is no unicity of the decomposition of an element of GL 2 (Z) in terms of S and T . But the Gaussian algorithm gives one precise of these possible decompositions. In the sequel of this paper, we will completely characterize this decomposition and we will call it the Gaussian decomposition of a unimodular matrix. Roughly speaking, we exhibit forbidden sequences of values for the x i -s. More precisely, we exhibit in Section 3 a set of rewriting rules that lead to the formulation output by the Gaussian algorithm, from any product of matrices involving S and T . The precise characterization of the Gaussian decomposition that we give makes appear the slowest manner the length of a unimodular matrix can grow with respect to its Gaussian decomposition. More precisely we consider unimodular matrices the length of Gaussian decomposition of which is fixed, say k:

U := T x k+1 ST x k ST x k-1 . . . ST x2 ST x1 .
We exhibit in Section 4 the Gaussian word of length k with minimal length. We naturally deduce the minimum length g(k) of all inputs demanding at least k steps (Section 5). Finally by "inverting" the function g we find the maximum number of steps of the Gaussian algorithm.

The Gaussian decomposition of a unimodular matrix

Let Σ be a (finite or infinite) set. A word ω on Σ is a finite sequence

(3.1) α 1 α 2 . . . α n
where n is a positive integer, and α i ∈ Σ, for all i ∈ {1, . . . , n}. Let Σ * be the set of finite words on Σ. We introduce for convenience the empty word and we denote it by 1.

Consider the alphabet Σ = {S, T, T -1 }. Remember that we call Gaussian decomposition, the expression of U output by the Gaussian algorithm. Remember also that, for a given basis B, there exists a unique couple (U, R) such that U and R are output by the Gaussian algorithm while reducing B.

Lemma 1. Let R = (b 1 , b 2 ) be a reduced basis. Then one of the following cases occurs:

• |b 1 | < |b 2 | and m = -1/2; • |b 1 | = |b 2 | and m = -1/2; • |b 1 | < |b 2 | and m = -1/2; • |b 1 | = |b 2 | and m = -1/2.
Now consider a word ω on Σ, that is, an element of Σ * , a unimodular matrix U and a reduced basis R. We give, in the following subsections, sets of rewriting rules depending on the form of R, such that any word in which none of these rewriting rules can be applied is Gaussian. Since the results of these subsections are very similar, we only give detailed proofs for Subsection 3.1 in the appendix.

3.1. The basis R is such that |b 1 | < |b 2 | and m = -1/2.
Say that ω is a reduced word or a reduced decomposition of the unimodular matrix U , if ω is a decomposition of U in which no one of the rewriting rules of Theorems 1 can be applied. Thus, Theorem 1 shows that, for a given reduced basis R such that |b 1 | < |b 2 | and m = -1/2, the Gaussian decomposition and a reduced decomposition of a unimodular matrix are the same, which implies that this decomposition is unique.

Theorem 1. Let ω 1 be any decomposition of U in terms of the family of generators {S, T }. The Gaussian decomposition of U is obtained from ω 1 by applying repeatedly the following set of rules:

(3.2) S 2 -→ 1; (3.3) T x T y -→ T x+y ; (3.4) ∀x ∈ Z * -, ST 2 ST x -→ T ST -2 ST x+1 ; (3.5) ∀x ∈ Z * + , ST -2 ST x -→ T -1 ST 2 ST x-1 ; (3.6) ∀x ∈ Z * , ∀k ∈ Z + , ST ST x 1 i=k ST yi -→ T ST -x-1 1 i=k ST -yi ; (3.7) ∀x ∈ Z * , ∀k ∈ Z + , ST -1 ST x 1 i=k ST yi -→ T -1 ST -x+1 1 i=k ST -yi .
The trivial rules (3.2) and (3.3) have to be applied whenever possible. So any word ω 1 on the alphabet Σ can trivially be written as

(3.8) T x k+1 1 i=k ST xi , with x i ∈ Z * for 2 ≤ i ≤ k and (x 1 , x k+1 ) ∈ Z 2 .
The integer k is called the length5 of ω 1 . Notice that usually the length of a word as in (3.1) is n, which would corresponds here to 2k + 1. Here the length is k, which correspond to the number of iterations of the algorithm minus 1. The proof of Theorem 1 is given in appendix. It consists in the following lemmas:

• Lemma 2, where we prove that the rewriting process terminates;

• Lemma 3, where we prove that any reduced word is also Gaussian;

• Lemmas 4 and 5, where we prove that the use of a nontrivial rewriting rules changes a base of the lattice in another base of the same lattice. Proofs of Theorems 2, 3 and 4, which are given in the following subsections, are very similar.

The basis

R is such that |b 1 | = |b 2 | and m = -1/2.
Theorem 2. Let ω 1 be any decomposition of U in terms of the family of generators {S, T }. The Gaussian decomposition of U is obtained from ω 1 by applying repeatedly the set of rules (3.2) to (3.7) of Theorem 1, together with the following rules:

(3.9) ∀x ∈ Z * , ∀k ∈ Z + , ST ST x 1 i=k ST yi -→ T ST -x-1 1 i=k ST -yi T ; (3.10) ∀x ∈ Z * , ∀k ∈ Z + , ST -1 ST x 1 i=k ST yi -→ T -1 ST -x+1 1 i=k ST -yi T ; (3.11) if ω 1 = ω S, then ωS -→ ω; (3.12) if ω 1 = ω ST, then ωST -→ ωT ST -1 . 3.3. The basis R is such that |b 1 | < |b 2 | and m = -1/2.
Theorem 3. Let R be a reduced basis and let U be a unimodular matrix, i.e., an element of GL 2 (Z). Let ω 1 be any decomposition of U in terms of the family of generators {S, T }. The Gaussian decomposition of U is obtained from ω 1 by applying repeatedly the rules (3.2) to (3.5) of Theorem 1 until ω 1 is reduced in the sense of Theorem 1. Then, if we have ω 1 = ω ST 2 S, the following rule applies:

(3.13) ωST 2 S -→ ωT ST -2 ST,
and the rewriting process is over. Theorem 4. Let R be a reduced basis and let U be a unimodular matrix, i.e., an element of GL 2 (Z). Let ω 1 be any decomposition of U in terms of the family of generators {S, T }. The Gaussian decomposition of U is obtained from ω 1 by applying repeatedly Rules (3.2) to (3.5) of Theorem 1, together with Rules (3.9) and (3.10) and the following set of rules:

(3.14) if ω 1 = ω S, then ωS -→ ω; (3.15) if ω 1 = ω ST, then ωST -→ ωT ; (3.16) if ω 1 = ω ST 2 , then ωST 2 -→ ωT ST -1 .

The length of a unimodular matrix with respect to its Gaussian decomposition

Let B = (b 1 , b 2 ) be a basis. The length of B, denoted by ℓ(B), is the sum of the squares of the norms of its vectors, that is,

ℓ(B) = |b 1 | 2 + |b 2 | 2 .
The easy but tedious proof of the following theorem is given in the appendix, see Lemmas 6, 7, 8, 9 and 10.

Theorem 5. Let R = (b 1 , b 2 ) be a reduced basis, let k be a positive integer, and let x 1 , . . . , x k+1 be integers such that the word ω = T x k+1 1 i=k ST xi is Gaussian. Then the following properties hold:

(1) if |b 1 | < |b 2 | and m ≥ 0 then ℓ(ωR) ≥ ℓ((ST -2 ) k-1 S R); (2) if |b 1 | < |b 2 | and -1/2 < m < 0 then ℓ(ωR) ≥ ℓ((ST 2 ) k-1 S R); (3) if |b 1 | < |b 2 | and m = -1/2 then ℓ(ωR) ≥ ℓ((ST -2 ) k-1 ST R); (4) if |b 1 | = |b 2 | then ℓ(ωR) ≥ ℓ((ST -2 ) k-1 ST -1 R).

The maximum number of steps of the Gaussian algorithm

Theorem 6. Let k > 2 be a fixed integer. There exists an absolute constant A such that input basis demanding more than k steps to the Gaussian algorithm has a length greater than A(1 + √ 2) k :

g(k) ≥ A(1 + √ 2) k .
It follows that any input with length less than A(1 + √ 2) k is demanding less than k steps. We deduce the following corollary.

Corollary 1. There is an absolute constant A such that the number of steps of the Gaussian algorithm on inputs of length less than M is bounded from above by

log (1+ √ 2)
M A .

Sorting algorithms

Let n be a positive integer, and let [1, . . . , n] be the sorted list of the n first positive integers. Let S n be the set of all permutations on [1, . . . , n], and let S be the set of all permutations on a list of distinct integers of variable size. Let us denote by t i the transposition which swaps the elements in positions i and i + 1 in the list , for all i ∈ {1, . . . , n}. Any permutation can be written in terms of the t i -s. Put Σ n = {t 1 , . . . , t n } and Σ = {t i : i ∈ N * }. Thus Σ n (resp. Σ) is a generating set of S n (resp. S).

As in previous sections, any word ω on Σ will be denoted as following:

ω = t i1 t i2 . . . t i k = k j=1 t ij ,
where k and i 1 , . . . , i k are positive integers.

Definition 1.

Let ω 1 = t i1 t i2 . . . t i k and ω 2 = t j1 t j2 . . . t j l be words on Σ.

(1) The length of ω, denoted by |ω|, is k;

(2) the distance between ω 1 and ω 2 , denoted by Dist(ω 1 , ω 2 ), is given by min ti∈ω1,tj ∈ω2 |i -j|;

(3) the maximum (resp. minimum) of ω 1 , denoted by max(ω 1 ) (resp. min(ω 1 )), is given by max ti∈ω1 (i) (resp. min ti∈ω1 (i)); (4) ω 1 is an increasing word (resp. decreasing word ) whether i p < i p+1 (resp. i p > i p+1 ), for all p ∈ {1, . . . , k -1}; (5) ω 1 is a consecutively increasing word (resp. consecutively decreasing word ) whether i j+1 -i j = 1 (resp. i j -i j+1 = 1), for all j ∈ {1, . . . , k -1}; (6) ω 1 < ω 2 (resp. ω 1 > ω 2 ) whether ω 1 and ω 2 are increasing (resp. decreasing) words such that max(ω 1 ) ≤ min(ω 2 ) (resp. min(ω 1 ) ≥ max(ω 2 )); ( 7) ω 1 is minimal on the left in ω 2 ω 1 (resp. maximal on the right in ω 1 ω 2 ) whether ω 1 is an increasing word such that i 1 ≤ j l (resp. j 1 ≤ i k ); (8) similarly, ω 1 is minimal on the right in ω 2 ω 1 (resp. maximal on the left in ω 1 ω 2 ) whether ω 1 is a decreasing word such that j l ≤ i 1 (resp. i k ≤ j 1 ).

It is easy to prove that any word ω on Σ can be uniquely written on the form (6.1)

ω = ω 1 ω 2 . . . ω m ,
where ω i is an increasing (resp. decreasing) word maximal on the right and on the left, for all i ∈ {1, . . . , m}.

We will call (6.1) the increasing decomposition (resp. decreasing decomposition) of ω, and we will denote it by [ω 1 , . . . , ω m ]. We define s : Σ * → N as the map given by the rule

s(ω) = m,
where [ω 1 , . . . , ω m ] is the increasing decomposition of ω. Moreover, it is also easy to prove that ω i can be uniquely written on the form

ω i = ω ′ i1 ω ′ i2 . . . ω ′ ip i ,
where the ω ′ j -s are consecutively increasing (resp. decreasing) and minimal on the left (resp. right), for all i ∈ {1, . . . , m}. The decomposition

[ω ′ i1 , ω ′ i2 , . . . , ω ′ ip i
] is called the consecutively increasing decomposition (resp. consecutively decreasing decomposition) of ω i . 6.1. Bubble sort. The basic idea of the bubble sort algorithm is the following: pairs of adjacent values in the list to be sorted are compared and interchanged if they are out of order, the process starting from the beginning of the list. Thus, list entries 'bubble upward' in the list until they bump into one with a higher sort value.

The algorithm first compares the two first elements of the list and swap them if they are in the wrong order. Then, the algorithm compares the second and the third elements of the list and swaps them if necessary. The algorithms continues to compare adjacent elements from the beginning to the end of the list. This whole process is iterated until no changes are done.

Let σ be a permutation on [1, . . . , n]. There exists a unique decomposition ω of σ on the alphabet Σ corresponding to the sequence of elementary transforms performed by the bubble sort algorithm on σ[1, . . . , n]. We will call it the bubblian decomposition of σ. Notice that (ω

) -1 σ = 1. (6.2) Input: σ ∈ S. Output: a decomposition of σ, σ := t 1 . . . t m .
Definition 2. A word ω on Σ is a bubblian word if it corresponds to a possible execution of the bubble sort algorithm.

Let us define some rewriting rules on Σ * . In the following equations, i, j and k are arbitrary positive integers and ω is a word on Σ:

(6.3) t i t i -→ 1; (6.4) if Dist(i + 1, ω) > 1, then t i+1 ω t i t i+1 -→ ωt i t i+1 t i ; (6.5)
if Dist(i + 1, ω) > 1 and ω is maximally increasing, then ω t i -→ t i ω;

(6.6) if Dist(j, kω) > 1 and either i ≤ j ≤ k or k < i ≤ j, then t i t k ω t j -→ t i t j t k ω.

Theorem 7. Let σ be a permutation and let ω ∈ Σ * be a decomposition of σ on Σ. The bubblian decomposition of σ is obtained from ω by applying repeatedly the rules (6.3) to (6.6).

Remark 1. Let ω and ω ′ be words on Σ. It is well known that a presentation of S on Σ is the following:

• t i t i = 1;
• t i t j = t j t i ;

• t i t i+1 t i = t i+1 t i t i+1 ; for all positive integers i, j such that |i -j| = 1. Thus, it is easy to prove that if ω ′ is obtained from ω, then ω = ω ′ in S.

The sketch of the proof of Theorem 7 is very similar to the proof of Theorem 1 and is given in the appendix. Notice that we can easily deduce from Theorem T:redbubble the worst-case for the bubble sort algorithm.

6.2. Other iterative sorting algorithms. We also give without proof some rewriting rules for the insertion sort algorithm and the selection sort algorithm, see the appendix.

Conclusion

In this paper we studied the Gaussian algorithm by considering a rewriting system over GL 2 (Z). We first believe that our method should be applied to other variants of the Gaussian algorithm (for example, Gaussian algorithm with other norms [START_REF] Kaib | The generalized Gauss reduction algorithm[END_REF]) and for each variant there is an adequate rewriting system over GL 2 (Z). The most important and interesting continuation to this work is to generalize the approach in higher dimensions. Even in three dimensions the worst-case configuration of all possible generalization of the Gaussian algorithm is completely unknown for the moment. ( [START_REF] Sprang | Basisreduktionsalgorithmen für Gitter kleiner Dimension[END_REF] has tried without success in 3 dimensions.) Although the problem is really difficult, we have already achieved a step, since the LLL algorithm uses the Gaussian algorithm as an elementary transform.

The group of n-dimensional lattice transformations has been studied first by Nielsen [START_REF] Nielsen | Die Gruppe der dreidimensionale G ittertransformationen[END_REF] (n = 3) and for an arbitrary n by Magnus [START_REF] Magnus | Über n-dimensionale G ittertransformationen[END_REF][START_REF] Magnus | Combinatorial group theory[END_REF], based on the work of Nielsen [START_REF] Nielsen | Die Isomorphismengruppe der freien Gruppen[END_REF]. Their work should certainly help to exhibit such rewriting systems on GL n (Z) if there exists. This approach may also be an insight to the still open problem of the complexity of the optimal LLL algorithm [START_REF] Akhavi | Worst-case complexity of the optimal LLL algorithm[END_REF][START_REF] Lenstra | Flags and lattice basis reduction[END_REF].

for any word ω of length k + 1 such that d > d(ω) ≥ 1. Let i be in S 1 ∪ S 2 . If x i = 1 (resp. x i = -1), then we use the rule (3.6) (resp. (3.7)), and the length of ω 1 strictly decreases. Suppose now that x i = 2. Then ω 1 can be written as ω 2 ST x ST 2 ST y ω 3 , where x ∈ Z, y ∈ Z * -, ω 2 and ω 3 are words on the alphabet Σ, such that ω 2 does not end by a S and ω 3 is either 1 or starts by S. If we use the rule (3.4), then we get the word ω

′ 1 = ω 2 ST x+1 ST -2 ST y+1 ω 3 . Put d ′ = d(ω ′ 1 )
, and δ = j∈S1∪S2\{i+1,i,i-1} j. Notice that if x = 0, then ω 1 = T z ST 2 ST y ω 3 , with z ∈ Z.

Case 1. Suppose that either x = -1 or y = -1.

Then |ω ′

1 | = k, and the rewriting process terminates. Case 2. Suppose that y / ∈ {-3, -2, -1}.

• Suppose that x / ∈ {-2, -1, 1}: then d ′ = d -1. • Suppose that x = -2. Then the following equalities hold:

ω 1 = ω 2 ST -2 ST 2 ST y ω 3 ; ω ′ 1 = ω 2 ST -1 ST -2 ST y+1 ω 3 . Thus, we have d ′ = i + 1 < d = 2i + 1 + δ.
• Suppose that x = 1. Then the following equalities hold:

ω 1 = ω 2 ST 1 ST 2 ST y ω 3 ; ω ′ 1 = ω 2 ST 2 ST -2 ST y+1 ω 3 . Thus we have d ′ = i + 1 < d = 2i + 1 + δ. Case 3. Suppose that y = -3. • Suppose that x / ∈ {-2, -1, 1}. Then d ′ ≤ i -1 + δ < i + δ ≤ d. • Suppose that x = -2. Then ω 1 = ω 2 ST -2 ST 2 ST -2 ω 3 ; ω ′ 1 = ω 2 ST -1 ST -2 ST -2 ω 3 . Thus d ′ ≤ 2i -1 + δ < 2i + 1 + δ ≤ d.
• Similarly, if x = 1, then the following equalities hold:

ω 1 = ω 2 ST 1 ST 2 ST -3 ω 3 ω ′ 1 = ω 2 ST 2 ST -2 ST -2 ω 3 . Thus d ′ ≤ 2i -1 + δ < 2i + 1 + δ ≤ d. Case 4. Suppose that y = -2. • Suppose that x / ∈ {-2, -1, 1}. Then d ′ ≤ i -1 + δ < i + δ ≤ d. • Suppose that x = -2.
Then the following equalities hold:

ω 1 = ω 2 ST -2 ST 2 ST -2 ω 3 ; ω ′ 1 = ω 2 ST -1 ST -2 ST -1 ω 3 . Thus d ′ ≤ 2i -1 + δ < 2i + 1 + δ ≤ d.
• Suppose that x = 1. Then the following equalities hold:

ω 1 = ω 2 ST 1 ST 2 ST -2 ω 3 ω ′ 1 = ω 2 ST 2 ST -2 ST -1 ω 3 . Thus d ′ ≤ 2i -1 + δ < 2i + 1 + δ ≤ d.
By induction hypothesis, the rewriting process always terminates. Lemma 3. Let B be the matrix of a proper basis (b 1 , b 2 ) (see (2.1), (2.2) and (2.3)). Let x ∈ Z * be a non zero integer and B := ST x B express the matrix of the basis ( b1 , b2 ), i.e. b1 is the first row of B and b2 is its second row.

( (1) We will show that ( b1, b1

|b 2 + xb 1 | 2 = |b * 1 | 2 (m + x) 2 |b * 1 | 2 + |b * 2 | 2 < 1 (m + x) 2 .
If mx < 0, we have 1 < 1. Then B ′ is such that B ′ = -B.

Proof. The following equalities hold:

ST 2 ST x = 2x + 1 2 x 1 and T ST -2 ST x+1 = -2x -1 -2 -x -1 ,
which concludes the proof.

Lemma 5. Let R be a reduced basis such that m = -1 2 . Put B := ST ST x ω B (resp. B := ST -1 ST x ω 1 B), where ω is a word on Σ of the form (3.8). Then the basis B ′ := (T ST -x-1 ω -) -1 B (resp. B ′ := (T -1 ST -x+1 ω -) -1 B) is a reduced basis.

Proof. Notice that:

ST ST x = x + 1 1 x 1 and T ST -x-1 = -x -1 1 -x 1 .
Thus, it is easy to prove that ST ST x = T ST -x-1 -1 0 0 1 .

The proof of the following easy claim is left to the reader.

Claim 1. Let y be an integer. Then the following equalities hold:

-1 0 0 1 ST y = ST -y 1 0 0 -1 and 1 0 0 -1 ST y = ST -y -1 0 0 1 .

Thus, it is easy to prove by induction on the length of ω 1 that there exists an integer β ∈ {-1, 1} such that ST ST x ω 1 = T ST -x-1 ω - 1 β -1 0 0 1 . Thus, we have B ′ = β -1 0 0 1 B, which concludes the proof.

Corollary 3. Let ω 1 = T x k+1 1 i=k ST xi be a non-reduced word, and let R be a reduced basis. If ω 1 B is the input of the Gaussian algorithm, then the sequence of elementary transforms made during the execution is exactly represented by the reduced word uniquely associated to ω 1 .

  |). The usual Gram-Schmidt orthogonalization process builds, in polynomial-time, from a basis b = (b 1 , b 2 ) an orthogonal basis b * = (b * 1 , b *

  Let (b 1 , b 2 ) be an input basis of a lattice and the matrix B expressing (b 1 , b 2 ) in the canonical basis of R 2 as specified by (2.1). The algorithm first makes an integer translation of b 2 in the direction of b 1 in order to make b 2 as short as possible. This is done just by computing the integer x nearest to m = (b 2 , b 1 )/(b 1 , b 1 ) and replacing b 2 by b 2 -xb 1 . Notice that, after this integer translation, the basis (b 1 , b 2 ) is proper. The second elementary transform is just the swap of the vectors b 1 and b 2 in case when after the integer translation we have |b 1 | > |b 2 |. The algorithm iterates these transforms, until after the translation, b 1 remains still smaller than b 2 , i.e., |b 1 | ≤ |b 2 |.

3. 4 .

 4 The basis R is such that |b 1 | = |b 2 | and m = -1/2.

) 2 ) 3 ) 4 )

 234 If |x| ≥ 3, then B is still proper. Moreover, • if (b 1 , b 2 ) and x are both positive or both negative, then B is proper whenever |x| ≥ 2. • if B is reduced, |b 1 | < |b 2 | and m = -1/2, then B is proper for all x ∈ Z. (If |x| ≥ 2, then | b2 | < | b1 |. Moreover, if (b 1 , b 2 ) and x are both positive or both negative, it is true provided that |x| ≥ 1. (If |x| ≥ 2, then max(| b1 |, | b2 |) ≥ max(|b 1 |, |b 2 |). (If |x| ≥ 1, then ( b1 , b2 ) and x are both positive or both negative. Proof. The definitions of B, b * and m are given by Relations (2.1), (2.2) and (2.3). We have b1 = b 2 + xb 1 and b2 = b 1 . In the sequel we express all the needed quantities in the orthogonal basis b * .

  5 ≤ ||x| -|m|| < |m + x|. If mx > 0, |m + x| ≥ 1, ∀x ≥ 1. (3) From the last point, we know that |b 1 | ≤ |b 2 + xb 1 |. If |b 2 | < |b 1 |, we have also |b 2 | < |b 2 + xb 1 |. (This is true for |x| ≥ 2 or for |x| ≥ 1 provided that xm > 0. Now if |b 2 | ≥ |b 1 |, since (b 1 , b 2 ) is proper, it is indeed Gauss-reduced. Sob 1 and b 2 are the shortest vector generating the whole lattice. So for all x = 0, |b 2 + xb 1 | > b 2 . (4) By definition ( b1 , b2 ) := (b 2 + xb 1 , b 1 ) = (x + m)|b * 1 | 2 . Since |m| ≤ 1/2 if |x| ≥ 1, the quantities x + m and x have the same sign.

Corollary 2 .

 2 Let ω 1 be a word of the form (3.8). Then there is a unique reduced word ω ′ 1 corresponding to ω 1 . Moreover, ω ′ 1 is a Gaussian word. Lemma 4. Let B be a proper basis. Put B := ST 2 ST x B and B ′ := (T ST -2 ST x+1 ) -1 B;(resp. B := ST -2 ST x B and B ′ := (T -1 ST 2 ST x-1 ) -1 B).

  Since ||x| -|m|| < |m + x| and |m| ≤ 1/2, when |x| ≥ 3, clearly 2 < |m + x| and when mx > 0 this is still true whenever |x| ≥ 2. (2) We have to show that |b 1 | < |b 2 + xb 1 |. We notice that |b 1 | 2

	Notice that	) ( b1, b2) ( b1 , b1 ) ≤ 2. |( b1 , b2 )|	=	(m + x) 2 |b * 1 | 2 + |b * 2 | 2 |m + x||b * 1 | 2	<	1 |m + x|	.

When dealing with a non-trivial algorithm f is always an increasing function.

Of course, b * is generally not a basis for the lattice generated by b.

A priori x 1 and x k+1 in (2.5) may be zero so the algorithm may start by a swap or finish by a translation.

The length of a word has of course to be distinguished with what we call the length of a unimodular matrix, that is the maximum of absolute values of its coefficients.

Of course saying that the rewriting process presented by the previous Theorem always terminates has a priori nothing to do with the well-known fact that the Gaussian algorithm always terminates.

Acknowledgments. The authors are indebted to Brigitte Vallée for drawing their attention to algorithmic problems in lattice theory and for regular helpful discussions.

Appendix A. The Gaussian decomposition of a unimodular matrix

In the following proofs, we will essentially use the set of rules (3.4), (3.5), (3.6), (3.7) and apply (3.2) and (3.3) implicitly whenever possible. So with any initial ω 1 , we always obtain a reduced word after applying a finite number of times the rewriting rules. Moreover, no matter in which order the different rewriting rules are used, the same unique reduced word -corresponding to a Gaussian word -is always obtained from ω 1 , as proved by the following lemmas.

Lemma 2. Let ω 1 be a word as in (3.8). Then the rewriting process always terminates 6 .

The proof of Lemma 2 will use the following notations. Notation 1. Let k be a nonnegative integer, and let x 1 , . . . , x k+1 be integers such that x 2 ,. . . , x k are nonzero. Put ω 1 = T x k+1 k i=1 ST xi . We denote by ω -

We also put d(ω 1 ) = i∈S1∪S2 i.

Proof. We proceed by induction on the length of ω 1 , and on the sum d = d(ω 1 ). The property is trivially true whether |ω 1 | ∈ {0, 1, 2} and d ∈ N.

Let k be a positive integer such that k ≥ 2. Suppose that the property holds for any word of length k. Suppose that |ω 1 | = k + 1. The property holds whether d belongs to {0, 1}. Suppose that the property holds Appendix B. The length of a unimodular matrix with respect to its Gaussian decomposition

The easy proof of the following lemma is left to the reader.

Lemma 6. Let k be a positive integer. There exist nonnegative integers α, β and γ such that:

Lemma 7. Let B be a proper basis, and let x be an integer such that |x| ≥ 3.

Proof. Put Bx = ( b1,x , b2,x ) = ST x B, for all integer x. Then

Lemma 8. Let B be a proper basis, let k be a positive integer, let ε ∈ {1, -1} be an integer, and let x be an integer such that |x| ≥ 3. The following properties hold:

The second part of the proof is very similar.

Proofs of Lemmas 9 and 10 are very similar to the proof of Lemma 8.

Lemma 9. Let B be a proper basis and let x be an integer. Then ℓ(T x B) ≥ ℓ(B).

Lemma 10. Let R be a reduced basis, let k be a positive integer, let x and x ′ be integers. Then

Moreover, the following properties hold:

Proof. Proof of Theorem 5.

Notice first that, by Lemma 9, we can suppose that x k+1 = 0. Suppose that k = 1. Then, by Lemma 10, ℓ(ST x1 B) ≥ ℓ(SB).

Suppose that k ≥ 1. The variable ε will denote an integer in {1, -1}. We construct a sequence ω 0 , ω 1 , . . . , ω k such that the following properties hold:

(1)

Notice that ω j may be equal to ω j-1 for some j ∈ {1, . . . , k}. We proceed by induction on an integer j such that 1

By Lemma 7, we know that ℓ( B) = ℓ(ST x k B′ ) ≥ ℓ(ST ε2 ) B′ ). Now, either x k-1 is positive and we put ω 1 = ST 2 ω ′ , or x k-1 is negative and we put ω 1 = ST -2 ω ′ , so that ω 1 is Gaussian.

Let j be an integer in {1, . . . , k -2} such that ω j verifies (2) and (3). By Lemma 8, it is obvious that we can put:

Suppose now that we constructed ω k-1 = (ST ε2 ) k-1 ST x1 . Then, by Lemma 10, we can put ω k = (ST 2 ) k-1 S whether m is positive and ω k = (ST -2 ) k-1 S whether m is negative.

Appendix C. The maximum number of steps of the Gaussian algorithm Proof. Proof of Theorem 6.

From the last section , we know that the input with the smallest length demanding k steps is (ST 2 ) k or (ST -2 ) k . Let Q be equal to (ST 2 ). The symmetrical matrix Q 2 1 1 0 has its eigenvalues equal to 1 + √ 2 and 1 -√ 2. It can be diagonalized and one deduces that there exist two constants α > 0 and β > 0 such that all coefficients of Q k are expressed in the form

This leads to the lower-bound proposed by the theorem.

Proof. Proof of Corollary 1.

Appendix D. Sorting algorithms

Lemma 11. The rewriting process always terminates.

Proof. Let l : Σ * → N be the map given by the rule

where ω = t α1 . . . t α |ω| . Let h : Σ * → N be the map given by the rule

where [ω 1 , . . . , ω m ] is the increasing decomposition of ω. We proceed here by induction on the nonnegative integers l(ω) and h(ω). Suppose that l(ω) = 0. Then σ = 1 and the rewriting process is over. Suppose that l(ω) = 1 and h(ω) = 0. Then ω = t 1 and the rewriting process is over. Notice that there exists no word on Σ * such that l(ω) = 1 and h(ω) > 0. Suppose now that l(ω) = l, that h(ω) = h and that we can apply a rewriting rule. If we apply one of the rules (6.3) or (6.4), then we get a word ω ′ such that l(ω ′ ) < l(ω). If we apply (6.5) or (6.6), then l(ω ′ ) = l(ω). Let [ω 1 , . . . , ω m ] be the increasing decomposition of ω.

Suppose that we can apply (6.5). Then there exists j ∈ {1, . . . , m -1} such that min(ω j+1 ) = i and min(ω

Suppose now that we can apply the rule (6.6). Then there exist p, q ∈ {1, . . . , m} and i, j, k ∈ {1, . . . , max(ω)} such that one of the following cases occurs.

which concludes the proof.

Lemma 12. Let ω be a reduced word, and let [ω 1 , . . . , ω m ] be its increasing decomposition. Let p ∈ {1, . . . , m -1} be an integer. If t i is in ω p+1 , then t i+1 is in ω p .

Proof. Let p ∈ {1, . . . , m} be such that the property does not hold. Let i ∈ {1, . . . , max(ω)} be the smallest integer such that t i ∈ ω p+1 , and t i+1 / ∈ ω p . Then, there exists

. . ω m ; and such that the following inequalities hold:

Then ω ′ p+1 = 1, ω ′′ p is maximal on the left and we can apply the rule (6.5). Case 2. Suppose that i = min(ω p+1 ) and that t i-1 ∈ ω ′′ p+1 . Since t i ∈ ω p and Dist(t i , ω ′′ p ) > 1, we can apply the rule (6.4). Case 3. Suppose that i = min(ω p+1 ) and that t i-1 / ∈ ω ′′ p+1 . Then Dist(t i , ω ′′ p ω ′ p+1 ) > 1. Thus, either ω ′ p = 1 and we can apply the rule (6.5), or ω ′ p = 1 and we can apply the rule (6.6).

The following corollary is an easy consequence of Lemma 12.

Corollary 4. Let ω be a reduced word, and let [ω 1 , . . . , ω m ] be its increasing decomposition. Let p ∈ {1, . . . , m -1} be an integer. Then

(1) max(ω p ) > max(ω p+1 );

(2) Dist(ω p , ω p+1 ) ≤ 1.

The easy but tedious proof of the following lemma is left to the reader, who can proceed by induction.

Lemma 13. Let ω = ω 1 . . . ω m be a permutation put under increasing decomposition. Put ω[1, . . . , n] = [α 1 , . . . , α n ] and ω 1 =

. Suppose that ω is reduced. Then the following properties hold:

for all k ∈ {1, . . . , q}.

Corollary 5. In the conditions of Lemma 13, the first iterations of the algorithm on ω[1, . . . , n] are represented by ω 1 .

The following corollary is an easy consequence of Lemma 13. Corollary 6. Let ω be a reduced word. Then ω is a bubblian word.

Since the bubblian word associated to a given permutation is unique and the rewriting process terminates, the bubblian words are the reduced words. D.1. Insertion sort. The basic idea of the insertion sort algorithm is the following: the beginning of the list being already sorted, the first non sorted element of the list is put at the right place in the already sorted part. Thus, an elementary transform made by the algorithm is a cycle (i, i + 1, . . . , i + p) = t i+p t i+p-1 . . . t i+1 t i in S. Thus, any permutation σ can be written on the form

and the word on Σ * produced by the algorithm, which we will call insertion word, is a particular decomposition of σ. Let ω be a word on σ * . The rewriting rules for the insertion sort algorithm are very similar to the rewriting rules for the bubble sort algorithm. In the following equations, i, j and k are arbitrary positive integers and ω is a word on Σ: (D. [START_REF] Akhavi | Worst-case complexity of the optimal LLL algorithm[END_REF] if Dist(i, ω) > 1, then t i ω t i -→ ω;

Let ω be a word on σ * . Using similar methods that in Subsection 6.1, we can prove that, by applying repeatedly rules D.1 to D.4, we obtain the insertion word uniquely associated to ω.

D.2. Selection sort.

The basic idea of the selection sort algorithm is the following: the beginning of the list being already sorted, the algorithm finds the smallest element of the non sorted list and put it at the right place at the end of the already sorted part. As in the previous subsection, an elementary transform made by the algorithm is a cycle (i, i + 1, . . . , i + p), which can be written as t i+p t i+p-1 . . . t i+1 t i in Σ * . The word on Σ * produced by the algorithm, called selection word, is a particular decomposition of σ.

Let ω be a word on σ * . The rewriting rules for the selection sort algorithm are very similar to the rewriting rules for the bubble sort algorithm. In the following equations, i, j and k are arbitrary positive integers and ω is a word on Σ: (D. [START_REF] Kaib | The generalized Gauss reduction algorithm[END_REF] if Dist(i, ω) > 1, then t i ω t i -→ ω;

(D.6) if Dist(i, ω) > 1, then t i ω t i+1 t i -→ ω t i+1 t i t i+1 ;

(D.7) if Dist(i, ω) > 1, then t i+1 ω t i -→ t i+1 t i ω;

(D.8) if i -j > 1, then t i t j t j-1 -→ t j t i t j-1 .

Let ω be a word on σ * . Using similar methods that in Subsection 6.1, we can prove that, by applying repeatedly rules D.1 to D.4, we can obtain the insertion word uniquely associated to ω.


N Saintier
email: nicolas.saintier@ensam.eu

G Cailletaud

R Piques

Cyclic loadings and crystallization of natural rubber: An explanation of fatigue crack propagation reinforcement under a positive loading ratio

Keywords:

published or not. The documents may come

Cyclic loadings and crystallization of natural rubber: An explanation of fatigue crack propagation reinforcement under a positive loading ratio

Nicolas Saintier, Georges Cailletaud, Roland Piques

Introduction

Natural rubber's resistance to crack growth and its ability to withstand large strains without permanent deformation are two of the main reasons for its extensive use in many industrial applications. Most of them involve significant static and cyclic loading. The need for appropriate multiaxial fatigue life criteria has become crucial over the past 10 years. A good understanding of the micromechanisms involved in the fatigue crack initiation process are essential for the establishement of physically motivated criteria. In the case of natural rubber, in addition of damage mechanisms, specific reinforcing mechanisms still have to be understood. Indeed, under particular loading conditions (under uniaxial loading these particular conditions correspond to positive stress ratio tests), natural rubber shows an exceptional fatigue resistance so that damage mechanisms only cannot fully describe the fatigue behavior of natural rubber. A reinforcing mechanism must be taken into account in order to propose a fatigue life criterion suitable for all types of loading. The aim of this paper is not to propose such a criterion but rather to understand the origin of this mechanism so that a physically based criterion can be proposed (see [1,2] for a multiaxial fatigue life prediction method taking into account reinforcing mechanisms on natural rubber). The particular strength of natural rubber, as opposed to synthetic rubber on which such reinforcing mechanisms are not observed, has been attributed to its ability to crystallize upon stretching. Strain induced crystallization is believed to play a major role in fracture properties of rubber by inducing strong microstructural changes in the crack tip region. Strain induced crystallization of natural rubber has been largely investigated using numbers of techniques such as X-ray diffraction [3][4][5][6], infra-red spectrometry [7,8], birefringence [9], low-angle light scattering [10], Raman [11,12], or nuclear magnetic resonance [13,14]. These studies have resulted in a better understanding of the link between microstructural features (crosslink density, chemical composition, fillers, see [6] for more details), temperature and strain on natural rubber crystallization. The work of Trabelsi et al. [3], Siesler [7] and Toki et al. [4,5] give interesting results concerning the effect of cyclic deformation on strain induced crystallization, which is of prior importance when dealing with fatigue loading. However, the aim of these studies was not to link the strain induced crystallisation to the reinforcement processes observed under fatigue loading so that the loading frequencies were several orders of magnitude below the one usually encountered in fatigue tests, the type of strain cycles did not correspond to cases where reinforcement processes are observed, and finally the link with fatigue crack initiation mechanisms was not assessed. For these reasons no satisfactory answer to the reinforcement process observed under cyclic loading has yet been proposed.

In this paper we present the crack initiation mechanisms observed under reinforcing conditions and propose an explanation for the reinforcement under cyclic loading and its relation to strain induced crystallization.

Strain induced crystallization and fracture properties

Strain induced crystallization is due to the particular steric purity of the polyisoprenne backbone (in our case 99.9% polyisoprenne cis-1,4). By stretching, the conformational entropy decreases, which increases the ability of natural rubber to crystallize. Strain induced crystallization of natural rubber has been largely investigated using a number of techniques as stated in the previous section. The morphology of the strain/stress induced crystallization has been reported to have many different structures: fibrils, fibrils and folded lamellae, and shish-kebabs [15][16][17][18]. In all cases, the microstructure induced is strongly anisotropic. It exhibits strong covalent bonds in the direction of straining and weaker Van der Waals forces in the plane perpendicular to the straining direction.

Under simple tension, strain induced crystallization has been shown to be responsible for the upturn in modulus observed on the load-displacement curve for carbon-black filled natural rubber. The sensitivity of the strain induced crystallization rate to both the presence and type of fillers is high. Recently, Trabelsi et al. [19], Rault et al. [20] analysed strain induced crystallization by synchrotron X-ray diffraction and Chenal et al. [6] analysed the parameters governing strain induced crystallization in filled natural rubber giving a good understanding of the filler type effect. Since only one type of natural rubber was available for this study, it was not possible to analyze the filler type effect on the features related in this paper. At room temperature, where isotropic ("cold") crystallization is limited [21], failure properties of rubber are governed by strain induced crystallization. The anisotropic microstructure induced in the highstrain regions surrounding crack tips is believed to play a major role in fracture mechanisms by opposing a high strength structure in the direction of crack propagation [22]. Hamed and Kim [23] studied crack path under monotonic loading for both synthetic (cisbutadiene) and natural rubbers. For synthetic rubber, the direction of crack growth was found to be close to a path perpendicular to the loading direction. For natural rubber, cracks were found to deviate from this perpendicular direction so that final rupture was the result of successive crack initiation, propagation and deviation. The propensity to secondary cracking was found to depend on the initial crack length.

For fatigue loading, Cadwell [24] was one of the first to observe the reinforcement process under fatigue loading. He performed one-dimensional fatigue tests on natural rubber and styrene-butadiene rubber using dumbbell-like specimens. For styrene-butadiene rubber, at constant strain amplitude, increasing the mean stress was found to reduce the fatigue life. For natural rubber, the same tendency was observed for mean stress values lower than the stress amplitude. However, as soon as the mean stress was greater than the stress amplitude (corresponding to positive loading ratio tests), increasing the mean stress value was found to increase markedly the fatigue life. Lindley obtained similar results by investigating crack propagation rates under one-dimensional fatigue loading on pre-cracked specimens. He identified so-called "non-relaxing loading conditions" under which natural rubber exhibited enhanced crack growth resistance [25]. In the following sections "Non-relaxing conditions" will correspond to a type of loading where the load is never completely removed over a cycle (i.e., positive loading ratio tests). Conversely, relaxing conditions will correspond to loading cases where the load is fully relaxed during a cycle (i.e., loading ratio negative or null). It must be noticed that the reinforcement process was found to occur for the same loading conditions for un-and pre-cracked specimens. Using the tearing energy concept, Lindley proposed to compute the crack propagation rate as: where c is the crack length, n the number of cycles, T max the maximum tearing energy, x the ratio T min /T max , T x the dynamic crack growth limit, A x the crack growth constant at the current x value, and r z a material constant associated with the crack growth rate due to ozone attack. However, in the case of cyclic loading, the process by which the crystallization enhances the fatigue life is not clear. Indeed, according to Eq. ( 1), during a cycle, the instant at which the maximum damage is reached corresponds to the instant of the maximum tearing energy (the crack propagation rate is controlled by the maximum tearing energy). However, since T max corresponds to the maximum extension of the specimen, it must coincide with the maximum degree of crystallization at the crack tip. Then, how can one explain, from the micromechanism point of view, that reinforcement is controlled by both T min and T max (i.e., the loading ratio x), and not T max only. Moreover, it should be noticed that if the x ratio is lower or equal to zero, whatever the maximum tearing energy, no reinforcement will be observed.

dc dn = A x (T max -T x ) + r z (1)
The following sections focus on experimental results which aim to propose an explanation of the reinforcement mechanisms under cyclic loading.

Experimental

Material

The elastomer used in the present study was a vulcanized natural rubber material filled with 23 parts of reinforcing carbon black (N772, N330) per hundred parts of rubber. Formulation and mechanical properties are given in Tables 1 and2. Thin strips of material were cut from 150 mm × 150 mm × 2 mm rubber sheets. Those specimens were used for one-dimensional cyclic tensile tests presented in Section 4.2.3. Before testing, the material was preconditioned 100 cycles at the maximal elongation (in our case = 3.5) and at an elongation ratio min / max = 0 in order to limit stress softening (Mullins effect) during cyclic loading. Using this procedure the material behavior was stable during cyclic loading at = 3.5 but could still show some stress softening at larger elongation values as it is usually the case with Mullins effect. The value of max = 3.5 was considered as a good compromise giving sufficient Mullins effect vanishing and low fatigue damage.

Fatigue testing

Fatigue testing was carried out on axisymmetrical diaboloshaped specimens (see Fig. 1) molded by injection, almost uniaxial when carrying out push-pull testing. The elastomer was bonded to the metal end pieces during the vulcanization process. Fatigue testing was carried out under displacement control using electro-mechanical fatigue machines developed at the laboratory. Specimen compliance was much greater than that of the fatigue machine. Hence, the applied displacement was considered as being fully applied to the specimen. Fatigue machines were supplied with waveforms generated by a digital-to-analogue converter under PC control. Cycles, load and displacement data were recorded by the PC via an analogue-to-digital converter. All tests were carried out at room temperature and at low frequency (1.5 Hz) due to the large displacements involved when testing elastomers. At that frequency, the temperature of the specimen was found to be stable during fatigue tests. Fatigue tests were conducted at least to crack initiation, and in most cases to rupture. The number of cycles to crack initiation N i is conventionally defined as the number of cycles necessary to obtain a crack of a 1 mm size. The parameter N i is difficult to determine unambiguously since neither compliance changes nor potential drop technique can be used with those materials. Hence, the specimen surface was observed using an optical microscope and N i obtained by visual inspection and measurement. In this paper, only the one-dimensional database obtained from push-pull fatigue tests on diabolo specimens (positive and negative loading ratios) will be presented. Multiaxial fatigue tests results and modeling can be found in [26,1].

SEM observations and specimen preparation

Specimen surfaces were observed after fatigue testing using a field effect Zeiss scanning electron microscope (SEM). Microtensile specimens were cut at the diabolos' surface and observed under tension in the SEM chamber using a Deben tensile testing stage. The typical shape of the microtensile specimens were strips of 50 mm × 15 mm × 5 mm. Areas observed by SEM were located in the center of the microtensile specimens. The elongation applied for SEM observation was not greater than 10% of the maximum elongation reached during the fatigue testing.

RX diffraction measurements

Three techniques were used: Laue diffraction (anti cathode Mn, voltage 40 kV, current 30 mA), pole figures (anti cathode Cr, voltage 40 kV, intensity 40 mA), and wide angle X-ray diffraction (anti cathode Cu, voltage 40 kV, intensity 30 mA). Pole figures were performed at the LIMM (Arts et Métiers ParisTech) laboratory, using a 3-axis SIEMENS D500. Wide angle X-ray diffraction spectrography (WAXS) was performed at the laboratory using a 1-axis SIEMENS D500 equiped with a proportional linear ELPHYSE detector. Measurements were conducted while straining the specimen at different strain levels ranging from 0% to 450%. WAXS scans were de-convoluted to extract the contribution of the crystalline structure from the rest of the material. The degree of apparent crystallization was calculated using the assumption made by many authors [27][28][29][30]22], which is that at a given strain level the total diffracted intensity can be partitioned into an amorphous and a crystalline phase contribution such as:

I total = I amorphous + I crystalline (2)
If the total diffracted intensity is assumed constant (the number of diffracting items is constant, only their arrangement is modified), a crystallinity index X c can be defined as:

X c = 1 - I amorphous I 0 total (3)
In this paper, X c will only be considered as a crystallization index and not the absolute value of crystallized chains. Indeed, the measurement of I amorphus (see Eq. ( 3)) by WAXS scans supposes to have a non-oriented amorphous phase (one assumes that the diffracted intensity associated with the amorphous halo is independent of the direction of the scan with respect to the tensile direction), which is not really the case for natural rubber under tension. Each WAXS scan was deconvoluted so that the area of each peak (amorphous + crystalline peaks) could be computed and X c achieved. A Pearson VII type function was chosen for describing the diffraction peak shape:

I(x) = I 0 1 + 4(2 1/m -1)((x -x 0 )/ )
where I 0 is the peak height, m a shape parameter, x 0 the peak position, the half height width. A typical deconvoluted scan is given in Fig. 2.

Results and discussion

Uniaxial fatigue results

One-dimensional fatigue results have been reported in Fig. 3(a) in a Haigh diagram with two parameters, the stress amplitude and mean stress. The dashed lines represent optimized iso-contour lines using a simple bi-linear model. It is interesting to note that the fatigue life sensitivity to the loading ratio R is in agreement with that observed by Cadwell in his early studies. At constant stress amplitude, increasing the mean stress increases the fatigue life for positive loading ratio tests. This phenomenon is characteristic of natural rubber and shows the reinforcement at positive loading ratios under one-dimensional loading. Taking into account the reinforcement process in the fatigue life modeling makes it possible to unify the experimental results for relaxing and non-relaxing conditions as shown in Fig. 3(b). More details on the fatigue modeling and discussions on the validity of such a representation can be found in [1,36]. The following section focuses on the very first stage of crack propagation where the crack size is very close to the size of the flaw from which it initiates.

SEM observations 4.2.1. Cracks at initiation

The very first stage of fatigue damage initiation on the material of the study has been closely investigated and was reported in [2]. Fig. 4(a) represents a crack at initiation (observed under tension) after fatigue testing under relaxing conditions. In this particular case, the crack initiated on a carbon black agglomerate of about 100 m (see Fig. 4(b)). The large crack blunting is characteristic of an elastomeric material. At the crack tip, small fibrils can be observed (see Fig. 4(c)) which confirm that the crack has been initiated and is propagating at this stage. The crack is semi-elliptical in a plane perpendicular to the tensile direction. Despite strong crack blunting, fibrils are only present in a narrow and continuous band at the crack tip. From those observations we can conclude that the crack propagates on a single plane under these particular conditions (no crack deviation at this stage of the crack propagation process). Fig. 5 shows a crack initiation for non-relaxing conditions. The crack morphology for relaxing and non-relaxing conditions are obviously different. Strong multi-cracking and crack deviation can be observed under non-relaxing conditions. In this particular case, not less than 7 different crack tips can be identified with typical crack length of 100 m. Moreover, at larger magnification, those microcracks appear to present additional secondary cracking with characteristic secondary crack length in the 2-10 m range. Below 2 m, micro-cracks can hardly be identified or considered as cracks.

Meso cracks

It has been shown in [2] that fatigue life is mostly controlled by a crack propagation process. The incubation time for a crack to be generated from a flaw (i.e., an inclusion for example) represents only 10-20% of the total fatigue life. In order to observe fatigue cracks morphologies on 1-2 mm cracks, interrupted fatigue tests were performed. The plane of observation was chosen so that it was perpendicular to the crack plane and to the crack front (see Fig. 6). To ensure a perfect sectioning while not inducing any damage during the preparation of the specimen, a cryogenic microtome was used (at sectioning temperature T = 90 • C). As observed on microcracks, the crack morphology of macrocracks obtained under relaxing and non-relaxing conditions are very different as shown in Fig. 7. Under relaxing conditions (Fig. 7(a)), the crack path is very close to a path perpendicular to the loading direction. For non-relaxing, strong crack branching is observed. Observations at higher magnifications show that the secondary cracking observed in Fig. 7(b) is accompanied by smaller scale secondary cracking in a fractal way. Then, the crack propagation process is not the result of a single crack front motion but of multiple crack fronts propagating simultaneously. This provides a first explanation of the fatigue life reinforcement or the crack propagation resistance increase for nonrelaxing conditions: by enabling strong secondary crack formation, those particular loading conditions allow the dissipation of much more energy than it would in a single crack propagation process (i.e., under relaxing conditions) and thus significantly reduce the global crack growth rate. It is interesting to note that the degree of branching increases with the crack length. This confirms previous observations made by Hamed et al. [31] under monotonic loading. However, the extent of secondary cracking in the present case is much larger than that observed by Hamed et al. Moreover, in our case, despite secondary cracking, the global crack propagation direction stays perpendicular to the applied loading direction, at least for crack sizes up to a few millimeters in size.

Using the tearing energy concept proposed by Lindley, there is a competition between the damage process controlled by the maximum tearing energy and a reinforcement process which induces the secondary cracking. However, the question of what induces this secondary cracking, and thus which mechanical parameter controls the reinforcement, is still open.

Crack branching and strain induced crystallization

Crack branching is a well known phenomenon in fracture mechanics. It can be due to the type of loading (high speed crack propagation, for example) or to some sort of anisotropy induced by the material (micro)structure (composite material, for example). Since one-dimensional fatigue loading has no natural propensity for inducing crack branching, the origin of crack branching must be found in the material itself. By comparing natural rubber behavior to that of synthetic rubbers, strain induced crystallization is most likely to play a major role in this process by creating a highly heterogeneous and anisotropic zone at the crack tip.

Under uniaxial tension, crystallization was found to start at about 150% strain (see Fig. 8). The maximum degree of crystallization of 25% was reached at approximatively 400% strain. The sharp reflections obtained on the X-ray diffraction patterns and associated pole figures have shown a well-developed three-dimensional structure, with the chain axis being along the tensile direction. Moreover, there is a rotational symmetry around the chain axis. These results are in accordance with already published results [32,4,33].

The sequential measurement procedure used makes it possible to characterize the induced microstructure. However, since WAXS diffractometer scans take at least 45 min to complete, no information could be obtained to characterize the dynamic behavior of strain induced crystallization and the effect of cyclic loading.

Toki [4] equiped a WAXS diffractometer with a special device which could stretch the sample at constant speed (55 mm/min). They followed the diffracted intensity of a unique peak (1 2 0) as function of the applied strain. They found that crystallites formation (loading) and fusion (un-loading) follow different kinetics, so that over a cycle, at a given elongation the degree of crystallinity is higher during un-loading than it is during loading. Further work of Toki [33] and Rault et al. [20] using in situ synchrotron X-ray, have shown similar results. However, they investigated the evolution of crystallinity over only one cycle and the effect of both non-relaxing conditions and several cycles has not been established. Moreover, the loading frequencies used in those studies were far from the one investigated here (10 -4 Hz for Rault et al. [20] versus 1 Hz in this study). Since it was not possible for us to equip our diffractometer with such a device, and that the measurement of crystallization dynamic at high strain rates is a challenge in itself, another parameter was used as a tracer of crystallinity: the global mechanical response. Indeed, since the upturn in modulus corresponds to the start of crystallization [4,33] (this point is still quite largely discussed in the literature since some authors have shown that crystallization might start earlier [3] but all agree that the upturn represents at least an upper bound for the minimum strain necessary for the crystallization to start), the evolution of the stress-strain response at high strains should give good information on the crystallinity evolution. More precisely, if the crystallization affects the local tangent modulus, any modification in the dynamic of strain induced crystallization (for example due to the type of loading applied) should produce an increase in the level of stress reached at a given elongation. Strain controlled cyclic tensile tests were performed with both relaxing and non-relaxing conditions. The maximum strain applied was chosen constant for both conditions ( max = 4.75). For non-relaxing conditions the minimum strain applied was changed at each cycle to increasing values ranging from min = 1.5 to max = 4. In this section, the term cycle will refer to a successive loading and unloading sequence. The applied strain path is given in Fig. 9(a). In order to clearly identify any stress softening or hardening effects the nondimensional quantity n is computed as follows:

n = max,n max,1 (4)
where max,1 (resp. max,n ) is the maximum stress reached during the first (resp. nth) cycle. Results are given in Fig. 9(b) and 10. Under relaxing conditions, the maximum stress slowly decreases at each cycle. This phenomenon is classically observed for rubbers and is known as the Mullins effect which can still take place (with far less intensity) despite the pre-stabilization. Under non-relaxing conditions, the maximum stress first decreases (stage 1), following the relaxing condition response, but then increases markedly as soon as the minimum strain reaches 75% (stage 2). The stress increase can be seen as a cyclic hardening or reinforcement of the material under these particular loading conditions. This reinforcement is able to overcome the softening effect (Mullins effect) since the maximum stress reached under non-relaxing conditions at the 7th cycle is 12% greater than the one reached at the very first cycle and 25% greater than the one reached under relaxing conditions. This result gives further understanding of the reinforcement mechanisms observed under fatigue testing under non-relaxing conditions and, to the authors' knowledge, has never been reported in the literature. This cyclic hardening can be understood as the result of a cumulative effect of crystallization under non-relaxing conditions. Indeed, if crystallization is not completely annealed at each cycle, every successive loading will induce a new increase in the crystallinity level until saturation is reached as shown by the evolution of max . This effect is also the consequence of the time dependance of strain induced crystallization: due to the cyclic nature of the loading, crystallization is not fully achieved during cyclic loading. However, it is still difficult to correlate the stress and crystallinity kinetics in a quantitative way (such a work implies real scientific challenges: [22], Alexander [34], Goppel [35] and Flory [15]. experimentally, crystallinity kinetics under dynamic loading have to be studied using synchrotron-WAXS and numerically, constitutive laws including strain induced phase transformation still have to be developed for those materials). After Toki [4], the evolution of the X-ray scattering intensity (i.e., apparent crystallization) under relaxing conditions is given in Fig. 11(a). Using those results we propose the evolution of the apparent crystallization for non-relaxing conditions as shown in Fig. 11(b). When the minimum strain is kept below a threshold value there is no cumulative effect. It should be noted that this threshold value is much lower than the strain needed to first crystallize. It is effectively observed on the stress response with a strain threshold around 75% whereas a 150% strain elongation is needed to first crystallize the natural rubber. Once the threshold is overcome, the cumulative effect can take place and cyclic hardening occurs. Stage 3 corresponds to the stabilization of the reinforcement process which is progressively overcome by stress relaxation mechanisms taking place at such high strain levels.

The strain rate effect observed in Fig. 10 can be explained by considering that since the crystallization takes time to settle, the higher the frequency, the lower the degree of crystallinity at the end of the test (at least using the particular strain path proposed here). The reinforcement should then be less pronounced for higher frequencies (higher strain rates). This trend has been observed on the presented experimental results.

Cumulative effect and crack branching

The aim here is to better understand from the previous results the microstructural evolution in the crack tip loading under relaxing and non-relaxing conditions. Under relaxing conditions the evolution of crystallinity follows the experimental results obtained by Toki [4] and can be modeled as shown in Fig. 11(a). At each cycle the crack tip is fully unloaded so that strain induced crystallization disappears and the crystallinity level restarts from zero. Under non-relaxing conditions, it is believed that a cumulative process takes place. The crystallinity in the crack tip region progressively increases until saturation, following the process proposed in Fig. 11(b). The degree and size of the crystallization zone at the crack tip is much larger than the ones reached under relaxing conditions. However, it has not been experimentally possible to fully demonstrate it by direct crystallinity measurement during this study. It should be noted that in order to demonstrate this cumulative process not only must the diffraction measurements be done at the same time as the deformation process but at loading frequencies sufficiently high to show this effect. The integration time of the measurement method must be compatible with the loading frequencies (a few Hz).

From the crack propagation process point of view, strong anisotropic microstructure takes place ahead of the crack tip when the cumulative process of crystallization takes place. In that case, the crack propagates continuously in an anisotropic media which results in symmetry being lost in the crack tip region and consequently the crack branching observed experimentally. This is illustrated in Fig. 12. Under uniaxial loading and relaxing conditions (Fig. 12(a)) the fatigue crack propagates normally to the loading direction and without strong deviation due to the weak anisotropy induced in the crack tip region. On the contrary, under uniaxial loading and non-relaxing conditions (Fig. 12(b)) the anisotropy caused by strain induced crystallization and the cumulative process (crystallites are symbolized by short vertical segments) makes the crack to deviate from the natural crack propagation direction. At any new crack tip formed, the process takes place again so that strong crack branching is observed as illustrated. Moreover, because the crack deviation process takes place at different scales simultaneously we obtain the fractal-like crack branching patterns observed. The proposed cumulative process confirms that when considering crack propagation modeling, both minimum and maximum tearing energies must be considered as proposed by Lindley [25]. However, from our observations it is believed that the cumulative process (reinforcement process) may influence not only the crack propagation threshold T x but would play a role throughout the propagation process.

Conclusions

Using SEM observations it was shown that the excellent fatigue resistance properties under non-relaxing conditions are related to strong crack branching extending in a fractal-like behavior during both the initiation and the propagation process. The crystallization process was studied using WAX diffraction. A cyclic hardening has been observed on a natural rubber using non-conventional stress-strain paths. This cyclic hardening was understood as the result of a cumulative process of strain-induced crystallization which progressively hardens the material. Toki's results on crystallization kinetics under relaxing conditions have been used to propose crystallization kinetics under non-relaxing conditions which explain the minimum tearing energy influence on crack propagation rates observed by Lindley et al. Further experimental and numerical work in that field are clearly needed. In particular, in situ synchrotron-WAXS during cyclic loading would be of great interest to better characterize the crystallization kinetics under cyclic loading. Also, constitutive laws taking into account time dependent strain induced phase transformation are needed in order to better assess the relationship between the strain level and the crystallinity level. Finally, comparisons with materials having different crystallization kinetics (modifying the filler type or using crystallizable synthetics rubbers) are needed.

Fig. 1 .

 1 Fig. 1. Specimen geometry used for fatigue tests (dimensions in mm).

Fig. 2 .

 2 Fig. 2. Computed and experimental diffraction spectrum for an elongation of = 4.

Fig. 3 .

 3 Fig. 3. Uniaxial fatigue test results and comparison with predicted results. (a) Haigh diagram. (b) Computed and experimental results.

Fig. 4 .

 4 Fig. 4. SEM image of a crack initiation under relaxing conditions on a diabolo specimen (loading ratio R = -0.3).

Fig. 5 .

 5 Fig. 5. SEM image of a crack initiation under non-relaxing conditions on a diabolo specimen (loading ratio R = 3.8).

Fig. 6 .

 6 Fig. 6. Relative position of the specimen surface S and the plane of observation P.

Fig. 7 .

 7 Fig. 7. Crack path under relaxing and non-relaxing conditions in a plane perpendicular to the crack propagation plane [31]. (a) Relaxing conditions (loading ratio R = -0.3). (b) Non-relaxing conditions (loading ratio R = 4.2).

Fig. 8 .

 8 Fig.8. Evolution of the crystallinity index as a function of applied elongation. Comparison with previously published results by Lee and Donovan[22], Alexander[34], Goppel[35] and Flory[15].

Fig. 9 .

 9 Fig. 9. Applied elongation path and Cauchy Stress response.

Fig. 10 .

 10 Fig. 10. Stress hardening for two different strain rates compared to the natural rubber behavior under relaxing conditions.

Fig. 12 .

 12 Fig. 12. Crack propagation process for relaxing and non-relaxing conditions (multiple crack branching obtained by repetition of this elementary sequence at the different scales). (a) Relaxing conditions. (b) Non-relaxing conditions.

Fig. 11 .

 11 Fig. 11. Crystallinity evolution under relaxing conditions adapted from Toki et al. [4] and proposed evolution under non-relaxing conditions. (a) Relaxing conditions. (b) Non-relaxing conditions.

Table 1

 1 Composition of the natural rubber in parts by weight phr.

	Rubber 100
	Zn oxide	10-20	Stearic acid	1
	Carbon black N772	20	Carbon black N330	3
	Sulfur	≥2	Plasticizers	5

Table 2

 2 Room temperature mechanical properties.

	Density (g/m 3 ) A shore	UTS (MPa)	ε fail (%)	300% elong.
		hardness			modulus (MPa)
	1.1	48	25.3	500	7.8