Tristan Vaccon
email: tristan.vaccon@unilim.fr

Thibaut Verron
email: thibaut.verron@jku.at

Kazuhiro Yokoyama
email: kazuhiro@rikkyo.ac.jp

On A ine Tropical F5 Algorithms

Keywords: Computing methodologies → Algebraic algorithms; Algorithms, Tropical geometry, Gröbner bases, F5 algorithm, p-adic precision

Let K be a eld equipped with a valuation. Tropical varieties over K can be de ned with a theory of Gröbner bases taking into account the valuation of K. Because of the use of the valuation, the theory of tropical Gröbner bases has proved to provide settings for computations over polynomial rings over a p-adic eld that are more stable than that of classical Gröbner bases.

Beforehand, these strategies were only available for homogeneous polynomials. In this article, we extend the F5 strategy to a new de nition of tropical Gröbner bases in an a ne setting.

We provide numerical examples to illustrate time-complexity and p-adic stability of this tropical F5 algorithm. We also illustrate its merits as a rst step before an FGLM algorithm to compute (classical) lex bases over p-adics.

INTRODUCTION

Tropical geometry as we understand it has not yet reached half a century of age. It has nevertheless spawned signi cant applications to very various domains, from algebraic geometry to combinatorics, computer science, economics, non-archimedean geometry (see [START_REF] Maclagan | Introduction to tropical geometry[END_REF], [START_REF] Einsiedler | Douglas Nonarchimedean amoebas and tropical varieties[END_REF]) and even attempts at proving the Riemann hypothesis (see [C15]).

E ective computation over tropical varieties make decisive use of Gröbner bases. Since Chan and Maclagan's de nition of tropical Gröbner bases taking into account the valuation in [START_REF] Chan | Gröbner bases over elds with valuations and tropical curves by coordinate projections[END_REF][START_REF] Chan | Diane Gröbner bases over elds with valuations[END_REF], computations of tropical Gröbner bases are available over elds

The second author is supported by the Austrian FWF grant F5004.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for pro t or commercial advantage and that copies bear this notice and the full citation on the rst page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior speci c permission and/or a fee. Request permissions from permissions@acm.org. ISSAC '18, July 16-19, 2018, New York, NY, USA © 2018 Copyright held by the owner/author(s). Publication rights licensed to the Association for Computing Machinery. ACM ISBN 978-1-4503-5550-6/18/07. . . $15.00 https://doi.org/10.1145/3208976.3209012 with trivial or non-trivial valuation, but only in a context of homogeneous ideals.

On the other hand, for classical Gröbner bases, numerous algorithms have been developed allowing for more and more e cient computations. The latest generation of algorithms for computing Gröbner bases is the family of signature-based algorithms, which keep track of where the polynomials come from in order to anticipate useless reductions. This idea was initiated in Algorithm F5 [F02], and has since then been widely studied and generalized ( [START_REF] Bardet | On the Complexity of the F5 Gröbner basis Algorithm[END_REF][START_REF] Christian | A survey on signature-based algorithms for computing Gröbner bases[END_REF]).

Most of those algorithms, including the original F5 algorithm, are speci cally designed for homogeneous systems, and adapting them to a ne (or inhomogeneous) systems requires special care (see [E13]).

An F5 algorithm computing tropical Gröbner bases without any trivial reduction to 0, inspired by the classical F5 algorithm, has been described in [START_REF] Vaccon | A Tropical F5 algorithm[END_REF]. The goal of this paper is to extend the de nition of tropical Gröbner bases to inhomogeneous ideals, and describe ways to adapt the F5 algorithm in this new setting.

The core motivation is the following. It has been proved [V15] that computing tropical Gröbner bases, taking into account the valuation, is more stable for polynomial ideals over a p-adic eld than classical Gröbner bases.

Thus, an a ne variant of tropical Gröbner bases is highly desirable to handle non-homogeneous ideals over p-adics. For classical Gröbner bases, it is always possible to homogenize the input ideal, compute a homogeneous Gröbner basis, and dehomogenize the result. This technique is not always optimal, because the algorithm may end up reaching a higher degree than needed, computing points at in nity of the system, but it always gives a correct result and, in the case of signature Gröbner basis algorithms, is able to eliminate useless reductions. However, in a tropical setting, terms are ordered with a tropical term order, taking into account the valuation of the coe cients. As far as we know it, there is no way to dehomogenize a system in a way that would preserve the tropical term order. Indeed, no tropical term order can be an elimination order.

Moreover, the FGLM algorithm can be adapted to the tropical case (see Chap. 9 of [V*]), making it possible to compute a lexicographical (classical) Gröbner basis from a tropical one. We provide numerical data to estimate the loss in precision for the computation of a lex Gröbner basis using a tropical F5 algorithm followed by an FGLM algorithm, in an a ne setting.

Related works

A canonical reference for an introduction to computational tropical algebraic geometry is the book of Maclagan and Sturmfels [START_REF] Maclagan | Introduction to tropical geometry[END_REF].

The computation of tropical varieties over Q with trivial valuation is available in the Gfan package by Anders Jensen (see [Gfan]), by using standard Gröbner bases computations. Chan and Maclagan have developed in [START_REF] Chan | Diane Gröbner bases over elds with valuations[END_REF] a Buchberger algorithm to compute tropical Gröbner bases for homogeneous entry polynomials (using a special division algorithm). Following their work, still for homogeneous polynomials, a Matrix-F5 algorithm has been proposed in [V15] and a Tropical F5 algorithm in [START_REF] Vaccon | A Tropical F5 algorithm[END_REF]. Markwig and Ren have provided a completely di erent technique of computation using projection of standard bases in [START_REF] Markwig | Yue Computing tropical varieties over elds with valuation[END_REF], again only for homogeneous entry polynomials.

In the classical Gröbner basis setting, many techniques have been studied to make the computation of Gröbner bases more efcient. In particular, Buchberber's algorithm is frequently made more e cient by using the sugar-degree (see [START_REF] Alessandro | One sugar cube, please" or selection strategies in the Buchberger algorithm[END_REF][START_REF] Bigatti | Computing inhomogeneous Gröbner bases[END_REF]) instead of the actual degree for selecting the next pair to reduce. This technique was a precursor of modern signature techniques, in the sense that the sugar-degree of a polynomial is exactly the degree of its signature. General signature-based algorithms for computing classical Gröbner bases of inhomogeneous ideals have been extensively studied in [E13].

Speci cities of computating tropical GB

The computation of tropical GB, even by a Buchberger-style algorithm, is not as straightforward as for classical Gröbner bases. One way to understand this is the following: even for homogeneous ideals, there is no equivalence between tropical Gröbner bases and row-echelon linear bases at every degree. Indeed,we can remark that

(f 1 , f 2 ) = (x + , 2x + ) is a tropical GB over Q[x,
] with 2adic valuation, w = [0, 0] and grevlex ordering. Nevertheless, the corresponding 2 × 2 matrix in the vector space of homogeneous polynomials of degree 2 is not under tropical row-echelon form.

As a consequence, reduction of a polynomial by a tropical GB is not easy. In [START_REF] Chan | Gröbner bases over elds with valuations and tropical curves by coordinate projections[END_REF][START_REF] Chan | Diane Gröbner bases over elds with valuations[END_REF], Chan and Maclagan relied on a variant of Mora's tangent cone algorithm to obtain a division algorithm. In [START_REF] Vaccon | Matrix-F5 Algorithms and Tropical Gröbner Bases Computation[END_REF][START_REF] Vaccon | A Tropical F5 algorithm[END_REF], the authors relied on linear algebra and the computation of (tropical) row-echelon form. In this article, we extend their method to the computation of tropical Gröbner bases in an a ne setting, through an F5 algorithm.

Main idea and results

Extending the tropical F5 algorithm to inhomogeneous inputs poses two di culties. First, as mentioned, tropical Gröbner bases used to be only de ned and computed for homogeneous systems. Even barebones algorithms such as Buchberger's algorithm are not available for inhomogeneous systems. The second problem is a general problem of signature Gröbner bases with inhomogeneous input. The idea of signature algorithms is to compute polynomials with increasing signatures, and the F5 criterion detects trivial reductions to 0 by matching candidate signatures with existing leading terms. For homogeneous ideals, the degree of the signature of a polynomial and the degree of the polynomial itself are correlated. This is what makes the F5 criterion applicable.

The survey paper [E13] has shown that Algorithm F5, using the position over term ordering on the signatures, has to reach a tradeo between eliminating all reductions to 0 and performing other useless reductions.

More precisely, let f 1 , . . . , f m be homogeneous polynomials with coe cients in a eld with valuation K, and de ne I k,d the vector space of polynomials in f 1 , . . . , f k with degree at most d. With the usual computational strategy, the algorithm computes a basis of I 1, 1 , then I 2, 1 , and so on until I m, 1 , and then I 1, 2 , and so on. In a lot of situations [START_REF] Bardet | On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations Proceeding of the[END_REF] ideals with more generators have a Gröbner basis with lower degree, and this strategy ensures that the algorithm does not reach a degree higher than needed.

However, the same algorithm for a ne system will, at each step, merely compute a set of polynomials in each I k,d . This set needs not be a generating set because of degree falls. To obtain a basis instead, one has to proceed up to some I k,δ with δ ≥ d. When δ > d, some polynomials will be missing for the F5 criterion in degree less than δ , and the corresponding trivial reductions to 0 will not be eliminated.

In this paper, we show that the tropical F5 algorithm [START_REF] Vaccon | A Tropical F5 algorithm[END_REF] works in an a ne setting, and we characterize those trivial reductions to 0 which are eliminated by the F5 criterion. In particular, we show that the Macaulay matrices built at each step of the computations are Macaulay matrices of all polynomials with a given sugar-degree.

Compared to [START_REF] Vaccon | A Tropical F5 algorithm[END_REF], the overall presentation of the F5 algorithms is clari ed. It can now be summarized as the following strategy: ltration, signature, F5 elimination criterion, Buchberger-F5 criterion and nally the F5 algorithm.

T 1.1. Given a set of (non-necessarily homogeneous) polynomials f 1 , . . . , f m ∈ K[X 1 , . . . , X n ], the Tropical F5 algorithm (Algorithm 3) computes a tropical Gröbner basis of I , without reducing to 0 any trivial tame syzygy (Def. 3.1).

We also examine an incremental a ne version of the homogeneous tropical F5-algorithm and an a ne tropical F4, and we compare their performances on several examples. Even in a nonhomogeneous setting, the loss in precision of the tropical F5 algorithm remains satisfyingly low.

Organization of the paper

Section 2 introduces notations and nonhomogeneous tropical Gröbner bases. Section 3 then introduces the ltration on ideals necessary for F5 algorithms in this context. Section 4 is devoted to provide a Buchberger-F5 criterion on which Section 5 elaborates a rst tropical F5 algorithm. Section 6 brie y presents other methods for the computation of nonhomogeneous tropical Gröbner bases. Finally, Section 7 displays numerical results related to the precision behaviour and time-complexity of the algorithms we have described.

AFFINE TROPICAL GB 2.1 Notations

Let k be a eld with valuation al . The polynomial ring k[X 1 , . . . , X n ] will be denoted by A. Let T be the set of monomials of A. For

u = (u 1 , . . . , u n ) ∈ Z n ≥0 , we write x u for X u 1 1 . . . X u n n and | f | for the degree of f ∈ A. In A s , (e i ) s i =1
is the canonical basis. The matrix of a list of polynomials written in a basis of monomials is called a Macaulay matrix.

Given a mapping ϕ : U → V , Im(ϕ) denotes the image of ϕ. For a matrix M, Rows(M) is the list of its rows, and Im(M) denotes the left-image of M (i.e. Im(M) = span(Rows(M)). For w ∈ Im( al) n ⊂ R n and ≤ 1 a monomial order on A, we de ne ≤ a tropical term order as in the following de nition: De nition 2.1. Given a, b ∈ k * and x α and x β two monomials in A, we write ax α < bx β if:

• |x α | < |x β |, or • |x α | = |x β |, and al(a) + w • α > al(b) + w • β, or al(a) + w • α = al(b) + w • β and x α < 1 x β . For u of valuation 0, we write ax α = ≤ uax α . Accordingly, ax α ≤ bx β if ax α < bx β or ax α = ≤ bx β .
Throughout this article, we are interested in computing a tropical Gröbner basis of I = f 1 , . . . , f s for some given f 1 , . . . , f s ∈ A (ordered increasingly by degree).

Tropical GB

A tropical term order provides an order on the terms of the polynomials f ∈ A.

De nition 2.2. For f ∈ A, we de ne LT (f ) to be the biggest term of f . We de ne LM(f ) to be the monomial corresponding to LT (f ) and LC(f ) the corresponding coe cient.

We de ne LM(I ) to be the monomial ideal generated by the monomials LM(f ) for f ∈ I .

We can then naturally de ne what is a tropical Gröbner basis (tropical GB for short):

De nition 2.3. G ⊂ I is a tropical GB of I if span(LM( ) for ∈ G) = LM(I ).
We can remark that for homogeneous polynomials this de nition coincide with that given in [START_REF] Vaccon | A Tropical F5 algorithm[END_REF].

FILTRATION AND S-GB

De nition and elimination criterion

One of the main ingredient for F5 algorithms is the de nition of a vector space ltration of the ideal I . It is de ned from the initial polynomials F = (f 1 , . . . , f s ) generating I . For simplicity, we assume that they are ordered by increasing degree.

First, we extend ≤ to the monomials of the vector space A s . To that intent, we highlight some monomials that appear as leading monomial of a syzygy.

De nition 3.1. Let (a 1 , . . . , a s ) ∈ A s and i ∈ {1, . . . , s } be such that: (1) j a j f j = 0. (2) a i 0 and a j = 0 for j > i. (3) for all j < i,

|a j f j | ≤ |a i f i |.
We call such a syzygy a tame syzygy and we de ne LM(a i )e i to be its leading monomial. We de ne LM(T S z(F )) as the module in A s generated by the leading monomials of the tame syzygies. Trivial tame syzygies are the tame syzygies that are also trivial (i.e. in the module generated by the f i e jf j e i ).

The F5 criterion that we use in this article is designed to recognize some of the tame syzygies and use this knowledge to avoid useless reduction to zero of some polynomials. It is the main motivation for de ning a ltration on the vector space A s . We use a degree-re ning monomial ordering ≤ m on A. 1 We de ne a total order on the monomials of A s . De nition 3.2. We write that x α e i ≤ si n x β e j if:

1 ≤ m is not necessarily related to ≤ 1 and ≤.

(1

) if i < j, or (2) if i = j and |x α f i | < |x β f j |, or (3) if i = j and |x α f i | = |x β f j |, and • x α LM(T S z(F )) and x β ∈ LM(T S z(F )), or • both x α , x β ∈ LM(T S z(F )) and x α ≤ m x β , or • both x α , x β LM(T S z(F )) and x α ≤ m x β .
De nition 3.3. We consider the vector space

I ≤ s i n x α e i := Span({x β f j , s.t. x β e j ≤ si n x α e i })
and the vector space I < s i n x α e i de ned accordingly. We de ne I =

↑x α e i I ≤ s i n x α e i as an increasing vector space ltration of I .

We then have a very natural de nition of signature. In litterature, this notion of signature is sometimes called minimal signature.

De nition 3.4. For f ∈ I , the smallest x α e i such that f ∈ I ≤ s i n x α e i is called the signature of f and noted S(f ).

The degree |x α f i | is called the sugar-degree of x α e i . 2 For the purpose of Algorithm 3, we design a ltration compatible with the sugar-degree.

De nition 3.5. We consider the vector space

I ≤d = Span({x β f j , s.t. |x β e j | ≤ d })
We then de ne, for x α e i with sugar-degree d, the vector space I ≤d ≤ s i n x α e i = Span({x β f j , s.t. x β e j ≤ si n x α e i and |x β f j | ≤ d }). I = ↑d I ≤d is also a vector space ltration. I ≤d can itself be ltrated by the I ≤d ≤ s i n x α e i . We have a compatible notion of signature:

De nition 3.6. For d ∈ Z >0 and f ∈ I ≤d , the smallest x α e i such that f ∈ I ≤d ≤ s i n x α e i is called the d-signature of f and noted S d (f ).

We remark that S d (f ) can be di erent from S(f ) for small f , but all S d (f ) are equal when d is large.

The main motivation for de ning the vector spaces I ≤d ≤ s i n x α e i is their nite dimension. Their compatibility with the sugar-degree allows the F5 algorithm to compute only one Macaulay matrix by sugar-degree d.

The goal of the F5 criterion is to recognize some x α e i such that the ltration is constant at I ≤d ≤ s i n x α e i . As a consequence, this knowledge allows to skip some calculation as, because of this constancy, they will not provide any new leading monomial. We can then state a rst version of the F5 elimination criterion:

P 3.7 ([F02]). If x α is such that x α e i ∈ LM(Ts z(F )), d ≥ |x α f i |, then the ltration is constant at I ≤d ≤ s i n x α e i . If x α ∈ LM(I ≤d ≤ s i n x β e j
) for some x β and j such that |x β f j | ≤ |x α |, then

x α e i ∈ LM(Ts z(F )) for any i > j.

P

. For the rst part, we can write (x α + )f i = j <i a j f j , with LT ( ) < x α and for all j < i, |a j f j | ≤ |x α f i |. Then:

x α f i = (-)f i + i -1 j=1 a j f j .
2 Sugar-degree has been introduced and explored in [START_REF] Alessandro | One sugar cube, please" or selection strategies in the Buchberger algorithm[END_REF][START_REF] Bigatti | Computing inhomogeneous Gröbner bases[END_REF].

By linear algebra and a complete reduction using as pivot the x β e j ∈ LM(Ts z(F )), we can assume that has no monomial in LM(T S z(F )) and obtain: x α f i ∈ I ≤d <x α e i , and therefore, the ltration is constant at I ≤d ≤x α e i . For the second part, we can write

x α + = k ≤j a k f k , with LT ( ) < x α and for all k ≤ j, |a j f j | ≤ |x β f j | ≤ |x α |. Then (x α + )f i -k ≤j (a k f i )f k = 0 and we do have |x α f i | ≥ |(a k f i )f k | for all k ≤ j.
If all the f i 's are homogeneous, this coincides with the usual F5 elimination criterion, as for example stated in [START_REF] Vaccon | A Tropical F5 algorithm[END_REF], which eliminates all trivial reductions to zero in the course of the algorithm. For a ne polynomials, the F5 criterion only eliminates those trivial reductions which are tame.

Tropical S-GB

In order to take advantage of the F5 elimination criterion to compute tropical Gröbner bases, we focus on the computation of tropical Gröbner bases which are compatible with the ltration: tropical S-GB. We rst need the de nition of reductions compatible with the ltration and the corresponding irreducible polynomials.

De nition 3.8 (S-reduction)

. Let e, ∈ I , h ∈ I . We say that e S-reduces to with h, e → h S , if there are t ∈ T and α ∈ k * such that:

• LT ( ) < LT (e), LM( ) LM(e) and eαth = and • S(th) < si n S(e).

It is then natural to de ne what is an S-irreducible polynomial.

De nition 3.9 (S-irreducible polynomial). We say that ∈ I is S-irreducible if there is no h ∈ I which S-reduces . If there is no ambiguity, we might omit the S -.

De nition 3.10 (Tropical S-Gröbner basis). We say that G ⊂ I , a set of S-irreducible polynomials, is a tropical S-Gröbner basis (or tropical S-GB, or just S-GB for short when there is no ambiguity) of I with respect to a given tropical term order, if for each S-irreducible polynomial h ∈ I , there exist ∈ G and t ∈ T such that LM(t ) = LM(h) and tS( ) = S(h).

De nition 3.11. De nitions 3.8, 3.9 and 3.10 have natural analogues when one restricts to the vector space I ≤d and S d with S dreduction, S d -irreducible polynomial and tropical S d -GB. P 3.12. If G is a tropical S-Gröbner basis, then for any nonzero h ∈ I , there exist ∈ G and t ∈ T such that:

• LM(t ) = LM(h) • S(t ) = tS( ) = S(h) if h is irreducible, and S(t ) = tS( ) < si n S (
h) otherwise. Hence, there is an S-reductor for h in G when h is not irreducible. As a consequence computing a tropical S-GB provides a tropical GB, and we can use the F5 elimination criterion 3.7 to our advantage when computing these tropical S-GB. Moreover, we also have the following niteness result: P 3.14. Every tropical S-Gröbner basis contains anite tropical S-Gröbner basis.

P

. We refer to the proof of Proposition 14 of [AP]. It uses an adapted Dickson's Lemma and since it is mostly a question of monomial ideals, the transposition to the tropical setting is direct.

Linear algebra and existence

For x α ∈ T and 1 ≤ i ≤ n, let us denote by Mac ≤ s i nx α e i (F ) the Macaulay matrix of the polynomials x β f j such that x β f j ≤ x α f i , ordered increasingly for the order on the x β e j 's. One can perform a tropical LUP algorithm on Mac ≤d (F ) (see Algo. 2) and obtain all the leading monomials in I ≤ s i n x α e i . This can be (theoretically) performed for all x α e i to obtain the existence of an S-GB of I .

More on signatures

We de ne Σ to be the set of signatures.

Thanks to Proposition 3.7, not all x α e i can be a signature:

Remark 3.15. If x α e i ∈ LM(T S z(F )) then x α e i Σ.
We provide two lemmata to understand the compatibility of Σ with basic operations on polynomials. If one takes the point of view of linear algebra, the proof is direct.

L 3.17. If ∈ I and τ ∈ T then S(τ ) ≤ τS( ). If moreover τS( ) ∈ Σ, then S(τ ) = τS( ) and for all µ ∈ T such that µ divides τ , S(µ ) = µS( ).

P

. The rst part is direct. For the second part, one can show that it is possible to write that τ = h+r for some h ∈ I of signature τS( ), irreducible, and r ∈ I < s i n τ S ( ) and conclude that S(τ ) = τS( ).

For the last statement, assume that there exists a µ ∈ T dividing τ such that S(µ ) < µS( ). Then S(τ ) = S( τ µ µ ) ≤ τ µ S(µ ) < τ µ µS( ) = τS( ), which is a contradiction.

BUCHBERGER-F5 CRITERION

In this section, we explain a criterion, the Buchberger-F5 criterion, on which we build our F5 algorithm to compute tropical S-Gröbner bases. It is an analogue of the Buchberger criterion which includes the F5 elimination criterion. We need a slightly di erent notion of S-pairs, called here normal pairs and can then state the Buchberger-F5 criterion.

De nition 4.1 (Normal pair). Given 1 , 2 ∈ I , let Spol( 1 , 2 ) = u 1 1u 2 2 be the S-polynomial of 1 and 2 , with for i ∈ {1, 2},

u i = l cm(LM( 1 ), LM( 2 )) LT ( i )
. We say that ( 1 , 2 ) is a normal pair if:

(1) the i 's are S-irreducible polynomials.

(2) S(u i i ) = LM(u i )S( i ) for i = 1, 2.

(3) S(u 1 1 ) S(u 2 2 ).

We de ne accordingly d-normal pairs in I ≤d .

T 4.2 (B F5

). Suppose that G is a nite set of S-irreducible polynomials of I = f 1 , . . . , f s such that:

(1) for all ∀i ∈ 1, s , there exists ∈ G such that S( ) = e i .

(2) for any 1 , 2 ∈ G such that ( 1 , 2 ) is a normal pair, there exists ∈ G and t ∈ T such that t is S-irreducible and tS( ) = S(t ) = S(Spol( 1 , 2 )). Then G is a S-Gröbner basis of I . The analogue result using d-normal pairs to recognize an S d -GB in I ≤d is also true.

Remark 4.3. The converse of this result is clear. Theorem 4.2 is an analogue of the Buchberger criterion for tropical S-Gröbner bases. To prove it, we adapt the classical proof of the Buchberger criterion and the proof of the tropical Buchberger algorithm of Chan and Maclagan (Algorithm 2.9 of [C13]). We need two lemmata, the rst one being elementary.

L 4.4. Let x α , x β , x γ , x δ ∈ T and P, Q ∈ A be such that LM(x α P) = LM(x β Q) = x γ and x δ = lcm(LM(P), LM(Q)). Then Spol(x α P, x β Q) = x γ -δ Spol(P, Q). L 4.5.
Let G be an S-Gröbner basis of I up to some signature σ . Let h ∈ I , be such that S(h) ≤ σ . Then there exist r ∈ N, 1 , . . . , r ∈ G, Q 1 , . . . , Q r ∈ A such that for all i and x α a monomial of Q i , S(x α i ) = x α S( i ) ≤ S(h) and LT (Q i i ) ≤ LT (h), the x α S( i )'s are all distinct and non-zero, and, nally, we have

h = r i =1 Q i i . P .
It is clear by linear algebra. One can form a Macaulay matrix whose rows correspond to polynomials cτ with τ ∈ T , c ∈ k * , ∈ G such that S(τ ) = τS( ) ≤ S(h). Only one row is possible per non-zero signature, and each monomial in LM(I ≤σ ) is reached as leading term by only one row. It is then enough to stack h at the bottom of this matrix and perform a tropical LUP form computation (see Algorithm 2) to read the Q i 's on the reduction of h.

PROOF

T 4.2. We prove the main result by induction on the signature. We follow the order ≤ si n for the induction. It is clear for σ = e 1 and also for the fact we can pass from an S-GB up to < si n e i to ≤ si n e i . We write the elements of G as 1 , . . . , r for some r ∈ Z >0 .

Let us assume that G is an S-GB up to signature < si n σ for some signature σ and let us prove it is a S-GB up to ≤ si n σ . We can assume that all ∈ G satisfy LC( ) = 1. Let P ∈ I be irreducible, with LC(P) = 1 and such that S(P) = σ . We prove that there is τ ∈ T , ∈ G such that LM(P) = LM(τ ) and S(τ ) = τS( ) = σ .

Our rst assumption for G implies that there exist at least one ∈ G and some τ ∈ T such that τS( ) = S(P) = σ .

If LM(τ ) = ≤ LM(P) we are done. Otherwise, by Lemma 3.16, there exist some a, b ∈ k * such that S(aP + bτ ) = σ ′ for some σ ′ < si n σ .

We can apply Lemma 4.5 to aP + bτ and obtain that there exist h 1 , . . . , h r ∈ A, such that P = r i =1 h i i , and for all i, and x γ monomial of h i , the x γ S( i ) = S(x γ i ) ≤ si n σ are all distincts. We remark that LT (P) ≤ max i (LT ( i h i )). We denote by m i := LT ( i h i ).

Among all such possible ways of writing P as r i =1 h i i , we dene β as the minimum of the max i (LT ( i h i ))'s. Such a β exists thanks to Lemma 2.10 in [START_REF] Chan | Diane Gröbner bases over elds with valuations[END_REF] (adaptation to the non-homogeneous setting is for free). We write x u = LM(β).

If LT (P) = ≤ β, then we are done. Indeed, there is then some i and τ in the terms of h i such that LM(τ i ) = LM(P) and S(τ i ) = τS( i ) ≤ si n σ .

We now show that LT (P) < β leads to a contradiction.

We can renumber the i 's so that:

• β = ≤ m 1 = ≤ • • • = ≤ m d . • β > m i for i > d.
We can assume that among the set of possible (h 1 , . . . , h r ) that reaches β, we take one such that this d is minimal.

Since LT (P) < β, then we have d ≥ 2. We can write

Spol( 1 , 2 ) = LC( 2 ) lcm(LM( 1 ), LM( 2 )) LM( 1 ) 1 -LC( 1 ) lcm(LM( 1 ), LM( 2 ) LM( 2 ) 2 .
By construction, LM(h 1 )S( 1) LM(h 2 )S( 2 ), so (LM(h 1 ) 1 , LM(h 2 2 ) is a normal pair. By Lemma 4.4, there exists a term µ such that µ l cm(LM( 1 ), LM( 2 ))

LM( i )

= LM(h i ) for i ∈ {1, 2}. So by Lemma 3.17, ( 1 , 2 ) is a normal pair as well.

If S(Spol( 1 , 2 )) = σ, by the second property of the F5 criterion, we are done.

Otherwise, S(Spol( 1 , 2 )) < si n σ . Moreover, let

L = LC(h 1 1 ) LC( 1 )LC( 2 )
x u lcm(LM( 1 ), LM( 2))

.

Then we have S(L • Spol( 1 , 2 )) ≤ si n σ thanks to Lemma 4.4. Using the same construction as before with the rst assumption of the F5 criterion and Lemmata 3.16 and 4.5, we obtain some

h ′ i 's such that L •Spol( 1 , 2 ) = r i =1 h ′ i i , LT (h ′ i i ) ≤ LT (L •Spol( 1 , 2 ))
< β for all i. Furthermore, the signatures S(x α i ) = x α S( i ) for i ∈ {1, . . . , r } and x α in the support of h ′ i are all distincts. We then get:

P = r i =1 h i i , = r i =1 h i i -L • Spol( 1 , 2 ) + r i =1 h ′ i i , = h 1 - LC(h 1 1 ) LC( 1 ) x u LM( 1 ) + h ′ 1 1 + h 2 - LC(h 1 1 ) LC( 2 ) x u LM( 2 ) + h ′ 2 2 + r i =3 h i + h ′ i i , =: r i =1 h i i ,
where the h i 's are de ned naturally. By construction, LT (

h 1 1 ) < LT (h 1 1 ) = β and LT ( h i ) ≤ β for i ≤ d and LT ( h i ) < β for i > d.
As a consequence, we have obtained a new expression for f with either max i (LT ( h i )) < β or this term attained stricly less than d times, which is in either case a contradiction with their de nitions as minima. So LT (P) = ≤ β, which concludes the proof of the main result. It is then direct to adapt the previous proof to the case of an S d -GB. This theorem holds also for S-GB (or S d -GB) up to a given signature. We have the following variant as a corollary for compatibility with sugar-degree: P 4.6. Suppose that d ∈ Z >0 , and G is a nite set of polynomials of I such that:

(1) Any ∈ G is S d -irreducible in I ≤d .

(2) For all 1 , 2 ∈ G we have 1 , 2 and Spol( 1 , 2 ) in I ≤d .

(3) For all i ∈ 1, s , there exists ∈ G such that S d ( ) = e i . (4) for any 1 , 2 ∈ G such that ( 1 , 2 ) is a d-normal pair, there exists ∈ G and t ∈ T such that t is S d -irreducible and

tS d ( ) = S d (t ) = S d (Spol( 1 , 2 )).
Then G is an S-Gröbner basis of I .

FALGORITHM

In this section, we present our F5 algorithm. To this intent, we need to discuss some crucial algorithmic points: how to recognize with which pairs to proceed and how to build the Macaulay matrices and reduce them. Some algorithms are on the following page.

Admissible pairs and guessed signatures

The second condition in the De nition 4.1 of normal pairs is not possible to check in advance in an F5 algorithm. One needs an S-Gröbner basis up to the corresponding signature to be able to certify it. To circumvent this issue, we use the weaker notion of admissible pair.

De nition 5.1 (d-Admissible pair). Given 1 , 2 ∈ I ≤d , let Spol( 1 , 2 ) = u 1 1u 2 2 be the S-polynomial of 1 and 2 . We have

u i = lcm(LM( 1 ), LM( 2 )) LT ( i ) .
We say that ( 1 , 2 ) is a d-admissible pair if:

(1) LM(u i )S d ( i ) = x α i e j i LM(T S z).

(2) LM(u 1 )S d ( 1 ) LM(u 2 )S d ( 2 ).

To certify that a set is an S d -GB, handling d-admissible pairs instead of d-normal pairs is harmless. Indeed, d-normal pairs in I ≤d are contained inside the d-admissible pairs. Whether a pair is d-admissible can be checked easily before proceeding to reduction.

During the execution of the algorithm, when a polynomial x α is processed, it is at rst not possible to know what is its signature. Algorithm 3 has computed S d ( ) beforehand. Thanks to the F5 elimination criterion (Prop 3.7), we can detect some of the x α such that S(x α ) x α S( ) and eliminate them. For the processed polynomials, we use x α S d ( ) as a guessed signature in the algorithm. Once an S-GB up to signature < x α S d ( ) is computed, we have the following alternative. First case: S d (x α ) < x α S d ( ) and x α reduces to zero (by the computed S d -GB up to d-signature < x α S d ( )). The guessed signature was wrong but it is harmless as the polynomial is useless anyway. Second case: S d (x α ) = x α S d ( ), and then the guessed signature is certi ed. Once the criterion of Proposition 4.6 is satis ed, all signatures are certi ed.

What happens when we can obtain f with signature S d (f ) = x α e i in degree d, and S d +1 (f ) = x β e j < si n x α e i in degree d + 1? Thanks to the way Algorithm 1 handles polynomials, always looking for smallest signature available, f and its multiples will then be built using only the second way. The rst way of writing will at most appear so as to be reduced by the second one.

Symbolic Preprocessing and Rewritten criterion

One of the main parts of the F5 algorithm 3 is the Symbolic Preprocessing : Algorithm 1. From the current set of S-pairs, sugar-degree d, and the current S d -1 -GB, it produces a Macaulay matrix. One can read on the tropical reduction of this matrix new polynomials to append to the current basis to obtain an S d -GB. It mostly consists of detecting which pairs are admissible and selecting a (complete) set of reductors.

A special part of the algorithm is the use of Rewritten techniques (due to Faugère (see [F02])).

The idea is the following. Once a polynomial has passed the F5 elimination criterion and is set to appear in a Macaulay matrix, it can be replaced by any other multiple of an element of G of the same d-signature. Indeed, assuming correctness of the algorithm without any rewriting technique, if one of them, h, is of d-signature x α e i , the algorithm computes a tropical S-Gröbner basis up to d-signature < si n x α e i . Hence, h can be replaced by any other polynomial of same signature: it would be reduced to the same polynomial. By induction, one can prove that all of them can be replaced at the same time. We also remark that this is still valid for replacing a row of a given guessed d-signature by another of the same guessed d-signature.

One e cient way is to replace a polynomial t × by the polynomial x β h (h ∈ G) of same (guessed) d-signature tS d ( ) such that x β has smallest degree. 3 Taking the sparsest available is another possibility. It actually leads to a substantial reduction of the running time of the F5 algorithm.

Linear algebra

To reduce the Macaulay matrices while respecting the signatures, we use the following tropical LUP algorithm from [V15]: Algorithm 2. If the rows correspond to polynomials ordered by increasing signature, it computes a row-reduction, respecting the signatures with each non-zero row with a di erent leading monomial.

A Complete Algorithm

We now provide with Algorithm 3 a complete version of an F5 algorithm wich uses Buchberger-F5 criterion and all the techniques introduced in this section.

T 5.2. Algorithm 3 computes an S-GB of I . It avoids trivial tame syzigies.

P

. It relies on Theorem 4.2 and then Proposition 4.6. The proof is by induction on the sugar-degree, then i, then the x α e i . One rst proves that at the end of the main while loop any guessed signature is correct, or its row has reduced to zero, and then that S d -GB are computed, signature by signature. One can then apply 4.6 on the output to conclude. Termination is a consequence of correctness and Prop. 3.14. For the syzygies, it is a consequence of Prop. 3.7 and the fact that trivial syzygies of leading monomial x α e i are such that x α ∈ LM( f 1 , . . . , f i -1 ).

Remark 5.3. Condition 1 of 4.2 and 3 of 4.6 is not satis ed when for some i, f i ∈ f 1 , . . . , f i -1 . This is harmless as: (1) As soon as it is found by computation, no signature in e i will appear anymore. (2) The Buchberger-F5 criterion can be applied omitting f i .

C 3 .

 3 13. If G is a tropical S-Gröbner basis, then G is a tropical Gröbner basis of I , for < .

L 3 .

 3 16. If f , ∈ I are such that S(f ) = S( ) and LM(f ) LM( ), then there exist a, b ∈ k * such that S(a f + b ) < S(f ) and a f + b 0.

Acknowledgements

We thank Jean-Charles Faugère, Marc Mezzarobba, Pierre-Jean Spaenlehauer, Masayuki Noro, and Naoyuki Shinohara for fruitful discussions.

Algorithm 1: Symbolic-Preprocessing-Rewritten input : P, a set of d -1-admissible pairs of sugar-degree d and G such that G ∩ I ≤d -1 is an S d -1 -GB output : A Macaulay matrix of degree d 1 for Q polynomial in P do 2 Replace Q in P by the polynomial (uS( ),u × ) with latest added to G reaching the same guessed signature ;

3 C ← the set of the monomials of the polynomials in P ; 4 U ← the polynomials of P with their signature, except only one polynomial is taken by guessed signature ; Find j such that M i, j has the greatest term M i, j x mon j for ≤ of the row i; 7 Swap the columns 1 and j of M, and the 1 and j entries of mon;

8 By pivoting with the rst row, eliminates the coe cients of the other rows on the rst column;

9 Proceed recursively on the submatrix M i ≥2, j ≥2 ; 10 Return M;

Algorithm 3: A complete F5 algorithm input : f 1 , . . . , f s polynomials, ordered by degree output :

Replace the occurence of f i in G by its reduction modulo G ∩ f 1 , . . . , f i -1 ; 6 OTHER ALGORITHMS 6.1 Iterative F5

In this subsection, we present brie y another way of extending the F5 algorithm to the a ne setting: a completely iterative way in the initial polynomials. The idea is to compute tropical Gröbner bases for f 1 , f 1 , f 2 , . . . , f 1 , . . . , f s . This corresponds to using the position over term ordering on the signatures, or in terms of ltration, to the following ltration on A s : De nition 6.1. We write that x α e i ≤ incr x β e j if:

(1) if i < j.

(2

, then the ltration is constant at I ≤x α e i .

P

. We can write x α + = j <i a j f j , with for all j a j ∈ I , and ∈ I with no monomial in LM(I i -1 ). Then:

and the ltration is constant at I ≤x α e i .

It is then possible to state a Buchberger-F5 criterion and provide an adapted F5 algorithm. The two algorithms will then di er in the following way. 1. For a given x α and e i , the vector space I <x α e i is much bigger in the iterative setting, often of in nite dimension. Thus, polynomials of signature x α e i can be more deeply reduced. 2. More syzygies can be avoided in the iterative setting. 3. However, many more matrices are to be produced: one for each i and each necessary degree. Construction of the matrices is not mutualised by degree anymore.

F4

Another way to compute tropical Gröbner bases for a ne polynomials is to adapt Faugère's F4 algorithm [F99] Roughly, the F4 algorithm is an adaptation of Buchberger's algorithm such that: all S-polynomials of a given degree are processed and reduced together in a big Macaulay matrix, along with their reducers. The algorithm carries on the computation until there is no S-polynomials to reduce.

In a tropical setting, we have adapted the so-called "normal strategy" of F4 using the tropical LUP algorithm to reduce the Macaulay matrices. We have used Algorithm 2 to reduce the Macaulay matrices. So-called tropical row-echelon forms (Algorithm 3.2.2 and 3.7.3 of [V15]) are also possible, enabling a trade-o between speed, thoroughness of the reduction and loss in precision.

NUMERICAL EXPERIMENTS

A toy implementation of our algorithms in Sagemath [Sage] is available on https://gist.github.com/TristanVaccon. We have gathered some numerical results in the following arrays. Timings are in seconds of CPU time. 4

Benchmarks

Here, the base eld is Q with 2-adic valuation. We have applied the tropical F5 algorithm, Algorithm 3, an iterative tropical F5, and a tropical F4 algorithm on the Katsura n and Cyclic n systems for varying n. Dots mean no conclusion in decent time.

w=[0,.

Trop. F5+FGLM

For a given p, we take three polynomials with random coe cients in Z p (using the Haar measure) in

We rst compute a tropical Gröbner basis for the weight w = [0, 0, 0] 5 and the grevlex monomial ordering, and then apply an FGLM algorithm (tropical to classical as in Chapter 9 of [V*]) to obtain a lex GB. For any given choice of d i 's, we repeat the experiment 50 times. Coe cients of the initial polynomials are all given at some high-enough precision O(p N ) for no precision issue to appear. We can not provide a certi cate on the monomials of the output basis though. Results are compiled in the following arrays. 4 Everything was performed on a Ubuntu 16.04 with 2 processors of 2.6GHz and 16 GB of RAM. 5 E ciency of this choice regarding to the loss in precision was studied in the extended version of [V15] Firstly, an array for timings given as couples: average of the timings for the tropical F5 part and for the FGLM part, with D = d 1 +d 2 +d 3 -2, the Macaulay bound. We add that for p = 2, 3, there is often a huge standard deviation on the timings of the F5 part. Coe cients of the output tropical GB or classical GB are known at individual precision O(p N -m ). We compute the total mean and max on those m's on the obtained GB. Results are compiled in the following array as couples of mean and max. The rst array is for the F5 part and the second for the precision on the nal result. Most of the loss in precision appears in the FGLM part. In comparison, the F5 part is quite stable, and hence, our goal is achieved.


Julie Coloigner

Chau Vu

PhD Matt Borzage

MS Adam M Bush

PhD Natasha Lepore

MD Thomas D Coates

MD, PhD John C Wood

Analysis of Hemodynamic Changes and Bold Signals of Sickle Cell Disease Patients during Desaturation

Introduction: Using nearinfrared spectroscopy (NIRS), previous studies have shown that sicklecell disease (SCD) patients have low cerebral oxygen saturation values [START_REF] Nahavandi | Nearinfrared spectra absorbance of blood from sickle cell patients and normal individuals[END_REF]. Moreover, the hemoglobin S in sickle cell disease has impaired oxygen carrying capacity [START_REF] Logothetis | The neural basis of the bloodoxygenleveldependent functional magnetic resonance imaging signal[END_REF]. Here, we propose to investigate the effect of induced desaturation on the SCD brain. In particular, we analyzed the falling functional magnetic resonance imaging (fMRI) response during hypoxia, which results from local concentration changes in paramagnetic deoxyhemoglobin (DHB). Moreover, we also explore the nearinfrared spectroscopy (NIRS) changes in oxygenated and deoxygenated hemoglobin from the human prefrontal cortex.

Methods: All patients were recruited through informed consent or assent; this study obtained approval from the IRB at Children's hospital Los Angeles. Exclusion criteria included pregnancy, previous stroke, and acute chest pain and crisis hospitalization within one month. Eight patients with SCD and 20 healthy age and ethnicity matched controls (CTL) were studied. All patients wore oxygen masks in order to control the oxygen level during the experiment in the fMRI. During the scan, the subjects breathed 1) room air for 50 s, 2) 100% N2 for 5 breaths and 3) room air for 6 minutes. The typical length of hypoxia is 5 breaths, but for patients with irregular breathing patterns the maximum duration is 20 seconds. NIRS was used to measure the hemoglobin (OHB, DHB and THB) and a tissue oxygen index (TOI), from the human prefrontal cortex. Differences oh hemoglobin measure, between the normoxia and hypoxia states, were computed and called ΔOHB, ΔDHB and ΔTOI. During resting state fMRI scanning, subjects were instructed to close their eyes, keep still as much as possible and not to think of anything systematically. FMRI images were acquired during 8 minutes and a total of 240 volumes were collected. Imaging data was first preprocessed with the FMRIB Software Library (FSL), using standard spatial preprocessing steps: Images were (1) slicetime corrected, (2) realigned to remove physiological motion and co registered to the MNI template space. The percent signal change from the fMRI, % BOLD, was computed based on an average signal in the GM mask.

Results: 9 SCD patients (age=23±8) and 20 CTL subjects (age=21±1) were recruited. Fig 1 presents the relationship between %BOLD versus ΔOHB and % BOLD versus ΔDHB, respectively. Due to the lower oxygen affinity of hemoglobin S [START_REF] Nahavandi | Nearinfrared spectra absorbance of blood from sickle cell patients and normal individuals[END_REF], the decrease in % BOLD (0.093 ± 0.034) and the ΔOHB (1.425 ± 0.588) in SCD patients are larger than the decrease in CTL individuals (% BOLD: 0.050 ± 0.021 and ΔOHB: 0.877 ± 0.539); the increase in ΔDHB (1.661 ± 0.805) in SCD patients is also greater than in the control group (ΔDHB: 0.959 ± 0.505), as shown on Figure 2. Based on the THB signal, we can detect hyperemia for most of the subjects during desaturation. Moreover, for some of the SCD patients, the reactivity is slower even at the end of the hypoxic state. We observe a slightly lower increase of ΔTHB for SCD patients, but this was found to be insignificant. This may be the result of a combination of the CBF variability in the SCD group, and of the small sample size. In our study, a decrease of ΔTOI was observed during hypoxia in both groups. The ΔTOI amplitude of the SCD group (0.080 ± 0.023) is higher than that of the CTL group (0.047 ± 0.024), which may be due to the SCD brain's diminished physiological adaptive capability to a hypoxic state.

Conclusion: Based on a conjoint acquisition of fMRI and NIRS, this study is the first investigation of the effect of the desaturation for SCD patients. As expected, based on these preliminary results, the SCD patients are more affected by hypoxic conditions, such as a larger changes of ΔOHB, ΔDHB, ΔTOI and % BOLD and a slower reactivity, likely due to anemia, high CBF and CBV, and decreased vessel elasticity. †= equal first author contribution https://ash.confex.com/ash/2015/cop/papers/confirmation.cgi?username=87096&EntryTable=Paper&step=8&StepEntry=583Paper87096&password=255707 2/4

Fig 1 :

 1 Fig 1: Minimum %BOLD versus minimum ΔOHB in the left side and minimum % BOLD versus maximum ΔDHB in the right side.

Fig 2 :

 2 Fig 2: Bar graph of % BOLD and NIRS signals in CTL and SCD groups


Julie Coloigner

Yeun Kim

Adam Bush

Matt Borzage

Vidya Rajagopalan

Natasha Lepore

John Wood

Low-frequency fluctuation amplitude analysis of resting-state fMRI

Keywords: Functional magnetic resonance imaging, Resting state, Connectivity, Sickle cell disease, amplitude of low-frequency fluctuations

INTRODUCTION

Sickle cell disease (SCD) is a chronic blood disorder caused by a mutation in the hemoglobin beta gene that affects millions of people throughout the world, particularly descendents of Sub-Saharan African. Red blood cells lack the flexibility required to flow in the circulatory system, leading to vasoocclusion, ischemia and infarcts. More particularly, SCD can cause neurological damage and strokes, leading to significant mortality and morbidity. Identification of cerebral biomarkers could be useful to predict brain alterations and to diagnose disease states. [START_REF] Elias | Quantitative mri analysis of craniofacial bone marrow in patients with sickle cell disease[END_REF] However, structural magnetic resonance imaging is not sensitive enough to detect biomarkers that may aid in SCD disease stratification. This has highlighted the need to investigate other neuroimaging markers in the brain of SCD patients. [START_REF] Steen | Brain volume in pediatric patients with sickle cell disease: evidence of volumic growth delay?[END_REF][START_REF] Kirk | Regionally specific cortical thinning in children with sickle cell disease[END_REF][START_REF] Balci | Quantitative brain diffusion-tensor mri findings in patients with sickle cell disease[END_REF] Functional Magnetic Resonance Imaging (fMRI) is a non-invasive technique for measuring and mapping the brain activity. Spontaneous low frequency fluctuations of Blood Oxygenation Level-Dependent (BOLD) signal have been observed during rest and can be identified with baseline spontaneous activity in the brain. The default mode network (DMN) which consists of the precuneus, posterior cingulate cortex, medial prefrontal cortex and lateral parietal cortex 5 is of particular interest. Indeed, in a growing number of studies, the activity within the DMN is analyzed to understand how spontaneous synchronized activity of neuronal populations is altered in diseases such as depression, Alzeihmer's diseases, schizophrenia or epilepsy. [START_REF] Fox | Clinical applications of resting state functional connectivity[END_REF][START_REF] Qi | Impairment and compensation coexist in amnestic mci mode network[END_REF] In this paper, we analyze the resting state functional magnetic resonance signal, whose low-frequency fluctuations are considered to reflect spontaneous synchronized activity of neuronal populations. The Amplitude of Low Frequency Fluctuations (ALFF) 8 is used to determine areas of spontaneous BOLD signal across brain regions. Given the cognitive deficits and abnormal blood flow in SCD patients, we hypothesize that significant alterations in DMN activation patterns exist between patients with SCD and control subjects. These abnormalities may be a trait marker and could be helpful for the future diagnosis of SCD stages.

MATERIAL AND METHODS

Dataset

This study was approved by institutional review board (CCI#1100083) and conducted in the Children's Hospital Los Angeles (CHLA) between January 2012 and May 2015. Written informed consent was obtained from all subjects. Since 70% of SCD patients develop stroke by 20 years of age, we restricted our population to adolescents and young adults without strokes. 20 SCD patients (age=23 ± 8) and 17 control subjects (age=21 ± 1) were included in this analysis. Exclusion criteria included pregnancy, previous stroke, acute chest or pain crisis hospitalization within one month. The patients were group-matched in terms of sex and education. All participants underwent a battery of tests: structural and functional imaging and neurophysiological tests.

Preprocessing steps

The resting-state fMRI data were preprocessed with the FMRIB Software Library (FSL), using standard spatial preprocessing methods. The first 5 volumes from each subject were discarded to allow the signal to reach equilibrium and to allow the participant to adapt to the scanning noise. The remaining 235 volumes were corrected for the acquisition time delay between slices. Rigid realignment was then performed to remove physiological motion such as high-frequency respiratory and cardiac noise, with FSLs MCFLIRT. A motion index, DVARS, which represents the change in BOLD signal from volume to volume, was then computed. This measure was calculated as the root mean squared value of the differentiated time series (by backwards differences). Some volumes were excluded because of excessive DVARS.

Then, a two-step coregistration method was used to transform the fMRI data into the Montreal Neurological Institute (MNI) template space. First, the mean fMRI image was coregistered (6 parameters) with the structural image; then these structural images were linearly transformed to the Montreal Neurological Institute (MNI) template space, using the FLIRT and FNIRT algorithms of FSL. The generated parameters for these two coregistration steps were then concatenated and used for the normalization of each fMRI volume. Finally, the registered fMRI volumes were normalized and smoothed with a Gaussian kernel of 8mm × 8mm × 8mm full-width at half maximum (FWHM).

After fMRI preprocessing, in order to remove residual motion, the parameters estimated by FSL's MCFLIRT, as well as their derivatives were used as regressors, computed by backwards differences (12 regressors). Moreover, the physiological noise was also reduced using other nuisance regressors which were calculated by the CompCor 9 method as implemented in Nilearn (http://nilearn.github.io/). These 5 regressors correspond to the principal components from noisy regions-of-non-interest, such as white matter, cerebral spinal fluid, and out-of brain. Then, the fMRI data were temporally band-pass filtered (0.009 < f < 0.08 Hz) to reduce the very low-frequency drift and high-frequency respiratory and cardiac noise.

ALFF analysis

The ALFF analysis 10 was performed using FSL functions. The power spectrum was obtained after the time series for each voxel were transformed to the frequency domain with a Fast Fourier Transform (FFT). Since the power of a given frequency is proportional to the square of the amplitude of this frequency component of the original time series in the time domain, the square root was calculated at each frequency of the power spectrum. The averaged square root was obtained across 0.009 -0.08 Hz for each voxel. This averaged square root was taken as the ALFF. To reduce global effects of variability across the participants, the ALFF value at each voxel location was divided by the global mean ALFF value. The individual map was transformed to a Z score (i.e., we subtracted the global mean value, and then divided by the standard deviation) instead of being simply divided by the global mean.

Statistical Analysis 2.4.1 Within-group ALFF analysis

To explore the within-group whole-brain ALFF patterns, one-sample t-tests were performed on the individual ALFF maps in a voxelwise manner for the two groups: SCD and control. A gray matter mask of the MNI template was used. The corrected threshold was determined using the AlphaSim program 11 with a p-value threshold set at P < 0.05 and a cluster size > 1.91 cm 3 .

Between-group ALFF analysis

To investigate the variability of the activation, one-way analysis of variance (ANOVA) was performed to determine the ALFF differences among the two groups at each voxel (within a gray matter mask). The statistical map was corrected again using the AlphaSim program, with the threshold set at P < 0.05 and a cluster size larger than 1.91 cm 3 . After identifying all significant clusters, we made a mask including these regions. A post hoc t-test was then performed to compare the Z-maps of the activations between the patient and control groups, restricting the analysis within this mask.

RESULTS

As illustrated in the Figure 1, within each group, significant higher ALFF was found in several brain regions, such as medial prefrontal cortex (mPFC), posterior cingulate cortex (PCC), precuneus and posterior frontal cortex.

The one-way ANOVA revealed 8 clusters with significant differences across the SCD and control groups, including medial orbitofrontal cortex (MOFC), anterior cingulate cortex (ACC), Brodmann Area 8 (BA 8), posterior region of middle cingulate cortex, posterior cingulate cortex (PCC), anterior lobe of cerebellum, posterior lobe of cerebellum and parietooccipital sulcus, as shown in table 1 and figure 2. Table 1 illustrates the results of the t-test for these 8 regions. Compared with the control subjects, the SCD patients showed a significant Table 1. List of brain areas with significant differences in ALFF during the resting state between the SCD and control groups. A positive sign in the peak t-value represents an increase, while a negative one represents a decrease in SCD group. A corrected threshold of p < 0.05 determined by Monte Carlo simulation was taken as meaning that there was a significant difference between groups for either t-test and ANOVA test.

Figure 2. Representative one-way ANOVA results of ALFF maps (P < 0.05, AlphaSim corrected) between SCD and control groups. On the the sagittal view (higher, left), five clusters are displayed by arrows (counter-clockwise): medial orbitofrontal cortex, anterior cingulate cortex, Brodmann Area 8 (BA 8), posterior region of cingulate cortex, posterior cingulate cortex and anterior lobe of cerebellum. In the axial views, the regions indicated by arrows are as follows: posterior cingulate cortex (Z=34), posterior region of middle cingulate cortex (Z=33), anterior cingulate cortex (Z=6), medial orbitofrontal cortex (Z=-9). In the coronal view, the anterior lobe of cerebellum is signed by an arrow.

decrease in ALFF in PCC, posterior region of cingulate cortex and MOFC. In addition, an increased activity in ACC, BA 8, cerebellum and parietooccipital sulcus was found in the sickle cell disease group.

DISCUSSION

Using the ALFF metric of resting state fMRI, several neuronal activity changes were detected in specific brain regions in SCD patients versus control subjects. These neuronal abnormalities were found in 8 areas in the SCD group. This may be due to a variety of factors, including for example fear extinction, tissue damage from strokes, and vasculature differences that are not apparent on MR imaging. The analysis of ALFF indicated that patients with sickle cell disease showed differences in activity within regions of the DMN. First, we observed that resting-state functional connectivity of the ACC was increased in patients with SCD when compared to control subjects. Previous studies have found a strong association between ACC and the emotional response to pain. [START_REF] Baliki | Functional reorganization of the default mode network across chronic pain conditions[END_REF] Buchel et. al. [START_REF] Bchel | Dissociable neural responses related to pain intensity, stimulus intensity, and stimulus awareness within the anterior cingulate cortex: a parametric single-trial laser functional magnetic resonance imaging study[END_REF] found a positive correlation between fMRI signal intensity and pain intensity. Since most SCD patients suffer from episodic or chronic pain, it seems plausible that their ACC will show abnormally increased activity.

Secondly, we observed a decreased activity in the posterior components of the DMN, the PCC and precuneus, which are thought to act as intrinsic mediatory nodes of this network. [START_REF] Cavanna | The precuneus: a review of its functional anatomy and behavioural correlates[END_REF] Regional differences in cortical thickness from SCD patients were also located on the posterior medial surfaces, the so-called "watershed" areas between the perfusion territories of the anterior cerebral artery (ACA) and the posterior cerebral artery (PCA). [START_REF] Kirk | Regionally specific cortical thinning in children with sickle cell disease[END_REF] The precuneus and the posterior cingulate are vulnerable to acute anemia and, thus, may be susceptible to abnormal development.

The orbitofrontal cortex covers the ventral surface of the primate prefrontal cortex. Several animal studies as well as human neuroimaging studies have reported that the medial orbitofrontal cortex (mOFC) and the ventromedial prefrontal cortex (vmPFC) are associated with fear extinction. [START_REF] Milad | Fear extinction in rats: implications for human brain imaging and anxiety disorders[END_REF][START_REF] Barad | Fear extinction in rodents: basic insight to clinical promise[END_REF][START_REF] Sotres-Bayon | Brain mechanisms of fear extinction: historical perspectives on the contribution of prefrontal cortex[END_REF][START_REF] Rauch | Neurocircuitry models of posttraumatic stress disorder and extinction: Human neuroimaging researchpast, present and future[END_REF][START_REF] Quirk | Prefrontal mechanisms in extinction of conditioned fear[END_REF][START_REF] Davis | Pharmacological treatments that facilitate extinction of fear: relevance to psychotherapy[END_REF] We found these areas to have lower ALFF values in the SCD patients than in the control group. We attribute this phenomenon to the heightened level of fear and anxiety of the control group due to their unfamiliarity to hospital exams and environment. Since the SCD patients are more used to hospital setting and exams, the lower ALFF value may reflect these differences. Lastly, we observed four regions with abnormal activity in the SCD group: Brodmann Area 8, anterior lobe of cerebellum, posterior lobe of cerebellum and parietooccipital sulcus. In fMRI studies, BOLD signals are often affected by vascular activities, causing the signals to fluctuate. Thus, the ALFF values of these four regions may be affected by vasculature, since they are located near large cerebral arteries such as the ACA, the superior cerebellar artery, the anterior inferior cerebellar artery and the parieto-occipital branch of posterior cerebral artery, respectively.

  MRI data were acquired on a 3T Philips Achieva at CHLA. A 3D T1-weighted image was acquired covering the whole brain (160 sagittal slices) with TR = 8.20 s, TE = 3.77 ms, flip angle = 8, in-plane resolution = 256 × 256, FOV = 256 mm × 224 mm and thickness/gap =1.0/0 mm). During resting-state fMRI scanning, subjects were instructed to close their eyes and keep still as much as possible, and not to think of anything systematically or fall asleep. The functional images were acquired with the following parameters: TR = 2000 ms, TE = 50 ms, flip angle = 90, in-plane resolution = 96 × 96, FOV = 220 mm × 220 mm, 26 axial slices, thickness/gap= 5/0 mm. A total of the 240 volumes were collected in 8 minutes.

Figure 1 .

 1 Figure 1. Representative one-sample t-test results of ALFF maps (P < 0.05, AlphaSim corrected) in groups of SCD (A) and control (B) subjects. Color scale indicates t values. Thresholds were set at a corrected p < 0.05, determined by Monte Carlo simulation. The planes are X = 0, Y = 50 and Z = 35 for the sagittal, coronal and axial views, repectively, in the Montreal Neurological Instititute (MNI) template.

CONCLUSION

In this paper, we studied the brain functional activation, using the ALFF analysis. Our comparison among the SCD and control groups confirmed our hypothesis about the difference in resting state activity for SCD patients, and revealed a difference in DMN and cortical regions near large cerebral arteries. The next step will consist in taking into account different measures in the study, such as the localization of the damage, venous vasculature and physiological parameters.


Laurence Pillant

INTRODUCTION OF PROCEDURES FOR MIGRATION CONTROLS IN GREECE Case study in the Aegean Islands

INTRODUCTION OF PROCEDURES FOR MIGRATION CONTROLS IN GREECE

Case study in the Aegean Islands unprecedented multiplication of actors involved in migration control in the region.

Nevertheless, is it possible that, by ending the government's exclusive responsibility for controlling the national territory, such transformations might in fact undermine the exercise of its powers at its frontiers? There are two possible, apparently contradictory, hypotheses: the introduction of more and different types of actors could lead either to a weakening of State power, or to a realignment or redeployment of government agencies. After this presentation of the main issues relating to migration controls at the Greek-Turkish border, the article will describe the implementation of security systems for handling a 'extended border area' and the interdependence of actors, be they private or public, national or European, governmental or non-governmental. Notwithstanding the fact that sovereignty of the State is paramount in managing these new elements, the introduction of plurality and its implications for migration controls at the border highlight the weaknesses that lie at the heart and at the outer edge of the procedures.

Migratory control in the Aegean Sea and the reinforcement of pluralities

Sensational language is continually used by the media and politicians when discussing migration to the European Union (EU), particularly in Southern European countries such as Italy (Maneri 2011) and Greece (Sintès 2009, 2011). Even though several European alternatives have been advanced to counter these arguments which tend to dramatize the presence of migrants in Greece,7 there seems little point in seeing these reactions as uniquely European. Indeed, the complexity of Greek migration control systems must first be seen within the international context for migration.

A new route for migrants: the Aegean Sea

The arrival of migrants from Africa, Asia and Middle East is not a new phenomenon, even though the numbers intercepted at the Greek-Turkish frontier, and in particular in the Aegean Sea (Pillant 2010), increased significantly during the 2000s. Greece was a country of emigration throughout the first half of the 20th century, but already in the 1980s, this trend was reversed with a substantial rise in the number of foreigners arriving to the point where it was experiencing a 'migration carry-over effect' 8 as seen in other Mediterranean countries, such as Italy and Spain (Claude 2002; Simon 1986). During this period, Greece was also a major country of destination for Albanians and other 'ex-socialist South Balkan countries' (Parsanoglou 2009; Sintès 2010).

More recently, the growing complexity of migration routes and flows to Europe (Simon 2002) not only made the journey much more dangerous, but also forced migrants to change their itinerary because of stricter controls and development of the Schengen zone (Clochard 2010). It appears that an increase in 'clandestine' migration to the EU made journeys much longer because people now had to travel through Southern European countries.

Because of these changes in migrants' itineraries and in the placement of crossing points, a new Mediterranean configuration emerged with the Aegean Islands becoming a popular destination for crossing into Europe during the early 2000s.

Historically speaking, the maritime frontier between Greece and Turkey has been a source of conflict between the two countries since its creation in 1922.9 It is regularly subject to closures and military installations and this has inevitably had an impact on all the Aegean islands.10 Even though the situation became gradually more open in the early 2000s (Sivignon 2005), local interaction between the two countries relating to migration controls has remained relatively weak until now (Pillant 2009). 11 Migrants usually make the short passage between the Anatolian coast and the Greek islands in makeshift and often overloaded boats.

Paradoxically, in this area where the maritime limits remain a source of political conflict, the two border agencies work side by side when intercepting and rescuing migrants at sea.

Greece's entry into the Schengen zone has added an extra dimension to the Greek-Turkish 'dyad' 12 and challenges the role of the State as principal actor in controlling Greek territory.

As can be seen from the way in which controls on this border, and more specifically detention 8 Closure of frontiers and attempts to reduce migratory flows in Northern European countries during petrol crises led to changes in the direction of these flows towards Southern European countries.

centres, have been installed, a wider range of actors and systems is now emerging.

Plurality of detention centres: local solutions make up for the lack of legislative provisions

Under the Schengen Agreement, crossing a frontier anywhere other than at an official border post is an offence. As the penalty for this offence is expulsion, offenders are placed in detention centres while their situation is reviewed and a decision taken on whether they should be sent back, granted asylum or ordered to leave the territory within 30 days. Although migrants are systematically placed in detention centres when they are intercepted in mainland Greece, none of the procedures currently used in the Aegean Sea take into account the need to detain hundreds of persons. The absence of a real legislative framework seems to be the primary reason for the wide variety of solutions for the detention of migrants in this region.

Without any regulations covering this situation, the authorities made use of measures available under two confidential emergency plans, Poseidonio and Balkano, until 2011. These plans specify that the prefectures,13 and more particularly the sections responsible for Civil Emergency Planning,14 are responsible for handling the massive arrival of people during a major crisis, such as a natural disaster, although no specific details are given as to what arrangements must be made for them. 15 No national directives appear to have been issued for the management of such situations during this period, 16 although the Ministry of the Interior does reimburse expenses related to the establishment of detention centres. The absence of appropriate national regulations has led to a variety of local improvised solutions in border regions which result in notable differences in the cost of detention. For example, there are marked differences in the ratio between number of arrests and costs incurred. In 2009, 17 the three islands that make up the Aegean border (Chios, Samos and Lesbos) received 75% of reimbursements, even though only 34% of Greek border interceptions took place in this region. Lack of legislation and the total absence of ministerial audits of local costs 18 have resulted in differing approaches to the management and funding of detention centres.

On these three islands, the requisitioned buildings were not built for the detention of migrants and few improvements have been made by the authorities in order to fulfil this purpose. 19 Despite these improvisations, some common issues have emerged. For example, the centres were generally in a poor state of repair and lacked basic equipment, because of the decision to use of abandoned or under-exploited buildings. This also explains the diversity of 'available' resources20 from one island to the next: a tobacco factory, a former police station, and a former prison. 21 Even though this improvisation resulted in a variety of buildings, this alone cannot explain why local authorities introduced different practices for handling the detention of migrants. To a certain extent, these practices provide insight into the attitude of the authorities towards migrants, viewed as either a nuisance or a threat. Indeed, a number of abuses have been observed -for example, boarded-up windows -that cannot be attributed merely to a lack of resources. The inhuman conditions in these buildings are a source of tension and have led to the creation of collectives22 to defend migrants' rights. Again, the strategies and methods used in the power struggle with the authorities vary on the islands.

Some of these collectives offer professional services in the detention centres where they have an opportunity to play an important role but little scope for denouncing the abuses they observe. Other collectives, however, have only sporadic access to the centres and have a single option for confronting the authorities: they have greater freedom for denouncing abuse, but only limited access to information. Much of the tension that occurred between actors during the 2000s was generated by questions relating to respect for human rights and arbitrary decisions by police which prevent collectives from having regular access to the centres. The results of this power struggle accentuated the differences in treatment from one centre to 18 Ministerial spending reviews are only carried out from a distance. Some requests for reimbursements are refused as unacceptable, but there appears to be no ministerial service responsible for carrying out on-site audits. 19 We found very little information on contracts with suppliers for the early 2000s and very few services appear to have been provided and do not appear to have succeeded in rendering the buildings habitable.

another in the Aegean islands. Despite public statements and measures that sought to ensure similar treatment and to regulate practices, differences still persist in the second series of detention centres. Practices introduced in response to an emergency situation remain in place and few improvements have been made to conditions inside detention centres. 23 Although migrants are systemically detained after interception, detention centres do not appear to receive the same resources as border controls over the last decade. A similar situation can be seen at the European level: as more efforts are made to supervise borders, less attention is paid to the basic rights and freedoms of individuals (Jeandesboz 2008).

Migration controls and a plethora of agents in the Aegean Sea

In the Aegean islands, the army is responsible for defending the country from external threats, and in particular from Turkey. With regard to the detection of clandestine border crossings, responsibility for the islands is divided between the national coastguard and police services. With the growing numbers of migrants, preparing their officers to adapt to this situation is limited to training programmes. 24 For example, police officers have been trained in using the Schengen information system and in detecting false papers. However, the most important change in terms of border controls is undoubtedly the presence of a new intergovernmental agency, Frontex. 25 who act as its representatives in the islands' port authorities. It is not exclusively European but operates at several levels together with other national and international actors. 28 As a result, there is a certain amount of opacity in its structure which makes its operations somewhat difficult to understand, as can be seen from the many challenges to the activities it coordinates (Rodier 2011; Jeandesboz 2012). It has three primary responsibilities: monitoring, dissuasion and searches. In addition, private operators are also involving in carrying out migration controls, on an ad hoc basis,29 at the border and inside national territory: for example, travel agencies and airline companies.

The variety and complexity of actors involved in Greek migration controls are signs of a markedly different approach to the European position on migration and migration controls. It seems that, by adapting to new and ever-changing migration flows, controls have to become more flexible and require a wider range of actors and control points. We must now see how these various elements are linked together in order to obtain a better understanding of the impact of these procedures.

Procedures in operation: Extended border areas and fragmented controls

While social science research has focused on the State as the actor with the greatest responsibility for transforming contemporary society, we should not conclude too quickly that it is in decline, since changes in State management of national territory do not necessarily mean that it is no longer present, as the factors discussed above demonstrate. Rather, the key issues are the extensions of the border area and the emergence of control systems. In addition, based on our observations of these procedures, we should ask why these controls have become fragmented, rather than whether the State, as prime actor, has become more fragile.

Council of Europe, Note n°13918/03.

These Frontex agents are Greek coastguards on secondment.

28

Frontex is responsible for training police officers in detecting false papers at official frontier crossings. In terms of control and dissuasion strategies, it is also required to identify current migration routes and anticipate future changes. Frontex' actions and officers have a larger brief, including arrangements for translations during police interviews of migrants and investigations into migrants' nationalities.

Extended border areas: the result of introducing new migration control procedures

In recent years, controls of identity were no longer limited to border crossing points, apparently as part of a general move towards the criminalization of migration (Palidda 1999), which made it possible to introduce more controls and a wider range of targets (Tsoukala 2002) and control points. It could be argued that these controls were needed to deter irregular entry and to ensure greater flexibility in countering new routes and strategies adopted by migrants (Bigo 1997). For control actors, the key objective was to find new ways of coming into contact with migrants. At the European level, this means 'externalization' of border operations (Audebert and Robin 2009, Morice and Rodier 2010, Weber 2010, Migreurop 2011). Similarly, at the Member States level, controls now take place within the national territory and the Aegean Islands obviously have to play their part in this process. Now identities were to be checked not only at the frontier or at official border crossings, but also throughout the country.

Given their geographical position and specific characteristics, the Aegean Islands are for the most part transit areas. Migrants intercepted at sea or on their arrival on the islands are almost always sent to detention centres. The period of their stay depends on such criteria as nationality and the specific context on each island. 30 They are usually released with an order to leave the country within 30 days. However, although travel to Athens does not involve crossing a national frontier, they are required to present identity papers when buying a ticket for the ferry. If they do not have legal papers, they must present the expulsion order which allows them to obtain a ticket for Athens. Therefore, undocumented migrants who have not been detained have difficulty leaving the island for the mainland. A circular for the Protection of Citizens issued by the Ministry in January 2010 clearly indicates that travel agencies are now responsible for checking the identities of people purchasing ferry tickets. 31 The main outcome of this circular is to make it 'quasi-obligatory' 32 for migrants to spend time in a detention centre if they want to continue their journey, usually to Athens. Thus, detention centres become another form of obligatory border crossing for entry into a foreign country, for 30 E.g. the NoBorder protests on Lesbos in 2009 which led to the release of dozens of migrants from the detention centres. This demonstrates the influence that the context in the islands can have.

31 http://www.minocp.gov.gr/index.php?option=ozo_content&perform=view&id=3440&Itemid=461&lang 32 Although many of the stratagems used by migrants relate to avoidance of identity checks (Diminescu 2001), here migrants who have not been intercepted have to find a way to buy tickets without papers and this is much more complicated. certain categories of migrants, thus introducing an extension of the national frontier inside the country itself and making it necessary to develop new strategies of avoidance. 33 According to this circular, travel agencies selling tickets have in fact become agents for migration control within the country. These controls apply to Greek nationals who must also present their identity cards when buying an internal travel ticket. Here we can see that detention centres, travel agencies and transport offices are now responsible for one of the most important aspects of border security: filtering. Is not this move towards extended border areas, as seen elsewhere in Europe (Clochard 2007, Cuttitta 2007), now the most visible feature of migration control systems? Indeed, the identification of various disparate elements -detention centres, actors, legislation -and their interaction in order to control migration seem to meet the criteria for Foucault's 'system'. 34 The extended border area is thus a territorial structure which relies on the installation of a migratory control system linking the various places where controls take place, regardless of the wide diversity of actors. By issuing various instruments (decrees, laws, circulars), the State has set up a system in which several agents can exercise official authority by controlling identities. In allocating these new tasks, has the government delegated its powers in order to withdraw from its responsibilities in the future?

The illusion of sub-contracting state responsibility for migration control

As we have seen above, the involvement of new actors and territories in migration controls goes hand-in-hand with an extended border area created by the establishment of a system that is supported to come into contact with the phenomenon they are expected to control. But is the State still the principal actor? In fact, the participation of non-governmental and supra-governmental actors does not necessarily imply delegation of sovereignty: rather, the government has authorized, or obliged, new actors to carry out identity controls. Travel agencies, for example, do not replace State border controls but carry out additional controls for the State at no additional cost. Having police officers or coastguards supervise the sale of tickets would be expensive, whereas a circular does not imply State intervention, yet makes provision for new forms of internal controls. 33 E.g. buying a ferry ticket on the black market. 34 Foucault defines this system as a "collection of completely heterogeneous elements" which responds, in the first instance, to an emergency situation with the "prevalence of a strategic objective": here it is applied to migration controls (Foucault 2001, 299).

What appears to be delegation of authority or allocation of state operations to private actors via sub-contracts is in fact an accumulation of new areas and new types of control that did not exist before. For example, asking private companies offering aerial archaeological services to watch out for boats crossing in the Aegean Sea illegally 35 does not mean they take the place of other state agencies previously responsible for migration controls. It merely introduces a new element, a combination of aerial and maritime controls. Similarly, Frontex agents interview migrants in detention centres in order to gather information on their journey and passage across the border. They are not replacing the police in this task but, clearly, these interviews provide useful information that was not previously obtained during local police investigations. 36 As the European agency for migration controls, Frontex is not expected to replace State authorities, but rather to enhance their efficiency in carrying out national migration controls and managing the external frontiers of Europe's shared space. Thus, the government takes a positive attitude to Frontex' presence in Greece, and in particular the Aegean Sea, and this is not perceived as a challenge to national sovereignty. Indeed, the agency's structure has been established, together with its principal intervention team (mostly coastguard officers from other Member States), as a way of providing assistance and partnership, and therefore not to conflict with existing Greek procedures. Nevertheless, the introduction of changes in the way the government carries out controls in its territory is bound to have major consequences. The absence of delegation of national sovereignty and the lack of clarity seems to have undermined these control procedures. Closer examination of relationships between these new actors at the local level allows us to identify the reasons why controls have been weakened through the installation of structures and extended borders areas without real delegation of authority.

The paradox of non-delegation of sovereignty: fragmentation of control procedures

Paradoxically, the absence of real delegation of state authority and the maintenance of national sovereignty with regard to migration, through the introduction of new procedures and the multiplication of actors, have produced two important results. First, the involvement of more actors has resulted in more opportunities for conflict and cooperation at the local level,

35

As occurred during an exercise carried out by Frontex on Lesbos in 2009. 36 These interviews are regularly analysed and compared with data obtained from intercepted migrants. Based on this information, state authorities can set up new strategies for controls.

rather than harmonized practices. The possibilities for interaction are as numerous as the current situations which in turn vary in space and time according to the specificities of the area in question. Frontex offers a particularly interesting example for this discussion. Its relations with the national coastguard and police services seem to be based on earlier links and conflicts with the civil society (Pillant 2010). In the Aegean islands, where the coastguards have sole responsibility for maritime controls, Frontex is obliged to work with them, but this does not mean that there are no clashes. 37 Where there are only limited relations between the coastguards and the police, cooperation between Frontex and the police also suffers. Relations between the islands' control agencies may thus have a direct impact on their cooperation with Frontex. In addition, the lack of a permanent Frontex presence and the involvement of different teams with members from several European countries may not contribute to the establishment of strong links with local agencies. The arrival of a new -European -actor in these circumstances does not guarantee a unified approach to border controls in the Aegean islands, but rather it makes the situation more complex. By creating several layers of control agents without transferring real power to any of them, the government has created a situation where relations between actors become conflictual and may even affect or interfere with the main objective: control of migrants.

Second, non-delegation of powers to intermediary actors may have an impact on relations with the private sector. By asking travel agencies and ferry companies to check travellers' identities, the government is able to maintain its control over the whole country without having to allocate additional resources. Initially, this new responsibility could paradoxically compromise migration controls, since these actors are often reluctant to take on additional responsibilities if they are not paid. Under the global restructuring programme for Greek ports,38 maritime transport companies will be responsible for checking passengers' identities before boarding. This move is not popular because the procedures are timeconsuming, create lengthy delays, slow down maritime traffic, and ultimately could lead to financial loss. Such demands from governments may generate conflicts and resistance, especially from shipping companies, a very powerful industrial sector in Greece.

In addition, broadening the range of migration controls without delegation of powers or provision of additional funds or grants has led to the creation of marginal agents and their territories. Shipping companies and travel agencies, for example, operate as businesses with commercial targets and, by the very nature of their activities, are required to act as the 'last link in the chain' for migration controls. In addition, these 'last link' controls must conform to certain procedural restrictions which are obligatory for government agencies, but cannot be imposed on commercial actors. This last condition may lead to the development of new illegal practices and thus undermine further the implementation of migration controls that used to be the exclusive prerogative of the state and its agencies. Paradoxically, more recent policies on migration in Europe appear to have reintroduced controls inside the Schengen zone. Although there is progress in the development of a common migration policy, governments continue to play a major role in setting up identity checks at national frontiers and in maintaining national sovereignty in terms of immigration and citizenship. The State is a key actor in the negotiation of readmission agreements with non-European countries, as with Turkey in 2001. However, even though to date this agreement has been only partially implemented, these negotiations were in fact easier than the current European Union-Turkey discussions in this domain. 39 Government agencies still play a predominant role in the establishment of detention centres and migration control practices. In the absence of a national policy on confinement of migrants, local solutions have to be found and here again, state agencies continue to take the 39 The first steps towards the signature of a readmission agreement between Turkey and the European Union took place on 21 June 2012, but negotiations have stalled because of Turkey's demands for easier access to Europe for its citizens. primary role. Even if this has not weakened the position of the State, the situation has nevertheless changed. The exercise of governmental responsibilities has been transformed by the introduction of new migration controls and the arrival of intermediary actors. These changes are not limited to migration controls, but appear to be the outcome of a more global transformation of the State itself. We are seeing a new combination of agencies and levels of decision-making that has changed the territory. And nowhere is this more obvious than when it is the State itself that introduces these changes. By creating marginal areas, it introduces new agents -political (Frontex) or commercial (travel agents and shipping companies) -and territories in which they operate, without actually delegating its authority and this has obviously had an impact on the situation. Whether or not this diminishes the key role played by the State, the State has developed a multiple presence on its territory, creating new connections with actors at various levels and new areas for controlling migration. Even though the complexity of these changes goes way beyond the question of migration controls, it offers a particularly interesting vantage point for observing them.

  Controls on migration and closing of frontiers in Europe during the 1970s had a serious impact on the routes taken by migrants coming into this region clandestinely. Today, migration controls are an official priority in all EU countries. Given the new situation in the Mediterranean, the Greek-Turkish frontier has now become a key area for border crossings by migrants who do not have the right to enter Europe legally. Even though most European Member States have established migration policies and legislation covering specific places and actors, in fact the situation remains extraordinarily diverse.These control structures, though composed of numerous elements, are linked together as an inherent part of the extended border. In the initial concept for the Schengen Agreement, freedom of movement throughout the European Union was expected to remove internal borders between EU Member States and strengthen frontiers with non-European countries.

  Our study of the modalities of Frontex's presence in Greece showed that a precursor, the EKTHAS office, 26 was already operational in 2005. Frontex is a multi-level agency with its European headquarters in Warsaw and a national office for cooperation agreements between EU Member States. Its local office members are Greek liaison officers27

Since its creation in 2004 and implementation on 1 May 2005, Frontex has become one of the major actors in migration control at European borders. For the Aegean region, it became part of the Poseidon programme in 2007 and its activities in Greece have increased since 2010 when Frontex's central operations office for the Eastern Mediterranean at Piraeus opened and an intervention force (RABIT) was deployed along the Greek-Turkish border. Even though Frontex is the principal instance for new European procedures on migration control, its link with Greece pre-dates its first operations in the Aegean Sea.

In 2011, the EU began to review the situation in Greece and controls of migrants at its frontiers. For example, there were discussions about conditions of detention in Greece, which were strongly criticized by the European Committee for the Prevention of Torture, the activities of RABIT (a special rapid action unit), establishment of a Frontex office in Piraeus, and transposition of the European Directive on Returns in Greece.

Following defeat of the Greek Army in Asia Minor in 1922, the Treaty of Lausanne 1923 created this frontier which is a source of conflict between Greece and Turkey for several reasons[START_REF] Prévélakis | Géopolitique de la Grèce[END_REF][START_REF] Pazarci | Le contentieux gréco-turc en Mer Egée[END_REF]).

By the late 20th century, the North Aegean islands had become once more very attractive for Greeks as a result of government decentralization programmes. The local population had decreased substantially because of the conflicts between Greece and Turkey, the definition of the frontier between the two countries, the rupture with the Anatolian coast and high levels of emigration[START_REF] Darques | Turcs, Grecs et réfugiés dans l'île de Lesbos au XXe siècle[END_REF].

Cultural exchanges have multiplied locally, thanks to Greek-Turkish friendship associations, in contrast with hostile attitudes and limited contacts between the two governments.

The Greek prefectures (Νομαρχια) do not have the same position as French prefectures, except in terms of their importance. Prefects are elected and are not directly involved in decisions on questions of security, which are handled by the police. The Kallikratis reforms, introduced in 2011, will change this system.

Literally Πολιτικής Σχεδίασης Έκτακτης Ανάγκης (ΠΣΕΑ -Civil Emergency Planning). This agency is covered by a confidentiality clause and is responsible for the management of emergency situations, such as natural disasters, in peacetime.

The Balkano and Poseidonio plans are confidential. We were not allowed access to them and had to rely on descriptions of their contents from various actors in prefectures and at the Ministry of the Interior.

Despite interviews with ministerial staff (including persons at the highest levels) and research in the archives, we have found no confirmation of this.

Reimbursements of these costs are often late and sometimes by up to a year. Payments in 2009 probably refer to spending in 2008.

Other possibilities were sometimes available but not used because of protests from the population which led to the emergence of other difficulties at the local level.

The tobacco factory on Chios was just a hangar with difficult access because of its distance from the island capital; the former prison on Lesbos stands above the town of Mytilini; and the former police station is situated in the centre of Vathy, Samos' main town.

The term 'collective' is used here for citizens groups that are not necessarily registered 'associations' and therefore not officially recognized.

Even though two centres have been built on Samos and Chios, the island of Lesbos is trying to rehabilitate a warehouse in a commercial zone.

There has been no real increase in staff but reinforcements are sent to handle specific events: e.g. in August 2009, additional officers were sent from Athens to handle demonstrations during the annual meeting of NoBorder, a European anti-racism network.

Frontex is the European agency for the "management of operational cooperation at the external borders of EU Member States" (Council Regulation (EC) 2007/2004).

The EKTHAS office, established in the 2000s, is responsible for coordinating "arrival controls in the ports and/or the coast of the European Union, joint patrols at sea, exchange of officers, standardization of technical methods of surveillance and monitoring of ship movements", terms similar to those for the European agency,

Private companies are involved in controlling identities, not in technical and technological aspects of control procedures.

On several occasions, Frontex agents have been described as unfriendly and uncommunicative. 'Forced' cooperation, in particular in terms of the agency's legal responsibilities in the country -a Greek coastguard on each Frontex boat -may explain the difficulties in establishing good relationships among various actors.

Amended in order to conform to new international, European and national codes on maritime safety and infrastructure, these reforms cover principally the Maritime and Port Code (ISPS) and constitute an additional element for migration controls in European ports (Migreurop 2011).