Guillaume Bonfante

Florian Deloup

Antoine Henrot

Polynomials over the reals are safe for program interpretations

In the field of implicit computational complexity, we are considering in this paper the fruitful branch of interpretation methods. Due to their good intensional properties, they have been widely developped. Among usual issues is the synthesis problem which has been solved by the use of Tarski's decision procedure, and consequently interpretations are usually chosen over the reals rather than over the integers. Doing so, one cannot use anymore the (good) properties of the natural (well-) ordering of N employed to bound the complexity of programs. We show that, actually, polynomials over the reals benefit from some properties that allows their safe use for complexity. We illustrate this by two characterizations, one of PTIME and one of PSPACE.

Among studies in rewriting are the noticeable work concerning termination. This is now a largely and thoroughly studied field and very elegant methods have been proposed that cover a large spectrum of algorithms (see for instance [START_REF] Dershowitz | Termination of rewriting[END_REF]). These studies can be refined to get a characterization of the complexity of first order programs. This has been one of the main successful approaches of implicit computational complexity, see for instance the early work [START_REF] Bonfante | Algorithms with polynomial interpretation termination proof[END_REF][START_REF] Cichon | The light lexicographic path ordering[END_REF].

To prove termination by interpretation over a well-founded ordering seems rather natural and such interpretation methods have been introduced in the 70's (see [START_REF] Lankford | On proving term rewriting systems are noetherien[END_REF][START_REF] Huet | Equations and rewrite rules: A survey[END_REF]). Lankford describes interpretations as monotone Σ-algebras with domain of interpretation being the natural numbers with their usual ordering. The fact that this ordering is well-founded gives immediately the wellfoundedness of the rewriting relation. Based on Kruskal's Theorem, Dershowitz showed in [START_REF] Dershowitz | A note on simplification orderings[END_REF] that the well-foundedness of the domain of interpretation is not necessary whenever the interpretations are chosen monotonic and have the subterm property.

One of the main interesting points about choosing of real numbers rather than natural numbers is that we get (at least from a theoretical point of view) a procedure to verify the validity of an interpretation of a program by Tarski's decomposition procedure [START_REF] Tarski | A Decision Method for Elementary Algebra and Geometry[END_REF]. But furthermore, we can even give a semi-algorithm to compute interpretations: indeed, for a given choice of the degree of the interpretations, finding the coefficients of these polynomial becomes decidable. Actually, since the problem of the verification or the synthesis (up to some degree) can be stated by a first order formula with two alternations of quantifiers, following Roy et al. [START_REF] Basu | Algorithms in real algebraic geometry[END_REF], the complexity of these algorithms is exponential with respect to the size of the program. To obtain a faster procedure, we have used in the crocus tool -developped by the first author-the (sufficient) criterion of Hong and Jakuš [START_REF] Hong | Testing positiveness of polynomials[END_REF].

A second good point is that the use of reals (as opposed to integers) enlarges the set of rewriting systems that have an interpretation, as shown recently by Lucas [START_REF] Lucas | On the relative power of polynomials with real, rational, and integer coefficients in proofs of termination of rewriting[END_REF].

The main concern of this work is to show that the structure of polynomials over the reals has an important role from the point of view of complexity. Our thesis is that, in the field of complexity, due to Stengle's Positivstellensatz [START_REF] Stengle | A nullstellensatz and a positivstellensatz in semialgebraic geometry[END_REF], polynomials over the reals can safely replace polynomials over the integers. To say it more precisely, one may recover both derivational complexity (up to a polynomial) and size bounds on terms as applications of the Positivstellensatz. Moreover, this can be done in a constructive way.

Given a strict interpretation for a Term Rewriting System (TRS), it follows immediately that for any rewriting step s → t, we have s > t . If one takes the interpretation on natural numbers (as they were introduced by Lankford [START_REF] Lankford | On proving term rewriting systems are noetherien[END_REF]), this can be used to give a bound on the derivation height. Thus, Hofbauer and Lautemann have shown in [START_REF] Hofbauer | Termination proofs and the length of derivations[END_REF] that the derivation height is bounded by a double exponential. However, their argument uses deeply the fact that the interpretation of a term is itself a bound on the derivation height:

dh(t) ≤ t . (1)
Indeed, suppose t 1 → t 2 → • • • → t n , then t 1 > t 2 > • • • > t n . On natural numbers, this means that n ≤ t 1 . Such a proof does not hold with real numbers.

Equation [START_REF] Basu | Algorithms in real algebraic geometry[END_REF] comes from the fact that t ≥ u + 1 for terms t → u. This fact itself is due to a)

> r implies that

≥ r + 1 (2)
and b) that for all x i > y i :

f (x 1 , . . . , x i , . . . , x n ) -f (x 1 , . . . , y i , . . . , x n ) ≥ x i -y i . (3)
The two inequalities (2), (3) do not hold in general for real interpretations. To recover the good properties holding with natural numbers, people have enforced the inequalities on terms. For instance [START_REF] Lucas | On the relative power of polynomials with real, rational, and integer coefficients in proofs of termination of rewriting[END_REF][START_REF] Marion | Characterizations of polynomial complexity classes with a better intensionality[END_REF] suppose the existence of some real δ > 0 such that ≥ r + δ. We prove that this is not necessary. The mathematical structure of polynomials over the reals has also been considered by Shkaravska et al [START_REF] Shkaravska | Polynomial size analysis of first-order shapely functions[END_REF] with the intention to compute the size of terms appearing in computations.

One of our two characterization use dependency pairs. In this vein, we mention here the work of Hirokawa and Moser [START_REF] Hirokawa | Automated complexity analysis based on the dependency pair method[END_REF], and, in the same spirit, Lucas and Peña in [START_REF] Lucas | Rewriting techniques for analysing termination and complexity bounds of safe programs[END_REF] made some investigation on the tools of rewriting to tackle the complexity of first order functional programs. In particular, they provide a certified compilation procedure to the JVM.

Preliminaries

We suppose that the reader has familiarity with first order rewriting. We briefly recall the context of the study, essentially to fix the notations. Dershowitz and Jouannaud's survey [START_REF] Dershowitz | Handbook of Theoretical Computer Science[END_REF] of rewriting is a good entry point.

Syntax of programs

All along, X will denote a set of variables, C a (finite) signature of constructor symbols and F a (finite) signature of function symbols.

Definition 1. The sets of terms and the rules are defined in the following way:

(Constructor terms) T (C) u ::= c | c(u 1 , • • • , u n ) (terms) T (C, F, X ) t ::= c | x | c(t 1 , • • • , t n ) | f(t 1 , • • • , t n ) (patterns) P p ::= c | x | c(p 1 , • • • , p n ) (D-rules) D d ::= f(p 1 , . . . , p n ) → t
where x ∈ X , f ∈ F, and c ∈ C.

We shall use a type writer font for function symbols and a bold face font for constructors. Finally, we use u to denote a (finite) sequence of terms u 1 , . . . , u n . The size of a term is the number of symbols occuring in the term. It is written |t|. Definition 2. A program is a quadruplet f = X , C, F, E such that E is a finite set of D-rules. Each variable in the right-hand side of a rule also appears in the left hand side of the same rule. We distinguish among F a main function symbol whose name is given by the program name f.

The set of rules induces a rewriting relation →. The relation * → is the reflexive and transitive closure of →. We write t 0 → n t n the fact that t 0 → t 1 • • • → t n . One defines the derivation height for a term t as the maximal length of a derivation:

dh(t) = max{n ∈ N | ∃v : t → n v}.
Moreover, we suppose programs to be confluent. This is achieved by the following syntactic restriction due to Huet [START_REF] Huet | Confluent reductions: Abstract properties and applications to term rewriting systems[END_REF]

: (i) Each rule f(p 1 , • • • , p n ) → t is left-linear, that is a variable appears only once in f(p 1 , • • • , p n ),
and (ii) there are no two left hand-sides which are overlapping. Such programs are called orthogonal.

A substitution σ is a mapping from variables to terms. We say that it is a constructor substitution when the range of σ is T (C).

Orthogonal programs define a class of deterministic first order functional programs. The domain of the computed functions is the constructor term algebra T (C). The program f computes a partial function f : T (C) n → T (C) defined as follows. For every

u 1 , • • • , u n ∈ T (C), f (u 1 , • • • , u n ) = v iff f(u 1 , • • • , u n ) * →v. Otherwise, it is undefined and f (u 1 , • • • , u n ) = ⊥.
Definition 3 (Call-tree). Suppose we are given a program X , C, F, E . Let be the relation

(f, t 1 , . . . , t n ) g(u 1 , . . . , u m ) ⇔ f (t 1 , . . . , t n ) → C[g(v 1 , . . . , v m )] * →C[g(u 1 , . . . , u m )]
where f and g are defined symbols, and t 1 , . . . , t n , u 1 , . . . , u m are constructor terms. Given a term f (t 1 , . . . , t n ), the relation defines a tree whose root is (f, t 1 , . . . , t n ) and η is a daughter of η iff η η . The size of a call-tree is the number of nodes it contains.

When we do not make a distinction between constructors and function symbols, we speak of Term Rewriting System (TRS). We present them as 3-tuple (X , Σ, R) where Σ is the signature and R is the set of rules.

Interpretations of programs

Given a signature Σ, a Σ-algebra on the domain A is a mapping -which associates to every n-ary symbol f ∈ Σ an n-ary function f : A n → A. A Σ-algebra can be extended to terms by x = 1 A , that is the identity on A, for x ∈ X , f (t 1 , . . . , t m ) = comp( f , t 1 , . . . , t m ) where comp is the composition of functions.

The interpretation t of a term t with n variables is then a function A n → A.

An interpretation for a rewriting system (Σ, R) is an order-preserving mapping -from (T (Σ), + →) to some (partially) ordered set (A, >). From now on, we restrict our attention to the case where (A, >) is the set of nonnegative real numbers R + with the usual ordering and -has the structure of a Σ-algebra: Definition 4. A polynomial strict interpretation of a rewriting system (Σ, R) is given by a Σ-algebra -such that:

1. for all symbol f , the interpretation f is a monotonic polynomial, that is if

x i > x i , then f (x 1 , . . . , x n ) > f (x 1 , . . . , x i , . . . , x n ),
2. for all symbol f , the interpretation f verifies the (weak) sub-term property, that is

f (x 1 , . . . , x n ) ≥ x i with i ∈ 1..n, 3
. for all rules → r, > r .

Example 1. Consider the system

A(B(x)) → B(B(A(x))) c(A(x)) → A(A(c(x)))
For this system, we define the interpretation A (x) = 3(x + 2), B (x) = x + 1 and c (x) = x 2 + 1. [START_REF] Marion | Resource analysis by sup-interpretation[END_REF]. We give a slight variant of their definition. In [START_REF] Marion | Resource analysis by sup-interpretation[END_REF], the last inequality refers to the size of normal forms. We prefered to have a more uniform definition. Definition 5. A (polynomial) sup-interpretation of a rewriting system (Σ, R) is given by a Σ-algebra -such that:

Sup-interpretation have been introduced by Marion and Pechoux in

1. f is a weakly monotonic polynomial, that is if

x i ≥ x i , then f (x 1 , . . . , x n ) ≥ f (x 1 , . . . , x i , . . . , x n ),
2. for all constructor terms t 1 , . . . , t n , we have the inequality

f (t 1 , . . . , t n ) ≥ f (t 1 , . . . , t n ) .
Lemma 1. Suppose that we are given a Σ-algebra for which interpretations of symbols f is bounded by some polynomials. Then, for all closed terms, t ≤ 2 2 O(|t|) .

Proof. By induction on terms. A proof (for natural numbers, but this has no consequences here) can be found in [START_REF] Bonfante | Algorithms with polynomial interpretation termination proof[END_REF]. Definition 6. An interpretation of a program is said to be additive if for all constructor c, we have c (x 1 , . . . , x n ) = n i=1 x i + c c for some constant c c > 0.

Positivstellensatz and applications

In this subsection, we introduce a deep mathematical result, the Positivstellensatz. Then we give some applications to polynomial interpretations. They will be key points of the Theorems 4 and 6 in our analysis of the role of reals in complexity ( §3).

Let n > 0. Denote by R[x 1 , . . . , x n ] the R-algebra of polynomials with real coefficients. Denote by (R + ) n = {x = (x 1 , . . . , x n ) ∈ R n | x 1 , . . . , x n > 0} the first quadrant. Since we need to consider only the R-algebra of polynomial functions (R + ) n → R, it will be convenient to identify the two spaces. In particular throughout this section, all polynomial functions are defined on (R + ) n .

Preliminary results Definition

7. A polynomial P ∈ R[x 1 , . . . , x n ] is said over-homogeneous of level d if there exists A, α > 0 such that for any λ > α and any x ∈ (R + ) n , ||x|| > A =⇒ P (λx) ≥ λ d P (x).
Remark . This notion is essentially independent of the chosen norm on R n . We say that P is (A, α)-over-homogeneous when we need to specify the bounds (A, α). In this case, the bounds depend on the choice of the norm

|| • || on R n . Lemma 2. Let Q ∈ R[x 1 , . . . , x n ] an over-homogeneous polynomial of level d ≥ 1 such that there is some r > A such that inf ||x||=r Q(x 1 , . . . , x n ) > 0 For any C > 0, there is D > 0 such that ||x|| > D =⇒ Q(x) > C. Proof. Let us write α = inf ||x||=r Q(x) > 0. One observes that Q(λx) ≥ λ d Q(x) ≥ λ d α > C for all λ > (C/α) 1/d = D. Lemma 3. Let Q ∈ R[x 1 , . . . , x n ] an over-homogeneous polynomial of level d ≥ 1. (i) If there is x ∈ (R + ) n such that P (x) ≥ 0 then P (λ x) ≥ 0 for all λ ≥ 0;
furthermore, the same statement holds with all inequalities replaced by strict inequalities. (ii) If there is x ∈ (R + ) n such that P (x) < 0 then P (λ x) < 0 for all λ > 0;

Proof. (i): P (λ x) ≥ λ d P (x) ≥ 0. (ii): arguing by contradiction, suppose there is λ 0 > 0 such that P (λ 0 x) > 0. Then by (i), P (λx) > 0 for all λ > 0. Hence P (x) > 0, which is a contradiction.

Lemma 4. Given P ∈ R[x 1 , . . . , x n ], a over-homogeneous polynomial of level d ≥ 2 such that ∀x ∈ (R + ) n , ||x|| > B =⇒ P (x) ≥ 0 for some constant C. Suppose that Q is over-homogeneous of level k with 1 ≤ k < d. Then, P + Q is over-homogeneous of level k.
Proof. Suppose that P is (A, α)-over-homogeneous and Q is (B, β)-over-homogeneous.

Let C = max(A, B). For ||x|| > C, λ > max(1, α, β), P (λx) + Q(λx) ≥ λ d P (x) + λ k Q(x) ≥ λ k P (x) + λ k Q(x) since P (x) ≥ 0 = λ k (P + Q)(x)
Given a polynomial P ∈ R[x 1 , . . . , x n ], we can decompose it in homogeneous components P = P d + P d-1 + • • • P 0 with each P i of degree i. Furthermore we note P ≥k the polynomial

d i=k P i . Lemma 5. Let P ∈ R[x 1 , . . . ,
x n ] of total degree greater than 1. Suppose that there is some C > 0 such that for all k ≥ 0, and all x ∈ (R + ) n with ||x|| > C, we have P (x) > 0. Then, P ≥k is over-homogeneous of level k for 1 ≤ k ≤ d and P ≥k (x) > 0 with ||x|| > C for some C .

Proof. By descending induction on k ≤ d. For the base case, P ≥d = P d is homogeneous, hence over-homogeneous, of level d. Moreover, P d has the sign of P for ||x|| > C (1 ) hence P d is nonnegative for ||x|| > C. Since each P i is homogeneous (and consequently over-homogeneous) of level i, the induction step is a direct consequence of Lemma 4.

Theorem 1. Given a polynomial P ∈ R[x 1 , . . . , x n ] such that (i) ∀x 1 , . . . , x n ≥ 0 : P (x 1 , . . . , x n ) > max(x 1 , . . . , x n ), then, there exist A ≥ 0 such that P (x 1 , . . . , x n ) > x 1 +• • •+x n whenever ||x|| > A.
Proof. Let d = deg(P ). Without loss of generality, we may assume that P (0) = P 0 = 0. For d = 1, the theorem is easily seen to hold. Assume that d > 1. Note that (i) implies that P (x) > 0 if x = 0 (x is assumed to lie in (R + ) n as usual). Applying Lemma 5, we see that P ≥k is positive and over-homogeneous of level k for any 1 ≤ k ≤ d. Lemma 6. If P is positive, over-homogeneous of level k ≥ 2 and satisfies the hypothesis (i), then for any K > 0, there exists

A = A K > 0 such that P (x 1 , . . . , x n ) > K(x 1 + • • • + x n ) whenever ||x|| > A.
In particular, the theorem holds.

Proof of the Lemma. Let x = (x 1 , . . . , x n ) ∈ (R + ) n , let λ ∈ R + and let X = λ x. We have

P (X) = P (λ x) ≥ λ k P (x) ≥ λ k max(x 1 , . . . , x n ) ≥ λ k x 1 + • • • + x n n = λ k-1 X 1 + • • • + X n n .
Since k ≥ 2, there exists A ≥ 0 such that for any λ > A, λ k-1 n > K > 0. This proves the lemma.

In particular the theorem holds if P has no homogeneous component P 1 of degree 1. We now complete the proof when

P 1 (x) = a 1 x 1 + • • • + a n x n = 0.
Lemma 7. P ≥2 = P -P 1 satisfies the hypothesis (i).

Proof of the lemma. Argue by contradiction and suppose it does not. There exists then x = (x 1 , . . . , x n ) ∈ (R + ) n such that P ≥2 (x) -x i ≤ 0 for some fixed 1 ≤ i ≤ n. Since P ≥2 (x) is over-homogeneous, Lemma 4 ensures that the polynomial Q(x) = P ≥2 (x) -x i is over-homogeneous of level 1. By Lemma 3, Q(λx) = P ≥2 (λ x) -λ x i ≤ 0 for any λ ≥ 0. Since P ≥2 is positive, the map λ → P ≥2 (λx) is a positive polynomial of degree d. Thus

lim λ→+∞ P ≥2 (λx) -λx i = +∞, which is a contradiction. Apply Lemma 6 to P ≥2 with K = 1+max(|a 1 |, . . . , |a n |). We obtain P ≥2 (x) > K(x 1 + • • • + x n ). Hence P (x) = P ≥2 (x) + P 1 (x) > (K + a 1 )x 1 + • • • + (K + a n )x n > x 1 + • • • + x n .
This achieves the proof of the theorem.

Corollary 1. Let P (x 1 , . . . , x n ) be a polynomial with the hypotheses of Theorem 1. There is a constant A such that for any subset I ⊆ {1..n}, such that

x 1 , . . . , x n ≥ 0, x i ≥ A, for all i ∈ I =⇒ P (x 1 , . . . , x n ) > i∈I x i . Proof. Use the norm ||x|| = max(|x 1 |, . . . , |x n |). Theorem 2. Given a polynomial P ∈ R[x 1 , . . . , x n ] such that (i) ∀x 1 ≥ 0, . . . , x n ≥ 0 : P (x 1 , . . . , x n ) > max(x 1 , . . . , x n ), (ii) ∀x 1 ≥ 0, . . . , x n ≥ 0 : ∂P ∂x i (x 1 , . . . , x n ) > 0 for all i ≤ n,
then, there exist A > 0 such that for any ∆ > 0, we have P (x 1 , . . . , x i + ∆, . . . , x n ) > P (x 1 , . . . , x n ) + ∆ whenever ||x|| > A.

Proof. For simplicity we take n = 2 (the reader will readily extend the argument to the general case) and we make an analysis by case. Consider the case where P (x, y) = P 0 (y) + xP 1 (y). Let us consider ∂P ∂x (x, y) = P 1 (y). First , we prove that P 1 (y) ≥ 1 for all y ≥ 0. Ad absurdum, suppose that P 1 (y) < 1. Then, take

x > P 0 (y) 1 -P 1 (y) > 0. Due to (i), we have

P (x, y) -x = P 0 (y) + x(P 1 (y) -1) > 0. (4)
Since P 1 (y) -1 < 0 and x > P 0 (y) 1 -P 1 (y) > 0, we have P 0 (y) + x(P 1 (y) -1) < P 0 (y) + P 0 (y) 1 -P 1 (y) × (P 1 (y) -1) = 0 which contradicts (4).

In particular, for y large enough, P 1 (y) > 1. The conclusion follows by the mean value inequality.

Consider now

∂P ∂y (x, y) = P 0 (y) + xP 1 (y). Suppose P 1 (y 0 ) < 0 for some

y 0 > 0. Then lim x→∞ ∂P ∂y (x, y 0 ) = lim x→∞ P 0 (y 0 ) + xP 1 (y 0 ) = -∞.
This contradicts (ii). So, P 1 (y) ≥ 0. Now, P (0, y) = P 0 (y) > y shows that P 0 (y) -1 ≥ 0 for y sufficiently large, say y > A. Then we have ∂P ∂y (x, y) = P 0 (y) + xP 1 (y) > 1. We conclude as before.

The case P (x, y) = Q 0 (x, y) + yQ 1 (x, y) is symmetric. So the remaining case is when deg x (P ) ≥ 1 and deg y (P ) ≥ 1. Thus Q := ∂P ∂x is positive and has total degree greater than 2. According to Lemma 5, Q ≥1 is positive over-homogeneous.

Hence Lemma 2 applies to Q ≥1 with C = 1 + ∂P ∂x (0, 0) . Hence there is some

D > 0 such that for ||(x, y)|| > D, ∂P ∂x (x, y) = Q ≥1 (x, y) + Q(0, 0) > 1 + C + ∂P ∂x (0, 0) > 1.
We conclude with the mean value inequality.

Corollary 2. With the hypotheses of Theorem 2, there is a bound B such that for all x 1 , . . . , x n ≥ 0, if x i > B, then, P (x 1 , . . . , x i +∆, . . . , x n ) > P (x 1 , . . . , x n )+ ∆.

Proof. Apply Theorem 2 with the norm ||x|| = max(|x 1 |, . . . , |x n |).

Positivstellensatz and applications

Theorem 3 (Positivstellensatz, Stengle [START_REF] Stengle | A nullstellensatz and a positivstellensatz in semialgebraic geometry[END_REF]). Suppose that we are given polynomials P 1 , . . . , P m ∈ R[x 1 , . . . , x k ], the following two assertions are equivalent:

1. {x 1 , . . . , x k :

P 1 (x 1 , . . . , x k ) ≥ 0 ∧ • • • ∧ P m (x 1 , . . . , x k ) ≥ 0} = ∅ 2. ∃Q 1 , . . . , Q m : -1 = i≤m Q i P i
where each Q i is a sum of squares of polynomials (and so is positive and monotonic).

Moreover, these polynomials Q 1 , . . . , Q i can effectively computed. We refer the reader to the work of Lombardi, Coste and Roy [START_REF] Lombardi | Effective real nullstellensatz and variants[END_REF][START_REF] Coste | Dynamical method in algebra: Effective nullstellensätze[END_REF]. As a consequence, all the constructions given below can be actually (at least theoretically) computed.

It will be convenient to derive from the Positivstellensatz a proposition useful for our applications. Proposition 1. Let (P i ) i∈I and (Q j ) j∈J two finite families of polynomials in R[x 1 , . . . , x n ]. Suppose that max i∈I P i (x) > max j∈J Q j (x) for all x ∈ (R + ) n . Then there exists a polynomial R ∈ R[x 1 , . . . , x n ] such that R(x) > 0 and max

i∈I P i (x) ≥ max j∈J Q j (x) + 1 R(x)
, for all x ∈ (R + ) n .

Proof. First we prove the result when J is a singleton. Suppose that max i∈I P

i (x) > Q(x) for all x ∈ (R + ) n . Let s ∈ I. Define D s = {x ∈ (R + ) n : P s (x) ≥ P i (x) for all i = s}.
For x ∈ D s , P s (x) = max i∈I P i (x) > Q(x). Therefore the set

   x 1 ≥ 0, . . . , x n ≥ 0, P s (x) -P i (x) ≥ 0, for alli = s, Q(x) -P s (x) ≥ 0    is empty. The Positivstellensatz yields positive monotonic polynomials (T k ) 1≤k≤n , (U i ) i =s and V s such that k U k (x)x k + i =s T i (x)(P s (x) -P i (x)) + V s (x)(Q(x) -P s (x)) = -1.
Hence for x ∈ D s ,

(P s (x) -Q(x))V s (x) = 1 + i =s T i (x)(P s (x) -P i (x)) ≥ 1. Thus ∀x ∈ D s , max i∈I P i (x) -Q(x) ≥ 1 V s (x)
.

Hence, setting R(x) = s∈I V s (x) > 0, we have

∀x ∈ (R + ) n , max i∈I P i (x) -Q(x) ≥ 1 R(x)
.

Next, we treat the general case. The previous argument yields for each j ∈ J a positive monotonic polynomial R j such that max

i∈I P i (x) -Q j (x) ≥ 1 Rj (x) for all x ∈ (R + ) n . Set R(x) = j∈J R j (x). For any j ∈ J, max i∈I P i (x) ≥ Q j (x) + 1 R(x)
.

Hence max i∈I P i (x) ≥ max j∈J Q j (x) + 1 R(x) .
We give a first application.

Proposition 2. Suppose that a TRS (Σ, R) admits an interpretation -over Max-Poly such that for all rules → r, we have > r . There is a positive, monotonic polynomial P such that for any rule → r, we have

(x 1 , . . . , x k ) - r (x 1 , . . . , x k ) ≥ 1 P (x 1 , . . . , x k ) .
Proof. For each symbol , there is a finite family of polynomials (P i ) i∈I such that (x 1 , . . . , x n ) = max i∈I P i (x 1 , . . . , x n ). Therefore, if > r , Proposition 1 applies: there is a positive monotonic polynomial P →r such that such that

(x 1 , . . . , x k )-r (x 1 , . . . , x k ) ≥ 1 P →r (x 1 , . . . , x k )
. Since there are only finitely many rules, we can take P = →r∈R P →r . Proposition 2 has an important consequence. Since, in a derivation all terms have an interpretation bounded by the interpretation of the first term, there is a minimal decay for each rule of the derivation. Proposition 3. Suppose that a TRS (Σ, R) admits a strict interpretationover Max-Poly. For all A > 0, the set of terms {t ∈ T (Σ) | t < A} is finite.

Proof. For all symbols f ∈ Σ, we have f (x 1 , . . . , x n ) > x i for all i. By Proposition 2, there is a polynomial P such that f (x 1 , . . . , x n ) ≥ x i + 1 P (x 1 , . . . , x n ) .

Take a term f (t 1 , . . . , t n ) such that f (t 1 , . . . , t n ) < A.

f (t 1 , . . . , t n ) ≥ t i + 1 P ( t 1 , . . . , t n ) ≥ t i + 1 P (A, . . . , A)
where the second inequality is due to the sub-term property together with the monotonicity of P . Consequently, the height of a term t with t < A is bounded by A × P (A, . . . , A). There are only finitely many such terms. Proposition 4. Suppose that a TRS (Σ, R) admits a strict interpretationover Poly. There is a real A > 0 and a positive, monotonic polynomial P such that for all x 1 , . . . , x n ≥ 0, if x i1 , . . . , x i k > A, then for all symbol f , we have

f (x 1 , . . . , x n ) ≥ x i1 + • • • + x i k + 1 P ( f (x 1 , . . . , x n ))
.

Proof. Due to Corollary 1, there is a bound A such that for all x 1 , . . . , x n ≥ 0, if x i1 , . . . , x i k > A, then for all symbol f , we have

f (x 1 , . . . , x n ) > x i1 +• • •+x i k . Applying Theorem 3, we get Q f such that f (x 1 , . . . , x n ) ≥ x i1 + • • • + x i k + 1 Q f (x 1 , . . . , x n ) ≥ x i1 + • • • + x i k + 1 Q f ( f (x 1 , . . . , x n ), . . . , f (x 1 , . . . , x n ))
. It is then routine to get a uniform polynomial wrt to all symbols.

The role of reals in complexity

We have now all the tools to prove that reals can safely replace integers from a complexity point of view. This is illustrated first by the following theorem.

Theorem 4. Functions computed by programs with an additive interpretation (over the reals) are exactly Ptime functions.

The rest of the section is devoted to the proof of the Theorem. The main difficulty of the proof is that inequalities as given by the preceding section only hold for sufficiently large values. So, the main issue is to split "small" terms (and "small rewriting steps") from "large" ones. The Positivstellensatz gives us the arguments for the large terms (Lemma 8), Lemmas 9,10 show that there are not too many small steps. Lemma 12 describe how small steps and big steps alternate.

From now on, we suppose we are given a program with an additive strict interpretation over polynomials. Lemma 8. There is a polynomial P and a real A > 0 such that for all step σ → rσ with rσ > A, then, for all context C, we have

C[ σ] ≥ C[rσ] + 1 P ( σ ) .
Proof. From Proposition 2, we have a polynomial P such that -r > 1 P .

From 2, we have a uniform bound A such that for all symbol f , f (x 1 , . . . ,

x i + ∆, . . . , x n ) ≥ f (x 1 , . . . , x n )+∆ if x i > A.
The Lemma is then obtained by induction on the context C. For the base case, we have σ ≥ rσ + 1 P ( t 1 , . . . , t n ) where t 1 , . . . , t n are in the range of σ. By sub-term property, t i ≤ σ , so that σ ≥ rσ + 1 P ( σ , . . . , σ )

. Using A as defined above, the induction step is immediate (by the sub-term property).

Definition 8. Given a real A > 0, we say that the A-size of a closed term t is the number of subterms u of t (including itself ) such that u > A. We note |t| A the A-size of t.

Lemma 9. There is a constant A and a polynomial Q for which

|t| A ≤ Q( t ) for all closed terms t. For all B > A, |t| B ≤ |t| A ≤ Q( t ).
Proof. Take A and P as given by Proposition 4. Consider one term t, we note

a = 1 P ( t )
. By induction on sub-terms u of t, we show that |u| A ≤ u /a.

If u ≤ A, then |u| A = 0 ≤ t /a. Otherwise, u > A. Let us write u = f (u 1 , . . . , u n ), and say that u i1 , . . . , u i k verify u ij > A. Then,

|u| A = 1 + |u i1 | A + • • • + |u i k | A ≥ (a + u i1 + • • • + u i k )/a (by induction) ≥ ( 1 P ( u ) + u i1 + • • • + u i k )/a (sub-term property) ≥ f (u 1 , . . . , u n ) /a (due to Proposition 4).
As a consequence, |t| A ≤ t × P ( t ).

For A > 0, we say that t = C[ σ] → C[rσ] = u is an A-step whenever rσ > A. We note such a rewriting step t → >A u. Otherwise, it is an ≤ A-step, and we note it t → ≤A u. We use the usual * notation for transitive closure. In case we restrict the relation to the call by value strategy2 , we add "cbv" as a subscript. Take care that an → ≤A -normal form is not necessarily a normal form for →.

Lemma 10. There is a constant A and a polynomial P such that for all terms t, any call by value derivation t → * ≤A,cbv u has length less than P ( t ).

Proof. Take A and P as in the Lemma above. Let S be the finite set of terms with interpretation smaller than A. According to Proposition 2, the set S is finite. Then, we can define a to be the maximal derivation length of terms in S. Let d be the maximal arity of a term. By induction on terms, we show that the derivation length t → * ≤A,cbv u of ≤ A-steps is bounded by max(|t| A × (d + 1) × (a + 1), a).

-If t ≤ A,
m ≤ (n -k) × a + (d + 1) × (a + 1) × k j=1 |t ij | A ≤ d × a + (d + 1) × (a + 1) × k j=1 |t ij | A . Consider f (u 1 , . . . , u n ), if f (u 1 , . . . , u n ) is not a ≤ A-normal form, since the u i are ≤ A-normal form, a ≤ A-step is of the form f (u 1 , . . . , u n ) → u with u ≤ A.
In which case, the derivation length of u is bounded by a. To sum up, the derivation length is then bounded by 1

+ a + d × (a + 1) + (d + 1) × (a + 1) × k j=1 |t ij | A = (d + 1) × (a + 1) × |t| A .
Using the Lemma above, |t| A ≤ P ( t ), and consequently, the derivation length is bounded by (d + 1) × (a + 1) × P ( t ). Lemma 12. Let us suppose we are given an additive program with interpretation in Poly. For a given function symbol f , there is a strategy such that for all constructor terms t 1 , . . . , t n , the derivation length of f (t 1 , . . . , t n ) is bounded by

Q(max(|t 1 |, . . . , |t n |)) where Q is a polynomial.
Proof. Let us consider A and P 0 as defined in Lemma 10 and B and P 1 as defined in Lemma 8. We define C = max(A, B). Let us consider the strategy as introduced above: rewrite as long as possible the according to → ≤C,cbv , and then, apply an C-step. That is, we have t 1 → * ≤C,cbv t 1 → >C,cbv t 2 → * ≤C,cbv t 2 → * . In Lemma 10, we have seen that there are at most (d + 1) × a × P 0 ( t i ) steps in the derivation t i → * ≤C,cbv t i . From Lemma 8, we can state that there are at most t 1 × P 1 ( t 1 ) such C-steps. Consequently, the derivation length is bounded by

t 1 × P 1 ( t 1 ) × (1 + (d + 1) × a × P 0 ( t 1 )) since t i < t 1 . Consider now a function symbol f ∈ F, from Lemma 11, f (t 1 , . . . , t n ) = f ( t 1 , . . . , t n ) ≤ f (Γ max(|t 1 |, . . . , |t n |), . . . , Γ max(|t 1 |, . . . , |t n |)). The con- clusion is immediate.
Proof (Theorem 4). With the strategy defined above, we have seen that the derivation length of a term f (t 1 , . . . , t n ) is polynomial wrt to max(|t 1 |, . . . , |t n |). The computation can be done in polynomial time due to dal Lago and Martini, see [START_REF] Dal | Derivational complexity is an invariant cost model[END_REF], together with the fact that the normal form has polynomial size (Lemma 11). For the converse part, we refer the reader to [START_REF] Bonfante | Algorithms with polynomial interpretation termination proof[END_REF] where a proof that Ptime programs can be computed by functional programs with strict interpretations over the integers. This proof can be safely used in the present context.

Dependency Pairs with polynomial interpretation over the reals

Termination by Dependency Pairs is a general method introduced by Arts and Giesl [START_REF] Thomas | Termination of term rewriting using dependency pairs[END_REF]. It puts into light recursive calls.

Suppose

f (t 1 , . . . , t n ) → C[g(u 1 , . . . , u n )
] is a rule of the program. Then, (F (t 1 , . . . , t n ), G(u 1 , . . . , u n )) is a dependency pair where F and G are new symbols associated to f and g respectively. S(C, F, R) denotes the program thus obtained by adding these rules. The dependency graph links dependency pairs (u, v) → (u , v ) if there is a substitution σ such that σ(v) * →σ(u) and termination is obtained when there is no cycles in the graph. Since the definition of the graph involves the rewriting relation, its computation is undecidable. In practice, one gives an approximation of the graph which is bigger. Since this is not the issue here, we suppose that we have a procedure to compute this supergraph which we call the dependency graph.

Theorem 5. [Arts,Giesl [START_REF] Thomas | Termination of term rewriting using dependency pairs[END_REF]] A TRS (C, F, R) is terminating iff there exists a well-founded weakly monotonic quasi-ordering ≥, where both ≥ and > are closed under substitution, such that -≥ r for all rules → r, s ≥ t for all dependency pairs (s, t) on a cycle of the dependency graph and s > t for at least one dependency pair on each cycle of the graph.

It is natural to use the polynomial orderings presented above for the quasiordering and the ordering of terms. However, the ordering > is not well-founded on R, so that system may not terminate. Here is such an example.

Example 2. Consider the non terminating system:

f (0) → 0 f (x) → f (s(x))
Take 0 = 1, s (x) = x/2. The system has a unique dependency pair F (x) → F (s(x)) for which we can give the interpretation F (x) = x+1. 3 Take f (x) = x.

One way to avoid these infinite descent is to force the inequalities over reals to be of the form P (x 1 , . . . , x n ) ≥ Q(x 1 , . . . , x n )+δ for some δ > 0 (see for instance Lucas's work [START_REF] Lucas | Practical use of polynomials over the reals in proofs of termination[END_REF]). Doing so, one gets a well-founded ordering on reals. We propose an alternative approach to that problem, keeping the original ordering of R. Definition 9. A weak polynomial4 algebra for a signature Σ consists of monotone polynomials f for all symbols in Σ.

Definition 10. A R-DP-interpretation for a program P = (C, F, R) is weak polynomial algebra -for S(P ) such that 1. there is δ > 0 such that for each n-ary constructor c with n > 0, for all x 1 , . . . , x n ≥ 0, we have c (x 1 , . . . , x n ) ≥ δ, 2.

≥ r for → r ∈ R, 3. s ≥ r for (s, r) ∈ DP (R), 4. for each dependency pair (s, t) in a cycle, s > r holds.

The main difference with say [START_REF] Marion | Characterizations of polynomial complexity classes with a better intensionality[END_REF] is that we do not ask for the existence of some δ such that s ≥ r + δ in the last equation. To simplify the proof of Theorem 6, we took s > t for all dependency pairs in a cycle, and not for only one. We make the conjecture that the theorem holds, even in the standard case: for each cycle, there is a dependency pair (s, t) such that s > r .

Lemma 13. Suppose that a polynomial P is weakly monotonic in every argument on (R + ) n . Suppose that it is not constant wrt some variable. Then for any arbitrarily small δ > 0, there is a polynomial P δ such that for all x 1 ≥ δ, . . . , x n ≥ δ, if x i ≥ P δ (A) for some i, then P (x 1 , . . . , x n ) ≥ A.

Proof. Consider first that n = 1. We write P (x) = ax k + R(x) with k being the degree of P . There is B > 0 such that for all x > B, we have P (x) ≥ a/2x k .

Then, define P δ (A) = 1 + B + 2 a × A. We observe P (x) ≥ P (P δ (A)) by monotonicity

≥ a 2 (P δ (A)) k since P δ (A) > B ≥ a 2 P δ (A) since P δ (A) > 1 ≥ A by definition of P δ (A)
For a polynomial with n + 1 variable P (x 1 , . . . , x n+1 ). Let us consider one of the variables. Wlog, we take it to be the last one: x n+1 . Then, for an arbitrary small δ, P is not constant wrt x n+1 . And, for all x 1 , . . . , x n ≥ δ, we have P (x 1 , . . . , x n , x n+1 ) ≥ P (δ, . . . , δ, x n+1 ) by monotonicity. Define Q(x n+1 ) = P (δ, . . . , δ, x n+1 ), and we come back to the case with one variable. Theorem 6. A program with a R-DP-interpretation is strongly terminating. Moreover, its derivation height is bounded by

2 2 2 O(n)
with n the size of the input. This bound is tight.

Proof. Since, in the present terms, the hypothesis of the Theorem 5 do not hold, we come back to its proof and show that we have an extra-ingredient to get the termination property. Actually, we give a presentation of the proof by means of call-tree. Since the size of a call tree gives an upper bound on the derivation height, we get a direct more proof for our Theorem.

Let us consider the call-tree of a term f (t 1 , . . . , t n ) for some constructor terms t 1 , . . . , t n . The size of the call tree bounds the derivation height of the term f (t 1 , . . . , t n ). Suppose that we prove that there is a polynomial P such that the height of the call tree is polynomial wrt to the interpretation of F (t 1 , . . . , t n ). Since the branching of the call-tree is bounded by R the maximal size of the right hand side of rules, the size of the call-tree is bounded by R P ( f (t1,...,tn) ) . But, since F (t 1 , . . . , t n ) ≤ 2 2 O(|F (t 1 ,...,tn)|) by Lemma 1, we have P (

F (t 1 , . . . , t n ) ) ≤ P (2 2 O( n i=1 |t i |+1) ) = 2 2 O(max n i=1 |t i |)
. And, the conclusion follows. So, it remains to prove that the existence of such a polynomial P . This is done by induction on the rank of symbols. But, first, consider a rule f (p i )σ → C[g(e i )]σ with f and g of same rank. Then, we have F (p i ) > G(e i ) . Notice that Proposition 2 applies in the present context for dependency pairs of same rank, so that we can state that F (p i ) -G(e i ) > 1 P (x 1 , . . . , x n ) where x i are the variables of F (p i ). Wlog, we can suppose (possibly by padding arguments) that P is common to all the dependency pairs of equal rank. Now, let's work on the induction. Actually, the base case draw the shape of the proof.

Base case Let us consider a symbol f of minimal rank and some constructor terms t 1 , . . . , t n and finally, let P = f 1 (u 1 ), . . . , f k (u k )), . . . be a path in the call tree of f (t 1 , . . . , t n ). From hypothesis (4) of Definition 10, we can state that

F 1 (u 1 ) > F 2 (u 2 ) > • • • .
Given a dependency pair given by = h(p i ) → C[g(e i )] = r with h and g of equal rank, we extract the sequence

P ψ = (f ψ(i) (u ψ(i) )) i∈N from P such that -f ψ(i) = h and -σ = f ψ(i) (u ψ(i) ) → C[f ψ(i)+1 (u ψ(i)+1 )] = r.
Wlog, we can suppose that H(p i ) varies with x 1 , . . . , x m and is constant wrt x m+1 , . . . , x n . Let us consider a (possibly empty) set θ ⊆ {1..m}. To simplify the readability of the proof, we suppose θ = {k..m}.

We extract the sequence P ϕ = (f ϕ(i) (u ϕ(i) )) i∈N from P ψ such that 1. for all j ≤ k, σ(x j ) = 0, 2. for all j ≥ k, σ(x j ) = 0, where σ is the substitution mentioned in the construction of P ψ . Observe that H(p i ) varies with x 1 , . . . , x k . And that σ(x i ) ≥ δ for all i ≤ k. Consequently, from Lemma 13, we get a polynomial Q such that σ(

x i ) ≤ Q( f i (u i ) ). But, then, H(p i ) ≥ G(e i ) + 1 P (Q( F i (u i ) ), . . . , Q( F i (u i ) )) ≥ G(e i ) + 1 P (Q( F 1 (u 1 ) ), . . . , Q( F 1 (u 1 ) ))
.

As a conclusion, we have a polynomial bound on the initial subsequence restricted to the redex of a chosen rule and a particular choice of variable whose interpretation is 0. Since the number of dependency pairs is finite, since the number of choice for the variables is finite (bounded by 2 D where D is the maximal number of variables in a rule), since only (finitely many) constants have interpretation equal to 0, we can say that the length of the sequence P is bounded by

N × 2 D × |C| × P (Q( F 1 (u 1 ) ), . . . , Q( F 1 (u 1 ) )).
Induction step Suppose f has a higher rank. A path of a call-tree can be decomposed in a sub-path of nodes with function of rank of f , and symbols of smaller rank. The depth of symbols of rank of f can be treated as it has been done in the base case. For symbols of lower rank, one employs the induction. The depth of symbols of different ranks sums, and we get a call-tree of polynomial depth in the interpretation of the initial term.

The bound is tight as shown by the next example.

Example 3. The Quantified Boolean Formula (QBF) problem is Pspace complete. It consists in determining the validity of a boolean formula with quantifiers over propositional variables. Without loss of generality, we restrict formulae to ¬, ∨, ∃. QBF problem is solved by the following program.

not(tt) → ff not(ff ) → tt or(tt, y) → tt or(x, tt) → tt or(ff , ff ) → ff 0 = 0 → tt s(x) = 0 → ff 0 = s(y) → ff s(x) = s(y) → x = y in(x, ε) → ff in(x, cons(a, l)) → or(x = a, in(x, l)) verify(Var(x), t) → in(x, t) verify(Not(ϕ), t) → not(verify(ϕ, t))
verify(Or(ϕ 1 , ϕ 2 ), t) → or(verify(ϕ 1 , t), verify(ϕ 2 , t)) verify(Exists(n, ϕ), t) → or(verify(ϕ, cons(n, t)), verify(ϕ, t)) qbf(ϕ) → verify(ϕ, ε) They admit the following interpretation :

0 = ε = 1 s (x) = Not (x) = Var (x) = x + 1 cons (x, y) = Or (x, y) = Exists (x, y) = x + y + 1 or (x) = not (x) = qbf (x) = 1 = (x, y) = in (x, y) = verify (x, y) = 1 NOT (x) = x OR (x, y) = EQ (x, y) = max(x, y) IN (x, y) = x + y VERIFY (x, y) = 2 × x + y + 1 QBF (x) = 2x + 1
It is well known that the derivation height of the QBF is exponential wrt the number of nested Exists symbols. Since the following program builds an input of double exponential depth, we get the triple exponential bound on the derivation height. gives the triple exponential derivation height lower bound. We provide in the technical report an interpretation for the system.

It is not clear whether there are some programs with R-DP-interpretation which do not admit L-weak interpretation. Nevertheless, there is at least one good point for R-DP-interpretation: the logical formulation of the synthesis of R-DP-interpretation involves less alternation of quantifiers. Suppose that we are given program and a fixed degree, the logical formula corresponding to > r is ∀x 1 , . . . , x n > 0 :

(x 1 , . . . , x n ) > r (x 1 , . . . , x n ). While for expressing > δ , we have to write ∃δ > 0 : ∀x 1 , . . . , x n > 0 :

(x 1 , . . . , x n ) > r (x 1 , . . . , x n )+δ. Since the complexity of the QED procedure depends drastically on the number of alternation, we may hope to get thus a better procedure.

With respect to complexity, the proof of Theorem 6 gives us some insight on the cost of a computation. Consider programs with a R-DP-interpretation such that any constructor c has an interpretation of the form k c + i x i , in other words, an additive R-DP-interpretation in [START_REF] Marion | Characterizations of polynomial complexity classes with a better intensionality[END_REF] terminology. There is a constant K such that for all contructor terms t, t ≤ K.|t|, so that f (t 1 , . . . , t n ) is polynomially bounded wrt the size of the (constructor) terms t i . 5 The proof shows then that the nesting of function calls is itself bounded polynomially. If, furthermore the interpretation of capital functions verify the sub-term property, due to Lemma 13, we can state that the size of arguments remain polynomial. This is an other formulation (and a slightly more general one) of the hypothesis of "bounded recursion call" which can be found in [START_REF] Marion | Characterizations of polynomial complexity classes with a better intensionality[END_REF]. So that computations can be performed within Pspace. Since polynomial time can be done with such systems (cf. [START_REF] Bonfante | Algorithms with polynomial interpretation termination proof[END_REF]), and QBF can be simulated, it is then clear that the following Theorem holds: Proof. The completeness comes from the example of the QBF, plus the fact that all functions in polynomial time can be easily computed by such programs. It is then routine to plug all these programs together.

Conclusion

If one goes back to the two characterization of complexity classes presented in this paper, one sees that we essentially use two arguments: a) interpretations with the subset properties provide a polynomial bound wrt the interpretation of the initial interpretation, and b) the size of terms is polynomial wrt their interpretation.

As a consequence, our result can be used in other context such as proofs of termination by matrix interpretations [START_REF] Hofbauer | Proving termination with matrix interpretations[END_REF]. Potentially, any system dealing with decreasing chain of (interpreted) could be treated.

Lemma 11 .

 11 For constructor terms, we have t ≤ Γ × |t| for some constant Γ . Proof. Take Γ = max{ 1 γ c | c (x 1 , . . . , x n ) = n i=1 x i + γ c }. By induction on terms.

  add(0, y) → y add(s(x), y) → s(add(x, y)) mult(0, y) → 0 mult(s(x), y) → add(y, mult(x, y))dexp(0) → s(s(0)) dexp(s (x)) → mult(dexp(x), dexp(x)) e(0) → tt e(s(n)) → Exists(n, e(n)) main(x) → qbf(e(x))with interpretations:0 = 0 s (x) = (x + 3) 2 e (x) = 3x E (x) = x main (x) = qbf(e(x)) MAIN (x) = 6x + 1 add (x, y) = x + y ADD (x, y) = x + y mult (x, y) = x × y MUL (x, y) = (x + 1)(y + 1) dexp (x) = x + 2 DEXP (x) = xWe observe that the term main(s • • • s n times q 0) → * Exists(s 2 n (0, . . . , Exists(0, tt) • • • )

Theorem 7 .

 7 Functions computed by programswith additive R-DP-interpretations the interpretation of capital symbols F has the sub-term property are exactly Pspace computable functions.

  then, by definition of a, we have dh(t) ≤ a = max(|t| A × (d + 1) × (a + 1), a). -Otherwise, let us write t = f (t 1 , . . . , t n ). According to ≤ A-call by value, consider the rewriting f (t 1 , . . . , t n ) → m ≤A,cbv f (u 1 , . . . , u n ). Let us note i 1 , . . . , i k indices for which t ij > A, we have by induction

This comes from the equality P (λx) = λ d P d (x) + R(λx) with deg λ (R) < d.

Innermost in the present context.

The interpretation is correct since for all terms t, t > 0.

L-polynomial algebra in the terminology of Lucas[START_REF] Lucas | Practical use of polynomials over the reals in proofs of termination[END_REF].


Noëlle Pottier
email: noelle.pottier@univ-paris-diderot.fr

Relaxation times distributions for an anomalously diffusing particle

Keywords: Anomalous diffusion, Mittag-Leffler decay, relaxation times distributions

As well-known, the generalized Langevin equation with a memory kernel decreasing at large times as an inverse power law of time describes the motion of an anomalously diffusing particle. Here, we focus the interest on some new aspects of the dynamics, successively considering the memory kernel, the particle's mean velocity, and the scattering function. All these quantities are studied from a unique angle, namely, the discussion of the possible existence of a distribution of relaxation times characterizing their time decay. Although a very popular concept, a relaxation times distribution cannot be associated with any time-decreasing quantity (from a mathematical point of view, the decay has to be described by a completely monotonic function).

Technically, we use a memory kernel decaying as a Mittag-Leffler function (the Mittag-Leffler functions interpolate between a stretched or compressed exponential behaviour at short times and an inverse power law behaviour at large times). We show that, in the case of a subdiffusive motion, relaxation times distributions can be defined for the memory kernel and for the scattering function, but not for the particle's mean velocity. The situation is opposite in the superdiffusive case.

Introduction

In this paper, we study some new aspects of the dynamics of an anomalously diffusing particle whose motion is described by the generalized Langevin equation:

m v(t) + m t 0 γ(t -t ′ )v(t ′ ) dt ′ = F (t), (1.1)
where v(t) is the particle velocity, F (t) is the Langevin force acting on the particle, as modelized by a stationary Gaussian random process of zero mean, and γ(t) is a dissipative memory kernel. Only the knowledge for t > 0 of this latter function is required in Eq. (1.1), but, when necessary, γ(t) will be defined for any t as an even function of time. As well-known, for a particle evolving in a bath at thermal equilibrium at a temperature T , the consistency of the above model requires that F (t) and γ(t) are not independent quantities, but instead are linked by the second fluctuation-dissipation theorem, that is:

F (t)F (t ′ ) = mk B T γ(t -t ′ ), (1.2)
where k B is the Boltzmann constant. (The symbol . . . denotes the average over the realizations of the noise).

In a previous paper [1], we studied this problem in detail in the case of a retarded memory kernel defined by its algebraic decay at large times (γ(t > 0) ∝ t -δ , with 0 < δ < 1 or 1 < δ < 2). We showed in particular that the mean-squared displacement of the particle then varies at large times as:

∆x 2 (t) ∼ t δ , (1.3)
the motion of the particle being thus subdiffusive in the case 0 < δ < 1, and superdiffusive in the case 1 < δ < 2. The subdiffusive case is especially interesting in relation with experiments in condensed matter physics. For instance, the above described model has been used to analyse the subdiffusion process undergone by the distance between a donor and an acceptor of electron transfer within a single protein molecule [2].

In the present paper, following [3], we will use a more general model for the retarded memory kernel, namely, a Mittag-Leffler function of index δ with the same large time algebraic decay as in [1] and a modified exponential behaviour at short times. In this framework, we will focus the interest on some new aspects of the dynamics of the anomalously diffusing particle, successively considering the memory kernel, the particle's mean velocity, and, last, the scattering function. All these quantities will be studied from a unique angle, namely, the discussion of the possible existence of a distribution of relaxation times characterizing their time decay. The concept of a relaxation times distribution is indeed a very popular one, but the quantity of interest (i.e., for which the existence of a distribution of relaxation times is discussed) needs to be made precise. For instance, it is not obvious that, in a given range of values of δ, such a relaxation times distribution exists for each one of the above quoted physical quantities.

The paper is organized as follows. In Section 2, we recall the general condition for the existence of a distribution of relaxation times associated with any time-decaying function, and the way this distribution can be obtained. In Section 3, we focus the interest on the retarded memory kernel γ(t) as described by a Mittag-Leffler function of index δ. We propose a microscopic model justifying such a choice. To this end, we show how, in the spirit of the Mori-Zwanzig memory function theory, the Mittag-Leffler memory kernel γ(t) can itself be viewed as evolving according to a Langevin-like equation associated with a power law second-order memory kernel, a feature which, to the best of our knowledge, does not seem to have been noticed before. The possible existence of a relaxation times distribution associated with γ(t) is then discussed in detail. The particular forms that this distribution (when it exists) takes in the short and long time regimes are discussed. In Section 4, we turn our attention to the particle's mean velocity v(t) . We recall its general expression as found in [3], as well as its approximate form in the long time regime as given in [1]. Then we use this latter expression to discuss the possible existence of a relaxation times distribution associated with v(t) . In Section 5, we study the dynamics of the particle over a coarse-grained time scale corresponding to the description of the motion by a non-inertial Langevin equation. We introduce the scattering function F s (q, t), defined as the spatial Fourier transform of the diffusion front, and we discuss the possible existence of a related relaxation times distribution. In Section 6, we provide an interpretation for our results, and we summarize our conclusions.

General condition for the existence of a distribution of relaxation times

In some instances, the time decay of the physical quantities of interest is described by completely monotonic functions. A function f (t) is said to be completely monotonic in the interval (a, b) if we have [START_REF] Widder | The Laplace Transform[END_REF]:

(-1) k f (k) (t) ≥ 0, a < t < b, k = 0, 1, 2 . . . (2.1)
We will assume f (t = 0) = 1 in what follows.

To begin with, let us recall the Bernstein's theorem, according to which the necessary and sufficient condition for a function f (t) to be completely monotonic in the interval 0 ≤ t < ∞ is that it can be written as [START_REF] Widder | The Laplace Transform[END_REF]:

f (t) = ∞ 0 e -kt dα(k), (2.2)
where α(k) is bounded and non-decreasing, and the above integral converges for

0 ≤ t < ∞. If α(k) is a function with a continuous first derivative µ(k), f (t) appears as the direct Laplace transform of µ(k) ≥ 0. The function µ(k), normalized such that ∞ 0 µ(k)dk = 1
, can be viewed as a probability density of rate constants [START_REF] Berberan-Santos | [END_REF].

Distribution of relaxation times

From Eq. (2.2), we can obtain the distribution of relaxation times associated with the time decay of the completely monotonic function f (t). Setting:

f (t) = ∞ 0 P (τ ) e -t/τ dτ, (2.3)
we get from Eq. (2.2) and the definition µ(k) = dα(k)/dk:

P (τ ) = 1 τ 2 µ 1 τ • (2.4)
The function P (τ ), normalized such that ∞ 0 P (τ )dτ = 1, is a distribution (more precisely, a probability density) of relaxation times. Conversely, we have:

µ(k) = 1 k 2 P 1 k • (2.5)
2.2. Getting P (τ ) from the Laplace transform of f (t)

In some cases, it may be more convenient to start, not from f (t), but from its Laplace transform f (z), as defined by:

f (z) = ∞ 0 f (t)e -zt dt. (2.6)
The decaying function f (t) can be obtained from f (z) by inverse Laplace transformation:

f (t) = 1 2πi Br f (z)e zt dz, (2.7)
where Br denotes the Bromwich path in the complex z-plane, i. This latter contribution to f (t) reads:

- 1 π ∞ 0 ℑm f (xe iπ ) e -xt dx. (2.8)
Thus, when no poles are present, the function:

- 1 π ℑm f (ke iπ ) (2.9)
can be identified with the probability distribution of rate constants:

µ(k) = - 1 π ℑm f (ke iπ ) , (2.10)
from which P (τ ) can be deduced using Eq. (2.4).

The Mittag-Leffler retarded memory kernel

Let us now come to the above described purpose, that is, the discussion of some relaxation times distributions intervening in anomalous diffusion. Following [3], we will introduce in the generalized Langevin equation (1.1) a Mittag-Leffler retarded memory kernel, namely:

γ(t) = γ δ t δ 0 E δ - t t 0 δ , t ≥ 0, (3.1)
with 0 < δ < 2. In Eq. (3.1), t 0 acts as a characteristic memory time linked to the particle's environment (thermal bath), and γ δ is a proportionality coefficient depending on the exponent δ but independent of time. The E α (y) function denotes the Mittag-Leffler function [START_REF] Erdélyi | Higher Transcendental Functions[END_REF]- [START_REF] Mainardi | [END_REF] defined through the series:

E α (y) = ∞ n=0 y n Γ(αn + 1) , α > 0, (3.2)
where Γ denotes the Euler Gamma function. For δ = 1, we just have an ordinary exponential decay as pictured by γ(t) = (γ 1 /t 0 ) exp(-t/t 0 ).

We assume δ = 1 in the rest of this subsection. As underlined for instance in [9], the choice (3.1) is especially convenient, since it allows γ(t) to interpolate, from a "stretched exponential" (in the case 0 < δ < 1) or a "compressed exponential" (in the case 1 < δ < 2) for t ≪ t 0 , to an inverse power law for t ≫ t 0 . More precisely, retaining only the two first terms of the series expansion (3.2), we can approximately write, in the short time regime [9], [10]:

γ(t) ≃ γ δ t δ 0 exp - (t/t 0 ) δ Γ(δ + 1) , t ≪ t 0 . (3.3)
In the long time regime, we have [START_REF] Erdélyi | Higher Transcendental Functions[END_REF]:

γ(t) ≃ γ δ t δ 0 1 Γ(1 -δ) t t 0 -δ , t ≫ t 0 . (3.4)
Note that, in this latter regime, we recover the power law retarded memory kernel previously used in [1]. Interestingly, the characteristic memory time t 0 linked to the bath is in fact not involved in the long time expression for γ(t) (Eq. (3.4)).

Setting γ δ = ω 2-δ δ , Eq. (3.4) reads:

γ(t) ≃ ω 2 Γ(1 -δ) (ω δ t) -δ , t ≫ t 0 . (3.5)
Formula (3.5) shows that the pertinent time scale is then ω -1 δ , which for consistency we assume to be much larger than t 0 . Summarizing, two different time scales enter into play in the Mittag-Leffler memory kernel (3.1), a short one denoted by t 0 , and a long one denoted by ω -1 δ .

The short time regime

Let us discuss in more detail the short time regime of the Mittag-Leffler function

E δ [-(t/t 0 ) δ ],
as given by the modified exponential exp[-(t/t 0 ) δ Γ(δ+1) ] in formula (3.3). As underlined in [START_REF] Berberan-Santos | [END_REF], the denominations of "stretched" and "compressed" exponentials are somewhat of a misnomer in the short time regime which precisely interests us now. Indeed the so-called stretched exponential exp[-(t/t 0 ) δ Γ(δ+1) ] in the case 0 < δ < 1 is actually a function whose decay with time is faster than that of the ordinary exponential exp[-t/t 0 Γ(δ+1) ] for 0 < t < t 0 (but slower afterwards, which is in fact the reason for the denomination of "stretched" exponential). The initial decay rate of the retarded memory kernel (3.3), which is given by the derivative [dγ(t)/dt](t = 0), is even equal to -∞ in this case.

In the case 1 < δ < 2, the time decay of the so-called compressed exponen-

tial exp[-(t/t 0 ) δ Γ(δ+1)
] is slower than that of the ordinary exponential exp[-t/t 0 Γ(δ+1) ] for 0 < t < t 0 (but faster afterwards, hence the denomination of "compressed" exponential). The initial decay rate of the retarded memory kernel vanishes in this case.

The Laplace transform of the Mittag-Leffler memory kernel

Following the same procedure as in [1], we will solve the generalized Langevin equation (1.1) using Laplace transformation. Introducing the Laplace transform γ(z) of the retarded memory kernel γ(t) defined in the usual way, namely:

γ(z) = ∞ 0 γ(t)e -zt dt, (3.6)
we get from Eq. (3.1) (as shown for instance in [START_REF] Mainardi | [END_REF]):

γ(z) = γ δ t δ 0 1 z + t -δ 0 z 1-δ • (3.7) For |z| ≪ t -1 0 , we have: γ(z) ≃ γ δ z δ-1 , (3.8)
that is:

γ(z) ≃ ω 2-δ δ z δ-1 , (3.9)
an expression consistent with the choice made in [1], as well as with the large time behaviour of γ(t) as given by Eq. (3.5).

A microscopic model for the Mittag-Leffler memory kernel

In the spirit of the Mori-Zwanzig memory function theory [11]- [START_REF] Zwanzig | Nonequilibrium statistical mechanics[END_REF], let us assume that the time evolution of the Langevin force F (t) acting on the particle velocity (a force which is denoted by F 1 (t) for more clarity in what follows) can in turn be described by the Langevin-like equation:

Ḟ1 (t) + t 0 φ(t -t ′ )F 1 (t ′ ) dt ′ = F 2 (t), (3.10)
where φ(t) is a second-order memory kernel associated with the time evolution of F 1 (t), and F 2 (t) acts as a second-order random "force". Assume in addition that

F 2 (t > 0) is uncorrelated with F 1 (0). The correlation function C 1 (t) = F 1 (t)F 1 (0)
then obeys the homogeneous evolution equation:

Ċ1 (t) + t 0 φ(t -t ′ )C 1 (t ′ ) dt ′ = 0, t > 0. (3.11)
The memory kernel

γ(t) = C 1 (t)/mk B T of the generalized Langevin equation (1.1)
obeys the same evolution equation:

γ(t) + t 0 φ(t -t ′ )γ(t ′ ) dt ′ = 0, t > 0. (3.12)
We want to solve Eq. (3.12) for a given γ(t = 0). Applying Laplace transformation, we get:

zγ(z) -γ(t = 0) + φ(z)γ(z) = 0. (3.13)
We thus recover for γ(z) an expression similar to formula (3.7):

γ(z) = γ(t = 0) z + φ(z) • ( 3
φ(z) = t -δ 0 z 1-δ , (3.15)
that is, to an inverse power law second-order memory kernel φ(t):

φ(t) = t -2 0 Γ(δ -1) t t 0 δ-2 , t ≥ 0. (3.16)
Since δ < 2, the function φ(t) decreases algebraically towards zero at large times (t ≫ t 0 ), except for δ = 1, in which case this algebraic tail vanishes, leaving us with the delta function behaviour φ(t) = (1/t 0 )δ(t), in accordance with the formal representation of the Dirac generalized function δ(t) = t -1 /Γ(0), t ≥ 0 [START_REF] Mainardi | [END_REF]. Note that only the short time scale t 0 is actually involved in the expression for φ(t) (but not the long time scale ω -1 δ ). We have φ(t) < 0 for 0 < δ < 1, and φ(t) > 0 for 1 < δ < 2.

The relaxation times distribution associated with γ(t)

The question of the existence of a relaxation times distribution associated with a Mittag-Leffler decay has been extensively discussed in the literature [10], [14]- [15]. We only summarize here the main results. Following [START_REF] Mainardi | [END_REF], we write γ(t) as the inverse Laplace transform of γ(z) as given by formula (3.7):

γ(t) = γ δ t δ 0 1 2πi Br 1 z + t -δ 0 z 1-δ e zt dz, (3.17)
where Br denotes the Bromwich path in the complex z-plane (ℜe z = σ with σ ≥ t -1 0 ). The Bromwich path is then bent into the equivalent Hankel path Ha(ε), i.e. a loop which starts from -∞ along the lower side of the negative real axis, encircles the origin in the positive sense along a circle of small radius ε, and ends at -∞ along the upper side of the negative real axis. In both cases 0 < δ < 1 and 1 < δ < 2, we obtain [START_REF] Mainardi | [END_REF]:

γ(t) = γ 1 (t) + γ 2 (t), t ≥ 0, (3.18)
where γ 1 (t) is the contribution of the Hankel path:

γ 1 (t) = γ δ t δ 0 1 2πi Ha(ε) 1 z + t -δ 0 z 1-δ e zt dz, (3.19)
and γ 2 (t) is the contribution of the relevant poles, i.e. the poles situated in the first Riemann sheet, of 1/(z + t -δ 0 z 1-δ ).

In the case 0 < δ < 1, no such poles exist [START_REF] Mainardi | [END_REF], and γ(t) = γ 1 (t) relaxes towards zero without oscillating. The result takes a form analogous to Eq. (2.2) (except for the fact that we do not have γ(t = 0) = 1, but instead γ(t = 0) = γ δ /t δ 0 ):

γ(t) = γ δ t δ 0 ∞ 0 µ γ (k) e -kt dk, (3.20)
with the rate constants distribution µ γ (k) as given by:

µ γ (k) = - 1 π 1 γ(t = 0) ℑm γ(ke iπ ) = sin δπ π t 0 (kt 0 ) δ-1 1 + 2(kt 0 ) δ cos δπ + (kt 0 ) 2δ • (3.21)
A distribution of relaxation times can thus be defined in this case (these relaxation times being linked to the thermal bath), which means that we can write:

γ(t) = γ δ t δ 0 ∞ 0 P γ (τ ) e -t/τ dτ, (3.22)
with P γ (τ ) a non-negative function normalized such that ∞ 0 P γ (τ )dτ = 1. From Eqs (2.4) and (3.21), we get [START_REF] Mainardi | [END_REF], [10], [START_REF] Mainardi | [END_REF]- [14]:

P γ (τ ) = sin δπ π 1 τ 1 τ t 0 δ + 2 cos δπ + τ t 0 -δ • (3.23)
The distribution P γ (τ ) as given by Eq. (3.23) is non-negative and normalized:

∞ 0 P γ (τ ) dτ = E δ (t = 0) = 1. (3.24)
It is widely referred to in the literature as the Cole-Cole distribution of relaxation times [16]. Its short time and large time limiting forms are discussed in detail in Appendix A. The behaviour of P γ (τ ) for τ ≪ t 0 is especially interesting. We have an integrable divergence of the distribution of small relaxation times:

P γ (τ ) ≃ sin δπ π 1 t 0 τ t 0 δ-1 , τ ≪ t 0 . (3.25)
In the case 1 < δ < 2, the situation is more intricate since γ(t) contains in addition an oscillating part. It can be written as [START_REF] Mainardi | [END_REF]:

γ(t) = γ δ t δ 0 2 δ exp t t 0 cos π δ cos t t 0 sin π δ + ∞ 0 P γ (τ ) e -t/τ dτ , (3.26)
where the function P γ (τ ), which is still given by Eq. (3.23), cannot be given the meaning of a relaxation times distribution. We now have:

∞ 0 P γ (τ ) dτ = E δ (t = 0) - 2 δ = 1 - 2 δ • (3.27)
Thus, in this range of values of δ, we cannot associate with γ(t) a distribution of relaxation times (all the more since now P γ (τ ) < 0).

The noise spectral density

Let us come back to the Mittag-Leffler memory kernel γ(t) as given by Eq. (3.1), and introduce its Fourier-Laplace transform defined as usual for real ω by:

γ(ω) = ∞ 0 γ(t)e iωt dt.
(3.28)

Inversely, we have:

γ(t) = 2 π ∞ 0 ℜe γ(ω) cos ωt dω. (3.29)
Eq. (3.29) displays the fact that it is enough to know ℜe γ(ω) for ω > 0 in order to get an integral representation for γ(t). Using the identity γ(ω) = γ(z = -iω),

together with the expression (3.7) for γ(z), we get (assuming ω > 0):

γ(ω) = γ δ ω δ-1 sin(δπ/2) + i (ωt 0 ) δ -cos(δπ/2) 1 + 2 cos(δπ/2)(ωt 0 ) δ + (ωt 0 ) 2δ , ω > 0. (3.30)
We have in particular:

ℜe γ(ω) = γ δ sin(δπ/2)ω δ-1 1 1 + 2 cos(δπ/2)(ωt 0 ) δ + (ωt 0 ) 2δ , ω > 0. (3.31)
The noise spectral density |F (ω)| 2 defined for any real ω as the Fourier transform of the correlation function F (t)F (t ′ ) , reads, making use of the second fluctuation-dissipation theorem (Eq. (1.2)):

|F (ω)| 2 = 2mk B T γ δ sin(δπ/2)|ω| δ-1 1 1 + 2 cos(δπ/2)(|ω|t 0 ) δ + (|ω|t 0 ) 2δ , (3.32)
in accordance with the expression provided in [3].

If, instead of the Mittag-Leffler memory kernel, we use a memory kernel γ(t)

about which we only know that it behaves at times t ≫ t 0 as an inverse power law of time (γ(t ≫ t 0 ) ∝ t -δ ), we usually write the noise spectral density as [1], [START_REF] Weiss | Quantum Dissipative Systems[END_REF]:

|F (ω)| 2 = 2mk B T γ δ sin(δπ/2)|ω| δ-1 f c (|ω|t 0 ), (3.33)
with f c a high-frequency cut-off function of typical width t -1 0 . For δ = 1, we have at hand a non-Ohmic dissipation model [START_REF] Weiss | Quantum Dissipative Systems[END_REF] (more precisely, sub-Ohmic for 0 < δ < 1, and super-Ohmic for 1 < δ < 2). The spectral density of the coupling, defined for positive ω by J(ω) = m ℜe γ(ω), is given by:

J(ω) = mγ δ sin(δπ/2)ω δ f c (ωt 0 ), ω > 0. (3.34)
These results are in accordance with those obtained in [START_REF] Kupferman | [END_REF], where it has been shown, in the framework of the Kac-Zwanzig model of a particle interacting through springs with a heat bath made of a collection of harmonic oscillators [19], how the distributions of frequencies, masses, and spring constants, determine the parameters of the generalized Langevin equation obeyed by the distinguished particle in the thermodynamic limit. The analysis carried out in [START_REF] Kupferman | [END_REF] has been applied to the case of a memory kernel decreasing as an inverse power law of time.

Let us come back to the full formula (3.32) for the noise spectral density. As put forward in [3], the choice of the Mittag-Leffler memory kernel allows us to make precise the cut-off function, which depends on the exponent δ:

f c (|ω|t 0 ) = 1 1 + 2 cos(δπ/2)(|ω|t 0 ) δ + (|ω|t 0 ) 2δ • (3.35)
Note that, for δ = 1, formula (3.35) for the cut-off function reduces to the Drude expression:

f c (|ω|t 0 ) = 1 1 + (|ω|t 0 ) 2 • (3.36)
Interestingly, instead of being introduced by hand (usual choices being an exponential or a Lorentzian cut-off function [START_REF] Weiss | Quantum Dissipative Systems[END_REF]) the δ-dependent cut-off function comes here into play in a natural way in the framework of the Mori-Zwanzig formalism (see Appendix B for more details).

The particle's mean velocity

The solution v(t) of the generalized Langevin equation (1.1) with γ(t) the Mittag-Leffler memory kernel as studied in Section 3 has first been obtained in [3] as the inverse Laplace integral:

v(t) = v(t = 0) 1 2πi Br 1 z + γ(z) e zt dz, (4.1)
with γ(z) as given by Eq. (3.7). To get an explicit formula, we write:

1 z + γ(z) = 1 z ∞ k=0 (-1) k γ(z) k z k • (4.2)
The expression in the r.h.s. of Eq. (4.2) can conveniently be rewritten as:

∞ k=0 (-1) k k! k! z k+1 γ δ t δ 0 k z + t -δ 0 z 1-δ (z + t -δ 0 z 1-δ ) k+1 , (4.3)
that is:

∞ k=0 (-1) k k! k! z k γ δ t δ 0 k 1 (z + t -δ 0 z 1-δ ) k+1 + ∞ k=0 (-1) k k! k! z k+δ γ δ t δ 0 k t -δ 0 (z + t -δ 0 z 1-δ ) k+1 • (4.4)
The result of the Laplace inversion takes the form of the sum of two infinite series of derivatives of generalized Mittag-Leffler functions (see for instance the formulas provided in [START_REF] Podlubny | Fractional Differential Equations[END_REF]):

v(t) = v(t = 0) ∞ k=0 (-1) k k! γ δ t δ 0 k t 2k E (k) δ,1+(2-δ)k - t t 0 δ + t t 0 δ ∞ k=0 (-1) k k! γ δ t δ 0 k t 2k E (k) δ,1+δ+(2-δ)k - t t 0 δ . (4.5)
The generalized Mittag-Leffler function E α,β (y) is defined through the series [6]- [START_REF] Podlubny | Fractional Differential Equations[END_REF]:

E α,β (y) = ∞ n=0 y n Γ(αn + β) , α > 0 β > 0, (4.6)
and

E (k)
α,β (y) represents its kth-order derivative with respect to its argument y:

E (k) α,β (y) = d k dy k E α,β (y). (4.7)
The main question we now want to address is that of the possible existence of a distribution of relaxation times associated with the particle's mean velocity.

This discussion would be tricky to achieve on the basis of the full exact formula (4.5). This is why, from now on, we will use a simpler expression for v(t) , valid for times t ≫ t 0 .

The average velocity at times t ≫ t 0

Let us thus take for γ(z) its approximate expression (3.8) valid for |z| ≪ t -1 0 , which amounts to use, in the time domain, the expression (3.5) for γ(t), valid for times t ≫ t 0 . We then write accordingly (with obvious notations) [1]:

v(z) ≃ v(t = 0) z + ω 2-δ δ z δ-1 , |z| ≪ t -1 0 , (4.8)
which gives:

v(t) ≃ v(t = 0)E 2-δ -(ω δ t) 2-δ , t ≫ t 0 . (4.9)
As shown in [3], this behaviour can also be retrieved from the general expression (4.5). Replace, in the two infinite series in the r.h.s. of Eq. (4.5), each generalized Mittag-Leffler function by its asymptotic expression for t ≫ t 0 , using the asymptotic formula [START_REF] Podlubny | Fractional Differential Equations[END_REF]:

E α,β (-y) ≃ 1 yΓ(β -α) , y > 0. ( 4.10)
The leading order terms, which come from the second series in formula (4.5), can be resummed. The pertinent time scale is now ω -1 δ (the shorter time scale t 0 being no more involved). We recover in this way formula (4.9).

Connection with the fractional Langevin equation

To shed some more light on the above results, let us remark that, using for γ(t) the approximate expression (3.5), amounts, in the case 0 < δ < 1, to writing the generalized Langevin equation (1.1) as a fractional Langevin equation, namely:

m v(t) + m γ δ Γ(1 -δ) t 0 (t -t ′ ) -δ v(t ′ ) dt ′ = F (t), 0 < δ < 1. (4.11)
In the range 1 < δ < 2, we write instead, in order to avoid divergencies:

m v(t)+mγ δ v(t = 0)t 1-δ Γ(2 -δ) +m γ δ Γ(2 -δ) t 0 (t -t ′ ) -δ+1 v(t ′ ) dt ′ = F (t), 1 < δ < 2.
(4.12) Accordingly, the average particle's velocity as given by Eq. (4.9) coincides as it should with the (averaged) solution of Eq. (4.11) (for 0 < δ < 1), or of Eq. (4.12)

(for 1 < δ < 2).

In addition, let us note that formulas (4.8) and (4.9) for the average particle's velocity have first been provided in [20] for 0 < δ < 1 as the force-free solution of a fractional Fokker-Planck equation, as well as in [21] for 1 < δ < 2 as the force-free solution of a fractional Kramers equation, this latter equation describing both the velocity and coordinate of a particle exhibiting anomalous diffusion in an external force field (see also [9]).

The noise spectral density

Let us here quote for completeness the corresponding expressions for the noise spectral density and the spectral density of the coupling. In the angular frequency range |ω| ≪ t -1 0 , formula (3.31) for ℜe γ(ω) reduces to the expression used in [1], namely:

ℜe γ(ω) ≃ γ δ sin(δπ/2)|ω| δ-1 . (4.13)
The corresponding noise spectral density (Eq. (3.33)) now reads:

|F (ω)| 2 ≃ 2mk B T γ δ sin(δπ/2)|ω| δ-1 . (4.14)
As for the spectral density of the coupling (Eq. (3.34)), it reduces to:

J(ω) ≃ mγ δ sin(δπ/2)ω δ , ω > 0. ( 4

Duality symmetry

Let us compare formula (3.14) for γ(z) (with φ(z) as given by Eq. (3.15)), with the approximate formula (4.8) for v(z) . Both expressions have the same structure.

They can even be identified, provided that one makes the change of indexes:

δ ←→ 2 -δ, (4.16)
together with the change of time scales:

t 0 ←→ ω -1 δ . (4.17)
This dynamical mapping between the Laplace transforms of the memory kernel, on the one hand, and of the particle's mean velocity, on the other hand, transforms the parameter region 0 < δ < 1 into the region 1 < δ < 2 (and vice-versa), with important consequences about the existence of relaxation times distributions for either quantities.

The relaxation times distribution associated with v(t)

We will take advantage of the duality symmetry to discuss the existence of a relaxation times distribution associated with the particle's mean velocity as given by the approximate formula (4.9). In both cases 0 < δ < 1 and 1 < δ < 2, we write:

v(t) = v 1 (t) + v 2 (t) , t ≥ 0, (4.18)
where:

v 1 (t) = v(t = 0) 1 2πi Ha(ε) 1 z + ω 2-δ δ z δ-1 e zt dz, (4.19)
and v 2 (t) is the contribution of the relevant poles of 1/(z + ω 2-δ δ z δ-1 ), if any.

In the case 1 < δ < 2, no such poles exist, and the mean velocity relaxes towards zero without oscillating. We have:

v(t) = v(t = 0) ∞ 0 P v (τ ) e -t/τ dτ, (4.20)
with the relaxation times distribution P v (τ ) as given by:

P v (τ ) = -sin δπ π 1 τ 1 ω δ τ 2-δ + 2 cos δπ + ω δ τ δ-2 • (4.21)
In the case 0 < δ < 1, the particle's mean velocity contains in addition an oscillating part:

v(t) = v(t = 0) 2 2 -δ e ω δ t cos[π/(2-δ)] cos ω δ t sin π 2 -δ + ∞ 0 P v (τ ) e -t/τ dτ , (4.22)
where P v (τ ), although still given by Eq. (4.21), cannot obviously be interpreted as a relaxation times distribution. We easily check that, when δ → 1, we have ω δ → γ 1 , and P v (τ ) → -δ(τ -γ -1 1 ). Formula (4.22) thus consistently yields in this limit the standard behaviour corresponding to a non-retarded Langevin equation with friction coefficient γ 1 :

v(t) → v(t = 0) e -γ 1 t .
(4.23)

In the opposite limit δ → 0, setting ω δ → ω 0 , we have an undamped oscillation:

v(t) → v(t = 0) cos ω 0 t. ( 4

.24)

A physical explanation for the presence of an oscillating term in the r.h.s. of Eq.

(4.22) can be provided in terms of the cage effect. As explained in [22], for small δ the friction force induced by the environment is not just slowing down the particle, but also causes the particle a rattling motion. The generalized Langevin equation can be written, for 0 < δ < 1, as the fractional Langevin equation (4.11), that is:

m v(t) + m ω 2 δ Γ(1 -δ) t 0 [ω δ (t -t ′ )] -δ v(t ′ ) dt ′ = F (t). (4.25)
In the limit δ → 0, Eq. (4.25) simply reads:

m v(t) + mω 2 0 [x -x(t = 0)] = F (t). (4.26)
This shows that a purely oscillating behaviour is expected in this limit. This oscillation can be explained by the rattling motion of the particle of interest in the cage formed by the surrounding particles.

Discussion

Let us comment the above found results concerning the fact that it is not possible to define a relaxation times distribution for the particle's average velocity in the range 0 < δ < 1.

Consider an assembly of independent particles obeying the usual simple Langevin equation:

m v(t) + m v(t) τ = F (t), (4.27)
where F (t) is the Langevin force and the relaxation time τ is random. For any given τ , the average velocity of an individual particle varies like v(t = 0) exp(-t/τ ).

An obvious question is whether it exists a relaxation times distribution function P v (τ ) such that the average velocity as defined by:

v(t) = v(t = 0) ∞ 0 P v (τ ) e -t/τ dτ, (4.28)
effectively obeys the (averaged) fractional Langevin equation, namely:

m v(t) + m γ δ Γ(1 -δ) t 0 (t -t ′ ) -δ v(t ′ ) dt ′ = 0, 0 < δ < 1. (4.29)
It ensues from the results of Subsection 4.5 that such a distribution function cannot be defined. In other words, it does not exist a relaxation times distribution which would map the simple Langevin equation onto the fractional one.

The scattering function

We continue in this section, and in the following of this paper as well, to study the various functions of time which enter into play at times t ≫ t 0 only. This latter time scale will thus no more appear in what follows.

The mean-squared displacement

Let us introduce the particle displacement x(t) = t 0 v(t ′ ) dt ′ . The two-time displacement correlation function can be obtained from the velocity correlation function as the double integral:

x(t)x(t ′ ) = t 0 t ′ 0 v(t 1 )v(t 2 ) dt 1 dt 2 .
(

On the basis of the first fluctuation-dissipation theorem (see formula (B.6)) together with formula (4.9) for the particle's mean velocity, the velocity correlation function is given by [1], [9]:

v(t)v(t ′ ) = k B T m E 2-δ -(ω δ |t -t ′ |) 2-δ . (5.2)
To obtain x(t)x(t ′ ) , we have to use the integration formulas:

t 0 E 2-δ -(ω δ t 1 2-δ dt 1 = t E 2-δ,2 -(ω δ t) 2-δ , (5.3)
and:

t 0 dt 1 t 1 0 E 2-δ -(ω δ t 2 2-δ dt 2 = t 2 E 2-δ,3 -(ω δ t) 2-δ . (5.4)
Making t ′ = t in Eq. (5.1), gives the expression for the mean-squared displacement ∆x 2 (t) = x 2 (t) [1], [9], [21]:

∆x 2 (t) = 2 k B T m t 2 E 2-δ,3 -(ω δ t) 2-δ . (5.5)
In the case 0 < δ < 1, the expression for ∆x 2 (t) contains an oscillating part. The general formula being a bit lengthy, we shall only quote its two limiting forms for δ → 1 and δ → 0. First, we can check that, when δ → 1, we recover the standard Brownian motion result:

∆x 2 (t) → 2 k B T m t γ 1 - 1 -e -γ 1 t γ 2 1 • (5.6)
In the opposite limit δ → 0, we get the undamped oscillator formula:

∆x 2 (t) = 2 k B T mω 2 0 (1 -cos ω 0 t). (5.7)
In the case 1 < δ < 2 in which the motion is superdiffusive, we can write the mean-squared displacement in terms of the relaxation times distribution function

P v (τ ) as: ∆x 2 (t) = 2 k B T m ∞ 0 P v (τ ) t -τ (1 -e -t/τ ) τ dτ. (5.8)

Large time behaviour of the mean-squared displacement: the noninertial regime

We mean here by "large times" the times for which we have ω δ t ≫ 1. The generalized Mittag-Leffler function in Eq. (5.5) can then be replaced by its leading order term as given by the asymptotic formula (4.10). We get [1]:

∆x 2 (t) ≃ 2 k B T mω 2 δ (ω δ t) δ Γ(δ + 1) , ω δ t ≫ 1.
(5.9) Formula (5.9) is valid for any δ (0 < δ < 2). Note that, when ω δ t ≫ 1, the oscillating contribution which exists at shorter times in the range 0 < δ < 1 does not appear any more.

Interestingly, the result (5.9) is fully consistent with the expression for the velocity correlation function obtained by considering, instead of the full generalized Langevin equation (1.1), the corresponding noninertial equation of motion, i.e.:

m t 0 γ(t -t ′ )v(t ′ ) dt ′ = F (t).
(5.10)

Applying Laplace transformation to Eq. (5.10), we get: mγ(z)v(z) = F (z), (5.11) hence the expression for the double Laplace transform of the velocity correlation function:

v(z)v(z ′ ) = 1 m 2 F (z) F (z ′ ) γ(z)γ(z ′ ) • (5.12)
From the second fluctuation-dissipation theorem, we have [1]:

F (z) F (z ′ ) = mk B T γ(z) + γ(z ′ ) z + z ′ , ( 5.13)
and thus:

v(z)v(z ′ ) = k B T m 1 z + z ′ 1 γ(z) + 1 γ(z ′ ) • (5.14)
Taking for γ(z) its expression (3.9) valid for |z| ≪ t -1 0 , we get:

v(z)v(z ′ ) = k B T m ω δ-2 δ z + z ′ (z 1-δ + z ′1-δ ). (5.15)
Neglecting the inertial term thus yields for the velocity correlation function the expression:

v(t)v = k B T m (ω δ t) δ-2 Γ(δ -1) • (5.16)
This latter formula is identical to the one which can be deduced by derivating twice with respect to time the large time expression (5.9) for ∆x 2 (t) . This fact is in accordance with the general view according to which considering the noninertial equation of motion is tantamount to studying the motion of the particle over a coarse-grained time scale (here, ω -1 δ ).

The scattering function

Let us introduce the scattering function F s (q, t), as defined by [START_REF] Berne | Dynamic Light Scattering[END_REF]:

F s (q, t) = G s (x, t) e iqx dx, (5.17)
with G s (x, t) the diffusion profile (if the present one-particle model is considered as picturing the diffusion of an ensemble of non-interacting particles, the function F s (q, t) describes the relaxation of a density fluctuation of wavevector q). Since the noise has been assumed to be Gaussian, the diffusion profile is a Gaussian function of width ∆x 2 (t) :

G s (x, t) = [2π ∆x 2 (t) ] -1/2 exp - x 2 2 ∆x 2 (t) • (5.18)
Performing the Fourier integration in Eq. (5.17), we get:

F s (q, t) = exp -q 2 ∆x 2 (t) 2 • (5.19)
Using Eq. (5.5), which gives the expression for the mean-squared displacement in terms of a generalized Mittag-Leffler function, would lead to a fairly involved formula for F s (q, t). Let us instead simply use for ∆x 2 (t) its expression (5.9) valid for ω δ t ≫ 1 (non-inertial regime). The scattering function is then simply a modified exponential function [START_REF] Bouchaud | Anomalous relaxation in complex systems: from stretched to compressed exponentials[END_REF]:

F s (q, t) ≃ exp -q 2 k B T mω 2 δ (ω δ t) δ Γ(δ + 1) , ω δ t ≫ 1.
(5.20)

5.4. The relaxation times distribution associated with F s (q, t)

In the range 0 < δ < 1 which corresponds to subdiffusion, the scattering function as given by formula (5.20) is a stretched exponential, whereas, in the range 1 < δ < 2 in which the motion is superdiffusive, it is a compressed exponential.

Accordingly, a relaxation times distribution can be associated with the scattering function in the range 0 < δ < 1, but not in the range 1 < δ < 2.

Introducing the time scale t q as defined by:

1 t δ q = q 2 k B T mω 2 δ ω δ δ , (5.21)
we can rewrite Eq. (5.20) as:

F s (q, t) ≃ exp - (t/t q ) δ Γ(δ + 1) , ω δ t ≫ 1.
(5.22) Formula (5.22) for F s (q, t) has the same form as the approximate formula (3.3) for γ(t) valid for t ≪ t 0 . Both formulas can be identified (up to a proportionality factor), provided that one makes the change of time scales:

t 0 ←→ t q , (5.23)
the parameter δ remaining unchanged.

In the range 0 < δ < 1, introducing the rates distribution µ F s (k), we write:

F s (q, t) = ∞ 0 µ F s (k) e -kt dk, (5.24)
that is, in terms of the relaxation times distribution P F s (τ ):

F s (q, t) = ∞ 0 P F s (τ ) e -t/τ dτ. (5.25)
The relaxation rates distribution µ F s (k) in Eq. (5.24), as given by:

µ F s (k) = 1 2πi Br exp - (z/t q ) δ Γ(δ + 1) e kz dz, (5.26)
identifies with the one-sided stable Lévy law L C δ,1 (k) as defined by [START_REF] Bouchaud | [END_REF]:

L C δ,1 (k) = 1 2πi Br e -Cz δ e kz dz, (5.27)
provided that one sets C = t -δ q /Γ(δ + 1). This property deserves to be mentioned since it relates the fractional Langevin equation to the generalized central limit theorem [START_REF] Bouchaud | [END_REF].

Carrying out a discussion similar to the one in Appendix A, we write the relaxation rates distribution µ F s (k) as:

µ F s (k) = 1 π t q ∞ 0 exp - x δ cos δπ Γ(δ + 1) sin
x δ sin δπ Γ(δ + 1) e -kt q x dx.

(5.28)

As for the relaxation times distribution P F s (τ ), it reads:

P F s (τ ) = 1 π t q τ 2 ∞ 0 exp - x δ cos δπ Γ(δ + 1) sin x δ sin δπ Γ(δ + 1)
e -xt q /τ dx.

(5.29)

For τ ≪ t q , we simply have:

P F s (τ ) ≃ sin δπ π 1 τ τ t q δ .
(5.30)

In the range 1 < δ < 2, F s (q, t) is a compressed exponential with which no relaxation times distribution can be associated. Finally, let us note for completeness that, in the limiting case δ = 1, we just recover an exponentially decaying scattering function:

F s (q, t) ≃ exp(-t/t q ), γ 1 t ≫ 1, (5.31)
with: 1 t q = q 2 k B T mγ 1 • (5.32)

Conclusion

In this paper, we studied the dynamics of an anomalously diffusing particle whose motion is described by a generalized Langevin equation and whose mean-squared displacement grows at large time like ∆x 2 (t) ∼ t δ , with 0 < δ < 1 (subdiffusion) or 1 < δ < 2 (superdiffusion). We successively focused our interest on three time decaying quantities, namely, the memory kernel of the generalized Langevin equation, the particle's mean velocity, and the scattering function.

Using for the memory kernel γ(t) a Mittag-Leffler function of index δ and characteristic time scale t 0 , we showed that its decay can be associated with a relaxation times distribution in the range 0 < δ < 1. We were able to make precise this distribution at any time t, as well as to check its consistency with the relaxation times distributions associated with the limiting forms of the Mittag-Leffler function for t ≪ t 0 (a stretched exponential) and for t ≫ t 0 (an inverse power law of time). Interestingly, the distribution of small relaxation times τ ≪ t 0 was shown to exhibit an integrable divergence ∝ τ δ-1 . As stated in [START_REF] Bouchaud | Anomalous relaxation in complex systems: from stretched to compressed exponentials[END_REF], such a divergence implies a profusion of short times scales in the Mittag-Leffler decay of index δ in the range 0 < δ < 1. As for the distribution of large relaxation times, it was shown to decay like an inverse power law ∝ τ -δ , which displays the fact that there exist also abundant long time scales in the Mittag-Leffler decay.

We then turned to the particle's mean velocity v(t) . Restricting the study to times t ≫ t 0 , we showed that v(t) is given by a Mittag-Leffler function of index 2 -δ and characteristic time scale ω -1 δ ≫ t 0 , and thus that it can be associated with a relaxation times distribution in the range 1 < δ < 2. More precisely, the dynamical mapping which allows us to deduce the behaviour of v(t) from that of γ(t) was shown to correspond to the change of indexes δ ←→ 2 -δ, together with the change of time scales t 0 ←→ ω -1 δ . The divergence of the distribution of small relaxation times of γ(t), all the more pronounced as δ approaches zero, induces for 0 < t < t 0 an efficient decrease of the dissipative kernel, resulting in turn in a weak damping of the particle's mean velocity, which is actually described by an oscillating function in the range 0 < δ < 1. Conversely, for 1 < δ < 2, the decrease of γ(t) for 0 < t < t 0 is relatively weak, which in turn implies an efficient decrease of the particle's mean velocity.

Finally, we turned our interest on the scattering function F s (q, t), whose be-haviour is directly linked to that of the mean-squared displacement. It results from the very definition of the scattering function that this quantity can be associated with a relaxation time distribution in the subdiffusive range 0 < δ < 1, but not in the superdiffusive range 1 < δ < 2.

Using a Tauberian theorem [START_REF] Widder | The Laplace Transform[END_REF], it is easy to deduce the behaviour of P KWW (τ ) for τ ≪ t 0 from the small-x behaviour of the function exp[-x δ cos δπ Γ(δ+1) ] sin[ x δ sin δπ Γ(δ+1) ]. As a result, we get:

B.2. Derivation of the noise cut-off function

Interestingly, in the framework of the Mori-Zwanzig formalism, the noise cut-off function is not introduced a priori for convenience purposes, but can be consistently derived once the second-order memory kernel φ(t) is known.

Applying standard harmonic analysis to Eq. (3.10), we get, introducing the Fourier-Laplace transform φ(ω) of φ(t):

|F 1 (ω)| 2 = |F 2 (ω)| 2 -iω + φ(ω) 2 • (B.

  e. a line ℜe z = σ with σ larger than the abscissas of the possibly existing singularities of f (z) and ℑm z running from -∞ to +∞. For those functions f (z) that have a cut along the negative real axis, it is possible to bend the Bromwich path into a Hankel path, i.e. a loop which starts from -∞ along the lower side of the negative real axis, encircles the origin in the positive sense, and ends at -∞ along the upper side of the negative real axis. If f (z) has poles in the first Riemann sheet, their contribution has to be taken into account, and it must be added to the contribution of the Hankel path.

. 14 )

 14 More details on the derivation of Eq. (3.14) can be found in Appendix B. Comparing formulas (3.7) and(3.14), makes it clear that the choice of the Mittag-Leffler memory kernel γ(t) as given by Eq. (3.1) corresponds to the modelization:

. 15 )Formulas ( 4 . 1 (

 1541 13), (4.14), and (4.15) are deduced from their counterparts valid for any ω (respectively, formulas (3.31), (3.33), and (3.34)) by making f c (|ω|t 0 ) ≃ indeed the cut-off function does not play any role in the angular frequency range |ω|t 0 ≪ 1).

5 ) 1 F 1 +∞ 0 F 1 0 F 1 F 1

 51101011 This result is fully consistent with the form taken by P γ (τ ) (i.e. the distribution of relaxation times associated with the Mittag-Leffler functionE δ [-(t/t 0 ) δ ])in the same range of values of τ (see Eq. (3.25)). Formulas (3.25) and (A.5) display an integrable divergence of the distribution of small relaxation times, which implies a profusion of short time scales in both the Mittag-Leffler function and the associated stretched exponential [24].A.2. The relaxation times distribution associated with the algebraically decaying function (t/t 0 ) -δ Γ(1-δ) (0 < δ < 1) In the same range of values of δ, consider the algebraic function (t/t 0 ) -δ Γ(1-δ) which pictures the long time behaviour of the Mittag-Leffler function E δ [-(t/t 0 ) δ ]. Interestingly, this algebraic function can be written as: A.6) displays the fact that the associated relaxation times distribution is: with the form taken by the function P γ (τ ) as given by Eq.(3.23) for large relaxation times (i.e., for τ ≫ t 0 ).or, in Laplace transforms notations:F1 (z) = ∞ 0 F 1 (t)F 1 e -zt dt F 2 (t)F 1 e -zt dt F (t)F 1 e -zt dt, f2 (z) = F2 (z) (B.9)Now, the second fluctuation-dissipation theorem reads: (t)F 1 = mk B T γ(t), (B.10)or, in Laplace transforms notations:

∞ 0 F 1

 01 (t)F 1 e -zt dt = mk B T γ(z). (B.11) Comparing Eqs. (B.9) and (B.11), gives: use of formula (B.10) at time t = 0, we recover formula (B.1).

13 )γ δ t δ 0 1 -

 131 On the other hand, the second-fluctuation theorem (1.2) reads, using Fourier transforms:|F 1 (ω)| 2 = 2mk B T ℜe γ(iω + φ(ω) , (B.15)

Acknowledgement

We thank the referees for helpful suggestions and comments.

Appendix A

Let us check the consistency, in the case 0 < δ < 1, between the relaxation times distributions obtained for the Mittag-Leffler function E δ [-(t/t 0 ) δ ], on the one hand, and for the stretched exponential function and the algebraically decreasing function respectively describing its short time and long time behaviours, on the other hand.

A.1. The relaxation times distribution associated with the stretched exponential exp[-(t/t 0 ) δ Γ(δ+1) ] (0 < δ < 1) Let us here discuss the existence of a distribution of relaxation times for the modified exponential function exp[-(t/t 0 ) δ Γ(δ+1) ] which pictures the short time behaviour of the Mittag-Leffler function

The stretched exponential exp[-(t/t 0 ) δ Γ(δ+1) ] with 0 < δ < 1 is completely monotonic (it is often referred to as the Kohlrausch-Williams-Watt (KWW) relaxation law [26]), but this is not the case for the compressed exponential exp[-(t/t 0 ) δ Γ(δ+1) ] with 1 < δ < 2. It is therefore solely in the range 0 < δ < 1 that a relaxation times distribution, denoted by P KWW (τ ), can be associated with the modified exponential exp[-(t/t 0 ) δ Γ(δ+1) ]. We set:

exp -

In Eq. (A.1), the relaxation rates distribution µ KWW (k) as given by:

identifies with the one-sided stable Lévy law

. We have [START_REF] Widder | The Laplace Transform[END_REF], [26]:

hence the associated relaxation times distribution:

Appendix B

B.1. The relation between γ(z) and φ(z)

Let us here come back in more detail to the relation (3.14) between γ(z) and φ(z), rewritten below for clarity:

together with the generalized Langevin equation (1.1), rewritten in Laplace transforms notations for convenience:

and the Langevin-like equation (3.10) for F 1 (t), also rewritten in Laplace transforms notations:

Following Mori's procedure [11], we write the particle's velocity as a sum of two orthogonal components, namely, its projective and vertical components with respect to the v axis (the symbol v denotes the value of v(t) at time t = 0):

or, in Laplace transforms notations:

Identifying Eqs. (B.2) and (B.5), gives:

i.e. the first fluctuation-dissipation theorem. In the same way, still following Mori's procedure, we write the Langevin force as a sum of its projective and vertical components with respect to the F 1 axis:

Eq. (B.14) reads:

From formulas (B.13) and (B.16), we deduce the spectral density of the secondorder random force:

that is, making use of the identity φ(ω) = φ(z = -iω), together with the expression (3.15) for φ(z):

Let us now come back to the spectral density |F 1 (ω)| 2 as given by Eq. (B.16).

We have:

an expression, which, once the expression for ℜe φ(ω) is made explicit, identifies with formula (3.33) of the main text, that is: The shorter time scale t 0 intervenes only in the cut-off function. This latter verifies: