A SHORT NOTE ON NUMBER PREFERENCE

Nicolas Gauvrit & Jean-Paul Delahaye

Since the early seventies, repeated experiments have shown a general preference, at least in the United States and Europe, for number seven against any other number in the brackets 0-9 (e.g. [START_REF] Simon | Number and color responses of some college students: preliminary evidence for a "blue and seven" phenomenon[END_REF]; [START_REF] Kubovy | The predominance of seven and the apparent spontaneity of numerical choices[END_REF]. When subjects are asked to choose a number between 0 and 9, 30% of them chose a 7. This "seven phenomenon" gave rise to two research trends that seem to grow apart, each one ignoring the other.

PURELY COGNITIVE APPROACH

In a cognitive science approach, [START_REF] Shepard | Additive cluttering: Representation of similarities as combinations of discrete overlaping properties[END_REF] suggested that the predominance of seven might be explained by mathematical properties of the numbers involved. This idea have been extended and specified by [START_REF] Griffiths | Randomness and coincidences: Reconciling intuition and probability theory[END_REF]. Their model is based on two main ideas.

First, when subjects are asked to produce a random-like response (or to pick the first item that comes to mind), they do not actually try to do so. Instead, they try to maximize the probability that their response be random, in a Bayesian way. More precisely, a response x could a priori be random or based on a simple rule (such as giving the first number in the list). The relevant information when it comes to pick up at random an item x is P(x|random). However, subjects actually try to maximize P(random|x), a quantity that can be computed through Bayesian procedures. In that way, they ascertain that their response is an evidence of randomness.

Second, subjects are sensitive to some properties of numbers: being even, power of 2, or holding special positions such as endpoints (0 or 9), and so on. The less properties a number x has within the list, the greater P(random|x). There comes number 7, which is the only number that, in the bracket 0-9, shows none of the properties Griffiths and Tennenbaum assume subjects spontaneously consider.

CULTURAL APPROACH

On a totally different basis, many researchers suggested that the number 7 preference can be explained by cultural context. The repetition of the symbol 7 in the Bible, for instance, could well explain its predominance.

Arguments in favour of the cultural approach, and against the purely cognitive view, are determining, and can be categorized in two types of evidence: First, the cultural dependency of numerical choices is well established. For instance, number 9 outdoes number 7 in Nigeria [START_REF] Vandewiele | Number and color preferences in four countries[END_REF], whereas 3 is preferred in Turkey [START_REF] Koloğlu | Color and number preferences of patients with psychiatric disorders in eastern Turkey[END_REF]. Other differences have been recently mentioned as well [START_REF] Strenge | Random number generation in bilingual Balinese and German students: Preliminary findings from an exploratory cross-cultural study[END_REF]. To the best of our knowledge, cultural differences in lotto players' behaviour have not been mentioned in any publication about number preference, but it provides a confirmation of the cultural approach as well. European players indeed prefer small numbers, and among those number 7 [START_REF] Roger | Efficiency of betting markets and the rationality of players: evidence from the french 6/49 lotto[END_REF], whereas players in Taiwan do show a totally different pattern of choices, preferring 8 over 7, and 36 even more [START_REF] Hwai-Chung | Gambler's Fallacy in the Taiwan Lotto Market[END_REF].

Second, the study of psychiatric disorders in relation with numerical choices shows no effect of mental impairment (Koloğlu et al., 2009). A numerical choice based on arithmetical considerations would need healthy executive functions, which does not seem to be the case. Using pseudo-random sequences in a neuropsychological approach, [START_REF] Loetscher | Random number generation in neglect patients reveals enhanced response stereotypy, but no neglect in number space[END_REF] even suggest that neglect patients are actually more likely to show enhanced response stereotypy. This result is based on sequential responses properties, but we may assume that stereotypy would mean, in a one-number pick up task, an even greater predominance of seven.

A THIRD WAY?

Considering the above arguments, opposing a purely cognitive approach and a cultural view gives no chance to cognitive theories of numbers preference. However, the two views are not contradictory, and the cognitive approach outmatches the cultural one in terms of predictive power.

The cognitive approach might be made more flexible to encompass some cultural aspects. For instance, one may imagine that the list of number properties subjects are aware of depends upon cultural context, therefore making a difference in the application of the purely cognitive process involved in the response choice.

One interesting feature in the cognitive approach is that it accounts not only for the predominance of seven (in Europe and the USA), but for the whole distribution of responses (e.g. [START_REF] Griffiths | Randomness and coincidences: Reconciling intuition and probability theory[END_REF].

Even if the purely cognitive approach obviously cannot account for cultural dependency, the cultural view could also be a dead end if it does not include cognitive aspects, since it would then be bound to remain qualitative. This is why we advocate "reconciliation" between the two views.


ARNAUD P ÊCHER Christine Bachoc
email: christine.bachoc@math.u-bordeaux1.fr

Arnaud Pêcher
email: arnaud.pecher@labri.fr

Alain Thiery
email: alain.thiery@math.u-bordeaux1.fr

Alain Thi Éry

ON THE THETA NUMBER OF POWERS OF CYCLE GRAPHS

Keywords: Mathematics Subject Classification. 05C15, 05C85, 90C27 theta number, circular complete graphs, circular perfect graphs

We give a closed formula for Lovász's theta number of the powers of cycle graphs C d k and of their complements, the circular complete graphs K k/d . As a consequence, we establish that the circular chromatic number of a circular perfect graph is computable in polynomial time. We also derive an asymptotic estimate for the theta number of C d k .

INTRODUCTION

Let G = (V, E) be a finite graph with vertex set V and edge set E. The clique number ω(G) and the chromatic number χ(G) are classical invariants of G which can be defined in terms of graph homomorphisms.

A homomorphism from a graph G = (V, E) to a graph G ′ = (V ′ , E ′ ) is a mapping f : V → V ′ which preserves adjacency: if ij is an edge of G then f (i)f (j) is an edge of G ′ . If there is a homomorphism from G to G ′ , we write G → G ′ . Then, the chromatic number of G is the smallest number k such that G → K k , where K k denotes the complete graph with k vertices. Similarly, the clique number is the largest number k such that K k → G.

In the seminal paper [START_REF] Lovász | On the Shannon capacity of a graph[END_REF], Lovász introduced the so-called theta number ϑ(G) of a graph. On one hand, this number provides an approximation of ω(G) and of χ(G) since (this is the celebrated Sandwich Theorem)

ω(G) ≤ ϑ(G) ≤ χ(G),
where G stands for the complement of G. On the other hand, this number is the optimal value of a semidefinite program [START_REF] Vandenberghe | Semidefinite programming[END_REF], and, as such, is computable in polynomial time with polynomial space encoding accuracy [START_REF] Vandenberghe | Semidefinite programming[END_REF], [START_REF] Grötschel | The ellipsoid method and its consequences in combinatorial optimization[END_REF]. In contrast, the computation of either of the clique number or the chromatic number is known to be NP-hard.

By definition, a graph G is perfect, if for every induced subgraph H, ω(H) = χ(H) [START_REF] Berge | Färbungen von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind, Wiss[END_REF]. As ϑ(G) = χ(G) and χ(G) is an integer, we have Theorem 1.1. (Grötschel, Lovász and Schrijver) [START_REF] Grötschel | The ellipsoid method and its consequences in combinatorial optimization[END_REF] For every perfect graph, the chromatic number is computable in polynomial time.

There are very few families of graphs for which an explicit formula for the theta number is known. In [START_REF] Lovász | On the Shannon capacity of a graph[END_REF], the theta numbers of the cycles C k and of the Kneser graphs K(n, r) are explicitly computed. In particular, it is shown that, if k is an odd number, [START_REF] Berge | Färbungen von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind, Wiss[END_REF] ϑ

(C k ) = k cos π k 1 + cos π k .
In this paper, we give a closed formula for the theta number of the circular complete graphs K k/d and of their complements K k/d . For k ≥ 2d, the graph K k/d has k vertices {0, 1, . . . , k -1} and two vertices i and j are connected by an edge if d ≤ |i -j| ≤ k -d. We have K k/1 = K k and K k/2 = C k . More generally, the graph K k/d is the (d -1) th power of the cycle graph C k . Because the automorphism group of K k/d is vertex transitive (it contains the cyclic permutation (0, 1, . . . , k -1)), we have (see [START_REF] Lovász | On the Shannon capacity of a graph[END_REF]Theorem 8])

(2) ϑ(K k/d )ϑ(K k/d ) = k.
Besides the case d = 2 demonstrated by Lovász, the only case previously known was due to Brimkov et al. who proved in [START_REF] Brimkov | On the Lovász number of certain circular graphs[END_REF] that, for d = 3 and k odd,

(3) ϑ K k/3 = k 1 - 1 2 -cos 2π k ⌊ k 3 ⌋ -cos 2π k ⌊ k 3 ⌋ + 1 cos 2π k ⌊ k 3 ⌋ -1 cos 2π k ⌊ k 3 ⌋ + 1 -1 .
In Section 3, we prove the following:

Theorem 1.2. Let d ≥ 2, k ≥ 2d, with gcd(k, d) = 1. Let, for 0 ≤ n ≤ d -1, c n := cos 2nπ d , a n := cos nk d 2π k . Then (4) ϑ(K k/d ) = k d d-1 n=0 d-1 s=1 c n -a s 1 -a s .
The notions of clique and chromatic numbers and of perfect graphs have been refined using circular complete graphs. The circular chromatic number χ c (G) of a graph G was first introduced by Vince in [START_REF] Vince | Star chromatic number[END_REF]. It is the minimum of the fractions k/d for which G → K k/d . Later, Zhu defined the circular clique number ω c (G) of G to be the maximum of the k/d for which K k/d → G and introduced the notion of a circular perfect graph, a graph with the property that every induced subgraph H satisfies ω c (H) = χ c (H) (see Section 7 in [START_REF] Zhu | Recent developments in circular colouring of graphs[END_REF] for a survey on this notion). The class of circular perfect graphs extends in a natural way the one of perfect graphs. So one can ask for the properties of perfect graphs that generalize to this larger class. In this paper, we prove that Theorem 1.1 still holds for circular perfect graphs: Theorem 1.3. For every circular perfect graph, the circular chromatic number is computable in polynomial time.

In previous works, the polynomial time computability of the chromatic number of circular perfect graphs was established in [START_REF] Pêcher | Clique and chromatic number of circular-perfect graphs[END_REF] and of the circular chromatic number of strongly circular perfect graphs (i.e. circular perfect graphs such that the complementary graphs are also circular perfect) was proved in [START_REF] Pêcher | Polynomial time computability of some graph parameters for superclasses of perfect graphs[END_REF].

In contrary to perfect graphs, ϑ(G) does not give directly the result, as ϑ(G) is not always sandwiched between ω c (G) and χ c (G): for instance, ϑ(C 5 ) = √ 5 and ω c (C 5 ) = χ c (C 5 ) = 5/2. To bypass this difficulty, we make use of this following basic observation: by definition, for every graph G with n vertices such that

ω c (G) = χ c (G) = k/d, we have ϑ(G) = ϑ(K k/d ),
where k, d ≤ n (see the next section for more details). Hence, to ensure the polynomial time computability of χ c (G), it is sufficient to prove that the values ϑ(K k/d ) with k, d ≤ n are all distinct and separated by at least ǫ for some ǫ with polynomial space encoding.

This paper is organized as follows: Section 2 gathers the needed definitions and properties of Lovász theta number and of circular numbers. Section 3 proves Theorem 1.2, while Section 4 proves Theorem 1.3. In Section 5, the asymptotic

estimate ϑ(K k/d ) = k d + O 1 k is obtained (Theorem 5.1).

PRELIMINARIES

The theta number ϑ(G) of a graph G = (V, E) was introduced in [START_REF] Lovász | On the Shannon capacity of a graph[END_REF], where many equivalent formulations are given. The one of [START_REF] Lovász | On the Shannon capacity of a graph[END_REF]Theorem 4] has the form of a semidefinite program:

(5)

ϑ(G) = max (x,y)∈V 2 B(x, y) : B ∈ R V ×V , B 0, x∈V B(x, x) = 1, B(x, y) = 0 xy ∈ E
where B 0 stands for: B is a symmetric, positive semidefinite matrix. For a survey on semidefinite programming, we refer to [START_REF] Vandenberghe | Semidefinite programming[END_REF]. The dual program gives another formulation for ϑ(G) (there is no duality gap here because the identity matrix is a strictly feasible solution of (5) so the Slater condition is fulfilled):

(6) ϑ(G) = inf t : B ∈ R V ×V , B 0, B(x, x) = t -1, B(x, y) = -1 xy / ∈ E From (6) one can easily derive that, if G → G ′ , then ϑ(G) ≤ ϑ(G ′ ). Indeed, if
B ′ is an optimal solution of the dual program defining ϑ(G ′ ), then the matrix B defined by B(x, y) := B ′ (f (x), f (y)) is feasible for ϑ(G). The circular complete graphs K k/d have the property that [START_REF] Bondy | A note on the star chromatic number[END_REF]). Thus the theta number ϑ(K k/d ) only depends on the quotient k/d, and we later conveniently assume that k and d are coprime.

K k/d → K k ′ /d ′ if and only if k/d ≤ k ′ /d ′ (see
From the definition, it follows that

ω(G) ≤ ω c (G) ≤ χ c (G) ≤ χ(G).
Moreover, ω(G) = ⌊ω c (G)⌋, χ(G) = ⌈χ c (G)⌉, and ω c (G) and χ c (G) are attained for pairs (k, d) such that k ≥ 2d and k ≤ |V | (see [START_REF] Bondy | A note on the star chromatic number[END_REF], [START_REF] Zhu | Circular perfect graphs[END_REF]).

If G is a circular perfect graph, let k, d be such that gcd(k, d) = 1 and

ω c (G) = χ c (G) = k/d. Because G and K k/d are homomorphically equivalent, ϑ(G) = ϑ(K k/d
). Summarizing, we have Proposition 2.1. Let G be a circular perfect graph with n vertices. Then,

1. ω c (G) = χ c (G) = k/d for some (k, d) such that k ≥ 2d, k ≤ n, and gcd(k, d) = 1. 2. ϑ(G) = ϑ(K k/d ).

AN EXPLICIT FORMULA FOR THE THETA NUMBER OF CIRCULAR COMPLETE GRAPHS

In this section we prove Theorem 1.2. We start with an overview of our proof: first of all we show that ϑ(K k/d ) is the optimal value of a linear program (Proposition 3.1). This step is a standard simplification of a semidefinite program using its symmetries. In a second step, a candidate for an optimal solution of the resulting linear program is defined (Definition 3.2) as the unique solution of a certain linear system. We give an interpretation of this element, in terms of the coefficients of Lagrange interpolation polynomials on the basis of Chebyshev polynomials. Then, playing with the dual linear program, it is easy to prove that this element, if feasible, is indeed optimal (Lemma 3.4). The last step, which is also the most technical, amounts to prove that this elements is indeed feasible, i.e. essentially that its coordinates are non negative (Lemma 3.3). To that end, we boil down to prove that a certain polynomial L 0 (y) has non negative coefficients when expanded as a linear combination of the Chebyshev polynomials (Lemma 3.6).

A linear program defining the theta number.

The vertex set of G = K k/d can be identified with the additive group Z/kZ, and the additive action of this group defines automorphisms of this graph. This action allows to transform the semidefinite program (5) into a linear program, as follows: Proposition 3.1. Let k 0 := ⌊k/2⌋. We have:

(7) ϑ(K k/d ) = max kf 0 : f j ≥ 0, k 0 j=0 f j = 1, k 0 j=0 f j cos 2jℓπ k = 0, 1 ≤ ℓ ≤ d -1
and also:

(8) ϑ(K k/d ) = min kg 0 : d-1 ℓ=0 g ℓ ≥ 1, d-1 ℓ=0 g ℓ cos 2ℓjπ k ≥ 0, 1 ≤ j ≤ k 0
Proof. Taking the average over the translations by the elements of Z/kZ, one constructs from a matrix B which is optimal for (5), another optimal matrix which is translation invariant, i.e. which satisfies B(x + z, y + z) = B(x, y) for all x, y, z ∈ Z/kZ. Thus one can restrict in [START_REF] Grötschel | The ellipsoid method and its consequences in combinatorial optimization[END_REF] to the matrices B which are translation invariant. In other words, we can assume that B(x, y) = F (x -y) for some F : Z/kZ → R. Then we can use the Fourier transform over Z/kZ to express F as

F (z) = k-1 j=0 f j e 2ijzπ/k .
Then B 0 if and only if f j = f k-j and f j ≥ 0 for all j = 0, . . . , k -1. After a change from f j to 2f j for j = 0, k/2, we can rewrite

B(x, y) = k 0 j=0 f j cos 2j(x -y)π k .
Then, it remains to transfer to (f 0 , . . . , f k 0 ) the constraints on B that stand in [START_REF] Grötschel | The ellipsoid method and its consequences in combinatorial optimization[END_REF].

We have (x,y)∈(Z/kZ) 2 B(x, y) = k 2 f 0 , and x∈Z/kZ B(x, x) = k k 0 j=0 f j . The edges of K k/d are the pairs (x, y) with 1 ≤ |x -y| ≤ d -1 so the condition that B(x, y) = 0 for all edges (x, y) translates to

k 0 j=0 f j cos 2jℓπ k = 0, 1 ≤ ℓ ≤ d -1.
Changing f j to f j /k leads to [START_REF] Lovász | On the Shannon capacity of a graph[END_REF]. The linear program ( 8) is the dual formulation of (7).

3.2.

A candidate for an optimal solution of [START_REF] Lovász | On the Shannon capacity of a graph[END_REF]. In order to understand the construction of this solution, it is worth to take a look at the case when d divides k. Indeed, in this case, the system of linear equations

k 0 j=0 f j cos 2jℓπ k = δ 0,l , 0 ≤ ℓ ≤ d -1 which is equivalent to k-1 j=0 f ′ j e 2ijℓπ/k = δ 0,l , 0 ≤ ℓ ≤ d -1 where f ′ j = f ′ k-j = f j /2 for j = 0, k/2, otherwise f ′ j = f j , has an obvious solution f = (f ′ 0 , . . . , f ′ k-1
) defined as follows: take f j = 1/d for the indices j which are multiples of k/d, i.e. for j = nk/d, n = 0, . . . , d -1. Take f j = 0 for other indices. Then f has exactly d non zero coefficients, is feasible because f j ≥ 0, and its objective value equals k/d, which is also the optimal value of the linear program.

In the case when gcd(k, d) = 1, none of the rational numbers nk/d, for n = 0, . . . , d-1, are integers. Instead, we choose indices which are as close as possible, namely we choose the indices of the form ⌊ nk d ⌋ for 0 ≤ n ≤ d -1 and set all other coefficients to zero. Then, the d-tuple of coefficients which are not set to zero, satisfies a linear system with d equations, and this linear system has a unique solution. We shall prove that in this way an optimal solution of ( 7) is obtained. Now we introduce some additional notations. The Chebyshev polynomials ( [START_REF] Szegö | Orthogonal polynomials[END_REF]), denoted (T ℓ ) ℓ≥0 are defined by the characteristic property: T ℓ (cos(θ)) = cos(ℓθ). They can be iteratively computed by the relation

T ℓ+1 (x) = 2xT ℓ (x) -T ℓ-1 (x)
and the first terms T 0 = 1, T 1 = x. These polynomials are orthogonal for the measure dx/

√ 1 -x 2 supported on the interval [-1, 1]. The numbers a n , 0 ≤ n ≤ d -1, introduced in Theorem 1.2, come into play now. Recall that a n = cos nk d 2π k .
We remark that the coefficients in the linear constraints of (7) associated to the indices ⌊ nk d ⌋ are precisely equal to T ℓ (a n ). We assume for the rest of this section that gcd(k, d) = 1. Then the real numbers a n are pairwise distinct. We introduce the Lagrange polynomials ( [START_REF] Szegö | Orthogonal polynomials[END_REF]) associated to (a 0 , . . . , a d-1 ):

(9) L n (y) := d-1 s=0 s =n y -a s a n -a s .
Now we have two basis for the space of polynomials of degree at most equal to d -1: the Chebyshev basis {T 0 , . . . , T d-1 } and the Lagrange basis {L 0 , . . . , L d-1 }.

We introduce the two

d × d matrices T = (τ ℓ,n ) and L = (λ n,ℓ ) such that (10) T ℓ (y) = τ ℓ,0 L 0 (y) + τ ℓ,1 L 1 (y) + • • • + τ ℓ,d-1 L d-1 (y) 0 ≤ ℓ ≤ d -1 and (11) L n (y) = λ n,0 T 0 (y) + λ n,1 T 1 (y) + • • • + λ n,d-1 T d-1 (y) 0 ≤ n ≤ d -1.
Obviously we have

(12) τ ℓ,n = T ℓ (a n ) and T L = LT = I d .
In particular, the d-tuple (λ 0,0 , λ 1,0 , . . . , λ d-1,0 ) satisfies the equations:

(13) d-1 n=0 λ n,0 T ℓ (a n ) = δ ℓ,0 , 0 ≤ ℓ ≤ d -1.
Now we can define our candidate for an optimal solution of (7):

Definition 3.2. With the above notations, let f * = (f * 0 , . . . , f * k 0 ) be defined by:

f * j = λ n,0 if j = ± nk d mod k f * j = 0 otherwise.
It remains to prove that f * is indeed optimal for [START_REF] Lovász | On the Shannon capacity of a graph[END_REF]. It will result from the two following lemmas: Lemma 3.3. For all j, 0 ≤ j ≤ k 0 , f * j ≥ 0. We postpone the proof of Lemma 3.3 to the next subsection. Lemma 3.4. f * is an optimal solution of (7).

Proof. Lemma 3.3, joined with [START_REF] Zhu | Circular perfect graphs[END_REF] shows that f * is feasible. Thus we can derive the inequality:

kλ 0,0 ≤ ϑ(K k/d ).
Now we claim that the element g * = (λ 0,0 , λ 0,1 , . . . , λ 0,d-1 ) is a feasible solution of the dual program [START_REF] Pêcher | Clique and chromatic number of circular-perfect graphs[END_REF]. For that we need to prove that

d-1 ℓ=0 λ 0,ℓ cos 2ℓjπ k ≥ δ j,0 , 0 ≤ j ≤ k 0
which can be rewritten as

d-1 ℓ=0 λ 0,ℓ T ℓ cos 2jπ k ≥ δ j,0 , 0 ≤ j ≤ k 0
or, taking account of ( 11), ( 14)

L 0 cos 2jπ k ≥ δ j,0 , 0 ≤ j ≤ k 0 .
For j = 0, (14) holds because L 0 (1) = L 0 (a 0 ) = 1. For j ≥ 1, we take a look at the position of cos(2jπ/k) with respect to the roots a 1 , . . . , a d-1 of L 0 . Indeed, these roots belong to the set {cos(2jπ/k), j = 1, . . . , k -1}, but it should be noticed that they go in successive pairs. More precisely, a n and a d-n are equal to the first coordinate of neighbor vertices of the regular k-gone. So either cos(2jπ/k) is equal to one of the a n , or there is an even number of roots a n , n ≥ 1, which are greater than cos(2jπ/k). In the later case, L 0 (cos(2jπ/k)) and L 0 (1) have the same sign. Since L 0 (1) = 1, we are done. Since g * is a feasible solution of (8), its objective value, which is equal to kλ 0,0 , upper bounds ϑ(K k/d ). So we conclude that ϑ(K k/d ) = kλ 0,0 and that f * is an optimal solution of (7).

3.3. The proof of Lemma 3.3. We want to prove that λ n,0 ≥ 0 for all n = 0, . . . , d -1. We first prove that this condition is equivalent to: λ 0,ℓ ≥ 0 for all 0 ≤ ℓ ≤ d -1.

a n ′ = cos vnk d 2π k = cos 2ntπ k .
If we set

(15) x = x(k, d) := cos 2tπ k = cos v d - 1 kd 2π ,
we have a n ′ = T n (x). If we reorder the a n according to the permutation n → vn mod d, which fixes 0, the coefficients of the corresponding matrix T are equal to:

τ ℓ,n = T ℓ (a n ′ ) = T ℓ (T n (x)) = T ℓn (x) = T nℓ (x) = τ n,ℓ .
Thus the new matrix T is symmetric. This reordering of the a n , permutes accordingly the coordinates of (λ n,0 , 0 ≤ n ≤ d -1). Also the matrix L = T -1 has become symmetric, so the permuted λ n,0 are equal to λ 0,n (who have not changed in the procedure because the polynomial L 0 (y) is not affected by the reordering of the a n ).

The next lemma ends the proof of Lemma 3.3:

Lemma 3.6. For all 0 ≤ ℓ ≤ d -1, λ 0,ℓ ≥ 0. Proof. Since d-1 s=1 (1 -a s ) ≥ 0, we can replace L 0 (y) by d-1 s=1 (y -a s ) = d-1 s=1 (y -T s (x))
where x is defined in (15). The right hand side becomes a polynomial in the variables x and y, depending only on d. This polynomial has an expansion in the Chebyshev basis:

(16)

d-1 s=1 (y -T s (x)) = d-1 ℓ=0 Q ℓ (x)T ℓ (y).
We introduce complex variables X and Y , such that 2x = X + 1/X and 2y = Y + 1/Y . Then, (16) becomes:

(17)

d-1 s=1 (Y -X s )(Y -X -s ) = Y d-1 d-1 ℓ=-(d-1) Q ′ ℓ (x)Y ℓ where Q ′ 0 = 2 d-1 Q 0 and, for ℓ = 1, . . . , d -1, Q ′ -ℓ = Q ′ ℓ = 2 d-2 Q ℓ .
We want to prove that Q ′ ℓ (x) ≥ 0 when x is given by (15). To that end, we will prove that this sequence of numbers is decreasing:

(18) Q ′ 0 (x) ≥ Q ′ 1 (x) ≥ • • • ≥ Q ′ d-1 (x) and since Q ′ d-1 (x) = 1,
we will be done. Now the idea is to multiply the equation ( 17) by (Y -1), so that the successive differences

Q ′ ℓ-1 (x) -Q ′ ℓ (x)
appear in the right hand side as the coefficients of Y ℓ . We obtain, setting

Q ′ -d = Q ′ d := 0: (19) d-1 s=-(d-1) (Y -X s ) = Y d-1 d ℓ=-(d-1) (Q ′ ℓ-1 (x) -Q ′ ℓ (x))Y ℓ .
We let:

(20)

P (Y ) := d-1 s=-(d-1) (Y -X s ) := 2d-1 j=0 C j (X)Y j .
We have:

P (XY ) = d-1 j=-(d-1) (XY -X j ) = X 2d-1 d-1 j=-(d-1) (Y -X j-1 ) = X 2d-1 Y -X -d Y -X d-1 P (Y ).

This equation leads to:

(Y -X d-1 ) 2d-1 j=0 C j (X)X j Y j = (X 2d-1 Y -X d-1 ) 2d-1 j=0 C j (X)Y j .
Comparing the coefficients of Y j in both sides, we obtain the formula:

(21) C j (X) = C j-1 (X) X j-d -X d X j -1 , 1 ≤ j ≤ 2d -1.
If X = e iθ , we obtain in (21)

(22) C j (X) = C j-1 (X) sin(( j 2 -d)θ) sin( jθ 2 ) , 1 ≤ j ≤ 2d -1.
Thus, taking account of ( 15), ( 19), ( 20) and ( 22), the inequalities (18) that we want to establish, are equivalent to the non negativity of

sin(( j 2 -d)θ) sin( jθ 2 )
when θ = 3.4. The end of the proof of Theorem 1.2. We have obtained an optimal solution f * of ( 7), given in Definition 3.2, with objective value equal to kλ 0,0 . So we have

(23) ϑ(K k/d ) = kλ 0,0 .
We recall that:

(24) L 0 (y) = λ 0,0 T 0 (y) + λ 0,1 T 1 (y) + • • • + λ 0,d-1 T d-1 (y).
If we plug in (24) the value y = c n and sum up for n = 0, . . . , d-1, taking account of T 0 = 1 and d-1 n=0 T j (c n ) = d-1 n=0 cos(2jnπ/d) = 0, we obtain the formula (4).

Other expressions for ϑ(K k/d

). Alternatively, we can integrate (24) for the measure dy/ 1 -y 2 , for which the Chebyshev polynomials are orthogonal, leading to different expressions for ϑ(K k/d ):

Theorem 3.7. We have, with the notations of Theorem 1.2:

ϑ(K k/d ) = k π 1 -1 L 0 (y) dy 1 -y 2 (25) = (-1) d-1 k d-1 n=1 (1 -a n ) ⌊(d-1)/2⌋ j=0 1 2 2j 2j j σ d-1-2j (a 1 , . . . , a d-1 ) (26)
where σ 0 , . . . , σ d-1 denote the elementary symmetric polynomials in d -1 variables.

Proof. Integrating (24) for the measure dy/ 1 -y 2 over the interval [-1, 1] leads to (25) because the Chebyshev polynomials T n satisfy:

1 π 1 -1 T n (y) dy 1 -y 2 = δ n,0 .
Then, ( 26) is obtained from (25) with the monomial expansion of L 0 (y) and the formula (ref ??)

1 π 1 -1 y j dy 1 -y 2 = 0 if j is odd 1 2 j j j/2
otherwise .

Remark 3.8. The expression (4) specializes, when d = 2 and d = 3, to the expressions given respectively in [START_REF] Lovász | On the Shannon capacity of a graph[END_REF] and [START_REF] Brimkov | On the Lovász number of certain circular graphs[END_REF]. Indeed, in the case d = 2, we have c 0 = 1, c 1 = -1, and a 1 =cos(π/k). Replacing in (4), we recover [START_REF] Berge | Färbungen von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind, Wiss[END_REF].

For d = 3, we have c 1 = c 2 = -1/2, a 1 = cos(⌊ k 3 ⌋ 2π k ) and a 2 = cos((⌊ k 3 ⌋ + 1) 2π k ).
We obtain in (4)

ϑ(K k/3 ) = k 3 1 + (c 1 -a 1 )(c 1 -a 2 ) (1 -a 1 )(1 -a 2 ) + (c 2 -a 1 )(c 2 -a 2 ) (1 -a 1 )(1 -a 2 ) = k(1/2 + a 1 a 2 ) (1 -a 1 )(1 -a 2 ) which agrees with the expression (3) given in [4, Theorem 1]. 4. SEPARATING THE ϑ(K k/d )
In this section, we prove Theorem 1.3. Jointly with Proposition 2.1, and following the discussion in the Introduction, it will be an immediate consequence of the following theorem: Theorem 4.1. There exists an absolute and effective constant c such that for all

N ∈ N, k ≤ N, k ′ ≤ N, k ≥ 2d, k ′ ≥ 2d ′ with gcd(k, d) = gcd(k ′ , d ′ ) = 1, and k/d = k ′ /d ′ , |ϑ(K k/d ) -ϑ(K k ′ /d ′ )| ≥ 1 c N 5 .
We start with a proof of the weaker property that ϑ

(K k/d ) = ϑ(K k ′ /d ′ ) if k/d = k ′ /d ′ . Theorem 4.2. If ϑ(K k/d ) = ϑ(K k ′ /d ′ ) then k/d = k ′ /d ′ . Proof. Assume that ϑ(K k/d ) = ϑ(K k ′ /d ′ ) for k/d < k ′ /d ′ . Since ϑ(K p/q ) is an increasing function of p/q (see Section 2), it implies that ϑ(K p/q ) is constant for all p/q ∈ [k/d, k ′ /d ′ ]
. This constant will be denoted ϑ for simplicity.

Claim 4.3. The number ϑ is rational.

Proof. Let q ≥ 5 be a prime such that 1/q < 1 4 (k ′ /d ′ -k/d). Then there exists r such that r/q, (r + 1)/q, (r + 2)/q, (r + 3)/q ∈ [k/d, k ′ /d ′ ]. Since q ≥ 5, it divides at most one of the four numbers r, r + 1, r + 2, r + 3. Hence one can find p such that p/q, (p + 1)/q ∈ [k/d, k ′ /d ′ ] and q is prime to p and p + 1.

For any positive integer a, denote ζ a = exp(2iπ/a). We refer to [START_REF] Lang | Algebraic Number Theory[END_REF] for the basic notions of algebraic number theory that will be involved next. For a number field K, we let Gal(K) denote its Galois group over Q. For number fields K ⊂ L, and x ∈ L, Trace L K (x) and Norm L K (x) denote respectively the trace and norm of x in the extension L/K.

It is well-known (see [START_REF] Lang | Algebraic Number Theory[END_REF]) that

Ψ a : (Z/aZ) × -→ Gal(Q(ζ a )) n → σ n such that σ n (ζ a ) = ζ n
a is an isomorphism. Furthermore, if a and b are coprime,

(Z/abZ) × = (Z/aZ) × × (Z/bZ) ×
by Chinese Remainder Theorem. It implies immediately that We now compute ϑ = ϑ(K p/q ) using formula [START_REF] Brimkov | On the Lovász number of certain circular graphs[END_REF]. By definition, we have

Gal(Q(ζ ab )) = Gal(Q(ζ a )) × Gal(Q(ζ b )),
c n = cos(2nπ/q) = 1 2 (ζ n q + ζ -n q ) = σ n (c 1 ) for 1 ≤ n ≤ q -1. It follows that ϑ = p q (1 + Trace Q(ζpq) Q(ζp) (L 0 (c 1 ))).
It gives immediately that ϑ ∈ Q(ζ p ). The same result using (p + 1)/q leads to ϑ ∈ Q(ζ p+1 ). Since the fields Q(ζ p ) and Q(ζ p+1 ) are linearly disjoint, this proves the result.

Claim 4.4. The number ϑ is an integer.

Proof. Let ϑ = a b with a, b ∈ N coprime. Using the same arguments as in the previous lemma, for any prime p such that 1/p < 1 4 (d/k -d ′ /k ′ ), one can find q, with p coprime to q and q + 1, such that q/p, (q + 1)/p ∈ [d/k, d ′ /k ′ ] . It means that p/q, p/(q + 1)

∈ [k/d, k ′ /d ′ ].
Using formula (4) for p/q, one sees that x = q q-1 n=1 (2 -2a n )ϑ is an algebraic integer, hence Norm Q(ζpq) Q (x) ∈ Z. We now compute this norm.

Since qϑ is rational, Norm pq) where φ is the Euler function. Since p is a prime, a n is a conjugate of a 1 for all 1 ≤ n ≤ q -1, hence Norm

Q(ζpq) Q (qϑ) = (qϑ) φ(
Q(ζpq) Q ( q-1 n=1 (2 -2a n )) = (Norm Q(ζpq) Q
(2 -2a 1 )) q-1 . We also have

2 -2a 1 = 2 -2 cos(⌊ p q ⌋ 2π p ) = (1 -ζ ⌊ p q ⌋ p )(1 -ζ -⌊ p q ⌋ p ). Hence Norm Q(ζpq) Q (2 -2a 1 ) = (Norm Q(ζpq) Q (1 -ζ p )) 2 . Finally, Norm Q(ζpq) Q (1 -ζ p ) = Norm Q(ζp) Q (Norm Q(ζpq) Q(ζp) (1 -ζ p )) = (Norm Q(ζp) Q (1 -ζ p )) φ(q) = p φ(q)
(see [START_REF] Lang | Algebraic Number Theory[END_REF]). Summing up all partial results, one gets (q a b ) φ(pq) p 2(q-1)φ(q) ∈ Z.

If l = p is a prime factor of b, then l divides q by the previous formula. But the same formula holds with q + 1, hence l divides also q + 1. It follows that b is a power of p. But this is true for any p large enough. Hence b = 1. This proves the result.

To finish the proof of Theorem 4.2, we use the following result from [START_REF] Pêcher | Clique and chromatic number of circular-perfect graphs[END_REF] (see also [START_REF] Grötschel | The ellipsoid method and its consequences in combinatorial optimization[END_REF]): if ϑ(K k/d ) ∈ N then k/d ∈ N. But every rational number in the interval [k/d, k ′ /d ′ ] cannot be an integer.

We can now start the proof of Theorem 4.1. It is based on the following obvious lemma. Proof. Since α is a non zero algebraic integer , | Norm

Q(α) Q (α)| ≥ 1. It follows immediately that |α|c δ-1 ≥ 1. Let α = dd ′ d-1 n=1 (2 -2a n ) d ′ -1 n=1 (2 -2a ′ n )(ϑ(K k/d ) -ϑ(K k ′ /d ′ )) = kd ′ d ′ -1 n=1 (2 -2a ′ n ) d-1 n=0 d-1 m=1 (2c n -2a m ) -k ′ d d-1 n=1 (2 -2a n ) d ′ -1 n=0 d ′ -1 m=1 (2c ′ n -2a ′ m )
with the obvious notations c

′ n := cos 2nπ d ′ and a ′ n := cos nk ′ d ′ 2π k ′ .
The number α is thus an algebraic integer, and it is non zero by Theorem 4.2. Moreover it belongs to Q(ζ kdk ′ d ′ ), hence its degree is less than N 4 .

Let β be a conjugate of α. Since the absolute values of the conjugates of a n , a ′ n , c n and c ′ n are all less than 1, one gets

|β| ≤ kd ′ 4 d ′ -1 d4 d-1 + k ′ d4 d-1 d ′ 4 d ′ -1 ≤ 2N N 2 4 N 2 N 2 4 N 2 ≤ N 3 4 N . It follows from Lemma 4.5 that |α| ≥ 1 (N 3 4 N ) N 4 . Furthermore, |dd ′ d-1 n=1 (2 -2a n ) d ′ -1 n=1 (2 -2a ′ n )| ≤ N 2 4 N . This implies imme- diately that |ϑ(K k/d ) -ϑ(K k ′ /d ′ )| ≥ 1 N 2 4 N (N 3 4 N ) N 4 .
This finishes the proof of Theorem 4.1.

THE ASYMPTOTIC BEHAVIOUR OF ϑ(K k/d )

From Lovász's formula (1), the asymptotic behaviour of the theta number of odd holes C 2k+1 is (see [START_REF] Bohman | A limit theorem for the Shannon capacities of odd cycles II[END_REF] for instance):

(27) ϑ (C 2k+1 ) = 2k + 1 2 + O 1 k .
In general, we have ϑ

(K k/d ) ≤ k/d. Indeed, ϑ(K k/d ) = k/ϑ(K k/d ) ≤ k/ω(K k/d ) = k/d.
In this section, we prove:

Theorem 5.1. If d ≥ 3 and k ≥ 4d 3 /π then ϑ(K k/d ) ≥ k d -4eπ 2 3 d k . Hence, for d fixed, ϑ(K k/d ) = k d + O 1 k .
Notice that for d = 2, Theorem 5.1 agrees with Equation (27).

Proof. Let d ≥ 3 and k ≥ 4d 3 /π. For every 0

≤ i ≤ d -1, let c i = cos(2iπ/d), σ i = sin(2iπ/d), a i = cos ik d 2π k and δ i = c i -a i . We have a i = cos(2iπ/d- 2πǫ i ), with ǫ i = s i /kd and s i = ik mod d. Claim 5.2. For every 1 ≤ j ≤ d -1, we have d-1 i=0 i =j,d-j (c j -c i ) = -d 2 2 d σ 2 j if j = 0, d/2 (28) d-1 i=0 i =j,d-j (c j -c i ) = -d 2 2 d-1 if j = d/2 (29) d-1 i=1 1 1 -c i = d 2 -1 6 (30)
Proof. The proof of these equalities is a short computation and the details are omitted. Equation (29) (respectively (28), (30)) is obtained by taking the first derivative (respectively the second derivative, the third derivative) with respect to x of the equality T k (cos x) = cos(kx), taking into account the identity T k (x) -1 = 2 k-1 k-1 i=0 (x -c i ), then by evaluating the resulting identity at π (respectively 2jπ/q, respectively 0). Proof. Indeed,

d-1 i=1 (1 -a i ) = d-1 i=1 (1 -c i ) d-1 i=1 1 + δ i 1 -c i ≥ d 2 2 d-1 d-1 i=1 1 - 2π k(1 -c i )
due to (29).

If x 1 , . . . , x l are real numbers belonging to [0, 1], then l i=1 (1 -x i ) ≥ 1 -(x 1 + . . . + x l ). Since for every i, 2π k(1-c i ) ≤ 1, it follows: Notice that Theorem 5.1 shows that ϑ is close to the circular chromatic number of dense circular perfect graphs (where dense means that the clique number is large compared to the stability number): Corollary 5.6. For every ǫ > 0, for every positive integer α, there is a positive integer ω such that for every circular-perfect graph G satisfying ω(G) ≥ ω and α(G) ≤ α, we have |ϑ G -χ c (G)| ≤ ǫ.

d-1 i=1 (1 -a i ) ≥ d 2 2 d-1 1 - 2π k d-1 i=1 1 1 -c i

Lemma 3 . 5 .

 35 The tuples (λ n,0 , 0 ≤ n ≤ d -1) and (λ 0,ℓ , 0 ≤ ℓ ≤ d -1) are equal up to a permutation of their coordinates.Proof. It turns out that, up to a permutation of the a n , the matrixT is symmetric. Since gcd(k, d) = 1, one can find v, 1 ≤ v ≤ d -1,and t ≥ 0, such that kv = 1 + td. By definition, a n := cos nk d 2π k only depends on n mod d. Let us compute a n ′ where n ′ = vn mod d. Since vnk/d = n/d + nt, we have

v d - 1

 1 kd 2π, 1 ≤ j ≤ d -1, and k ≥ 2d. Let us prove it now: let N = N (k, d) := ⌊ jv d ⌋ ε = ε(k, d) := jv d -N. Since v and d are coprime and 1 ≤ j < d, we have ε ∈ { 1 d , 2 d , . . . , d-1 d }. We first study the sign of sin( jθ 2 ): since jθ 2 = π(N + ε -j kd ), this number belongs to ]N π, (N + 1)π[, which means that the sign of sin( jθ 2 ) is (-1) N . Now we determine the sign of sin(( j 2 -d)θ) : we have ( j 2 -d)θ = π(N -2v+εj kd + 2 k ), from which we obtain that ( j 2 -d)θ belongs to ](N -2v)π, (N -2v+1)π[, thus the sign of sin(( j 2 -d)θ) equals (-1) N +2v .

  hence the fields Q(ζ a ) and Q(ζ b ) are linearly disjoint over Q.

Lemma 4 . 5 .

 45 Let α be a non zero algebraic integer of degree less than δ and c ≥ 1 such that the absolute values of the conjugates of α are less than c then |α| ≥ 1 c δ

Claim 5 . 3 .Claim 5 . 4 . 2 k 2 .since |c j -c i | ≥ π 2 2d 2

 5354222 For every 1 ≤ j ≤ d -1, we haveδ j δ d-j |δ j | ≤ 4π 2 k 2 if j = d/2 (32) Proof. For every 1 ≤ j ≤ d -j, let z j ∈ [2jπ/d -2πǫ j , 2jπ/d] such that δ j = -2πǫ j sin(z j ). As | sin(z j )| ≤ |σ j | or | sin(z d-j )| ≤ |σ j |, we get |δ j δ d-j | ≤ 4π 2 |σ j |(|σ j | + 2π/k)/k 2 .Taking into account |σ j | ≥ sin π d ≥ 2/d, we obtain (31). The inequality (32) is straightforward. For every 1 ≤ j ≤ d -1, we have(33) d-1 i=1 |c j -a i | ≤ eπ 2 2 d-3 (1 -c j ) d Proof. Let m j = δ j δ d-j if j = d/2, and m d/2 = δ d/2 . We have d-1 i=1 |c j -a i | = m j d-1 i=1 i =j,d-j (c j -c i ) for every i = j, d -j ≤ π 2 e 2 d-3 (1 -c j ) d 2 k 2 as k ≥ 4d 3 /π.

≥ d 2 2 d

 2 due to (30) and k ≥ 4d 3 /π. Now we are ready to prove Theorem 5.1. We have the following chain of inequalities:ϑ K k/d = k n -a i ) by Claim 5.5

Supported by the ANR/NSC project GraTel ANR-09-blan-0373-01, NSC98-2115-M-002-013-MY3 and NSC99-2923-M-110-001-MY3.


MD Alessandro Poggi
email: alessandro.poggi@istge.it

Claudia Prevosto

Silvia Catellani

Ilaria Rocco

Anna Garuti

Maria Raffaella Zocchi

Bcl-X L Bax

In Cll

Engagement of

teaching and research institutions in France or abroad, or from public or private research centers.

INTRODUCTION

Accumulation of long-lived, mature monoclonal B cells in peripheral blood, bone marrow and lymphoid tissues has long been recognised as the central feature of chronic lymphocytic leukaemia (CLL) [START_REF] Rai | Chronic lymphocytic leukaemia[END_REF][START_REF] Meinhardt | Molecular pathogenesis of chronic lymphocytic leukaemia: factors and signaling pathways regulating cell growth and survival[END_REF][START_REF] Danilov | Molecular pathogenesis of chronic lymphocytic leukaemia[END_REF]. Then, it has become evident that proliferation signals are crucial for the progression of the disease [START_REF] Chiorazzi | Chronic lymphocytic leukaemia[END_REF][START_REF] Calissano | In vivo intraclonal and interclonal kinetic heterogeneity in B-cell chronic lymphocytic leukaemia[END_REF]. Nevertheless, CLL cells are resistant to both programmed cell death and to standard chemotherapy [START_REF] Kitada | Expression of apoptosis-regulating proteins in chronic lymphocytic leukaemia: correlations with in vitro and in vivo chemoresponses[END_REF][START_REF] Rai | Chronic lymphocytic leukaemia[END_REF][START_REF] Meinhardt | Molecular pathogenesis of chronic lymphocytic leukaemia: factors and signaling pathways regulating cell growth and survival[END_REF]; indeed, CLL show high levels of transcription of anti-apoptotic proteins belonging to the Bcl-2 family, while proapoptotic proteins as Bax are not increased [START_REF] Schena | Growth and differentiation-associated expression of bcl-2 in B chronic lymphocytic leukaemia cells[END_REF][START_REF] Mcconkey | Apoptosis sensitivity in chronic lymphocytic leukaemia is determined by endogenous 34[END_REF][START_REF] Kitada | Expression of apoptosis-regulating proteins in chronic lymphocytic leukaemia: correlations with in vitro and in vivo chemoresponses[END_REF]. Despite this, CLL undergo spontaneous apoptosis in vitro [START_REF] Collins | Spontaneous programmed death (apoptosis) of B-chronic lymphocytic leukaemia cells following their culure in vitro[END_REF][START_REF] Sanz | Bcl-2 family gene modulation during spontaneous apoptosis of B-chronic lymphocytic leukaemia cells[END_REF], thus implying that ex-vivo conditions lack important survival signals conceivably delivered from microenvironment [START_REF] Meinhardt | Molecular pathogenesis of chronic lymphocytic leukaemia: factors and signaling pathways regulating cell growth and survival[END_REF][START_REF] Caligaris-Cappio | Role of the microenvironment in chronic lymphocytic leukaemia[END_REF]. Indeed, CLL can be rescued from apoptosis by co-culture with bone marrow stromal cells, due to increased expression of We and others have shown that the CD31 adhesion molecule can protect from starvation induced apoptosis both CD34 + hemopoietic precursors and endothelial cells, due to the activation of PI-3Kdependent phosphorylation of Akt and induction of Bcl-2 and Bcl-x L antiapoptotic proteins, but not of pro-apoptotic proteins such as Bax [START_REF] Ferrero | Transendothelial migration leads to protection from starvation-induced apoptosis in CD34+CD14+ circulating precursors: evidence for PECAM-1 involvement through Akt/PKB activation[END_REF][START_REF] Gao | PECAM-1 functions as a specific potent inhibitor of mitochondrial-dependent apoptosis[END_REF]. In CLL, CD38 engagement by CD31 has been reported to deliver a survival signal in leukemic B cells; in particular, CD38 + CLL would receive such signal upon binding to CD31 + nurse like cells (NLC) in the bone marrow [START_REF] Deaglio | In-tandem insight from basic science combined with clinical research: CD38 as both marker and key component of the pathogenetic network underlying chronic lymphocytic leukaemia[END_REF][START_REF] Deaglio | CD38/CD31 interactions activate genetic pathways leading to proliferation and migration in chronic lymphocytic leukaemia cells[END_REF]. Besides NLC, CD31 is expressed on multiple cell types, including endothelial cells, platelets and healthy peripheral blood mononuclear cells (PBMC) [START_REF] Delisser | Molecular and functional aspects of PECAM-1/CD31[END_REF]Newman et al, 1997), thus making it possible that several types of interactions However, there are reports showing that the CD38/CD31 couple does not deliver a survival signal in CLL [START_REF] Tonino | No convincing evidence for a role of CD31-CD38 interactions in the pathogenesis of chronic lymphocytic leukaemia[END_REF].

Herein we show that: 1) two groups of CLL can be defined, on the basis of Bcl-x L /Bax and Bcl-2/Bax ratios; 2) oligomerization of CD31 at the surface of CLL induces PI-3K-dependent Akt phosphorylation, NF-kB nuclear translocation and transcription of Bcl-x L and Bcl-2, but not that of Bax, thus increasing Bcl-x L /Bax and Bcl-2/Bax protein ratios; 3) this signal leads to prolonged survival of CLL in vitro; 4) interactions between CD31 expressed by CLL and CD31-expressing transfectants leads to the same results, regardless the expression of CD38 by CLL.

MATERIALS AND METHODS

Patients. Thirty untreated patients with CLL were studied, provided IRB-approved informed consent, at the Clinical Haematology Division (Department of Haematology and Oncology, University of Genoa). The patients met the diagnostic criteria of the National Cancer Institute

Working Group (NCI-WG) [START_REF] Cheson | National Cancer Institute-sponsored Working Group guidelines for chronic lymphocytic leukaemia: revised guidelines for diagnosis and treatment[END_REF] and were staged according to the Rai modified criteria [START_REF] Mcconkey | Apoptosis sensitivity in chronic lymphocytic leukaemia is determined by endogenous 34[END_REF]) as low risk (LR), intermediate risk (IR) and high risk (HR). Their clinical features and risk factors are summarized in table 1. Progressive disease is defined as a change in the clinical features (i.e. from LR to IR or from IR to HR or from LR to HR).

Isolation of B cells, cell culture and apoptotic assay. Peripheral blood mononuclear cells (PBMCs)

were isolated from CLL patients by density gradient centrifugation as described (Poggi et al, 2004).

Cells were then cultured (2x10 6 were cultured either in the absence or presence of the F(ab') 2 of the M89D3 mAb. Apoptotic events were evaluated by annexin-V labeling method, to show the exposure of phosphatidyl-serine at the external side of the plasma membrane, according to the manufacturer's protocol (Bender MedSystem GmBH, Vienna, Austria). B cells were identified by staining with an allophycocyanin (APC)-conjugated anti-CD19 mAb (BD Pharmingen). Apoptotic cells were differentiated from necrotic cells by flow cytometry (Cyan ADP cytofluorimeter, Beckman-Coulter S.p.A., Milan, Italy), after PI staining of non-permeabilized cells. At least 10 4 cells per sample were analysed and apoptotic cells were identified as annexin V + PI + cells [START_REF] Ferrero | Transendothelial migration leads to protection from starvation-induced apoptosis in CD34+CD14+ circulating precursors: evidence for PECAM-1 involvement through Akt/PKB activation[END_REF]. In some experiments, 5x10 5 cells were washed and analysed on Cyan ADP after permeabilisation and PI staining to analyse DNA staining and to identify cells with DNA<2n as apoptotic cells [START_REF] Ferrero | Transendothelial migration leads to protection from starvation-induced apoptosis in CD34+CD14+ circulating precursors: evidence for PECAM-1 involvement through Akt/PKB activation[END_REF].

Viable, non apoptotic cells were evaluated by gating on CD19 + B cells, as annexinV -PI -cells. after CD31-XL. The time point was chosen on the basis of preliminary kinetics experiments in order to detect optimal NF-kB activation. TransAM NF-kB Kits is a 96-well plate with immobilized oligonucleotide containing the NF-kB consensus site (5'-GGGACTTTCC-3') that highly specifically binds to the active form of NF-kB contained in cell extracts. Primary antibodies directed against an epitope of p65 or p52 that is accessible only when NF-kB is activated and bound to its target DNA are then added, followed by HRP-conjugated secondary antibody and reaction developed by the specific substrate contained in the commercial kit. Plates were then read with and ELISA reader at OD 450nm and results expressed as p65 or p52 nuclear/cytoplasmic (N/C) ratio.

Determination of mutational status of

RESULTS

Two groups of CLL can be identified on the basis of in vitro survival and of the ratio between antiapoptotic and pro-apoptotic proteins.

Among the 30 patients analyzed, we have identified two groups of CLL, the former (from now on CLL-I) showing rapid in vitro apoptotic rate (14 out of 30 patients), the latter (CLL-II) more resistant to programmed cell death (16 out of 30 patients). In particular, upon in vitro culture, among CLL-I about 50% of B cells died by day 5 (cut off to assign each case to group I or group II) and almost no living cells were recovered after 10 days; conversely, only 10% of CLL-II cells underwent apoptosis by day 5 and about 50% of these cells were still alive on day 14 (Fig. 1A andB).

Interestingly, the rate of apoptosis seems to be related to the stage of disease; indeed, the 14 patients belonging to CLL-I group, were all at the LR stage, whereas the 16 patients of CLL-II group were HR (12 out of 16) or IR (4 out of 16); moreover, the four patients at IR stage showed progressive disease (PD) over one year (table 1).

To investigate the biochemical basis of such different survival rate, we addressed the question of whether transcription of the anti-apoptotic proteins Bcl-2 and Bcl-x L , referred to a pro-apoptotic protein such as Bax, was different in the two different CLL groups. To this aim, mRNA was extracted from CLL cells immediately after isolation and at different days of culture and analyzed by Q-RT-PCR. First, we found that CLL-II show higher Bcl-x L /Bax or Bcl-2/Bax ratio than CLL-I (1. were confirmed also by measuring the content of each anti-apoptotic protein by ELISA referred to Bax as a ratio (Fig. 1C). Of note, χ 2 analysis revealed a correlation between Bcl-xL/Bax or Bcl-2/Bax ratio and IgV H mutational status (p<0.05) and Zap70 expression (p<0.05).

NLC are present in CLL-II cultures in higher number than in CLL-I cultures.

On the basis of these results, one may hypothesize that in CLL-II are operating survival mechanisms related to their resistance to spontaneous apoptosis and that they are reduced in CLL-I. Thus, we tried to identify such factors. It has been previously described that blood-derived, adherent NLC can protect CLL B cells from spontaneous apoptosis in vitro, through the production of SDF-1 [START_REF] Burger | Blood-derived nurse-like cells protect chronic lymphocytic leukaemia B cells from spontaneous apoptosis through stromal cell-derived factor-1[END_REF]. In keeping with this, in all CLL-II cultures we observed the presence of adherent cells, starting from day 3 and increasing in the following days (day 10 depicted in Fig. 2), to which CLL B cells were attached (Fig. 2Aa and2Ab). On the other hand, a few adherent cells were found in cell cultures performed with cells isolated from peripheral blood of CLL-I donors (Table 1).

First, these adherent cells expressed CD31 (Fig. 2Bb). Second, adherent cells were CD14 -(Fig. 2Bc), CD68 + (Fig. 2Bd), expressed the prolyl-4-hydroxilase (P4H, Fig. 2Be), a marker of collagenproducing cells of mesenchymal origin, as fibroblasts or BMSC [START_REF] Aggarwal | Mesenchymal stem cells modulate allogeneic immune cell responses[END_REF]; Anauta and Fibbe, 2007), and vimentin (Fig. 2Bf) [START_REF] Burger | Blood-derived nurse-like cells protect chronic lymphocytic leukaemia B cells from spontaneous apoptosis through stromal cell-derived factor-1[END_REF]. Moreover, these cells were CD45 + , CD33 + , CD3 -, CD19 -(not shown). Third, by Q-RT-PCR we found that adherent cells expressed transcripts for SDF-1 and the cytoplasmic protein (Fig. 2C), in keeping with what described for NLC in previous reports [START_REF] Burger | Blood-derived nurse-like cells protect chronic lymphocytic leukaemia B cells from spontaneous apoptosis through stromal cell-derived factor-1[END_REF]; nevertheless, the levels of transcription and expression of SDF-1 were significantly higher in CLL-II than in CLL-I NLC (Fig. 2C), while the surface phenotype, including the intensity of CD31 expression, was superimposable in NLC from the 2 CLL groups (not shown). Of note, the number of NLC was significantly higher in CLL-II (mostly HR) than in CLL-I (LR) and related to the stage of disease ( phosphorylation is needed for NF-kB activation [START_REF] Cuni | A sustained activation of PI3K/NF-kappaB pathway is critical for the survival of chronic lymphocytic leukaemia B cells[END_REF]). Thus, we analysed whether CD31 cross-linking by specific mAb could trigger all these biochemical events. We found that basal levels of pAkt in freshly isolated B cells were higher in CLL-II than in CLL-I (Fig. 4A, left vs. right).

Interestingly, CD31 engagement was able to trigger phosphorylation of Akt, that was prevented by the specific inhibitor of PI-3K LY294002 (Fig. 4A), in keeping with our previous data on CD34 + precursors [START_REF] Ferrero | Transendothelial migration leads to protection from starvation-induced apoptosis in CD34+CD14+ circulating precursors: evidence for PECAM-1 involvement through Akt/PKB activation[END_REF]. Of note, oligomerisation of CD31 induced the nuclear translocation (increase of the nuclear/cytoplasmic ratio) of NF-kBp65 (Fig. 4B) and of NF-kBp52 (Fig. 4C) in freshly isolated CLL-I; whereas no effect was observed in the presence of an unrelated mAb (Fig. 4B andC). Activation of NF-kB was not so evident in CLL-II that displayed, on day 0, a high N/C ratio of both subunits (Fig. 4B andC); however, after 2 days of culture in the absence of stimuli, the N/C ratio of NF-kB p65 and p52 decreased also in CLL-II that became responsive to the signal delivered via CD31, detectable 12h after cross-linking of the molecule, i.e. on day 3 (Fig. 4C).

To obtain these survival and biochemical effects, cross-linking of the CD31 molecule was needed, since the F(ab') 2 fragment that binds to CD31 but is unable to be oligomerised by anti-isotype GAM [START_REF] Ferrero | Transendothelial migration leads to protection from starvation-induced apoptosis in CD34+CD14+ circulating precursors: evidence for PECAM-1 involvement through Akt/PKB activation[END_REF], not only was not efficient, but could even exert an opposite effect on survival, possibly due to inhibition of cell-to-cell contacts (Fig. 3A andB, not shown in Fig. 4).

CD31 heterotypic homophilic interactions contribute to prevent CLL apoptosis.

To well as in CD38 + CLL (Fig. 6A). Again, Bcl-x L /Bax and Bcl-2/Bax protein ratio raised upon interaction with CD31 + D12P transfectants both in CD38 -and in CD38 + CLL (Fig. 6B). Both increased survival and enhancement of anti-apoptotic proteins were inhibited by covering CD31

with the specific F(ab') 2 mAb (Fig. 6A andB). Taken together, these data seem in favour of an activating signal delivered via CD31 in CLL, possibly leading to increased survival. Herein, we confirm the existence of two groups of CLL, one with better survival rate and higher levels of anti-apoptotic proteins (CLL-II), the other with the opposite characteristics (CLL-I). We also suggest that homophilic engagement of CD31 during transendothelial migration, which might be favoured in the areas of bone marrow enriched in blood vessels, or upon interaction with NLC, can sustain the transcription of anti-apoptotic proteins and activate both PI-3K and NF-kB in CD38 -CLL. This might be of interest as both these biochemical events and bone marrow angiogenesis, have been proposed as possible therapeutic targets in CLL [START_REF] Cuni | A sustained activation of PI3K/NF-kappaB pathway is critical for the survival of chronic lymphocytic leukaemia B cells[END_REF] Stage defined in 2004 (beginning of this study) according to the Rai classification. 4 Ig mutations were evaluated as described. In most patients CLL were sIgM + with the exception of patients 5,7,16,22 that were sIgD + . The sequences with a germ line homology 98% or higher were considered unmutated and those with a homology less than 98% mutated.

5

WBC and among them lymphocyte count at the time of the study.

6

Zap70 cytoplasmic expression was evaluated by immunofluorescence as described in materials and methods and was considered positive (Pos) when detected on >20% of B cells according to reported data.

Bcl- 2

 2 and activation of cell cycle-associated kinases (Panayoditis et al, 1996; Lagneaux et al, 1998; Ringhausen et al, 2002; Longo et al, 2007). These observations indicate that positive signals occurring in the bone marrow may by-pass pro-apoptotic signals and sustain prolonged survival of CLL.

  bone marrow between leukemic cells and other components of the microenvironment.

3 vs. 0. 6 ,

 36 Fig.1B left or 1.4 vs. 0.55 Fig.1B right). Second, on day 5 Bcl-x L /Bax and Bcl-2/Bax ratio decreased in CLL-I (0.3 vs 0.6 Bcl-x L /Bax, Fig.1B left and 0.3 vs. 0.5 for Bcl-2/Bax, Fig.1B right), while in CLL-II these ratios were still high, although decreased (1.1 on day 5 vs. 1.3 on day 0 for Bcl-x L /Bax, Fig.1B left; 1.1 on day 5 vs. 1.4 on day 0 for Bcl-2/Bax, Fig.1B right). These results

  specific mAb and cultured up to 14 days, in the absence of any growth factor added. At different time points, cells were harvested and checked for apoptosis and for transcription of Bcl-2, Bcl-x L and Bax. As shown in figure3(panel A), engagement of CD31 could delay the apoptotic rate of CLL-I, as more then 60% of alive cells were found on day 7 (<40% apoptotic cells, Fig.3A, left panel), while most of untreated cells or cells incubated with murine Ig died by the same day (about 70% apoptotic cells, Fig.3A, left panel). This effect was less evident on CLL-II (Fig.3A, right panel) possibly due to the fact that during the first days of culture CLL-II still have high levels of antiapoptotic proteins, although decreased compared to day 0 (Fig.1B and C). Of note, on day 5 of culture after CD31 cross-linking, the ratio of Bcl-x L /Bax significantly raised in both CLL-I (0.8 vs. 0.3) and CLL-II (1.1 vs. 0.7), compared to untreated cells or upon incubation of with an unrelated mAb (Fig.3B, left panel). Although to a lesser extent, an increase in Bcl-2/Bax ratio was also observed after CD31 oligomerisation in CLL-I (0.5 vs.0.2) and CLL-II (0.8 vs. 0.6), but not in untreated cells or incubated with unrelated mAb (Fig.3B, right panel). These data were confirmed by measuring the intracellular content of the mentioned proteins (Fig.3C), supporting that the engagement of CD31 can sustain the synthesis of anti-apoptotic proteins in CLL and delay their apoptosis rate.Transcription of Bcl-2 and Bcl-x L is regulated by nuclear translocation of the NF-kB subunits p65 and p52, respectively[START_REF] Turco | NF-kappaB/Rel-mediated regulation of apoptosis in hematological malignancies and normal hematopoietic progenitors[END_REF], moreover, the activation of PI-3K and subsequent Akt et al.PECAM-1 signalling in CLL 12

  Fig.5B, lower panel for CLL-II, Bcl-2/Bax ratio 1.2 vs. 0.8 on day 5). Of note, survival on day 7 was

Finally, as CD38

  is a NF-kB target gene (Kang et al., 2006), we addressed the question of whether CD31-mediated signal could induce or up-regulate CD38 expression on CLL. To this aim, 10 CD38 -(MFI 9±2 a.u.) and 2CD38low (30 or 35% positive cells, MFI 30 or 40 a.u.) were subjected to CD31 cross-linking (i.e. preincubated with the specific mAb, added to GAMcoated plates) or cultured onto CD31 positive transfectants (D12P) compared to CD31 negative mock transfectants, and cultured for 1, 3 or 5 days. No significant variations in the percentage of positive cells or intensity (MFI) of CD38 expression was observed at any of the time points analysed (not shown).

  , we describe two groups of CLL with a different kinetics of apoptosis in vitro, and distinct ratios between anti-apoptotic and pro-apoptotic proteins. Of note, we show that engagement of CD31 induces PI-3K-dependent Akt phosphorylation and NF-kB nuclear translocation in CLL, followed by the enhancement of anti-apoptotic protein transcription and increased survival.In recent years, it has become evident that proliferation signals are crucial for CLL pathogenesis[START_REF] Calissano | In vivo intraclonal and interclonal kinetic heterogeneity in B-cell chronic lymphocytic leukaemia[END_REF]. Nevertheless, enhanced survival of leukemic cells contributes to disease progression; moreover, CLL cells are resistant to standard chemotherapy that exploits apoptosis (Kitada et al, 1998; Meinhart et al, 1999; Danilov et al, 2006). Overexpression of anti-apoptotic genes, such as Bcl-2 and Bcl-x L , deficiency of pro-apoptotic pathways and sustained activation of Akt and NF-kB proteins have been implied in regulating the life and chemotherapy resistance of leukemic B cells (Munzert et al, 2002; Turco et al, 2004; Cuni et al, 2004). Thus, pharmacological inhibition of NF-kB has been proposed to accelerate apoptosis and restore chemosensitivity in CLL (Pickering et al, 2007). We and other have described that, indeed, in a fraction of CLL Akt is constitutively phosphorylated and contributes not only to an increased nuclear translocation of NF-kB, but also to a rise in the transcription of Bcl-x L and Bcl-2 (Longo et al, 2007; Poggi et al, 2008).

( 2002 )

 2002 Tumor necrosis factor receptor-associated factor 1 gene overexpression in B-cell chronic lymphocytic leukaemia: analysis of NF-kappa B/Rel-regulated inhibitors of apoptosis. Blood, 100, 3749-3756. 29. Newman, P.J. (1997) The biology of PECAM-1. Journal of Clinical Investigation, 100, S25-29. 30. Panayiotidis, P., Jones, D., Ganeshaguru, K., Foroni, L. & Hoffbrand, A.V.. (1996) Human bone marrow stromal cells prevent apoptosis and support the survival of chronic lymphocytic leukaemia cells in vitro. British Journal of Haematology, 92, 97-103. 31. Pickering, B.M., de Mel, S., Lee, M., Howell, M., Habens, F., Dallman, C.L., Neville, L.A., Potter, K.N., Mann, J., Mann, D.A., Johnson, P.W., Stevenson, F.K. & Packham, G. (2007) Pharmacological inhibitors of NF-kappaB accelerate apoptosis in chronic lymphocytic leukaemia cells. Oncogene, 26, 1166-1177. 32. Poggi, A., Venturino, C., Catellani, S., Clavio, M., Miglino, M., Gobbi, M., Steinle, A., Ghia, P., Stella, S., Caligaris-Cappio, F. & Zocchi, M.R. (2004) Vdelta1 T lymphocytes from B-CLL patients recognize ULBP3 expressed on leukemic B cells and up-regulated by trans-retinoic acid. Cancer Research, 64, 9172-9179. 33. Poggi, A., Catellani, S., Bruzzone, A., Caligaris-Cappio, F., Gobbi, M. & Zocchi, M.R. (2008) Lack of the Leukocyte-associated Ig-like receptor-1 expression in high risk chronic lymphocytic leukemias results in the absence of a negative signal regulating kinase activation and cell division. Leukemia, 22, 980-988.

7 CD38

 7 expression on leukemic B cells at the time of this study was evaluated by immunofluorescence and was considered positive (Pos) when detected on >28% of B cells according to reported data. 8 Percentage of dead cells determined by Trypan blue exclusion on day 7 of culture. 9 Number (n) of adherent cells/field counted at 200x magnification on day 7 of culture. 10 Expression of CD31 on leukemic B cells evaluated by immunofluorescence as mean fluorescence intensity (MFI). CLL-I: MFI 73±9. CLL-II: 67±6. MFI on B cells from healthy donors: 72±8 (not shown in the table).

Figure 1 .

 1 Figure 1. In vitro survival of CLL on the basis of Bcl-x L /Bax or Bcl-2/Bax ratio.

Figure 2 .

 2 Figure 2. Phenotype of NLC derived from CLL.

Figure 3 .

 3 Figure 3. CD31 oligomerization prevents CLL apoptosis and up-regulates Bcl-x L and Bcl-2.

Figure 4 .

 4 Figure 4. Akt activation and NF-kB nuclear translocation of upon CD31 cross-linking in CLL.

Figure 5 .

 5 Figure 5. Binding to CD31-expressing transfectants up-regulate Bcl-x L and Bcl-2 preventing

Figure 6 . 1 A

 61 Figure 6. Effect of CD31 cross-linking on CD38 + and CD38 -CLL. CD38 -CLL-I (n=10) or CD38 + CLL-II (n=11) were co-cultured with CD31 + D12P transfectants, in the

  Immunofluorescence and confocal microscopy. Samples from CLL cells were cultured for 10 days on glass slides (10 6 cells/mL); then, slides were washed to remove non-adherent cells and fixed in ice-cold 2% paraformaldehyde solution for 10 min. Surface staining was performed with the anti-

	A. Poggi et al. A. Poggi et al. A. Poggi et al.	PECAM-1 signalling in CLL PECAM-1 signalling in CLL PECAM-1 signalling in CLL
	follows: Bcl-2 up-stream 5'-CgC CTT CgC CgA gAT gTC Cag Cca g, down-stream 5'-ACT TgT
	ggC CCA gAT Agg CAC CCA g (385-bp); Bcl-x L up-stream 5'-TTg gAc AAT ggA CTg gTT gA, Akt and NF-kB activation assays. Phosphorylated Akt (pAkt) and total Akt (tAkt) were measured in
	down-stream 5'-gTA gAg Tgg Atg gTC AgT g (780 bp); Bax up-stream 5'-TCC CCC CgA gAg the same samples by ELISA (BioSource Europe, Pantec, Turin, Italy) in CLL lysates prepared as
	CD14 (IgG1) monoclonal antibody (mAb) purchased from BD Pharmingen Europe (Milan, Italy), or gTC TTT T, down-stream 5'-Cgg CCC CAg TTg AAg TTg. Primers for SDF-1 amplifications and above, before or 5min (optimal time, based on kinetics experiments) (Ferrero et al, 2003) after
	the anti-CD68 mAb (Ki-M7, IgG1) from Serotec (Kidlington, OX5 1GE, UK) or the anti-CD31 probes were purchased from Applied Biosystem (userid: Hs00171022_m1). CD31-XL or UmAb-XL, with or without the PI-3K inhibitor LY294002 (5µM, Sigma). Data were
	mAb M89D3. Intracytoplasmic staining on permeabilised cells with 1% NP-40, was performed with Q-RT-PCR was performed on the 7900HT FastRT-PCR system (Applied Biosystems) with the referred to standard curves and results expressed as percentage of pAkt, normalized for tAkt.
	the anti-prolyl-4-hydroxylase (P4H, IgG1) from Dako Italia (Milan, Italy) or the anti-vimentin fluorescent Taqman method (Gabert et al, 2003). mRNAs were normalized to 18s as a control gene, NF-kB activation was evaluated by the TransAM Assay Kit in nuclear extracts obtained using the
	F o r (hVIN-1, IgG1) from Sigma followed by Alexa 647-conjugated anti-isotype goat anti-mouse F o r and referred to a standard curve, i.e. serial dilutions of plasmids containing cloned sequences of 18s (Applied Biosystem). After subtracting the threshold cycle (C T ) value for 18s (Applied Biosystem) from the C T values of the target genes, the ∆C T values were converted with the formula 2 -∆∆CT to r o F Nuclear Extract Kit (Active Motif, Rixensart, Belgium) from CLL B lymphocytes before or 12h
	P P show the fold relative increase in mRNA expression compared to levels prior to cross-linking of the P
	e e different molecules which were given the arbitrary value of 1 (Fleige et al, 2006). Results are e
	e r e r expressed as fold increase for SDF-1 or as Bcl-2/Bax or Bcl-x L /Bax ratio. e r
	R e v i e w Zap70 were performed with the APC-conjugated anti-CD19 mAb or the phycoerythrin (PE)-conjugated anti-CD38 mAb (BD Pharmingen) or with the Alexafluor 488-conjugated anti-Zap70 (CALTAG Labs., Burlingame, CA, USA) as described and this method was validated with a R e v i e R ELISA for Bcl-2, Bcl-x L and Bax and SDF-1 protein measurement. e Purified CLL B cells, or adherent cells obtained from CLL patients or healthy donors (Hds), before or after CD31 cross-linking, were lysed in 1mM EDTA, 0.5% Triton x-100, 10µg/mL aprotinin, v i e semiquantitative western blotting (Scielzo et al, 2006) and samples were analysed on a Cyan ADP cytofluorimeter (Beckman-Coulter). w 10µg/mL leupeptin, 3µg/mL pepstatin and 100µM PMSF (all from Sigma) in PBS; the lysates normalized for protein content and Bcl-2, Bcl-xL or Bax proteins were measured by the commercial w
	ELISA kit (DuoSet IC, R&D Systems Europe, Abingdon, UK), based on the use of capture and
	mRNA isolation, reverse transcription and Q-RT-PCR for SDF-1, Bcl-2, Bcl-x L and Bax. biotinylated detection antibodies, specific for each protein, followed by HRP-streptavidin.
	Adherent cells, or B cells, obtained from healthy donors (Hds) or CLL patients, were recovered; total Following development with ABTS, plated were read at OD 405 , referred to a standard curve as
	RNA was extracted with TriPure (Roche Diagnostics, Milan, Italy) and reverse-transcribed with pg/mL and results expressed as Bcl-x L /Bax or Bcl-2/Bax ratio. SDF-1 was measured by ELISA
	random primers. In some experiments B cells were also collected after CD31 cross-linking. Primers (Bender MedSystem) in cell lysates and in the SN of adherent cells, obtained from CLL patients,
	and probes for Bcl-2, Bcl-x L and Bax were designed using the PrimerExpress software (Applied cultured for 24h in the absence or presence of CD31-XL and results, referred to a standard curve,
	Biosystems, Foster City, CA, USA). The sequence (5' to 3') of the specific primers used are as are expressed as pg/mL.
		6 7 8

immunoglobulins (GAM) (Invitrogen Molecular Probes Europe BV, Leiden, NL). Samples were then analysed by FV500 (Fluoview confocal Laser Scanning Microscope System, Olympus Europe GMBH, Hamburg, Germany) equipped with an He-Neon Red laser at 633nm to excite AlexaFluor 647 dye and associated to a IX81 motorized microscope (Olympus). Samples were observed with PlanApo 40x NA1,00 or 60x NA 1,40 oil objectives and data analysed with FluoView 4.3b computer program (Olympus). Surface staining for CD19 or CD38 and cytoplasmic staining for

  Chi square analysis was also performed for some experiments to correlate of Bcl-2/Bax or Bcl-x L /Bax with IgV H genes mutational status.

	A. Poggi et al.	PECAM-1 signalling in CLL
	α=0.05.
	F o r
	P
	e
	e r
	R
	e
	v i e
	w
		9

IgV H genes. The analysis of IgV H genes mutational status was performed on cDNA as described

(Poggi et al, 2004)

. Sequences were compared with those present in the V BASE sequence directory (http://www.mrc-cpe.cam.ac.uk/imt-doc/vbase-home-page.htlm) and in the IMGT/V-QUEST database (http://imgt.cines.fr). Results are expressed as percentages of germ line homology

[START_REF] Damle | Ig V gene mutational status and CD38 expression as novel prognostic indicators in chronic lymphocytic leukaemia[END_REF][START_REF] Hamblin | Unmutated Ig V(H) genes are associated with a more aggressive form of chronic lymphocytic leukaemia[END_REF]

.

Statistical analysis. Data are presented as mean±SD. Statistical analysis was performed using ANOVA, calculating the F ratio and, when corrected, applying the Bonferroni-Dunnett test with a

Table 1 ), IgV H mutational status

 1 Based on previous observations on myeloid and endothelial cells[START_REF] Ferrero | Transendothelial migration leads to protection from starvation-induced apoptosis in CD34+CD14+ circulating precursors: evidence for PECAM-1 involvement through Akt/PKB activation[END_REF][START_REF] Gao | PECAM-1 functions as a specific potent inhibitor of mitochondrial-dependent apoptosis[END_REF], we planned a series of experiments to demonstrate that engagement of CD31 at the surface of CLL is able to improve their survival in vitro triggering the transcription of anti-apoptotic proteins.

	A. Poggi et al.	PECAM-1 signalling in CLL
	F o r
	P
	e
	e r
	R
	e
	v i e
	w

(p<0.05) and Zap70 expression (p<0.05) (χ χ χ χ 2 analysis).

we observed that CD31 was present at similar level of expression both on CLL-I and CLL-II: indeed, the mean fluorescence intensity (MFI) was 73±9 arbitrary units (a.u.) on CLL-I vs 67±6 a.u. on CLL-II (Table 1), compared to an intensity of 71±8 a.u. in healthy B cells (Table 1 )

 1 . Thus, CLL-I and CLL-II cells were subjected to CD31 cross-linking with the

Of note CLL-I samples represent predominantly low risk CLL, whereas CLL-II samples represent predominantly high risk CLL, according to Ig V/H status, ZAP70 and CD38 expression and clinical stage.

  In both groups, Bcl-x L and Bcl-2 decreased during culture, while the occur, all contributing to the activation of pro-survival signal. We cannot exclude that soluble factors, such as SDF-1 produced and released by NLC, can also sustain CLL survival, although we could not detect SDF-1 in the supernatants of our CLL cultures (not shown). Thus, NLC might provide leukemic B cells with multiple survival signals, one mediated by SDF-1 as reported[START_REF] Burger | Blood-derived nurse-like cells protect chronic lymphocytic leukaemia B cells from spontaneous apoptosis through stromal cell-derived factor-1[END_REF], the others delivered via CD38 and/or via CD31 through the different types of cell-to-cell interaction mentioned above. It

	A. Poggi et al. A. Poggi et al.	PECAM-1 signalling in CLL PECAM-1 signalling in CLL
	has already been demonstrated (Deaglio et al, 2006; Deaglio et al, 2010), and other adhesion binding). During these events, both CD31/CD31 (homophilic) and CD31/CD38 (heterophilic)
	molecules would contribute to this signal (Zucchetto et al, 2009). interactions, can
	In our study we provide evidence that also CD31 can deliver a positive signal in CLL, leading to the
	activation of those biochemical events needed for the enhancement of cell survival. Indeed, the
	engagement and oligomerization of the molecule by the specific mAb, induces PI-3K-dependent Akt
	phosphorylation, nuclear translocation of the NF-kB subunits that contribute to up-regulate the
	transcription of Bcl-x L and Bcl-2, with consequent increase in Bcl-x L /Bax and Bcl-2/Bax protein
	F o r ratio. Interestingly, a similar effect has been described by us and other authors in myeloid and endothelial cells (Ferrero et al, 2003; Gao et al, 2003). Second, upon CD31 cross-linking, in vitro survival of CLL is increased. Superimposable results were obtained by co-culturing both CD38 -CLL F o r
	P e e r R e v i e w P e e r R e v i e and CD38 obtained only under confluent conditions and is important to achieve the so-called haptotactic w
	gradient that is needed for initiating transendothelial migration of CD31 + leukocytes (Zocchi et al,
	1996; Mamdouh et al, 2009). It is conceivable that this gradient is also needed to engage in a
	apoptotic rate increased; supporting the notion that in vitro signals delivered by the homophilic binding the molecule expressed by lymphocytes and deliver the activating signal. This
	microenvironment to leukemic cells (Lagneaux et al, 1998; Caligaris-Cappio et al, 2003) are explanation may also account for the missing evidence, so far, for a role of homophilic CD31-CD31
	interactions in CLL.
		15 16

missing. In the bone marrow, or in lymphoid tissues, intimate contact with stromal and endothelial cells or with NLC occur, and CLL can receive signals during these interactions. That CD38 engagement by CD31 leads to a survival signal in leukemic B cells, upon binding to CD31 + NLC, + CLL with CD31-expressing transfectants; the finding that CD31 + transfectants, that do not express CD38, can trigger survival signals also in CD38 -CLL strongly supports the hypothesis that CD31-CD31 homophylic heterotypic interactions may contribute to CLL resistance to apoptosis. These results are apparently not in agreement with other reports

[START_REF] Deaglio | In-tandem insight from basic science combined with clinical research: CD38 as both marker and key component of the pathogenetic network underlying chronic lymphocytic leukaemia[END_REF][START_REF] Tonino | No convincing evidence for a role of CD31-CD38 interactions in the pathogenesis of chronic lymphocytic leukaemia[END_REF]

; however, in the reported papers gene expression was evaluated, and not transcription or intracellular content of anti-apoptotic proteins. Moreover, subconfluent CD31 + transfectants were used, with a likely diffuse distribution of CD31 molecule at the cell surface. We and others have demonstrated that junctional distribution of CD31, as it occurs in vivo in vascular endothelium, is In our culture experiments different types cell-to-cell adhesion were observed: indeed CLL cells could bind one to each other (homotypic binding) and to NLC grown in culture (heterotypic

is of note that the number of NLC, significantly higher in CLL-II than in CLL-I, and the in vitro survival of leukemic B cells correlate not only with risk factors (CLL-II being predominantly high risk) and the stage of disease, but also with disease progression

. It might be hypothesized that in CLL that are going to show a worst clinical progression, NLC originally resident in the bone marrow, reach the bloodstream and contribute to leukemic cell survival, spreading and colonization of other tissues.

Table 1 .

 1 Clinical features of CLL patients.

	Patients 1 Sex Age Year 2 Stage 3 IgV/H% homol 4	WBC 5 (x10 3 /µl -1 )	L 5 (x10 3 /µl -	Zap70 %pos 6	CD38 %pos 7	Apoptosis (%) 8	NLC 0 (n/field)	CD31 (MFI) 10
						1 )
	CLL-I
	1.	F 63 1997	IR	94.2	16.2	11.5	Neg	Neg	66	2	81
	2.	M 58 2000	IR	94.0	18.1	13.1	Pos	Neg	72	4	73
	3.	M 70 1999 LR	90.1	15.9	12.9	Neg	Neg	78	0	58
	4.	M 65 2000 LR	91.9	23.3	18.0	Pos	Pos	69	0	64
	5.	M 62 2002 LR	98.4	24.0	19.3	Pos	Neg	65	6	78
	6.	F 58 2000 LR	97.2	15.7	10.9	Neg	Neg	73	4	79
	7.	F 65 2000 LR	96.9	22.3	19.9	Pos	Neg	74	8	83
	8.	F 64 1999 LR	96.3	16.7	11.5	Pos	Neg	78	6	80
	9.	F 65 2002 LR	92.5	22.9	19.2	Neg	Neg	67	1	79
	10.	F 56 1999 LR	89.7	28.8	26.8	Pos	Neg	76	8	66
	11.	M 52 2002 LR	96.6	20.0	18.0	Neg	Neg	80	0	59
	12.	M 62 1998 LR	96.9	12.6	10.6	Neg	Neg	72	9	86
	13.	F 69 2003 LR	92.6	16.8	12.5	Neg	Neg	66	4	68
	14	M 71 2004 LR	91.9	18.8	12.9	Neg	Neg	76	6	67
	CLL-II
	01.	M 68 2000 HR	91.3	18.6	11.6	Pos	Pos	18	50	68
	02.	F 83 1994 HR	100	16.5	12.6	Pos	Neg	15	25	76
	03.*	F 80 2002 HR	98.6	23.4	20.3	Pos	Pos	24	75	59
	04.	M 48 2001 HR	99.7	16.2	12.3	Pos	Pos	30	48	75
	05.	M 60 2002 HR	100	14.9	10.9	Pos	Pos	16	42	66
	06.	F 55 2003 HR	98.7	18.9	15.3	Pos	Neg	26	48	71
	07.*	M 71 2003 HR	98.2	26.0	21.5	Pos	Pos	25	29	68
	08.	M 66 1990 HR	99.1	26.2	22.7	Pos	Pos	19	31	62
	09.	M 62 2003 HR	97.6	16.3	12.7	Pos	Pos	20	42	58
	10.*	M 53 2001 HR	98..0	23.2	18.0	Pos	Neg	30	49	64
	11.	M 66 2001	IR	99.3	18.5	15.3	Pos	Pos	18	78	61
	12.	M 65 2000	IR	100	19.1	15.7	Pos	Neg	16	62	76
	13.	M 62 2002	IR	98.0	14.0	10.5	Pos	Neg	22	55	73
	14.	M 61 2003	IR	98.6	21.5	18.3	Pos	Pos	28	60	67
	15.	F 58 2004 HR	98.8	20.6	16.9	Pos	Pos	19	64	68
	16.	F 62 2004 HR	99.8	23.2	19.9	Pos	Pos	18	65	63
	1 Chemonaive patients who never had received chemotherapy unless indicated.* These patients underwent
	chemotherapy in 2005: fludarabine 25 mg/m 2 /day for 3 days; cyclophosphamide 250 mg/m 2 /day for 3 days.

2 Year of diagnosis.

3

British Journal of Haematology

Salute Coordinated Grant Special Project di San Paolo n.2007.


M Sevaux

M J Geiger

Inventory Routing and On-line Inventory Routing File Format

This document presents a simple extension of the TSPLIB file format to serve our needs in the Inventory Routing Problem types. Instead of creating a new file format or putting ASCII files online with a simple description, we have chosen to extend the TSPLIB file format.

This document is an extension of the TSPLIB file format description proposed in [1] to be used for the Inventory Routing Problem and variants. No repetition of the information in [1] is given, unless strictly necessary, but the present file is self-contained to describe our instances.

TSPLIB is a library of sample instances for the TSP (and related problems) from various sources and of various types. In addition to the following problem classes TSP, HCP, ATSP, SOP and CVRP described in [1], we have created two new classes called:

Inventory routing problem (IRP)

We are given n -1 nodes, one depot and distances from the nodes to the depot, as well as between nodes. For delivery to the nodes, trucks with identical capacities are available. The problem is defined for a known a finite horizon 1 . . . H. For each time period, each node has a demand. Each node has also a maximum inventory level. An initial stock is also associated with the node. Potentially, for the depot, an initial stock and a production for all periods might be given. The problem is to find tours for the trucks that satisfy the node demands over the whole horizon without violating the truck capacity constraint and the node maximum inventory level constraint. The number of trucks is not specified. Each tour visits a subset of the nodes and starts and terminates at the depot.

On-line inventory routing problem (OIRP)

The problem definition is the same as above except for the demand, but the data is more complex. Instead of having a complete overview of the demand for the whole horizon, at the beginning of each time period, and for each node, the user will be given a forecast of the forthcoming demand and the precise demand for the current period. This forecast is rather accurate but not precise enough to calculate the exact demand of the next period. The forecast is represented by several figures corresponding to the expected cumulative demand of a range of consecutive periods starting from the current period. For example, 3 figures can be given, representing the expected cumulative demand of the next 5 periods, the expected cumulative demand of the next 20 periods, and the expected cumulative demand of the next 60 periods.

The file format

Each file consists of a specification part and a data part. The specification part contains information on the file format and on its contents. The data part contains explicit data.

The specification part

All entries in this section are of the form <keyword > : <value>, where <keyword > denotes an alphanumerical keyword and <value> denotes alphanumerical or numerical data. The terms <string>, <integer > and <real > denote character string, integer or real data, respectively. The order of specification of the keywords in the data file is arbitrary (in principle), but must be consistent, i. e., whenever a keyword is specified, all necessary information for the correct interpretation of the keyword has to be known. Below we give a list of all available keywords. Additional comments (usually the name of the contributor or creator of the problem instance is given here).

OBJECTIVE : <string>

Since the problem is vast, we would like to allow different people to contribute, and we have let the opportunity here to choose their own objective function.

Possible objective functions are

ROUTING Minimise the total routing cost (sum of routing costs/tour lengths for all periods).

BI OBJECTIVE Both the total routing cost and the total inventory cost are taken into account. Inventory cost is the sum of inventory levels at each node at the end of each period.

SPECIAL The cost function is described later in the file in the section named COST FUNCTION.

COST FUNCTION : <string>

If the OBJECTIVE specification is SPECIAL, this section should describe the special cost function used (e. g. a linear combination of different objectives).

DIMENSION : <integer >

For a TSP or ATSP, the dimension is the number of its nodes. For a CVRP, IRP or OIRP, it is the total number of nodes and depots. For a TOUR file it is the dimension of the corresponding problem. Up to now we have used only the EUC 2D specification which is the most commonly used for CVRP and IRP problem types.

Some of the sections used in the original paper are not relevant if we limited our usage to the EUC 2D specification. We refer the reader to the original paper [START_REF] Reinelt | Tsplib95[END_REF] for a complete description of other sections. Since the default value is NO COORDS, it is necessary to choose the right option here, especially for the EDGE WEIGHT TYPE specification compatibility.

EOF :

Terminates the input data. This entry is optional.

The data part

Depending on the choice of specifications some additional data may be required. This data is given in corresponding data sections following the specification part. Each data section begins with the corresponding keyword. The length of the section is either implicitly known from the format specification, or the section is terminated by an appropriate end-of-section identifier.

NODE COORD SECTION :

Node coordinates are given in this section. Each line is of the form

<integer > <real > <real >
if NODE COORD TYPE is TWOD COORDS. Note that for some instances, coordinates are integer. Think about automatic conversion while reading the file.

The integers give the number of the respective nodes. The real numbers give the associated x and y coordinates.

DEPOT SECTION :

Contains a list of possible alternate depot nodes. This list is terminated by a -1.

MULTIPLE PERIOD DEMAND SECTION :

The demands of all nodes of an IRP are given in the form (per line)

<integer > <integer > <integer >

The first integer specifies a node number, the second the period identifier, and the third its demand for the specified period. The depot nodes should not occur in this section since their demand is null for all periods.

INVENTORY LEVEL SECTION :

The maximum inventory level at all nodes of an IRP are given in the form (per line)

<integer > <integer >

The first integer specifies a node number and the second the maximum inventory level. Please note that this inventory level is a hard constraint at any time. It means that a customer with a maximum inventory level of 100 and 50 units in stock cannot be delivered 60 units in a period, even if its consumption for the period is 20.

INITIAL INVENTORY SECTION :

The initial inventory level at all nodes and at the depot of an IRP are given in the form (per line)

<integer > <integer >

The first integer specifies a node number (or the depot identifier), and the second integer the initial inventory level.

DEPOT SUPPLY SECTION :

To be compatible with [START_REF] Archetti | A hybrid heuristic for an inventoryrouting problem[END_REF], we have added this special section which specifies the number of units that are produced at the depot. The units produced at each period of an IRP are given in the form (per line)

<integer > <integer >

The first integer specifies a period identifier and the second integer the number of units produced. Note that the unit produced in period t cannot be used before period t + 1.

FORECAST DEMAND SECTION :

If the TYPE specification is OIRP, then this section should provide information on the demand forecast.

The forecast at all nodes and for all periods are given in the form (per line)

<integer > <integer > <integer > <integer >

The first integer specifies a node number, the second integer the period index, the third integer the number of periods in the forecast,and the last integer the expected cumulative demand for the number of periods.

For example, an entry like 3 12 5 150 indicates that for node 3 at period 12 and for the next five periods including the current period (so for periods 12 to 16), the expected cumulative demand is 150. It does not mean that the demand will be 30 in each of the periods 12 to 16! Note that the forecast might be wrong, but we hope that the people given the forecast are good enough not to deviate too much from reality.

The distance functions

For the various choices of EGDE WEIGHT TYPE, we now describe the computations of the respective distances. In each case we give a (simplified) C-implementation for computing the distances from the input coordinates.

In some cases, distances are required to be integral. In that case, we round to the nearest integer (as rounding is defined mathematically -if ≥ x.5 rounds up to x + 1, otherwise rounds down to x). Below we have named the rounding function "nint".

Euclidean distance (L 2 -metric)

For edge weight type EUC 2D INT, floating point coordinates must be specified for each node. Let x[i] and y[i] be the coordinates of node i.

In the 2-dimensional case EUC 2D INT, the distance between two points i and j is computed as follows: This distance measure has been used in [START_REF] Kohl | 2-path cuts for the vehicle routing problem with time windows[END_REF] but the user should be aware that this function really depends on the coordinate values.

The function sqrt is the C square root function and floor is the classical mathematical floor function that rounds down real numbers to the integer below.

Access

IRP and OIRP instances are available at logistik.hsu-hh.de/IRP

1. 1 . 1

 11 NAME : <string> Identifies the data file. 1.1.2 TYPE : <string> Specifies the type of the data. Possible types are IRP Inventory routing problem data OIRP On-line inventory routing problem data 1.1.3 COMMENT : <string>

1. 1

 1 .7 CAPACITY : <integer > Specifies the truck capacity in a CVRP, IRP or OIRP. 1.1.8 PERIODS : <integer > Specifies the number of periods in an IRP or OIRP 1.1.9 EDGE WEIGHT TYPE : <string> Specifies how the edge weights (or distances) are given. The values are EUC 2D INT Weights are Euclidean distances in 2-D (integer rounding) EUC 2D DBL Weights are Euclidean distances in 2-D (real value) EUC 2D 1DD Weights are Euclidean distances in 2-D (real value but rounded with 1 decimal digits) Note that the original EUC 2D has been replaced by the EUC 2D INT.

1. 1 .

 1 10 NODE COORD TYPE : <string> Specifies whether coordinates are associated with each node (which, for example may be used for either graphical display or distance computations). The values are TWOD COORDS Nodes are specified by coordinates in 2-D THREED COORDS Nodes are specified by coordinates in 3-D NO COORDS The nodes do not have associated coordinates

  xd = x[i] -x[j]; yd = y[i] -y[j]; dij = nint( sqrt( xd*xd + yd*yd) )For edge weight type EUC 2D DBL, the distance between two points i and j is computed as follows:xd = x[i] -x[j]; yd = y[i] -y[j]; dij = sqrt( xd*xd + yd*yd)For edge weight type EUC 2D 1DD, the distance between two points i and j is computed as follows:xd = x[i] -x[j]; yd = y[i] -y[j]; dij = 1/10*floor(10*sqrt( xd*xd + yd*yd))


P Adde

C Jégo

R Le Bidan

Near maximum likelihood soft-decision decoding of a particular class of rate-1/2 systematic linear block codes

This paper presents a soft-decision decoding algorithm for a particular class of rate-1/2 systematic linear block codes. The proposed algorithm performs successive reencoding of both the data and parity bits, to produce a list of codewords among which the most likely candidate is chosen. Simulation results show that close to optimal performance can be obtained at reasonable complexity. They validate the potential of the proposed algorithm as a practical approach for soft-decision decoding.

Introduction: This paper focuses on Soft-Decision Decoding (SDD) of a particular class of rate-1/2 (n=2k,k) systematic binary linear block codes characterized by the property that their generator matrix G in canonical form can be written as G = [I k , P],

where I k is the k×k identity matrix and P is constrained to be a k×k invertible binary matrix. Note that the considered code family includes self-dual codes as a particular case since the latter satisfy P -1 = P t [START_REF] Blahut | Algebraic codes for data transmission[END_REF]. Many interesting block codes falls into this category, including the (24,12,8) extended Golay code, self-dual Reed-Muller codes, extended quadratic residue codes, or the more recent Cortex codes [START_REF] Carlach | A new family of block turbo-codes[END_REF]. The Cortex construction offers a broad spectrum of possibilities for the problem of constructing short linear block codes with good minimum distance properties and low-complexity soft-decision decoders.

Previous work: Maximum-likelihood (ML) soft-decision decoding is known to offer the best decoding performance in terms of block error probability. However it is computationally intractable for most codes of practical interest. Hence sub-optimal SDD algorithms usually have to be considered. Belief Propagation (BP) is a soft-input softoutput decoding algorithm relying on the exchange of soft information along the edges of a graph defined by the parity-check matrix H of the code [START_REF] Kschischang | Factor Graphs and the Sum-Product Algorithm[END_REF]. BP is known to closely approximate the performance of optimal Maximum A Posteriori (MAP) decod-ing at reduced complexity for codes with sparse parity-check matrices. On the other hand, BP performs poorly with most block codes since the latter usually have highdensity parity-check matrices, and thus graphs with many short cycles. A very general approach to SDD builds a list of candidate codewords and selects the codeword at minimum Euclidean distance from the received word in this list. Various strategies have been proposed to generate the list. A first category of algorithms performs successive re-encoding of different information sets [START_REF] Macwilliams | Permutation decoding of systematic codes[END_REF][START_REF] Dorsch | A decoding algorithm for binary block codes and J-ary output channels[END_REF][START_REF] Fossorier | Soft-decision decoding of linear block codes based on ordered statistics[END_REF][START_REF] Lalam | Sliding window encoding for Reed-Solomon code decoding[END_REF]. We recall that an information set is any set of k linearly independent coordinates in an (n,k) linear block code.

These k positions uniquely determine the codeword, and thus can be used for systematic encoding. In another family of algorithms, the list is constructed by applying candidate error patterns to the received word and by running a hard-decision decoder on the resulting sequences [START_REF] Forney | Generalized minimum distance decoding[END_REF][START_REF] Chase | A class of algorithms for decoding block codes with channel measurement information[END_REF]. In both cases, reliability information available at the matched-filter output can be taken into account during the generation of candidate codewords to significantly reduce the list size (and thus the decoding complexity) at a given performance level. The final decision is given by the candidate codeword at minimum Euclidean distance from the observation r.

Comparison with other SDD algorithms:

Compared to the more general information-set SDD algorithms described in [START_REF] Dorsch | A decoding algorithm for binary block codes and J-ary output channels[END_REF] [START_REF] Fossorier | Soft-decision decoding of linear block codes based on ordered statistics[END_REF], the proposed algorithm is computationally much simpler since it does not need to identify the most reliable information set for each received vector, thereby avoiding a costly Gaussian elimination process. Instead, our algorithm takes advantage of the code symmetry to operate on two, fixed information sets, for which encoding functions are easily derived. Further, unlike [START_REF] Forney | Generalized minimum distance decoding[END_REF][9], no hard-decision decoder is required. Hence this algorithm can be applied to codes for which no algebraic decoder exists. The error patterns generation strategy also differs from the one used in [START_REF] Dorsch | A decoding algorithm for binary block codes and J-ary output channels[END_REF] and [START_REF] Fossorier | Soft-decision decoding of linear block codes based on ordered statistics[END_REF]. In [START_REF] Dorsch | A decoding algorithm for binary block codes and J-ary output channels[END_REF] (see also [START_REF] Valembois | An improved method to compute lists of binary vectors that optimize a given weight function with application to soft-decision decoding[END_REF]), error patterns are generated in order of increasing Euclidean weight, whereas order-i ordered-statistics decoding (OSD) in [START_REF] Fossorier | Soft-decision decoding of linear block codes based on ordered statistics[END_REF] exhaustively tests all combinations of i errors or less in the k most reliable information coordinates. In the proposed algorithm, similarly to the Chase-2 algorithm [START_REF] Chase | A class of algorithms for decoding block codes with channel measurement information[END_REF] (see also [START_REF] Lalam | Sliding window encoding for Reed-Solomon code decoding[END_REF]), the N ep = 2 p candidate error patterns are constructed by testing all configurations of errors confined in the p least reliable positions in each of the considered information set (z s or z p ).

Simulation results:

Figure 1 shows the bit-error-rate (BER) performance of the proposed algorithm for the (24,12,8) extended Golay code. For reference purpose, the performance of ML and OSD decoding are also shown. Order-1 and order-2 OSD involve 13 error patterns and 79 error patterns, respectively. We observe that 2×16 error patterns are sufficient to reach near-ML performance with the proposed algorithm. Order-1 OSD performs slightly better with less error patterns, but this comes at a much higher computational cost, due to the Gaussian elimination process. Order-2 OSD achieves ML performance but with 79 error patterns.

The BER performance of several rate-1/2 block codes of length n=8 up to 48 under SDD with the proposed algorithm are shown in Figure 2. The considered codes in-clude classical algebraic constructions such as the [START_REF] Forney | Generalized minimum distance decoding[END_REF][START_REF] Macwilliams | Permutation decoding of systematic codes[END_REF][START_REF] Macwilliams | Permutation decoding of systematic codes[END_REF] extended Hamming code, the (24,12,8) extended Golay code or the (48,24,12) extended quadratic residue code. The (16,8,5) code was obtained using the Cortex construction. First introduced in [START_REF] Carlach | A new family of block turbo-codes[END_REF], Cortex codes are a family of rate-1/2 self-dual systematic linear block codes with good minimum distance properties. The Cortex construction combines a short base code C with a finite sequence of permutations to produce the k parity bits. The reader is referred to [START_REF] Carlach | A new family of block turbo-codes[END_REF] [START_REF] Perez Chamorro | Decoding a family of dense codes using the sum-product algorithm and subthreshold PMOS[END_REF] for a detailed description of the encoding process. The number of error patterns used in the simulations is specified in Table 1. It was optimized in order to obtain performance within 0.05-0.25 dB from ML decoding for each code. For comparison purpose, we also give the number of error patterns required by order-d min /4 OSD which was shown in [START_REF] Fossorier | Soft-decision decoding of linear block codes based on ordered statistics[END_REF] to practically achieve ML for block codes of length n ≤ 128. These results show that the proposed algorithm is able to achieve near-ML performance at reduced complexity. Indeed, fewer error patterns are necessary and no Gaussian elimination operation (costly in terms of latency and hardware resources) is employed.

Conclusion

Proposed algorithm :

 algorithm The proposed algorithm falls into the class of reliability-based information-set SDD algorithms. It takes advantage of the code properties to further simplify the decoding process. Assuming Binary Phase-Shift Keying (BPSK) transmission over an Additive White Gaussian Noise (AWGN) channel, the algorithm operates as follows. Let r = (r 0, …, r n-1 ) denote the received sequence at the matchedfilter output, and z = (z 0, …, z n-1 ) the corresponding hard-decision sequence (z i = 1 if r i > 0, and 0 otherwise). The vector z is split into two parts z = (z s , z p ) by separating the k systematic and k parity coordinates, respectively. A series of N ep error patterns is applied to the k systematic coordinates z s which are then re-encoded using the canonical generator matrix G s = [I k , P], to produce a first list of N ep candidate codewords. A second list of N ep candidates is obtained by repeating the procedure in parallel on the k parity coordinates z p . Re-encoding of the parity set z p is realized using the generator matrix G p = P -1 × G s = [P -1 , I k ]. By construction, the matrices G s and G p are equivalent up to elementary row operations and thus generate the same code.

  Figure captions:

Figure 1 :

 1 Figure 1: BER performance of soft decoding of the (24,12,8) Golay code.

Figure 2 :

 2 Figure 2: Soft-decision decoding performance of different rate-1/2 block codes of length n=8 up to 48 with the proposed decoding algorithm

Figure 1 1

 1 Figure 1

TableTable 1 :

 1 Number of error patterns required by the proposed solution and by OSD for different codes (n,n/2) block codes (n=8 up to 48).

Table 1 Code (8,4,4) (16,8,5) (24,12,8) (48,24,12)

 1

	Proposed algorithm	2×2	2×4	2×16	2×512
	Order-   d min /4    OSD	5	9	79	2325