Christine Bachoc

Gilles Z Émor

BOUNDS FOR BINARY CODES RELATIVE TO PSEUDO-DISTANCES OF k POINTS

Bounds for binary codes relative to pseudo-distances of k points

Christine Bachoc, Gilles

INTRODUCTION

Let H n := F n 2 denote the binary Hamming space, endowed with the Hamming distance. One of the longstanding problems of coding theory is to find estimates for the maximum cardinality A(n, d) of a code C ⊂ H n with the constraint that the Hamming distance of any pair of distinct elements of C is at least equal to d. The best known upper bound for A(n, d) is obtained with the so-called linear programming method, due to Philippe Delsarte, and is the optimal value of a linear program (LP for short) ( [START_REF] Delsarte | An algebraic approach to the association schemes of coding theory[END_REF], [START_REF] Conway | Sphere Packings, Lattices and Groups[END_REF]Chapter 9]). Because linear programs come with efficient algorithms, this method yields good numerical bounds for given parameters (n, d). Moreover, close to optimal explicit feasible solutions have been found from which upper bounds in the form of explicit functions of n and d have been derived [START_REF] Levenshtein | Universal bounds for codes and designs[END_REF], as well as an upper bound in the asymptotic range [START_REF] Mceliece | New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities[END_REF]. After these significant achievements, the subject fell into a period of about twenty years during which nothing really new was discovered, until A. Schrijver in [START_REF] Schrijver | New code upper bounds from the Terwilliger algebra and semidefinite programming[END_REF] obtained improved upper bounds on A(n, d) for some small values of the parameters (n, d), using semidefinite programming. Although these improvements are numerically not all that impressive, the method behind them introduces genuinely new ideas. In order to explain them, it is good to go back to Delsarte's method. Let us recall that the variables of the Delsarte linear program represent the distribution of the Hamming distance in the constrained code. More precisely, let

x i := 1 card(C) card{(x, y) ∈ C 2 : d(x, y) = i}.
Then the main idea is to observe that these variables satisfy certain linear inequalities, the non trivial ones being related to the Krawtchouck polynomials K n k (x), namely, for 0 ≤ k ≤ n,

n i=0 K n k (i)x i ≥ 0.
Schrijver's new idea [START_REF] Schrijver | New code upper bounds from the Terwilliger algebra and semidefinite programming[END_REF] is to exploit constraints on triples of points (x, y, z) ∈ C 3 rather than deal only with pairs. It turns out that the natural constraints are semidefinite positive (SDP) instead of linear. The variables of the program are where 0 stands for "is positive semidefinite", for some symmetric matrices S(a, b, c). These SDP constraints are closely related to the action of the symmetric group S n on the functional space R Hn ; more precisely, each S n -irreducible module occuring in R Hn gives rise to an SDP inequality with matrices of size equal to its multiplicity. It should be noted that the full group of automorphisms Aut(H n ) acts multiplicity free on the same space R Hn , and that it is the true reason why in the case of the Delsarte method, the constraints are linear.

The aim of the present paper is to show that the Schrijver method can be used not only to strengthen the LP bounds, but also to give bounds for other problems, to which the LP method does not apply. Indeed, in recent years several generalizations of the Hamming distance, in the form of functions (we will call them pseudo-distances) of k ≥ 3 elements of H n have attracted attention. We consider here three such functions f (x 1 , . . . , x k ), namely the generalized Hamming distance d(x 1 , . . . , x k ), the radial distance r(x 1 , . . . , x k ) and the average radial distance r(x 1 , . . . , x k ). They share the crucial property of being invariant by the action of the automorphism group Aut(H n ) of the Hamming space.

The generalized Hamming weights of linear codes were introduced by Ozarow and Wyner [START_REF] Ozarow | Wire Tap Channel II[END_REF] in view of cryptographic applications related to the so-called wire-tap channel. The concept was later made popular for its own sake by Wei [START_REF] Wei | Generalized Hamming weights for linear codes[END_REF]. The notion was extended to the non linear setting in [START_REF] Cohen | Upper bounds on generalized Hamming distances[END_REF] in order to derive bounds on generalized weights. The generalized Hamming distance d(x 1 , . . . , x k ) of k points is the number of coordinates where the k points are not all equal. Thus d(x 1 , x 2 ) is the classical Hamming distance. In [START_REF] Cohen | Upper bounds on generalized Hamming distances[END_REF], the authors derive bounds for generalized distances, focusing on asymptotics, which are analogs of the classical Hamming, Plotkin and Elias-Bassalygo bounds. In the case of linear codes the best known asymptotic upper bounds were obtained in [START_REF] Ashikhmin | New upper bounds on generalized weights[END_REF].

The radial distance and the average radial distance are related to the notion of list decoding. The radial distance or radius of k elements is the smallest radius of a Hamming ball that contains the k points. If a code C has the property that the radius of any k-tuple of pairwise distinct points is at least equal to some value r, then any ball of the Hamming space of radius r -1 intersects C in at most k -1 points. Thus a decoding procedure that outputs every codeword at distance at most r -1 of any given received vector yields a list of codewords of cardinality at most k -1. The search for large codes with given minimum k-radius is also studied in the litterature as the quest for dense multiple packings: indeed, a code of minimal k-radius r provides a packing of balls (centered at the codewords, of radius r -1) such that any element of H n belongs to at most k -1 balls. These notions have a long standing history, going back to problems in Euclidean geometry and to early coding theory. They came back into the limelight some ten years ago when Sudan discovered his now famous algorithm for list decoding of Reed-Solomon codes [START_REF] Sudan | Decoding of Reed Solomon codes beyond the error-correction bound[END_REF]. Blinovskii [START_REF] Blinovskii | Bounds for codes in the case of list decoding of finite volume[END_REF] establishes asymptotic bounds on the maximal number of elements of a code with given minimal radius: in the process he defines an auxiliary quantity, the average radius of k elements that we will also investigate.

In general, we are given a function f from H k n into the set of non-negative integers, and we denote by A k-1 (n, f, m) the maximal number of elements that a binary code C can have under the constraint that f (x 1 , . . . , x k ) ≥ m for every k-tuple of pairwise distinct codewords. Our goal is to show that the SDP method gives good upper bounds for A 2 (n, f, m) for modest values of n, when compared with the classical bounds. Our results provide strong motivation for the development of the SDP method, which is far from being at the same stage of achievement as the LP method.

The paper is organized as follows: Section 2 provides a description of the orbits of Aut(H n ) acting on H k n . This preliminary task is essential since the pseudo-distances we are dealing with only depend on these orbits. Section 3 recalls the definitions and basic properties of the three particular functions we consider. Section 4 defines the code invariants associated to these functions and recalls their significance for applications. Section 5 settles the "classical" bounds. These bounds already appear in the litterature ( [START_REF] Cohen | Upper bounds on generalized Hamming distances[END_REF], [START_REF] Blinovskii | Bounds for codes in the case of list decoding of finite volume[END_REF], [START_REF] Blinovskii | Generalization of Plotkin bound to the case of multiple packing[END_REF]) but not in the precise form needed here: either they are settled only for linear codes, or the concern is in the asymptotic setting and they are not as tight as they can be for small parameters. Section 6 recalls the SDP method of [START_REF] Schrijver | New code upper bounds from the Terwilliger algebra and semidefinite programming[END_REF] using the language of group representation, i.e. following [START_REF] Bachoc | Semidefinite programming, harmonic analysis and coding theory[END_REF], [START_REF] Vallentin | Lecture notes: Semidefinite programs and harmonic analysis[END_REF], [START_REF] Vallentin | Symmetry in semidefinite programs[END_REF]. Section 7 provides some numerical results.

(x ′ , y ′ ) ⇔ d(x, y) = d(x ′ , y ′ ).
Here (x, y) ∼ Aut(Hn) (x ′ , y ′ ) stands for: there exists g ∈ Aut(H n ) such that g(x) = x ′ and g(y) = y ′ . We want to study the action of Aut(H n ) on k-tuples (x 1 , . . . , x k ) ∈ H k n . We introduce: Definition 2.1. For x = (x 1 , . . . , x k ) ∈ H k n , and for u ∈ F k 2 , let n u (x) := card{ j, 1 ≤ j ≤ n : ((x 1 ) j , . . . , (x k ) j ) = u} and let the "weight distribution" of x be defined by

W(x) := (n u (x)) u∈F k 2 .
For u ∈ F k 2 , the word obtained from u by flipping zeros and ones, will be denoted by u. In other words u = u + 1 k . One of {u, u} has the form 0w with w ∈ F k-1 2 . Let n w (x) := n 0w (x) + n 1w (x).

The "symmetrized weight distribution" of x is defined by: W(x) := (n w (x)) w∈F k-1 2

Remarks:

(i) It is nice to identify x with the (k, n) matrix M (x) whose i-th line equals x i . Then n u (x) is the number of columns of x which are equal to u: . . . . . .

M (x) = x 1 =
(ii) We have u∈F k 2 n u (x) = w∈F k-1 2 n w (x) = n.
Proposition 2.2.

x ∼ Aut(Hn) y ⇔ W(x) = W(y).

Proof. It is clear that x ∼ Aut(Hn) y iff x ′ ∼ Sn y ′ where x ′ = (0, x 2x 1 , . . . , x kx 1 ) and y ′ = (0, y 2y 1 , . . . , y ky 1 ). Then W(x ′ ) = W(y ′ ) iff W(x ′ ) = W(y ′ ) and is left unchanged if the coordinates are permuted. Conversely, for an appropriate permutation σ of the coordinates, σ(x ′ ) has its columns reordered in lexicographic order. Another permutation τ has the same effect on y ′ ; since

W(σ(x ′ )) = W(τ (y ′ )), it means that σ(x ′ ) = τ (y ′ ). Remark 2.3. (i) If k = 2, we have of course n 1 (x) = d(x 1 , x 2
) and n 0 (x) = nn 1 (x). In the case k = 3, we have

n 10 + n 11 = d(x 1 , x 2 ) n 01 + n 10 = d(x 2 , x 3 ) n 01 + n 11 = d(x 3 , x 1 )
and the triple (d(x 1 , x 2 ), d(x 2 , x 3 ), d(x 3 , x 1 )) uniquely determines the orbit of (x 1 , x 2 , x 3 ). (ii) For arbitrary k, taking into account the relation w n w = n, the orbits of Aut(H n ) on H k n are described by 2 k-1 -1 independent parameters. In contrast, the orbits of k-tuples of elements of the unit sphere of the Euclidean space S n-1 under the action of the orthogonal group O(R n ) need only k 2 real numbers in order to be uniquely determined, namely the pairwise inner products of the k vectors. The orbits of H k n under Aut(H n ) are determined by the pairwise distances d(x i , x j ) only if k = 2, 3. (iii) In the next section we introduce several functions f (x 1 , . . . , x k ) such that

f (σ(x 1 ), . . . , σ(x k )) = f (x 1 , . . . , x k )
for all σ ∈ Aut(H n ). It follows from the above description of the orbits of H k n that such functions have an expression of the form f (x 1 , . . . , x k ) = f (W(x)).

Aut(H

n )-INVARIANT FUNCTIONS ON H k n . 3.
d(x 1 , . . . , x k ) = card{j, 1 ≤ j ≤ n : card{(x 1 ) j , . . . , (x k ) j } ≥ 2} = card{j, 1 ≤ j ≤ n : ((x 1 ) j , . . . , (x k ) j ) / ∈ {0 k , 1 k }} Proposition 3.2.
The following properties hold for the generalized Hamming distance:

(i) d(x 1 , x 2 ) is the usual Hamming distance. (ii) For all permutation τ of {1, . . . , k}, d(x 1 , . . . , x k ) = d(x τ (1) , . . . , x τ (k) ). (iii) For all σ ∈ Aut(H n ), d(x 1 , . . . , x k ) = d(σ(x 1 ), . . . , σ(x k )). The generalized distance d(x 1 , . . . , x k
) is related to the weight distribution by:

d(x 1 , . . . , x k ) = w =0 k-1 n w (x). (iv) d(x 1 , . . . , x k-1 , x k ) = d(x 1 , . . . , x k-1 ) if x k belongs to the affine subspace generated by x 1 , . . . , x k-1 . (v) "Triangular" inequality: for all y ∈ H n , d(x 1 , . . . , x k ) ≤ 1 k -1 k i=1 d(x 1 , . . . , x i-1 , y, x i+1 , . . . , x k ).
(vi) The distance of three points can be expressed in terms of pairwise Hamming distances:

d(x 1 , x 2 , x 3 ) = 1 2 (d(x 1 , x 2 ) + d(x 2 , x 3 ) + d(x 3 , x 1 )).
(vii) For more than three points we have only the inequality:

d(x 1 , x 2 , . . . , x k ) ≤ 1 k -1 1≤i<j≤k d(x i , x j ).
(viii) We also have the inequalities:

d(x 1 , . . . , x k ) ≤ 1 k -1 k i=1 d(x 1 , . . . , x i-1 , x i+1 , . . . , x k ) d(x 1 , . . . , x k ) ≥ 1 k k i=1 d(x 1 , . . . , x i-1 , x i+1 , . . . , x k ).
Proof. Properties (i), (ii), (iii) are obvious. If x k belongs to the affine subspace generated by x 1 , . . . , x k-1 , then we can write

x k = k-1 i=1 α i x i with k-1 i=1 α i = 1. Consequentely, if ((x 1 ) j , . . . , (x k-1 ) j ) = 0 k-1 , respectively 1 k-1 , then we have ((x 1 ) j , . . . , (x k ) j ) = 0 k , respectively 1 k . It follows (iv) that d(x 1 , . . . , x k-1 , x k ) = d(x 1 , . . . , x k-1 ).
The announced "triangular" inequality (v) is easily checked in the case n = 1. The general case follows from the fact that ( 1)

d(x 1 , . . . , x k ) = n j=1 d((x 1 ) j , . . . , (x k ) j ).
Again because of (1), it is enough to prove (vi) (vii) and (viii) for n = 1. In this case, let the Hamming weight of (x 1 , . . . , x k ) be denoted by w, then

d(x 1 , . . . , x k ) = 1 if 1 ≤ w ≤ k -1 0 if w = 0, k. and 1≤i<j≤k d(x i , x j ) = w(k -w).
Obviously w(kw) ≥ k -1 if w = 0, k and equals 0 otherwise. Inequality (vii) follows. In the case k = 3, w(kw) takes only the values 0 and 2 hence (vi).

To prove (viii), notice that we have

k i=1 d(x 1 , . . . , x i-1 , x i+1 , . . . , x k ) =    k if 2 ≤ w ≤ k -2 k -1 if w = 1, k -1 0 if w = 0, k
hence the announced inequalities.

The radial distance.

Definition 3.3. The radial distance or radius of k elements of H n is defined by:

r(x 1 , . . . , x k ) = min{r : there exists y ∈ H n s.t. {x 1 , . . . , x k } ⊂ B(y, r)} = min y { max 1≤i≤k d(y, x i )}.
Proposition 3.4. The radial distance has the properties:

(i) r(x 1 , x 2 ) = ⌈ d(x 1 ,x 2 ) 2 ⌉. (ii) For all permutations τ of {1, . . . , k}, r(x 1 , . . . , x k ) = r(x τ (1) , . . . , x τ (k) ). (iii) For all σ ∈ Aut(H n ), r(x 1 , . . . , x k ) = r(σ(x 1 ), . . . , σ(x k )). (iv) For all k, r(x 1 , . . . , x k ) ≥ max 1≤i≤k r(x 1 , . . . , x i-1 , x i+1 , . . . , x k ). (v) For k = 3, we have r(x 1 , x 2 , x 3 ) = max{r(x 1 , x 2 ), r(x 2 , x 3 ), r(x 3 , x 1 )}.
Proof. Properties (i) (ii) (iii) and (iv) are obvious. Let (x 1 , x 2 , x 3 ) ∈ H 3 n . Without loss of generality we can assume that d(x 2 , x 3 ) ≤ d(x 3 , x 1 ) ≤ d(x 1 , x 2 ) and that x 1 = 0. With the notation of section 1 it amounts to assume that n 01 ≤ n 10 ≤ n 11 . Let y ∈ H n be the center of a smallest ball containing the three words; clearly the coordinates of y at the positions corresponding to w = 00 in M (x) must be equal to 0. Let y w be the number of ones at the positions corresponding to w. We have: We choose y such that:

y 01 = 0 y 11 = ⌊ n 01 + n 10 + 2n 11 4 ⌉ ≤ n 11 y 10 = ⌊ n 10 -n 01 4 ⌉ ≤ n 10
Then one easily verifies that for i = 1, 2, 3, d(y, x i ) ≤ ⌈ n 10 +n 11

2

⌉ thus the ball centered at y with radius ⌈ n 10 +n 11 2 ⌉ contains the three words x 1 , x 2 , x 3 . Since

n 10 + n 11 = d(x 1 , x 2 ) = max(d(x 2 , x 3 ), d(x 3 , x 1 ), d(x 1 , x 2 ))
we have proved that r(x 1 , x 2 , x 3 ) ≤ max{r(x 1 , x 2 ), r(x 2 , x 3 ), r(x 3 , x 1 )}.

Remark 3.5. For k ≥ 4 we cannot give a nice expression of r(x) as an explicit function of W(x).

It should be noted that the determination of the center y and thus of r(x) cannot be performed by a sequence of local decisions at each coordinate or even at each subset of coordinates corresponding to each u; in other words property (1) of d( ) does not hold for r and it makes it more difficult to study. However for k randomly chosen points, the distances of each point to the center y of the smallest ball containing them are expected to have about the same value, in other words the points are expected to be close to the border of the ball. When it is the case, the radius of the k points is approximated by a much nicer function, called the average radius (or moment of inertia), introduced in [START_REF] Blinovskii | Bounds for codes in the case of list decoding of finite volume[END_REF].

The average radial distance.

Definition 3.6. The average radial distance or average radius (or moment distance or moment of inertia) of k elements of H n is defined by:

r(x 1 , . . . , x k ) = min y 1 k 1≤i≤k d(y, x i ).
Proposition 3.7. The average radius has the properties:

(i) r(x 1 , x 2 ) = d(x 1 ,x 2 ) 2 .
(ii) For all permutation τ of {1, . . . , k}, r(x 1 , . . . , x k ) = r(x τ (1) , . . . , x τ (k) ). (iii) For all σ ∈ Aut(H n ), r(x 1 , . . . , x k ) = r(σ(x 1 ), . . . , σ(x k )). In terms of the weight distribution

W(x) = (n w (x)) w∈F k-1 2 , r(x 1 , . . . , x k ) = 1 k w∈F k-1 2 min(wt(w), k -wt(w))n w (x) (iv) For all k, r(x 1 , . . . , x k ) ≥ 1 k k i=1 r(x 1 , . . . , x i-1 , x i+1 , . . . , x k ) (v)
The above inequality is an equality for k = 1 mod 2. In particular, we have

r(x 1 , x 2 , x 3 ) = r(x 1 , x 2 ) + r(x 2 , x 3 ) + r(x 3 , x 1 ) 3 (vi) For all k, r(x 1 , . . . , x k ) ≤ 2(k -1) k(k -2) k i=1 r(x 1 , . . . , x i-1 , x i+1 , . . . , x k ).
(vii) "Triangular" inequality: for all y ∈ H n ,

r(x 1 , . . . , x k ) ≤ 1 k -1 k i=1 r(x 1 , . . . , x i-1 , y, x i+1 , . . . , x k ).
Proof. Properties (i) (ii) and the Aut(H n )-invariance are trivial.

If the j-th column of the matrix M (x) equals u ∈ F k 2 , the contribution of this column in i d(y, x i ) is equal to wt(u) if y j = 0 and to wt(u) if y j = 1. So the minimum of this sum over all y equals u min(wt(u), wt(u))n u (x).

which leads to the formula announced in (iii). It also shows that

r(x 1 , . . . , x k ) = n j=1 r((x 1 ) j , . . . , (x k ) j ).
Consequently, in order to prove the remaining assertions, we can assume n = 1. Let the weight of x be denoted by w. Without loss of generality we assume that either w < k/2 or w = k/2. This last case can only happen if k = 0 mod 2. We prove (v) and (vi): in the case w < k/2, removing x i = 1 makes kr(x) drop by 1 while removing x i = 0 does not change kr(x). In the case w = k/2, kr(x) always drops by 1. In other words,

(k -1)r(x 1 , . . . , x i-1 , x i+1 , . . . , x k ) =    w -1 if x i = 1 and w < k 2 w if x i = 0 and w < k 2 w -1 if w = k 2 and (k -1) k i=1 r(x 1 , . . . , x i-1 , x i+1 , . . . , x k ) = (k -1)w if w < k 2 k(k -2)/2 if w = k 2 .
We obtain

1 k k i=1 r(x 1 , . . . , x i-1 , x i+1 , . . . , x k ) = r(x) if w = k 2 (k-2) (2k-2) r(x) if w = k 2 hence the inequalities (k -2) (2k -2) r(x) ≤ 1 k k i=1 r(x 1 , . . . , x i-1 , x i+1 , . . . , x k ) ≤ r(x).
If k = 1 mod 2, the case w = k/2 never happens so the second inequality is always an equality.

For the triangular inequality (vii), we find

k k i=1 r(x 1 , . . . , x i-1 ,y, x i+1 , . . . , x k ) =        (k -1)w + k if w < ⌊ k 2 ⌋ and y = 1 (k -1)w if w = k 2 and y = 1 kw if w = k-1 2 and y = 1 (k -1)w if y = 0 hence k k i=1 r(x 1 , . . . , x i-1 , y, x i+1 , . . . , x k ) ≥ (k -1)w = k(k -1)r(x).
3.4. Relationships between d, r, r.

Proposition 3.8. The following hold:

(i) For all x = (x 1 , . . . , x k ) ∈ H k n , 1 k d(x) ≤ r(x) ≤ r(x) ≤ d(x) and r(x) ≤ 1 2 d(x).
(ii) For k = 2, 3, d(x) = kr(x).

(iii) If r(x) = r(x) then the center of any of the balls of minimal radius r(x) containing the points (x 1 , . . . , x k ) is equidistant to these points. The converse is false, in the sense that the points may be equidistant to some y while r(x) < r(x).

Proof. Since

1 k k i=1 d(y, x i ) ≤ max i d(y, x i ),
we obviously have r(x) ≤ r(x). From

1 ≤ min(wt(w), k -wt(w)) ≤ k/2
for w = 0 k-1 and from the expressions given in Proposition 3.7 (iii) for r(x) and in Proposition 3.2 (iii) for d(x) we have

1 k d(x) ≤ r(x) ≤ 1 2 d(x).
Let J be the set of coordinates where x j ∈ {0 k , 1 k }. If we choose y such that y j agrees with (x i ) j for j ∈ J, then d(y, x i ) ≤ n -|J| = d(x). Thus r(x) ≤ d(x). This concludes point (i).

(ii) is obvious from previous formulas. Let us assume that r(x) = r(x) = r and let y be the center of a ball of radius r containing all x i . Then we have the inequalities

r = r(x) ≤ 1 k i d(y, x i ) ≤ max i d(y, x i ) = r thus 1 k i d(y, x i ) = max i d(y, x i )
which means that all d(y, x i ) are equal to r. We build a counterexample with k = 3. If n 01 , n 10 , n 11 are even numbers, the points will be equidistant to some point y with y w = n w /2. We assume moreover that n 01 ≤ n 10 ≤ n 11 . From Proposition 3.4, r(x) = (n 10 + n 11 )/2 and from Proposition 3.7, r(x) = (n 01 + n 10 + n 11 )/3 so if 2n 01 < n 10 + n 11 we are done.

CODE INVARIANTS AND THEIR SIGNIFICANCE

f k-1 (C) = min f (x 1 , . . . , x k )
where the minimum is taken over all k-tuples of pairwise distinct elements of C. Moreover we define

d aff k-1 (C) = min d(x 1 , . . . , x k )
where the minimum is taken over all k-tuples of affinely independent elements of C. Following standard notation in coding theory, we let A k-1 (n, f, m) be the maximal number of elements that a code C ⊂ H n can have under the condition f k-1 (C) ≥ m. Proposition 4.2. The following hold:

(i) d 1 (C) = d aff 1 (C) is the Hamming distance of the code C. (ii) d 2 (C) = d aff 2 (C). (iii) If C is a linear code, and 2 t-1 < k ≤ 2 t , d k-1 (C) = d aff t (C). (iv) If C is a linear code, d aff k-1 (
C) coincides with the minimum (k -1)-th generalized weight as defined in [START_REF] Wei | Generalized Hamming weights for linear codes[END_REF], namely:

d aff k-1 (C) = min{w(D) : D ⊂ C, D linear, dim(D) = k -1}.
where w(D) is the set of coordinates i at which at least one element of D is non zero.

Proof. Obvious.

Remark. The quantity d k (C) is more natural and easier to deal with than the more intricate d aff k (C). Unfortunately, d k (C) only coincides with the minimum k-th generalized weight of a linear code for k = 1, 2, hence the definition of d aff k (C), originally stated in [START_REF] Cohen | Upper bounds on generalized Hamming distances[END_REF]. In [START_REF] Bassalygo | Supports of a code[END_REF] yet another generalisation of the minimum k-th generalized weight to non-linear codes is introduced that does not consider affinely independent sets of vectors. We will not dwell on the differences here and our study will mostly focus on the quantity d k (C) itself, of interest in its own right since it has a natural interpretation in terms of list decoding "radius" for lists of size k when decoding from erasures (see section 4.2 below). Proposition 4.3. For f = d, d aff , r, r and for any code C,

f k-1 (C) ≤ f k (C)
Proof. It follows from Propositions 3.2 (viii), 3.4 (iv) and 3.7 (iv) that for pairwise distinct x f (x 1 , . . . , x k+1 ) ≥ f k-1 (C)

respectively for affinely independent x d(x 1 , . . . , x k+1 ) ≥ d aff k-1 (C). Hence f k-1 (C) ≤ f k (C).

List decoding.

A list decoding procedure is a decoding procedure that outputs a list of codewords. The length L of the list is determined in advance. This list is usually obtained by the enumeration of all codewords in a ball B(y, r). For a given code C, the associated value of r is known as the L-list decoding radius of C: Definition 4.4. The L-list decoding radius R L (C) is the largest value of r such that, for all y ∈ H n , card(B(y, r) ∩ C) ≤ L.

In the case L = 1, we recover the notion of the (unique) decoding radius of a code, R 1 (C) = ⌊(d(C) -1)/2⌋. This number is also the largest value of r such that the balls of radius r centered at the codewords have the property that any L + 1 of them have an empty intersection. A set of balls with this property is called a L-multiple packing. Thus a classical packing of balls is a 1-multiple packing. The notion of list decoding can also be investigated in the framework of erasure decoding, see [START_REF] Guruswami | List Decoding from Erasures: Bounds and Code Constructions[END_REF].

Definition 4.6. The L-list decoding radius for erasures R er L (C) is the largest value of r such that, for all E ⊂ {1, . . . , n}, card(E) ≤ r, and for any y = (y

i ) i ∈E ∈ {0, 1} n-card(E) card({x ∈ C : (x i ) i ∈E = y}) ≤ L.
The following proposition, which is a straightforward consequence of the definition of d L , makes generalized distances relevant to erasure decoding [START_REF] Guruswami | List Decoding from Erasures: Bounds and Code Constructions[END_REF][START_REF] Zémor | Threshold effects in codes, in First French-Israeli workshop on algebraic coding[END_REF][START_REF] Zémor | The threshold probability of a code[END_REF].

Proposition 4.7. R er L (C) = d L (C) -1. 5. UPPER BOUNDS FOR d k , r k , r k .
In this section we gather the analogs of the Singleton, Hamming, Plotkin and Elias bounds for f = d, r, r. The methods are well-known and some of the bounds may be found explicitely in the litterature, but not always in form precise enough for numerical computation (in particular only asymptotic versions of the Elias bounds can be found) which we need to compare them to the new SDP bounds.

The Singleton bound.

This bound for d is the most elementary and is a natural generalisation of the classical Singleton bound for the ordinary Hamming distance.

Proposition 5.1. Let C ⊂ H n . Then, if d k-1 (C) ≥ d k-1 |C| ≤ (k -1)2 n-d k-1 +1 .
Proof. Consider the restriction of the codewords on a fixed set of (nd k-1 + 1) indices. The number of possible images is of course

2 n-d k-1 +1 . If |C| > (k-1)2 n-d k-1 +1
, there is a subset of k codewords having the same image. Thus they have a generalized Hamming distance at most equal to d k-1 + 1 and we have a contradiction.

It is worth noticing that the Singleton bound for k = 3 is tight for d = 3 and for d = n.

Hamming type bound.

This volume type bound is established in [START_REF] Cohen | Upper bounds on generalized Hamming distances[END_REF][Prop II.I] for d k-1 and for linear codes and generalized to the non-linear case in [START_REF] Bassalygo | Supports of a code[END_REF]. We take the following notations: the number of elements of a ball of radius r in H n is denoted b n r or b r if n is clear from the context. We recall the formula

b n r = r k=0 n k . Proposition 5.2. Let C ⊂ H n . Then (i) If r k-1 (C) ≥ r k-1 or r k-1 (C) ≥ r k-1 then |C| ≤ (k -1)2 n b n r k-1 -1 (ii) If d k-1 (C) ≥ d k-1 then |C| ≤ (k -1)2 n b n ⌈d k-1 /k⌉-1 (iii) If d aff k-1 (C) ≥ d k-1 then |C| ≤ 2 n+k-2 b n ⌈d k-1 /k⌉-1 Proof. (i) If r k-1 (C) ≥ r k-1 or r k-1 (C) ≥ r k-1
, from Proposition 3.8 (i) and Proposition 4.5 we have, for all y ∈ H n , card(B(y, r k-1 -1) ∩ C) ≤ k -1. In order to establish the announced inequality, we count in two ways the elements of

E := {(c, y), c ∈ C, y ∈ H n : d(c, y) ≤ r k-1 -1}.
We have

card(E) = c∈C card{y ∈ H n : d(y, c) ≤ r k-1 -1} = |C|b n r k-1 -1 = y∈Hn card{c ∈ C : d(y, c) ≤ r k-1 -1} ≤ card(H n )(k -1) = (k -1)2 n . (ii) If d k-1 (C) ≥ d k-1 , from Proposition 3.8 (i) we have r k-1 (C) ≥ ⌈ d k-1
k ⌉ thus we can apply the previous result.

(iii) Let (x 1 , . . . , x k ) ∈ C k be affinely independent and let y ∈ H n . We have

d k-1 ≤ d(x 1 , . . . , x k ) ≤ 1 k -1 1≤i<j≤k d(x i , x j ) ≤ 1 k -1 1≤i<j≤k (d(x i , y) + d(y, x j )) ≤ 1≤i≤k d(x i , y).
Thus for some i,

1 ≤ i ≤ k, d(x i , y) ≥ ⌈ d k-1 k ⌉.
Since any subset of H n with at least 2 k-2 + 1 elements contains k affinely independent ones, we have for all y ∈ H n ,

card(B(y, ⌈ d k-1 k ⌉ -1) ∩ C) ≤ 2 k-2 .
and we follow the same line as in (i).

Plotkin type bound.

This type of bound is usually derived from the estimate of the average value of f among C k . This average value can be estimated when f can be calculated from its value at each coordinate, which is the case for f = d, r.

We take the following notations: let C be a binary code with M elements; let w j be the number of ones in the j-th column of the M × n matrix whose rows are the M elements of C. Let J k (C), respectively J aff k (C) be the set of k-tuples of pairwise distinct, respectively affinely independent codewords. We moreover define

j k (x) := 0 if x ≤ k -1 k-1 t=0 (x -t) if x ≥ k -1 and j aff k (x) := 0 if x ≤ 2 k-2 x k-2 t=0 (x -2 t ) if x ≥ 2 k-2 . We have obviously |J k (C)| = j k (M ) and |J aff k (C)| ≥ j aff k (M )
, this last inequality being an equality if C is linear. For x ∈ R, we also denote as is usual x k := j k (x)/k!. Proposition 5.3. With the above notations:

(i) If d k-1 (C) ≥ d k-1 then δ k-1 := d k-1 n ≤ 1 -2 M/2 k M k . (ii) If C is linear or if k = 3, and if d aff k-1 (C) ≥ d k-1 , we have δ k-1 := d k-1 n ≤ 1 - 1 2 k-1 M M -1 . (iii) If r k-1 (C) ≥ r k-1 then ρ k-1 := r k-1 n ≤ k-1 i=1 1 k M/2 i M/2 k-i min(i, k -i) M k
Proof. (i) For the generalized Hamming distance, we have

x∈J k (C) d(x) = x∈J k (C) n j=1 d((x 1 ) j , . . . , (x k ) j ) = n j=1 x∈J k (C) d((x 1 ) j , . . . , (x k ) j ) = n j=1 k-1 i=1 k! w j i M -w j k -i . The function x → x i M -x k-i + x k-i M -x i
is concave and invariant by x → Mx thus it takes its maximum at x = M/2. We derive the inequalities:

j k (M )d k-1 ≤ d(x) ≤ n k-1 i=1 k! M/2 i M/2 k -i = nk! M k -2 M/2 k .
(ii) In the special case k = 3, we obtain from (i) the desired inequality. In the case C linear, we observe that w j = 0, M, M/2 and that d((x 1 ) j , . . . , (x k ) j ) is non zero only if w j = M/2 and x 1 , . . . , x k do not all belong to {x ∈ C : x j = 0} or to {x ∈ C : x j = 1}, which have M/2 elements. Thus

j aff k (M )d k-1 ≤ n j aff k (M ) -2j aff k (M/2) hence the announced inequality.
(iii) The result for r is derived similarly to the result (i) in the d case.

k-1 ≥ 1 -1/2 k-1 and ρ k-1 ≥ 1/2 - k-1
⌊(k-1)/2⌋ /2 k . 5.4. The Elias-Bassalygo technique and constant weight codes. We recall that A k-1 (n, f, m) denotes the maximal number of elements that a code C ⊂ H n can have under the condition f k-1 (C) ≥ m; analogously let A k-1 (n, w, f, m) be the maximum among the codes with constant weight w. With a standard argument, the following inequality holds:

(2)

A k-1 (n, f, m) card(H n ) ≤ A k-1 (n, w, f, m) card(J w n ) where J w
n is the set of the n w binary words of length n and weight w. This so-called Elias Bassalygo technique is expected to improve the bounds on H n , if similar bounds are established on the Johnson spaces J w n . Note that the value of w on the right hand side can be chosen freely. This line was followed in [START_REF] Cohen | Upper bounds on generalized Hamming distances[END_REF] for the generalized Hamming distance, and required moreover to extend the methods to non linear codes. In view of (2), we work out Plotkin type bounds for constant weight codes:

(i) If d k-1 (C) ≥ d k-1 then δ k-1 := d k-1 n ≤ 1 - M ω k + M (1-ω) k M k . (ii) If d aff k-1 (C) ≥ d k-1 , we have δ k-1 := d k-1 n ≤ j k (M ) j aff k (M ) 1 - M ω k + M (1-ω) k M k . (iii) If r k-1 (C) ≥ r k-1 then ρ k-1 := r k-1 n ≤ k-1 i=1 1 k M ω i M (1-ω) k-i min(i, k -i) M k
.

Proof. For d and r, we follow the same line as for the proof of Proposition 5.3. There we applied the inequality n j=1 g(w j ) ≤ ng(M/2) for relevant functions g, being concave and invariant by x → Mx. Since C ⊂ J w n , we have n j=1 w j = M w, so we can instead use the stronger inequality n j=1 g(w j ) ≤ ng(M w/n).

THE SDP

BOUND FOR d 2 , r 2 , r 2 .
The method developed in [START_REF] Schrijver | New code upper bounds from the Terwilliger algebra and semidefinite programming[END_REF] can be used to derive upper bounds for the cardinality of a binary code C with given d 2 (C) (respectively r 2 (C), r 2 (C)). Recall that d 2 (C) ≥ d if and only if, for all (x, y, z) ∈ C 3 such that x = y, y = z, d(x, y) + d(y, z)

+ d(z, x) ≥ 2d , z = x (respectively r 2 (C) ≥ r iff max(⌈ d(x,y) 2 ⌉, ⌈ d(y,z) 2 ⌉, ⌈ d(z,x)
2 ⌉) ≥ r and r 2 (C) ≥ r iff d(x, y)+d(y, z)+d(z, x) ≥ 6r for all (x, y, z) ∈ C 3 ).

The SDP constraints at work in [START_REF] Schrijver | New code upper bounds from the Terwilliger algebra and semidefinite programming[END_REF] are exactly SDP constraints on triples of points. In order to describe these constraints we adopt the group theoretic point of view of [START_REF] Bachoc | Semidefinite programming, harmonic analysis and coding theory[END_REF], [START_REF] Vallentin | Lecture notes: Semidefinite programs and harmonic analysis[END_REF], [START_REF] Vallentin | Symmetry in semidefinite programs[END_REF].

Let X := H n and, for all k := 0 . . . n, the so-called Johnson spaces X k := {x, x ∈ X : wt(x) = k}. We consider the action of the symmetric group S n on H n . The Johnson spaces X k are exactly the orbits of this action. Now we consider the decomposition of the functional space L2 (X) = R X of real valued functions on X under the action of S n . The space R X is endowed with the S n -invariant scalar product

(f, g) = 1 |X| x∈X f (x)g(x).
We have the obvious decomposition into pairwise orthogonal S n -invariant subspaces:

R X = R X 1 ⊥ R X 1 ⊥ • • • ⊥ R Xn .
The decomposition of R X k into S n -irreducible subspaces is described in [START_REF] Delsarte | Hahn polynomials, discrete harmonics and t-designs[END_REF]. We have

R X k = H 0,k ⊥ H 1,k ⊥ • • • ⊥ H min(k,n-k),k
where the H i,k are pairwise isomorphic for fixed i and pairwise non isomorphic for fixed k. The picture looks like:

R X = R X 1 ⊥ R X 1 ⊥ . . . ⊥ R X ⌊ n 2 ⌋ ⊥ . . . ⊥ R X n-1 ⊥ R Xn H 0,0 ⊥ H 0,1 ⊥ . . . ⊥ H 0,⌊ n 2 ⌋ ⊥ . . . ⊥ H 0,n-1 ⊥ H 0,n H 1,1 ⊥ . . . ⊥ H 1,n-1 . . . . . . H ⌊ n
where the columns represent the decomposition of R X k and the rows the isotypic components of R X , with multiplicity n -2k + 1, i.e. we have for 0

≤ k ≤ ⌊ n 2 ⌋, H k,k ⊥ H k,k+1 ⊥ • • • ⊥ H k,n-k ≃ H n-2k+1 k,k .
To each of these isotypic components, indexed by k, for 0 ≤ k ≤ ⌊ n 2 ⌋, we associate a matrix E k of size n -2k + 1 as explained in [START_REF] Bachoc | New upper bounds for kissing numbers from semidefinite programming[END_REF], indexed with s, t subject to k ≤ s, t ≤ nk, in the following way: Let (e k,k,1 , e k,k,2 , . . . , e k,k,h k ) be an orthonormal basis of H k,k and let e k,s,j = ψ k,s (e k,k,j ). The application ψ k,s is defined by:

ψ k,s : R X k → R X k f → ψ k,s (f ) : ψ k,s (f )(y) = wt(x)=k x⊂y f (x)
and has the property to send and orthonormal basis of H k,k to an orthogonal basis of H k,s , the elements of this basis having constant square norm equal to n-2k s-k . The (s, t) coefficient of E k is defined by:

E k,s,t (x, y) = 1 h k h k j=1
e k,s,j (x)e k,t,j (y).

From [START_REF] Bachoc | New upper bounds for kissing numbers from semidefinite programming[END_REF], E k,s,t (x, y) = E k,s,t (gx, gy) for all g ∈ S n . Thus for k ≤ s ≤ t ≤ nk, we can define P k,s,t by E k,s,t (x, y) = P k,s,t (s -|x ∩ y|). It turns out that these P k,s,t express in terms of Hahn polynomials.

The Hahn polynomials associated to the parameters n, s, t with 0 ≤ s ≤ t ≤ n are the polynomials Q k (n, s, t; x) with 0 ≤ k ≤ min(s, nt) uniquely determined by the properties:

(i) Q k has degree k in the variable x (ii) They are orthogonal polynomials for the weights

0 ≤ i ≤ s w(n, s, t; i) = s i n -s t -s + i (iii) Q k (0) = 1
The combinatorial meaning of the above weights is the following: Lemma 6.1. Given x ∈ X k , the number of elements y ∈ X t such that |x ∩ y| = si is equal to w(n, s, t; i).

Finaly we have:

Proposition 6.2. If k ≤ s ≤ t ≤ n -k, wt(x) = s, wt(y) = t, E k,s,t (x, y) = |X| t-k s-k n-2k t-k n t t s Q k (n, s, t; s -|x ∩ y|) If wt(x) = s or wt(y) = t, E k,s,t (x, y) = 0.
By the construction, the matrices E k satisfy the semidefinite positivity properties:

Theorem 6.3. For all k, 0 ≤ k ≤ ⌊ n 2 ⌋, for all C ⊂ H n , (c,c ′ )∈C 2 E k (c, c ′ ) 0.
These constraints are not interesting for pairs because they are not stronger than the positivity properties from Delsarte method. They are only interesting if triples of points are involved: namely we associate to (x, y, z) ∈ H 3 n the matrices

F k (x, y, z) := E k (x -z, y -z).
We have for all C ⊂ H n , and for all z ∈ H n ,

(c,c ′ )∈C 2 F k (c, c ′ , z) 0
which leads to the two positive semidefinite conditions:

(3) (c,c ′ ,c")∈C 3 F k (c, c ′ , c") 0 (c,c ′ )∈C 2 ,c" / ∈C F k (c, c ′ , c") 0 From Proposition 6.2, E k (x -z, y -
z) only depends on the values of wt(xz), wt(yz), wt(xy); so with a := d(y, z), b := d(x, z), c := d(x, y), we have for some matrices T k (a, b, c),

F k (x, y, z) = T k (a, b, c).
We introduce the unknowns x a,b,c of the SDP. Let, for

(a, b, c) ∈ Ω := {(a, b, c) ∈ [0 . . . n] 3 : a + b + c ≡ 0 mod 2 a + b + c ≤ 2n c ≤ a + b b ≤ a + c a ≤ b + c           
(i) x 0,0,0 = 1 (ii) x a,b,c ≥ 0 (iii) x a,b,c = x τ (a),τ (b),τ (c) for every permutation τ of {a, b, c} (iv) x a,b,c ≤ t(a, b, c)x 0,c,c (v) x a,b,c ≤ t(b, c, a)x 0,a,a (vi) x a,b,c ≤ t(c, a, b)x 0,b,b (vii) a,b,c T k (a, b, c)x a,b,c 0 for all 0 ≤ k ≤ ⌊ n 2 ⌋ (viii) a,b,c T k (a,

NUMERICAL RESULTS

In this section we compare the SDP bounds obtained for A 2 (n, d, m) and for A 2 (n, r, m) with the previously known bounds, stated in Section 5. We recall the obvious values A 2 (n, d, 3) = 2 n-1 , A 2 (n, d, n) = 4, A 2 (n, r, 1) = 2 n , A 2 (n, r, ⌊n/2⌋) = 4.

Table 1 gives two upper bounds for A 2 (n, d, m): one is the tightest of the combinatorial bounds of section 5, with a superscript 1, 2, 3, 4 denoting which of the four methods, Singleton, Hamming, Plotkin, Elias (respectively) achieves this best, and the other is the bound obtained by the SDP method of Section 6. As we can see, in the non-trivial cases the SDP bound gives a substantial improvement almost all the time.

For the radius r, we can restrict ourselves to codes in which the pairwise distances are even. Let us denote A + 2 (n, r, m) the maximal number of elements of such a code with minimal radius at least equal to m; then one easily sees that A 2 (n, r, m) = A + 2 (n + 1, r, m), with the standard extension of an optimal code to an even code with an extra coordinate. Table 2

  y, z) ∈ C 3 : d(y, z) = a, d(x, z) = b, d(x, y) = c} and the SDP constraints take the form a,b,c x a,b,c S(a, b, c) 0, Date: February 15, 2010.

1

 1

1 .Definition 3 . 1 .

 131 The generalized Hamming distance. The generalized Hamming distance of k elements of H n is defined by:

  d(y, x 1 ) = y 01 + y 10 + y 11 d(y, x 2 ) = y 01 + n 10y 10 + n 11y 11 d(y, x 3 ) = n 01y 01 + y 10 + n 11y 11

4. 1 .Definition 4 . 1 .

 141 Code invariants. For any C ⊂ H n , and for f = d, r, r, we define

Proposition 4. 5 .

 5 R L (C) = r L (C) -1.Proof. There exists (x 1 , . . . , x L+1 ) ∈ C L+1 and y ∈ H n such that for all 1 ≤ i ≤ L + 1, x i ∈ B(y, r L (C)) and x i = x j thus card(B(y, r L (C)) ∩ C) = L + 1 and R L (C) < r L (C). Moreover, if r < r L (C), L + 1 codewords cannot be elements of the same ball of radius r thus R L (C) = r L (C) -1.

Remark 5 . 4 .

 54 The upper bounds established in Proposition 5.3 can easily be turned into upper bounds for M = |C|. Indeed, if φ k-1 := f k-1 /n ≤ A(M )/B(M ) where A and B are polynomials of the same degree, with respective leading coefficients α and β, with B(M ) > 0, then, if φ k-1 ≥ α/β, M is upper bounded by the largest zero of the polynomial φ k-1 B(M ) -A(M ). The bound obtained this way holds for δ

Proposition 5 . 5 .

 55 Let C ⊂ J w n have M elements and let ω := w/n.

  x a,b,c := 1 |C| card{(x, y, z) ∈ C 3 : d(y, z) = a, d(x, z) = b, d(x, y) = c}. Note that x 0,c,c = 1 |C| card{(x, y) ∈ C 3 : d(x, y) = c}. With the definition t(a, b, c) := card{z ∈ H n : d(x, z) = b and d(y, z) = a} for d(x, y) = c = c i n-c a-i where ab + c = 2i the following inequalities hold for x a,b,c :

  b, c)(t(a, b, c)x 0,c,cx a,b,c ) 0 for all 0 ≤ k ≤ ⌊ n 2 ⌋ where conditions (vii) and (viii) are equivalent to (3). To the above semidefinite constraints we add the extra condition (ix) that translates the assumption that d 2 (C) ≥ d for some given value d (respectivelyr 2 (C) ≥ r, r 2 (C) ≥ r), namely (ix) d x a,b,c = 0 if abc = 0 and a + b + c ≤ 2(d -1) respectively (ix) r x a,b,c = 0 if abc = 0 and a + b + c < 6r or (ix) r x a,b,c = 0 if abc = 0 and max(⌈ a 2 ⌉, ⌈ b 2 ⌉, ⌈ c 2 ⌉) ≤ r -1. It remains to notice that (x) |C| = c x 0,c,c . Thus an upper bound on |C| is obtained with the optimal value of the program that maximizes c x 0,c,c under the constraints (i) to (ix). It is worth noticing that the conditions (ix) can be replaced by any other conditions of the type (ix * ) x a,b,c = 0 if (a, b, c) ∈ I where I is a set of forbidden values in C related to some other situation. In the classical case treated in [15], d 1 (C) ≥ δ, I = {(a, b, c) : a or b or c ∈ [1 . . . (δ -1)] 3 }.

  2. THE ORBITS OF Aut(H n ) ACTING ON H k n The automorphism group of the binary Hamming space H n := F n 2 , denoted by Aut(H n ), is the semi-direct product of the group of translations by elements of H n with the group of permutations on the n coordinates. The group Aut(H n ) acts two-point homogeneously on H n , which means that the orbits of Aut(H n ) acting on H 2 n are characterized by the Hamming distance. In other words (x, y) ∼ Aut(Hn)

TABLE 1 .

 1 compares the best bound for A + 2 (n, r, m) (in italics) given by the combinatorial methods of Section 5 to the SDP bound. Again we have improvements in almost every instance. 2048 1 1024 1 309 2 256 1 128 1 64 1 4096 1 2048 1 541 2 512 1 256 1 113 2 64 1 7710 2 4096 1 956 2 956 2 512 1 188 2 128 1 64 1 13 3 7 3 5 3 14563 2 7710 4 1702 2 1702 2 963 4 314 2 256 1 128 1 52 3 11 3 6 3 4 3 27594 2 15420 4 3048 2 3048 2 1927 4 530 2 512 1 256 1 128 1 28 3 10 3 6 3 4 3 52428 2 52428 2 27594 4 5489 2 5489 2 3246 4 903 2 903 2 512 1 208 2 128 1 20 3 9 3 6 3 4 3 99864 2 99864 2 55188 4 9939 2 9939 2 5518 4 1552 2 1514 4 1024 1 338 2 256 1 128 1 16 3 8 3 6 3 4 3 Bounds on A 2 (n, d, m).

	n \m 4	5	6	7	8	9	10	11	12	13	14	15	16 17 18 19
	10 170	85	42	24	12	6
	186 2	128 1	6 4 1	32 1	16 1	6 3
	11 290	170	85	35	24	12	5
	341 2	256 1	128 1	61 2	32 1	12 3 5 3
	12 554	277	170	68	33	24	8	5
	630 2	512 1	256 1	103 2 64 1	32 1 10 3	5 3
	13 1042	521	266	130	64	32	16	8	5
	1170 2 1024 1 512 1	178 2 128 1 64 1 32 1	8 3	5 3
	14 2048	1024	512	257	128	64	32	16	8	5
	2184 2 22 3	8 3	5 3
	15 3616	2048	1024	414	256	128	43	32	16	6	5
	4096 2 16 3	7 3 5 3
	16 6963	3489	2048	766	382	256	83	41	32	10	6	5
	7710 2 17 13296	6696	3407	1395 708	359	151	80	41	20	10	6	4
	14563 2 18 26214	13107	6555	2559 1313 682	288	142	80	40	20	10 6	4
	27594 2 19 47337	26214	13107	4531 2431 1284 513	276	142	51	40	20 8	6 4
	20 91750	46113	26214	8133 4342 2373 1024 512	274	94	50	40 12 8 6 4
					m=2	3	4	5	6 7 8
				n=10	96	16
					102	22
				11 174	26	5
					186	36	11
				12 341	48	10
					341	61	17
				13 582	89	14	5
					630	103 27 10
				14 1109 161 22	5
					1170 178 43 14
				15 2085 283 36	9	5
					2184 309 69 22 9
				16 4096 526 64 13 5
					4096 541 113 33 13
				17 7235 848 123 18 5 4
					7710 956 188 52 19 8
				18 13926 1550 216 30 10 5
					14563 1702 314 81 27 12
				19 21883 2852 379 48 12 5 4
					27594 3048 530 129 41 16 8

TABLE 2 .

 2 Bounds on A + 2 (n, r, m).

⌋,⌊ n


IPNO T Junquera #

THE SPIRAL 2 PROJECT: CONSTRUCTION PROGRESS AND RECENT DEVELOPMENTS ON THE SC LINAC DRIVER

The construction of the new Spiral 2 facility has started in Caen (France) at the National Heavy Ions Accelerator Center (GANIL). The SPIRAL 2 project is based on a multi-beam Superconducting Linac Driver delivering 5 mA deuterons up to 40 MeV and 1 mA heavy ions up to 14.5 MeV/u. Different Radioactive Isotope Beams (RIB) production methods are foreseen: 1) by fission process (up to 10 14 fissions/s, induced in an UCx target by fast neutrons from a C converter bombarded by deuterons), 2) by fusion-evaporation residues or transfer products, using p, D, 3,4He and heavy ions beams in different targets. The high intensity beams delivered by the Superconducting LINAC Driver, will also open new perspectives for superheavy and very-heavy nuclei synthesis and spectroscopy. In addition to fundamental research in nuclear physics, the SPIRAL 2 facility will be also a high performance multidisciplinary tool for many other areas of science and technology: nuclear energy, material sciences, atomic physics and biology.

INTRODUCTION

After a Detailed Design Study phase (Nov. 2002 -Jan. 2005) [START_REF]SPIRAL 2 Project Scientific Objectives and Technical Reports[END_REF] and following the recommendations of international committees, the French Minister of Research took the decision in May 2005 to construct Spiral 2 at the GANIL in Caen, France. On the 1st of July 2005, the construction phase of SPIRAL2 was launched within a consortium formed by CNRS, CEA and the region of Basse-Normandie in collaboration with French, European and international institutions.

The importance of the availability of Radioactive Ion Beams (RIB) has been often underlined in the last years. The GANIL facility (Caen, France) is one of the major RNB and stable-ion facilities for nuclear physics, astrophysics and interdisciplinary research in Europe. Since the first beams delivered in 1983 the performances of the GANIL accelerator complex, was constantly improved with respect to the beam intensity, energy and available detection systems. Almost since the beginning of the experimental program, the facility delivered RIB produced "in-flight" at fragment separators. The new facilities related to the Spiral 2 project enlarge the range of accelerated ions by production of high intensity RIB of fission fragments. The new buildings: Driver Accelerator, RIB Production, and two new Experimental Halls, are illustrated in Fig. 1. A new experimental hall dedicated to high intensity stable beams and neutron experiments (AEL) and a hall for low energy RIB experiments. The Spiral 2 project proposes three different methods of production of radioactive beams [START_REF] Lewitowicz | Symposium on Nuclear Physics VI[END_REF] [3]:

1) fission of Uranium Carbide (UCx) target with a high neutron flux produced by a deuteron beam impinging on a Carbon converter, 2) direct interaction of deuterons in a UCx target, 3) interaction of heavy ion beam with different targets The radioactive atoms are then ionized and extracted from a target/ion-source system, and finally sent to either a low energy experimental hall, or driven towards a charge breeder and post-accelerated by the existing CIME cyclotron (Fig. 2)

The radioactive neutron rich beams will be mainly produced via the fission process induced by fast neutrons in a depleted UCx target (11g/cm 3 density), with the aim of 5.10 13 -10 14 fissions/s. For efficient diffusion and effusion of the radioactive atoms, the UCx target must be heated at temperatures above 2000°C.

The neutrons (about 14 MeV) are generated by the break-up of 40MeV deuterons in a thick Carbon target (Converter). For such a high fission rate, the final converter should sustain 200kW. Initial operation with a _________________ # , junquera@ipn.in2p3.fr • ECR for gaseous elements.

• FEBIAD (Forced Electron Beam Ion Arc Discharge). • Surface Ionization Source.

• Laser Ion Source. The RIB intensities in the mass range from A=60 to A=140 will be of the order of 10 6 to 10 11 particles/s (pps) surpassing by one or two order of magnitude any existing facilities in the world. For example, the intensities should reach 10 9 pps for 132 Sn and 10 10 pps for 92 Kr. A direct irradiation of the UCx target with beams of deuterons, 3,4 He, 6,7 Li, or 12 C can be used for higher excitation energy that could increase a higher production rate for specific nuclei.

Target -Ion Source Production Module

Two RIB production systems, using the high energy primary beams from the driver accelerator are presently considered [START_REF] Moscatello | Cyclotron Conference[END_REF] :

• A "Red" Production cave where the C converter, the UCx target and associate Ion Source are located. • A "Yellow" Production cave for lower intensity and less critical production systems.

The first Target-Ion Source (TIS) system under development is based on the fusion-evaporation reaction type, and is being designed in the IN2P3/CENBG laboratory. The main technical challenge concerns the thermal design of the target, which has to withstand very high power densities (several 100µA beams).

The high power TIS production module has been totally redesigned, taking into account the numerous constraints given by the radiological environment and the safety and contamination handling rules. The production module will be a totally remote-operated system, which will be disconnected, transported into the hot cell for maintenance and TIS replacement, and reconnected by a robot and manipulator system Fig. 3.

Radioactive Beam transport lines

A preliminary implementation scheme of the RIB transport lines is proposed in Fig. 4, and the detailed study has still to be started in close collaboration with the building technical design team.

The single charged beam (1+) line, going from the ion sources towards the identification stations, the low-energy experimental area DESIR or the charge booster (ECR ion source 1+ to n+) will include both electrostatic and magnetic components. The mechanical design of the lines is based on the use of independent modules that will be extracted with remotely operated tools from inaccessible places like the production caves, around the charge booster, and in any zone where radioactivity and/or contamination will become important. The n+ line transports the beam from the charge booster to an existing cyclotron CIME will be constructed with mechanical interfaces allowing the addition of remoteoperated valves and bellows in the future, when the RIB intensities reach the nominal values.

The production building, which will host the RIB production caves and the RIB transport lines will be a nuclear type building. The safety requirements imply a double confinement in the whole building that will host the UCx production cave as well as the transport lines for the radioactive beams composed of fission products. The whole vacuum system will be connected to the gas storage system, and a public enquiry will be launched to get the authorization to release gas from the storage facility, after a suitable period of radioactivity decrease.

SPIRAL2 DRIVER ACCELERATOR

Beams to be accelerated

In order to fulfil the physics requirements, the SPIRAL2 driver accelerator must be able to accelerate high-intensity beams of protons, deuterons, ions with A/q<3, and optionally ions with A/q<6. As indicated in table 1, a maximum beam power of 200kW is required for deuterons in CW mode. In order to transport and accelerate these intense beams with a minimum of losses, many beam dynamics calculations have been performed all along the machine, by using realistic source particle distributions, real 3D magnetic fields, compensation space charge effects in various situations, and also with systematic errors studies. The whole driver accelerator will be controlled using the EPICS software coupled with the TRACEWIN/PARTRAN code in order to implement the notion of a "virtual machine".

Injector-1

The Injector-1, dedicated to protons, deuterons and ions of q/A=1/3, is mainly composed of two ECR ion sources with their associated LEBT lines, a warm RFQ and the MEBT line connected to the LINAC. The 2.45GHz ECR source for deuterons is a "simplified" SILHI-like source (100mA CW, 95kV), initially developed by the CEA/DAPNIA laboratory for the IPHI project. In 2005, the Saclay source demonstrated its capability to produce a very stable 6.7mA D + CW beam with an rms normalised emittance less than 0.1ʌ.mm.mrad [START_REF] Gobin | Proceedings of LINAC04[END_REF]. It will also produce protons (5mA) and H 2 + , with a voltage of 20kV for protons and 40kV for D+ and H 2 + (β=0.0067). The ECR source for SPIRAL2 is now under construction.

The objective for SPIRAL2 is also to produce a large diversity of heavy ions with intensities up to 1mA: noble gases like Ar 12+ , and metallic ions like Cr, Ni and Ca are required. During the initial DDS phase, an R&D program was conducted to measure the performances of the PHOENIX ECR heavy ion source from the LPSC laboratory (Grenoble), and in particular to measure the Table 1: Beam Specifications transverse emittances obtained for 1mA of O 6+ at 60kV (0.22 π.mm.mrad rms norm.) In parallel, a new ECR source design has recently been proposed by the LPSC: the so called "A-Phoenix" source [START_REF] Th | Proceedings of the 12th International Conference on Ion Sources[END_REF]. It is a compact hybrid ECRIS with high-temperature superconducting (HTS) coils (3T axial magnetic field) and a permanentmagnet design (2T hexapolar field). With a 28-GHz frequency, the goal is to approach 1-mA intensity for an Ar 12+ ion beam. The components of the source are now assembled and the first plasma tests are being performed presently (Fig. 5). Both light and heavy-ion ECR sources have their own chromatic transfer line able to separate the species extracted from the source and select the desired purified beam. These lines are connected to a common LEBT which contains a slow chopper, diagnostics and slits to redefine the emittance before connection to the RFQ. The magnetic elements are being manufactured, and their magnetic measurements will start by the end of 2007.

Developed by the CEA/DAPNIA team, the RFQ [START_REF] Ferdinand | Proceedings of EPAC 2006[END_REF] is a 4-vanes, 5-meter warm copper cavity (88Mhz) performs an adiabatic bunching of the continuous beam, and an acceleration at 0.75Mev/u (β=0.04). It is specially designed to give a transmission of better than 99%. A 1meter segment prototype was built during the APD phase and tested at Grenoble and Catania in order to check the feasibility. The construction of the RFQ is now starting and will take about two years. The RFQ cavity requires some 150kW and will be driven by four 50kW amplifiers equipped with circulators.

The MEBT line takes care of the beam transmission and matching between the RFQ exit and the LINAC entrance. Its function is also to allow future connection of the injector-2, and to operate a very clean fast chopping of the beam bunches for various AEL experiments. This explains the length of this part (8m) and the necessity to use three rebunchers in order to match the beam longitudinally. Most of the devices are completely designed and will be orded very soon. One exception is the challenging fast chopper and its associated 7.5kW beam stopper, which are under detailed study.

Due to delays concerning the construction of the accelerator building, the whole Injector-1, in the configuration illustrated in the Fig. 6, will be installed at Saclay and tested with beam, before being transported to GANIL. In addition, a specific medium-energy diagnostic plate is under construction at the CNRS-IHC laboratory in Strasbourg, in order to prepare the beam commissioning of the RFQ and of the MEBT during this first phase, and to test various diagnostic devices on line. Associated with a phase length monitor, the first rebuncher will be used to determine the longitudinal emittance of the RFQ.

Injector-2

The optional Injector-2 will be dedicated to q/A=1/6 heavy ions connected to the LINAC via the MEBT line. This injector is under detailed study in order to prepare enough space in the accelerator building for the future. Although it will give only half the energy compared to Injector-1, there is much interest in having higher beam intensity for very heavy ions. A design study is being conducted in the frame of a MoU with the Argonne laboratory.

Superconducting Linac

The LINAC accelerator is based on superconducting independently-phased resonators. It is composed of 2 families of quarter-wave resonators (QWR) at 88MHz, (Fig. 7) developed respectively by the CEA/DAPNIA and the IN2P3/IPNO teams: 12 resonators with β 0 =0.07 (1 cavity /cryomodule), and 16 resonators at β 0 =0.12 (2 cavities/cryomodule). The transverse focusing is ensured by means of warm quadrupole doublets located between each cryomodule. Additional dipolar coils are installed into the Q-pole in order to compensate the steering effect of QWR cavities and eventually adjust the optimum beam position. These warm sections include also beam diagnostic boxes implementing different types of sensors (preliminary specifications are: 20 BPM, 10 TOF and 4 phase length measurement devices) and 20 vacuum pumps. The total length of the SC Linac is 30 m.

The maximum operational accelerating gradient of the QWR cavities is Eacc=Vacc/ȕȜ=6.5MV/m. To acceleration of a deuteron beam of 5 mA at a maximum energy of 40 MeV with minimum losses, leads to an optimization of the operational gradients along the Linac: the β_0.07 cavities between 1.3 and 6.5 MV/m, and the β_0.12 cavities between 5.0 and 6.5 MV/m. The calculated transverse and longitudinal emittance are displayed in the Fig 8 . The energy gain along the Linac is displayed in Fig. 9. The beam optics simulations were performed using the TRACEWIN and PARTRAN codes (CEA/DAPNIA). The space charge effects were studied using the 3D-PICNIC routine with 100 000 particles [START_REF] Duperrier | [END_REF] Figure 7: The SPIRAL2 superconducting cryomodules (top: β=0.07, bottom: β=0.12)

In a first attempt, multi-particle calculations were performed without errors (alignment errors and component dimensions and fields errors). An increase of the QWR electrode diameter has been adopted: 38 mm for β_0.07 and 44 mm for β_0.12. The expected input emittance at the SC Linac was also limited introducing slits after the RFQ cavity, intercepting 130 W for a D + 5 mA beam). With these precautions a theoretical total loss of < 1 W in the SC linac was obtained. The worst case is obtained at low energy operation range. For example: a 2 MeV proton beam and intensity of 5 mA gives a theoretical level of losses < 10 W for all the SC Linac .

HEBT lines and AEL experimental hall

The high energy beam transfer lines (HEBT) are divided into three main parts (Fig. 10): -HEBT1: A straight beam line with a beam dump is needed for beam commissioning, eventual tuning and beam studies. The maximum power accepted by the beam dump is not precisely defined yet; it will depend on the nuclear safety licensing requirements for handling and maintenance and could range between 50 and 200 KW.

-HEBT2: This transfer line will transport light-and heavy-ion beams towards the two RIB production areas, located in a separate building. (see next section). -HEBT3: These lines will deliver light and heavy ions to the AEL experimental hall, installed in the same building as the driver accelerator. Three large experimental rooms are presently being studied: a) for neutron experiments where a neutron time-of-flight facility will be installed, b) for high-intensity stable ions experiments where a spectrometer with high mass selectivity will be installed, and c) an inter-disciplinary experimental area for atomic physics and material studies. Several rebunchers are installed in this line in order to reach the bunch length requirements at the target level (<1ns). Various targets will be used, in particular actinides, which necessitate special safety procedures for manipulation.

PROGRESS ON THE SUPERCONDUCTING LINAC CONSTRUCTION

Two prototypes QWR1 and QWR2 were constructed during the initial R&D phase. Installed in vertical testcryostats, both resonators reached very high accelerating gradients, between 9 and 11MV/m. [START_REF] Devanz | 12 th SRF Workshop 2005[END_REF]. Three new cavities: 1 QWR 0.07 and 2 QWR 0.12 have been fabricated in the last period, incorporating all the needed ancillary components (helium tank, tuning system anchoring, etc). The first tests with the QWR 0.07 show low Q O value due to extra losses not yet identified, but confirm excellent performance in peak electric field (11 MV/m). One of the new QWR 0.12 was tested and reached an E acc of 9 MV/m. In the second QWR 0.12 a leakage was observed and the investigations on the causes are under way.

The three best results are presented in the Fig. 11 More details on the results of these measurements are presented in this Workshop [START_REF] Olry | this Workshop[END_REF].

The RF power couplers, developed by IN2P3/LPSC (Grenoble), have to provide 12kW CW power to each cavity. Two coupler prototypes, using either disk or cylinder ceramic window geometries, were also constructed. Both prototypes have reached CW power levels greater than 30kW, giving a good margin for the nominal operation power levels. Five new couplers were recently constructed, three of them will be installed in the two first cryomodules. More details on RF couplers are given in this Workshop [START_REF] Gomez-Martinez | this Workshop[END_REF] Two cryomodules (one of each beta value) have been designed and constructed and its test will allow the launch of the series units construction. Both cryomodules integrate all the needed components and are completely equipped to be eventually installed in the Driver Accelerator. All the components for the first cryomodules are now available: the β 0.12 Cryomodule is presently assembled and final tests have started, the integration of the β 0.07 Cryomodule components is planned for the end of this year (Fig. 12 a,b). The cryomodules tests include the assessment of two major design aspects: 1) cryogenic operation and static losses measurements, and 2) complete RF tests with a final check at full RF power. This test phase will end in December 2007, in order to launch the cryomodules series production in the period 2008-2009.

Figure 12(a) : The first β 0.07 Cryomodule Solid-state RF amplifiers will be used, and the two first prototypes of 10 and 20 kW have recently been tested at GANIL [START_REF] Digiacomo | this Workshop MO[END_REF]. These amplifiers are based on new power transistors for FM applications implemented in water cooled boards, allowing the use of only four 3kW racks for each 10kW cabinet. Power tests on the cryomodules will help to choose the best compromise between the required gain linearity and the working class operating point. An operating efficiency of around 55% is expected.

A new digital low-level RF system is under development and will ensure 10 -2 and 1° in amplitude and phase stability respectively. The CEA/DAPNIA team in charge of the LLRF is studying a standard card which will be used to control all types of cavities along the accelerator (RFQ, rebunchers and SC LINAC resonators).

SPIRAL 2 CONSTRUCTION MILESTONES

The reference project for the Driver Accelerator was decided by October/November 2006, the RIB production building and its main components must be defined at the end of 2007. Both the detailed study of the buildings and the licensing procedures conducted by the nuclear safety regulation authorities, condition the reference planning and the final steps to reach the foreseen performances. The regulation authorities have recently agreed (July 2007) on a roadmap and an associated planning for the construction and initial operation of the facility. The construction of the SPIRAL 2 buildings (driver accelerator and production areas) at the GANIL site will start in 2009. First commissioning of beams delivered by the Driver Accelerator should take place at the end of 2011 (Fig. 13). Full intensity stable beams should be available for experiments in the 1 st Qr. of 2012. Availability of radioactive beams is presently being considered at the end of 2012, with several phases, corresponding to a progressive increase of the power on the production target.

  NuPECC (Nuclear Physics European Collaboration Committee) and ESFRI (European Strategy Forum on Research Infrastructures) established roadmaps and recommendations for the next generation of facilities in Europe. FAIR in GSI laboratory in Darmstadt (Germany) and Spiral 2 in GANIL laboratory are among the selected projects. Both projects are complementary and are based on two different RIB production methods: FAIR is based on In-Flight Fragmentation techniques, while Spiral 2 uses the Isotope Separation on Line (ISOL) techniques.

Figure 1 :

 1 Figure 1 : Spiral 2 new buildings (blue) and existing facilities at the GANIL site

  Reports IV Carbon converter at 50 KW is presently considered. The converter study takes benefit of recent development and collaborations with INFN-LNL and BNPI-Novosibirsk laboratories.

Figure 2 :

 2 Figure 2 : RIB Production technique in Spiral 2 Different types of Ion Sources (single charge state) are presently been studied :• ECR for gaseous elements.• FEBIAD (Forced Electron Beam Ion Arc Discharge). • Surface Ionization Source.• Laser Ion Source. The RIB intensities in the mass range from A=60 to A=140 will be of the order of 10 6 to 10 11 particles/s (pps) surpassing by one or two order of magnitude any existing facilities in the world. For example, the intensities should reach 10 9 pps for 132 Sn and 10 10 pps for 92 Kr. A direct irradiation of the UCx target with beams of deuterons,3,4 He,6,7 Li, or12 C can be used for higher excitation energy that could increase a higher production rate for specific nuclei.

Figure 3 :

 3 Figure 3: Spiral 2 UCx production module

Figure 4 :

 4 Figure 4: Layout of the RIB production systems and beam transfer lines

Figure 5 :

 5 Figure 5 : The new heavy ions ECR source (A-Phoenix) in test at LPSC Grenoble

Figure 6 :

 6 Figure 6: View of the Spiral 2 Injector (phase 1)

Figure 8 :Figure 9 :

 89 Figure 8 : Transverse and longitudinal emmittances in the Spiral 2 Driver Accelerator (d+, 40 MeV, 5 mA) TraceWin -CEA/DSM/DAPNIA/SACM

Figure 10 :

 10 Figure 10: The High Energy beam lines

Figure 11 :

 11 Figure 11: QWR performances of the Spiral 2 prototypes

Figure 12 (

 12 Figure 12(b) : The first β 0.12 Cryomodule

Figure 13 :

 13 Figure 13 : Spiral 2 planning (October 2007)

Proceedings of SRF2007, Peking Univ., Beijing, China

ACKNOWLEDGMENTS

Thanks to the SPIRAL 2 project group for their help and specific contributions, in particular: Marcel Jacquemet (Project Leader), Marek Lewitowicz (Scientific Leader), M.H. Moscatello (RIB Leader), J.M. Lagniel (Buildings Leader), R. Ferdinand, P. Bertrand, M. DiGiacomo, C. Van Hille, P. Ausset, J.L. Biarrotte, R. Duperrier, D. Uriot, H. Saugnac, and P. Bosland.