Frédéric Bayart

F R Éd

Éric Bayart

MULTIPLE SUMMING MAPS: COORDINATEWISE SUMMABILITY, INCLUSION THEOREMS AND p-SIDON SETS

Keywords: coordinatewise summability, inclusion theorems and p-Sidon sets . 2010 Mathematics Subject Classification. 46G25, 47H60 Multiple summing operators, multilinear mappings, Sidon sets

1. Introduction 1.1. Multiple and coordinatewise summability. Let T : X → Y be linear where X and Y are Banach spaces. For r, p ≥ 1, we say that T is (r, p)-summing if there exists a constant C > 0 such that, for any sequence

x = (x i ) i∈N ⊂ X N , +∞ i=1 T (x i ) r 1 r ≤ Cw p (x)
where the weak ℓ p -norm of x is defined by

w p (x) = sup x * ≤1 +∞ i=1 |x * (x i )| p 1 p .
The theory of (r, p)-summing operators is very rich and very important in Banach space theory (see [START_REF] Diestel | Absolutely summing operators[END_REF] for details). In recent years, the interest moves to multilinear maps. We start now from m ≥ 1, X 1 , . . . , X m , Y Banach spaces and T : X 1 × • • • × X m → Y mlinear. Following [START_REF] Bombal | Multilinear extensions of Grothendieck's theorem[END_REF] and [START_REF] Matos | Fully absolutely summing and Hilbert-Schmidt multilinear mappings[END_REF], for r ≥ 1 and p = (p 1 , . . . , p m ) ∈ [1, +∞) m , we say that T is multiple (r, p)-summing if there exists a constant C > 0 such that for all sequences x(j) ⊂ X N j , 1 ≤ j ≤ m,

i∈N m T (x i ) r 1 r ≤ Cw p 1 (x(1)) • • • w pm (x(m))
where T (x i ) stands for T (x i 1 (1), . . . , x im (m)). The least constant C for which the inequality holds is denoted by π mult r,p (T ). When all the p i 's are equal to the same p, we will simply say that T is multiple (r, p)-summing. Even if the notion of multiple summing mappings was formalized only recently, its roots go back to an inequality of Bohnenblust and Hille appeared in 1931 (see [START_REF] Bohnenblust | On the absolute convergence of Dirichlet series[END_REF]). Using the reformulation of [START_REF] Pérez-García | Multiple summing operators on C(K) spaces[END_REF], this inequality says that every m-linear form T :

X 1 × • • • × X m → K
is multiple (2m/(m + 1), 1)-summing. Observe that the restriction of T to each X k (fixing the other coordinates) is, as all linear forms, (1, 1)-summing. This motivates the authors of [START_REF] Defant | Coordinatewise multiple summing operators in Banach spaces[END_REF] to study the following question: let T : X 1 × • • • × X m → Y be m-linear and assume that the restriction of T to each X k is (r, p)-summing (we will say that T is separately summing). Can we say something about the multiple (s, t)-summability of T ? The authors of [START_REF] Defant | Coordinatewise multiple summing operators in Banach spaces[END_REF] get a successful answer in the case p = t = 1 (their results were later improved and simplified in [START_REF] Popa | Blei's inequality and coordinatewise multiple summing operators[END_REF] and in [START_REF] Albuquerque | Absolutely summing multilinear operators via interpolation[END_REF]). Precisely, they showed the following result:

Theorem (Defant, Popa, Schwarting). Let T : X 1 × • • • × X m → Y be m-linear with Y a cotype q space. Let r ∈ [1, q] and assume that T is separately (r, 1)-summing. Then T is multiple (s, 1)-summing, with

1 s = m -1 mq + 1 mr .
We intend in this paper to fill out the picture by allowing the full range of possible values for t and p, namely t ≥ p ≥ 1. The following result is a more readable corollary of our main theorems, Theorems 2.1, 2.2, 2.3, 7.1 (p * will denote the conjugate exponent of p).

Theorem 1.1. Let T : X 1 × • • • × X m → Y be m-linear with Y a cotype q space. Assume that T is separately (r, p)-summing and let t ≥ p.

• If 1 r + 1 p * -m t * > 1
q , then T is multiple (s, t)-summing with

1 s = m -1 mq + 1 mr + 1 mp * - 1 t * . • If 0 < 1 r + 1 p * -m t * ≤ 1
q , then T is multiple (s, t)-summing with

1 s = 1 r + 1 p * - m t * .
When 1 ≤ p = t ≤ 2 and q = 2, the above values of s are optimal.

1.2. Inclusion theorems. Our methods have other interesting consequences. A basic result in the theory of (r, p)-summing operators is the inclusion theorem: if T ∈ L(X, Y ) is (r, p)-summing, then it is also (s, q)-summing provided s ≥ r and 1 s -1 q ≤ 1 r -1 p . The proof of this result follows from a simple application of Hölder's inequality. In the multilinear case, the situation seems more involved. Using probability in a clever way, Pérez-García in [START_REF] Pérez-García | The inclusion theorem for multiple summing operators[END_REF]

succeeded to prove that if T ∈ L(X 1 , . . . , X m ; Y ) is (p, p)- summing, p ∈ [1, 2)
, then it is also (q, q)-summing for q ∈ [p, 2). However, this result is not very helpful to provide inclusion theorems for (r, p)-summing multilinear maps as those coming from the Bohnenblust-Hille inequality. The next result seems to be a natural multilinear analogue to the linear inclusion theorem. It already appeared in [START_REF] Pellegrino | Regularity principle in sequence spaces and applications[END_REF]Proposition 3.4] in the particular case where all the p i are equal, with a different proof. Its optimality will be discussed in Theorem 7.2.

Theorem 1.2. Let T : X 1 ו • •×X m → Y be m-linear, let r, s ∈ [1, +∞), p, q ∈ [1, +∞) m .
Assume that T is multiple (r, p)-summing, that q k ≥ p k for all k = 1, . . . , m and that 1 r -m j=1 1

p j + m j=1 1 q j > 0. Then T is multiple (s, q)-summing, with 1 s - m j=1 1 q j = 1 r - m j=1 1 p j .
1.3. Harmonic analysis. A second application occurs in harmonic analysis. Let G be a compact abelian group with dual group

Γ. A subset Λ of Γ is called p-Sidon (1 ≤ p < 2) if there is a constant κ > 0 such that each f ∈ C(G) with f supported on Λ satisfies f ℓp ≤ κ f ∞ .
It is a classical result of Edwards and Ross [START_REF] Edwards | p-Sidon sets[END_REF] (resp. Johnson and Woodward [START_REF] Johnson | On p-Sidon sets[END_REF]) that the direct product of two 1-Sidon sets (resp. m 1-Sidon sets) is 4/3-Sidon (resp. 2m/(m + 1)-Sidon). We generalize this to the product of p-Sidon sets.

We need an extra assumption. A subset Λ of Γ is called a Λ(p)-set, p ≥ 1, if for one q ∈ [1, p) (equivalently, for all q ∈ [1, p)), there exists κ > 0 such that, for all f ∈ C(G) with f supported on Λ,

f L p (G) ≤ κ f L q (G) . Theorem 1.3. Let G 1 , . . . , G m , m ≥ 2, be compact abelian groups with respective dual groups Γ 1 , . . . , Γ m . For 1 ≤ j ≤ m, let Λ j ⊂ Γ j be a p j -Sidon and Λ(2)-set. Then Λ 1 × • • • × Λ m is a p-Sidon set in Γ 1 × • • • × Γ m for 1 p = 1 2 + 1 2R and R = m k=1 p k 2 -p k .
Moreover, this value of p is optimal.

It is well known that any 1-Sidon set is automatically a Λ(p)-set for all p ≥ 1. It is not known whether all p-Sidon sets are Λ(2) or not. We also get an analogous result for another natural generalization of 1-Sidon sets, the so-called p-Rider sets, without any extra assumption.

Organization of the paper. Section 2 is devoted to the introduction of some notations and definitions. We then give the statements of our main theorems (Theorems 2.1, 2.2 and 2.3). These statements may look technical but we derive immediately from them several striking corollaries. We emphasize particularly Corollary 2.6 whose proof needs the three main results.

In Section 3, we prove several auxiliary results. They seem interesting for themselves; for instance, they are at the heart of the proof of Theorems 1.2 and 1.3. We apply these auxiliary results in the three next sections to the problems we have in mind: coordinatewise summability in Section 4, inclusion theorems in Section 5, and harmonic analysis in Section 6. Finally, in Section 7, we discuss the optimality of our results.

Preliminaries: notations and statements of the results

2.1. General statements. We shall use the terminology and notations introduced in [START_REF] Defant | Coordinatewise multiple summing operators in Banach spaces[END_REF] and [START_REF] Popa | Blei's inequality and coordinatewise multiple summing operators[END_REF]. For Banach spaces X 1 , . . . , X m , m ≥ 2, and a proper subset C of {1, . . . , m}, we write X C = j∈C X j and identify in the obvious way

X 1 × • • • × X m with X C × X C where C denotes the complement of C in {1, . . . , m}. With this identification, if y ∈ X C and z ∈ X C , then x = (y, z) ∈ X 1 × • • • × X m . For x ∈ X 1 × • • • × X m ,
we shall also denote by x(C) its projection on X C , so that we may write x = (x(C), x(C)). We take the norm on finite products of Banach spaces to be the maximum of the component norms; hence the identification is isometric. We shall abbreviate x({k}) by x(k), namely the k-th

coordinate of x ∈ X 1 × • • • × X m . If T : X 1 × • • • × X m → Y is m-linear and z ∈ X C , the map T C (z) defined on X C by T C (z)(x) = T (x, z
) is clearly |C|-linear. For r, p ≥ 1, we say that T is coordinatewise multiple (r, p)-summing in the coordinates of C provided T C (z) is multiple (r, p)-summing for all z ∈ C. In that case, we shall denote

T C CW (r,p) = sup π mult r,p (T C (z)); z X C ≤ 1 .
Our first result deals with (r, p)-multiple summing maps where r does not exceed the cotype of the target space.

Theorem 2.1. Let m ≥ 2, let {1, . . . , m} be the disjoint union of n ≥ 2 non-empty subsets C 1 , . . . , C n , let Y be a Banach space with cotype q and let r 1 , . . . , r n ∈ [1, q), p 1 , . . . , p n ∈ [1, +∞). Define

1 γ k = 1 r k - j =k |C j | p * j × 1 -q r k -q|C k | p * k 1 -q r j - q|C j | p * j , k = 1, . . . , n 1 γ k,l = 1 r k - j =k,l |C j | p * j × 1 -q r k -q|C k | p * k 1 -q r j - q|C j | p * j , k = l ∈ {1, . . . , n} R = n k=1 γ k q -γ k s = qR 1 + R q j = p k provided j ∈ C k , j = 1, . . . , m q = (q 1 , . . . , q m ).
Let us also assume that, for all k = l ∈ {1, . . . , n}, γ k > 0, 0 < γ k,l ≤ q and

|C l |γ k,l p * l ≤ 1. Then all m-linear maps T : X 1 × • • • × X m → Y which are (r k , p k )-
summing in the coordinates of C k for each k = 1, . . . , n are multiple (s, q)-summing.

Our second result deals with (r, p)-multiple summing maps with r exceeding the cotype of the target space, but when we start from (r k , p k )-coordinatewise summability with r k ≤ q. Theorem 2.2. Let m ≥ 2, let {1, . . . , m} be the disjoint union of n ≥ 2 non-empty subsets C 1 , . . . , C n , let Y be a Banach space with cotype q and let r 1 , . . . , r n ∈ [1, q), p 1 , . . . , p n ∈ [1, +∞). Define

1 γ k,J = 1 r k - j / ∈J∪{k} |C j | p * j × 1 -q r k -q|C k | p * k 1 -q r j - q|C j | p * j
, k = 1, . . . , n, J ⊂ {1, . . . , n}\{k} q j = p k provided j ∈ C k , j = 1, . . . , m q = (q 1 , . . . , q m ).

Assume that there exists J ⊂ {1, . . . , n} such that (1) there exists k 0 / ∈ J with γ k 0 ,J ≥ q; (2) For any k, l ∈ {1, . . . , n}\J, k = l, γ k,J∪{l} ∈ (0, q];

(3) For any k, l ∈ {1, . . . , n}\J, k = l,

|C l |γ k,J ∪{l} p * l ≤ 1.
We finally set

1 s = 1 γ k 0 ,J - j∈J |C j | p * j
and assume that s > 0. Then all m-linear maps T :

X 1 × • • • × X m → Y which are (r k , p k )-
summing in the coordinates of C k for each k = 1, . . . , n are multiple (s, q)-summing.

Our third result solves the case when one r k is greater than q.

Theorem 2.3. Let m ≥ 2, let {1, . . . , m} be the disjoint union of n ≥ 2 non-empty subsets C 1 , . . . , C n , let Y be a Banach space with cotype q and let r 1 , . . . , r n ∈ [1, +∞), p 1 , . . . , p n ∈ [1, +∞). Assume that there exists k ∈ {1, . . . , n} such that r k ≥ q. We set

1 s = 1 r k - j =k |C j | p * j
and assume that s > 0. Then all m-linear maps T :

X 1 × • • • × X m → Y which are (r k , p k )-
summing in the coordinates of C k for each k = 1, . . . , n are multiple (s, q)-summing where q is defined by q j = p k for j ∈ C k , j = 1, . . . , m.

2.2.

Corollaries. The statement of Theorems 2.1, 2.2 and 2.3 may look complicated; this is due to their generality. In particular cases, they look nicer; they cover and extend many known statements. We begin by assuming that p k = 1 for all k ∈ {1, . . . , n}.

Corollary 2.4. Let m ≥ 2, let {1, . . . , m} be the disjoint union of n ≥ 2 non-empty open subsets C 1 , . . . , C n , let Y be a Banach space with cotype q and let r 1 , . . . ,

r n ∈ [1, q). Set R = n k=1 r k q -r k , s = qR 1 + R .
Then all m-linear maps T :

X 1 × • • • × X m → Y which are (r k , 1)-summing in the coordi- nates of C k for each k = 1, . . . , n are multiple (s, 1)-summing.
This corollary is the main result of [START_REF] Popa | Blei's inequality and coordinatewise multiple summing operators[END_REF] which was itself an improved version of the main theorem of [START_REF] Defant | Coordinatewise multiple summing operators in Banach spaces[END_REF].

Proof. We may apply Theorem 2.1. Its assumptions are satisfied because p * k = +∞.

Remark 2.5. Observe that there is no restriction to assume r k < q. Indeed, any linear map with value in a cotype q space is always (q, 1)-summing and we may apply Theorem 2.3 to deduce that any multilinear map with value in a cotype q space is always multiple (q, 1)-summing, a result already observed in [START_REF] Bombal | Multilinear extensions of Grothendieck's theorem[END_REF]Theorem 3.2] Our second more appealing result happens when we start from a (r k , p k )-separately summing map (namely

|C k | = 1 for all k) with 1 r k -1 p k = θ ∈ (-∞, 0].
In view of the inclusion theorem, this last assumption is not surprising. It implies that all the quotients

1 -q r k -q|C k | p * k 1 -q r j - q|C j | p * j are equal to 1. Corollary 2.6. Let T : X 1 × • • • × X m → Y with Y a cotype q space and p ∈ [1, +∞) m . Assume that T is (r k , p k )-summing in the k-th coordinate and that there exists θ < 0 such that 1 r k -1 p k = θ for all k. Set 1 γ = 1 + θ - m k=1 1 p * k .
(1) If γ ∈ (0, q), then T is multiple (s, p)-summing with

1 s = m -1 mq + 1 γm .
(2) If γ ≥ q, then T is multiple (γ, p)-summing.

Proof. Suppose first that γ ∈ (0, q). Then with the notations of Theorem 2.1,

γ k = γ for all k and 1 γ k,l = 1 γ + 1 p * l for all k = l. This implies that r k < q and 1 γ k,l ≥ 1 p * l .
Hence the assumptions of Theorem 2.1 are satisfied and this leads to (1). To prove (2), we suppose first that r k < q for all k. Let J be a maximal set of {1, . . . , n} such that there exists k 0 / ∈ J with γ k 0 ,J ≥ q. Such a set does exist since γ 1,∅ = γ ≥ q and γ k,{1,...,n}\{k} = r k < q for all k. This couple J and k 0 being fixed, we may observe that for all k, l ∈ {1, . . . , n}\J, k = l, γ k,J∪{l} < q (otherwise J would not be maximal) and

1 γ k,J∪{l} = 1 γ k,J + 1 p * l ≥ 1 γ + 1 p * l ≥ 1 p * l .
Thus we may apply Theorem 2.2. Finally, if r k ≥ q for some k, then the result follows from Theorem 2.3.

In turn, this last corollary implies several interesting results. First, half of Theorem 1.1 may be deduced easily from it.

Proof of Theorem 1.1 (without optimality). Assume first that t = p. Then the conclusion follows directly from Corollary 2.6 with r k = r and p k = p for all k. Suppose now that t > p. Then, by the inclusion theorem for linear maps, T is separately (ρ, t)-summing for

1 ρ = 1 r + 1 t -1 p .
We conclude again by an application of Corollary 2.6 with r k = ρ and

p k = t for all k. Corollary 2.7. Let T : X 1 × • • • × X m → C be m-linear and let p = (p 1 , . . . , p m ) ∈ [1, +∞) m . Set 1 γ = 1 - m k=1 1 p * k . (1) If γ ∈ (0, 2) then T is multiple (s, p)-summing with 1 s = m -1 2m + 1 mγ .
(

) If γ ≥ 2, then T is multiple (γ, p)-summing. 2
Proof. This follows immediately from Corollary 2.6 since any linear form is (p, p)-summing.

Observe finally that Theorem 1.1 extends also Theorem 1.2 of [START_REF] Dimant | Summation of coefficients of polynomials on ℓp spaces[END_REF].

Notations. Part of the notations we shall use was already introduced at the beginning of this section. We shall also denote by (e i ) i∈N the standard basis of ℓ p and e i , i ∈ N m , will mean (e i 1 (1), . . . , e im (m)) where (e i (j)) i is a copy of (e i ) i . For u ∈ m j=1 ℓ p j , i ∈ N m and α ∈ R, u i will stand for

u i 1 (1) × • • • × u im (m) and u α i for u i 1 (1) α × • • • × u im (m) α . As indicated above, if (a i ) i∈N m
is a sequence indexed by N m and C ⊂ {1, . . . , m}, we shall identify i with j, k with j = i(C), k = i( C) so that we shall write a i = a j,k .

Useful lemmas

3.1. Coefficients of non-negative m-linear forms. We shall need the following nonnegative version of a theorem of Praciano-Pereira [START_REF] Praciano-Pereira | On bounded multilinear forms on a class of l p spaces[END_REF]. It already appears in [START_REF] Lacruz | Hardy-Littlewood inequalities for norms of positive operators on sequence spaces[END_REF] for bilinear forms.

Proposition 3.1. Let m ≥ 1, 1 ≤ p 1 , . . . , p m ≤ +∞ and A : ℓ p 1 × • • • × ℓ pm → C be a non-negative m-linear form. Then i∈N m A(e i ) ρ 1/ρ ≤ A provided ρ -1 = 1 -m j=1 p -1 j > 0.
Here, non-negative simply means that for any i ∈ N m , A(e i ) ≥ 0.

Proof. We shall give a proof by induction on m. Our main tool is the following factorization result of Schep [26] which extends to multilinear maps a result of Maurey [START_REF] Maurey | Théorèmes de factorisation pour les opérateurs linéaires à valeurs dans les espaces L p[END_REF].

Lemma 3.2. Let B : ℓ p 1 × • • • × ℓ pm → ℓ q be a non-negative m-linear map such that r ≥ max(q, 1) with r -1 = p -1 1 + • • • + p -1 m .
Then there exist a non-negative φ ∈ ℓ s with s -1 = q -1 -r -1 and a non-negative m-linear map C :

ℓ p 1 × • • • × ℓ pm → ℓ r such that B = M φ C
where M φ is the operator of multiplication by φ. Moreover, B = inf φ s C where the infimum is taken over all possible factorizations.

Let us come back to the proof of Proposition 3.1. The result is clear for m = 1 (it does not require positivity) and let us assume that it is true for m-linear forms, m ≥ 1. Let

A : ℓ p 1 × • • • × ℓ p m+1 → C be a non-negative (m + 1)-linear form. It defines a bounded m-linear map B : ℓ p 1 × • • • × ℓ pm → ℓ p * m+1 by e j , B(x) = A(x, e j ). By Lemma 3.2, B factors through ℓ r , r -1 = p -1 1 + • • • + p -1 m ; namely we may write B = M φ C with φ ∈ ℓ s , s -1 = 1 -p -1 1 -• • • -p -1 m+1 and C : ℓ p 1 × • • • × ℓ pm → ℓ r
a non-negative continuous m-linear map. Thus, writing a i,j = A(e i , e j ) = e j , B(e i ) , c i,j = e j , C(e i ) , i ∈ N m , j ∈ N, we get

  j∈N i∈N m a s i,j   1/s =   j∈N φ s j i∈N m c s i,j   1/s ≤ φ s sup j∈N i∈N m c s i,j 1/s
.

Define now C j : ℓ p 1 × • • • × ℓ pm → C by C j (x) = e j , C(x)
. Then C j is a bounded nonnegative m-linear form with C j ≤ C , and by the induction hypothesis, since s ≥ t where

t -1 = 1 -p -1 1 -• • • -p -1 m , we have i∈N m c s i,j 1/s ≤ C .
The result now follows by taking the infimum over all possible factorizations of A.

Remark 3.3. The example of A(x(1), . . . , x(m)) = n i=1 x i (1) • • • x i (m)
shows that the constant ρ in Proposition 3.1 is optimal.

3.2. An abstract Hardy-Littlewood method. To prove their bilinear inequality on ℓ p -spaces in [START_REF] Hardy | Bilinear forms bounded in space [p, q][END_REF], Hardy and Littlewood have introduced a methode to go from ℓ p to c 0 and back again. This was performed several times later (for instance in [START_REF] Praciano-Pereira | On bounded multilinear forms on a class of l p spaces[END_REF], [START_REF] Albuquerque | Sharp generalizations of the multilinear Bohnenblust-Hille inequality[END_REF] or [START_REF] Dimant | Summation of coefficients of polynomials on ℓp spaces[END_REF]). We shall develop here an abstract version of this machinery, first in the bilinear case and then in the m-linear one.

Lemma 3.4. Let m 1 , m 2 ≥ 1, p 1 , p 2 , q ∈ [1, +∞), (a i,j ) i∈N m 1 , j∈N m 2
a sequence of nonnegative real numbers. Assume that there exists κ > 0 and 0 < α, β ≤ q such that

• for all u ∈ m 1 j=1 B ℓp 1 ,   j∈N m 2 i∈N m 1 u q i a q i,j α/q   1/α ≤ κ; • for all v ∈ m 2 j=1 B ℓp 2 ,    i∈N m 1   j∈N m 2 v q j a q i,j   β/q    1/β ≤ κ. Then   j∈N m 2 i∈N m 1 a q i,j γ/q   1/γ ≤ κ where 1 γ = 1 α - m 1 p 1 1 -q α -m 2 q p 2 1 -q β -m 1 q p 1 provided γ > 0, m 1 α p 1 ≤ 1 and m 2 β p 2 ≤ 1.
Proof. For j ∈ N m 2 , we denote S j = i∈N m 1 a q i,j

1/q
. Let also θ > 0 with m 2 /θ < 1 and let 1/ρ = 1 -m 2 /θ. For any γ ∈ R, we may write

j S γ j = j S γ ρ ρ j ≤   sup w∈ m 2 j=1 B ℓ θ j w j S γ ρ j   ρ
where we have used Proposition 3.1. We then set γ ′ = γ/ρ and we write for

w ∈ m 2 j=1 B ℓ θ , j w j S γ ′ j = j w j S γ ′ -q j i a q i,j = i j w j a q i,j S q-γ ′ j ≤ i   j a q i,j S (q-γ ′ )s j   1/s   j w s * j a q i,j   1/s * ≤    i   j a q i,j S (q-γ ′ )s j   t/s    1/t    i   j w s * j a q i,j   t * /s *    1/t *
where (s, s * ) and (t, t * ) are two couples of conjugate exponents such that t * /s * = β/q. Now, w s * /q belongs to m 2 j=1 B ℓ θq/s * . Thus, if we can set θ = p 2 s * q , then we can deduce that

j w j S γ ′ j ≤ κ 1/t *    i   j a q i,j S (q-γ ′ )s j   t/s    1/t .
We then apply Proposition 3.1 to the m-linear form defined on m 1 k=1 ℓ ω by A(e i ) =

j∈N m 2 a q i,j S (q-γ ′ )s j
where

m 1 ω = 1 - s t (this requires s ≤ t). We obtain i∈N m 1   j∈N m 2 a q i,j S (q-γ ′ )s j   t/s ≤   sup y∈ m 1 k=1 B ℓω i∈N m 1 y i j∈N m 2 a q i,j S (q-γ ′ )s j   t/s . Fix now y ∈ m 1
k=1 B ℓω and let us apply another time Hölder's inequality with r satisfying (q -γ ′ )sr = q. We get

i y i j a q i,j S (q-γ ′ )s j = j i y i a q i,j S (q-γ ′ )s j ≤ j i a q i,j S q j 1/r =1 i y r * i a q i,j 1/r * .
We may then conclude provided

r * ω = q p 1 and 1 r * = α q .
All the conditions imposed on r, s, t and ω fix the value of γ ′ . Indeed, we get successively

1 ω = q p 1 r * = α p 1 , s = 1 - m 1 α p 1 t, t = 1 -β q 1 -m 1 α p 1 1 -m 1 α p 1 1 -β q since t * s * = β q , s = 1 -β q 1 -m 1 α p 1 1 -β q , γ ′ = q   1 - 1 -α q 1 -β q 1 -β q + αβm 1 p 1 q   .
We may then compute γ by checking that

1 ρ = 1 - m 2 q p 2 s * = 1 - αβm 1 m 2 p 1 p 2 1 -β q + αβm 1 p 1 q
.

We finally deduce that

γ = γ ′ ρ = α 1 -β q + βm 1 p 1 1 -β q + αβm 1 p 1 q -αβm 1 m 2 p 1 p 2 which leads to 1 γ = 1 -β q + αβm 1 p 1 q -αβm 1 m 2 p 1 p 2 α 1 -β q + βm 1 p 1 = 1 α + m 1 p 1 αβ q -β -m 2 αβ p 2 α 1 -β q + βm 1 p 1 = 1 α - m 1 p 1 × 1 -q α -m 2 p 2 q 1 -q β -m 1 p 1 q
.

We verify now that our applications of Hölder's inequality and Proposition 3.1 were legitimate. It is clear that s, r ≥ 1. Since

s t = 1 - m 1 α p 1
we also have 1 ≤ s ≤ t. In particular, our application of Proposition 3.1 to m 2 k=1 ℓ ω was possible. Finally, our first application of this proposition requires that ρ > 0, namely

αβm 1 m 2 p 1 p 2 ≤ 1 - β q + αβm 1 p 1 q ⇐⇒ αm 1 p 1 βm 2 p 2 - β q ≤ 1 - β q .
It is easy to check that this last inequality is satisfied provided αm 1 ≤ p 1 , βm 2 ≤ p 2 and β ≤ q.

The following proposition is the main step towards the proof of our main results. It is an n-linear version of the previous lemma.

Proposition 3.5. Let q ∈ [1, +∞) m . Let (C 1 , . . . , C n ) be a partition of {1, . . . , m} into non-empty open subsets and let us assume that there exists p ∈ [1, +∞) n such that, for any l ∈ {1, . . . , n} and any k ∈ C l , q k = p l . Let also (a(i)) i∈N m be a sequence of nonnegative real numbers. Assume that there exist κ > 0, 0 < r 1 , . . . , r n ≤ q such that for all k ∈ {1, . . . , n}, for all sequence v ∈ l =k j∈C l B ℓp l ,

i∈N C k   j∈N C k v q j a q i,j   r k q ≤ κ r k .
Define, for all k = l,

1 γ k = 1 r k - j =k |C j | p j   1 -q r k -|C k |q p k 1 -q r j - |C j |q p j   1 γ k,l = 1 r k - j =k,l |C j | p j   1 -q r k -|C k |q p k 1 -q r j - |C j |q p j  
Then, for all k ∈ {1, . . . , n},

   i∈N C k   j∈N C k a q i,j   γ k q    1 γ k ≤ κ provided, for all k = l, γ k > 0, γ k,l ∈ (0, q] and |C l |γ k,l p l ≤ 1. (1)
Proof. The proof is done by induction on n. For n = 1, there is nothing to prove (the inner sum does not appear) and the case n = 2 is the content of Lemma 3.4. So, let us assume that the result is true for n -1 ≥ 2 and let us prove it for n. We fix some l ∈ {1, . . . , n} and some w ∈ j∈C l B ℓp l . We then define, for i

∈ N C l , b l (i) =   j∈N C l w q j a q i,j   1 q
.

Our assumption implies that, for k = l,

i∈N C k   j∈N C k ∪C l v q j b l (i, j) q   r k q ≤ κ r k
where v is any element of s =k,l j∈Cs B ℓp s . We may thus apply the induction hypothesis to get that, for any k = l

i∈N C k   j∈N C k ∪C l b l (i, j) q   γ k,l ≤ κ γ k,l .
We then set, for i

∈ N C k and j ∈ N C l , c k,l (i, j) =   k∈N C k ∪C l a q i,j,k   1 q
so that our inequality becomes

i∈N C k   j∈N C l w q j c k,l (i, j) q   γ k,l q ≤ κ γ k,l
which is satisfied for all w ∈ j∈C l B ℓp l . But of course, we can exchange the role played by k and l and we also have

j∈N C l   i∈N C k w q i c k,l (i, j) q   γ l,k q ≤ κ γ l,k
for all w ∈ j∈C k B ℓp k . We now apply Lemma 3.4 to find that (1) is satisfied with

1 γ k = 1 γ k,l - |C l | p l   1 -q γ k,l -|C k |q p k 1 -q γ l,k -|C l |q p l   .
It remains to verify that this is the expected value of γ k . This follows from

1 - q γ k,l - |C k |q p k = 1 - q r k -q j =k,l |C j | p j   1 -q r k -|C k |q p k 1 -q r j - |C j |q p j   - |C k |q p k = 1 - q r k - |C k |q p k   1 - j =k,l q 1 -q r j - |C j |q p j  
and from the symmetric computation involving γ l,k .

3.3.

A mixed-norm inequality. We finally need a last result which is a combination of a mixed-norm Hölder inequality (see [START_REF] Benedek | The space L p with mixed norm[END_REF]) and an inequality due to Blei (see [START_REF] Blei | Fractional cartesian products of sets[END_REF]). It appears in [START_REF] Popa | Blei's inequality and coordinatewise multiple summing operators[END_REF]. Let (M j , µ j ) be σ-finite measure spaces for j = 1, . . . , n and introduce the product measure spaces (M n , µ n ) and (M n k , µ n j ) by

M n = n k=1 M k , µ n = n k=1 µ k , M n j = n k=1 k =j M k , µ n j = n k=1 k =j µ k . Lemma 3.6. Let q > 0, n ≥ 2 and r 1 , . . . , r n ∈ (0, q). If h ≥ 0 is µ n -measurable, then Mn h Q dµ n 1 Q ≤ n j=1   M j M n j h q dµ n j r j q dµ j   1 R(q-r j )
where R = n j=1 r j q-r j and Q = qR 1+R .

Proof of the main results

Proof of Theorem 2.1. Let, for 1 ≤ j ≤ m, x(j) = (x i (j)) i∈N ⊂ X N j with w q j (x(j)) ≤ 1. We set a i = T (x i ) for i ∈ N m and we intend to show that the assumptions of Proposition 3.5 are satisfied. So, let k ∈ {1, . . . , n}. For l = k ∈ {1, . . . , n} and u ∈ C l , we consider a sequence v(u) ∈ B ℓ p * l = B ℓ q * j and we set y(u) = (v i (u)x i (u)) i∈N so that w 1 (y(u)) ≤ 1.

Writing C k = {u 1 , . . . , u s } and picking j ∈ N C k , we set y j = y j (C k ) = (y j 1 (u 1 ), . . . , y js (u s )), so that

i∈N C k   j∈N C k v q j a q i,j   r k q = i∈N C k   j∈N C k T (x i (C k ), y j (C k )) q   r k q
.

Since Y has cotype q, and using Kahane's inequalities, there exists a constant A k (depending only on r k , on |C k | and on the cotype q constant of Y ) such that

i∈N C k   j∈N C k v q j a q i,j   r k q ≤ A k Ω i∈N C k T (x i (C k ), y(ω)) r k dP(ω)
where y(ω) = +∞ i=1 ε j,i (ω)y i (j) j∈C k and (ε j,i ) j∈C k , i∈N are sequences of independent Bernoulli variables on the same probability space (Ω, A, P). Recall that |ε j,i (ω)| ≤ 1, for any j ∈ C k and any i ∈ N. Therefore,

y(j, ω) X j = sup x * ∈B X * j x * , +∞ i=1 ε j,i (ω)y i (j) ≤ w 1 (y(j)) ≤ 1.
Since T is coordinatewise multiple summing in the coordinates of C k , this yields

i∈N C k   j∈N C k v q j a q i,j   r k q ≤ A r k k T C k r k CW (r k ,p k ) . Setting κ = max k A k T C k CW (r k ,p k )
, we may apply Proposition 3.5 which yields, for any k ∈ {1, . . . , m},

   i∈N C k   j∈N C k T (x i (C k ), x j (C k ) q   γ k q    1 γ k ≤ κ.
We conclude by Lemma 3.6.

Remark 4.1. We have

A k ≤ (C q (Y )K r k ,q ) |C k |
where C q (Y ) is the cotype q constant of Y and K r k ,q is the constant appearing in Kahane's inequality between the L r k and the L q -norms. Hence, we have shown that

π mult r,q (T ) ≤ sup k=1,...,m (C q (Y )K r k ,q ) |C k | T C k CW (r k ,p k ) .
The forthcoming lemma will be uselful for (r, p)-multiple summing maps with r greater than the cotype of the target space. It is inspired by the proof of Theorem 1.2 of [START_REF] Dimant | Summation of coefficients of polynomials on ℓp spaces[END_REF].

Lemma 4.2. Let T : X 1 × • • • × X m → Y be m-linear with Y a cotype q space. Let q ∈ [1, +∞) m and C ⊂ {1, . . . , m}. We define t ∈ [1, +∞) C by t k = q k for all k ∈ C. Let finally s, r ∈ [1, +∞) satisfying 1 r = 1 s + j∈ C 1 q * j ,
r ≥ q and s ≥ q k for all k ∈ {1, . . . , m}. Then there exists κ > 0 such that

π mult s,q (T ) ≤ κ sup π mult r,t T C (z) ; z X C ≤ 1 .
If all the q k are equal to the same p, the conclusion takes the more pleasant form:

π mult s,q (T ) ≤ κ T C CW (r,t) , 1 r = 1 s + | C| p * .
Note that we require now coordinatewise summability only in the coordinates of C (and nothing on C). But now, we start with (r, t)-summability with r greater than the cotype of the target space.

Proof. Let x belong to m k=1 B ℓ w q k (X k ) . We write

(2)

i∈N m T (x i ) s 1/s =   i∈N C y i s ℓs(Y )   1/s
where, for a fixed i ∈ N C , y i is the sequence T (x i ( C), x j (C) j∈N C . Since r ≥ q, ℓ r (Y ) has cotype r so that id : ℓ r (Y ) → ℓ r (Y ) is (r, 1)-summing. By the ideal property of summing operators, id : ℓ r (Y ) → ℓ s (Y ) is still (r, 1)-summing. By the inclusion theorem, this last map is (s, ρ)-summing, with

1 ρ = 1 - 1 r + 1 s = 1 - j∈ C 1 q * j ∈ (0, 1).
Applying this to (2) yields

i∈N m T (x i ) s 1/s ≤ κ sup ϕ∈B [ℓr (Y )] *   i∈N C |ϕ(y i )| ρ   1/ρ .
Observe that the constant κ > 0 does not depend on T , but only on Y , r and q. We now apply Proposition 3.1 to get

i∈N m T (x i ) s 1/s ≤ κ sup ϕ∈B [ℓr (Y )] * sup v∈ j∈ C B ℓ * q j i∈N C v i ϕ(y i ) ≤ κ sup v∈ j∈ C B ℓ * q j sup ϕ∈B [ℓr (Y )] * ϕ     T   i∈N C v i x i ( C), x j (C)     j∈N C   ≤ κ sup v∈ j∈ C B ℓ * q j   j∈N C T   i∈N C v i x i ( C), x j (C)   r   1/r ≤ κ sup z∈X C , z ≤1   j∈N C T (z, x j (C)) r   1/r
since, for any m ∈ C, by Hölder's inequality,

i v i (m)x i (m) = sup x * ∈X * m i v i (m) x * , x i (m) ≤ 1.
Proof of Theorem 2.2. We fix k 0 and J satisfying the assumptions of the theorem. At the beginning we argue like in the proof of Theorem 2.1. Let D = j∈J C j and z ∈ B X D . We also set C = D and C ′ = C\{k 0 }. Let, for j ∈ C, (x i (j)) ∈ X N j with w q j (x(j)) ≤ 1. We can follow the arguments of the proof of Theorem 2.1 up to the application of Lemma 3.6 for the multilinear map T C (z). This gives

    i∈N C k 0   j∈N C ′ T (x i (C k 0 ), x j (C ′ ), z) q   γ k 0 ,J q     1 γ k 0 ,J ≤ κ.
Observe that the constant κ does not depend on z ∈ B X D . Since γ k 0 ,J ≥ q, this implies

  i∈N C T (x i (C), z) γ k 0 ,J   1 γ k 0 ,J ≤ κ.
We may then apply Lemma 4.2 to T with r = γ k 0 ,J and

1 s = 1 r - j∈D 1 q * j = 1 γ k 0 ,J - j∈J |C j | p * j to get the conclusion.
Proof of Theorem 2.3. The proof is completely similar but more elementary. Indeed, we can start from

  i∈N C k T (x i (C k ), z) r k   1 r k ≤ κ
for all z ∈ j∈C k B X j and apply directly Lemma 4.2 since r k ≥ q.

The inclusion theorem

The proof of Theorem 1.2 follows rather easily from Proposition 3.1.

Proof of Theorem 1.2. We start from x ∈ m k=1 B ℓ w q k (X k ) and u ∈ m k=1 B ℓ θ k where 1

θ k = 1 p k -1 q k .
Then by Hölder's inequality, ux = (u(1)x(1), . . . , u(m)x(m)) belongs to m k=1 B ℓ w p k (X k ) . Hence,

i∈N m |u i | r T (x i ) r 1/r ≤ π mult r,p (T ).
We may then apply Proposition 3.1 to the multilinear form A :

ℓ θ 1 r ו • •×ℓ θm r → C defined by A(v) = i∈N m v i T (x i ) r . This is possible since 1 - m j=1 r θ j = r   1 r - m j=1 1 p j + m j=1 1 q j   > 0.
This yields immediately Theorem 1.2.

Of course, it is natural to compare Pérez-García result with ours. If we start from a (p, p)-summing multilinear map, the former is better. But if we start from a multiple 2m m+1 , 1 -summing m-linear map, Theorem 1.2 shows that, for any s ∈ 2m m+1 , 2 , it is also multiple s, 2m 2 s 2m+(2m 2 -m-1)s -summing whereas we cannot expect from Pérez-García theorem a better result than it is (s, s)-summing. It is easy to check that for those s,

2m 2 s 2m + (2m 2 -m -1)s < s.
In other words, Theorem 1.2 gives a better conclusion. Applications of Theorem 1.2 are given in [START_REF] Pellegrino | Regularity principle in sequence spaces and applications[END_REF].

6. Applications to harmonic analysis 6.1. Product of p-Sidon sets.

Proof of Theorem 1.3.

Let G = G 1 × • • • × G m and f = i∈N m a i γ i be a polynomial with spectrum in Λ 1 ו • •×Λ m .
Here γ i denotes the tensor product γ i 1 (1)⊗• • •⊗γ im (m) and each γ i j (j) belongs to Γ j . Fix k ∈ {1, . . . , m}, let

C k = {k}, G k = G 1 ו • • G k-1 ×G k+1 ו • •×G m and Λ k = Λ 1 × • • • Λ k-1 × Λ k+1 × • • • × Λ m .
It is well-known that the product of Λ(2)-sets is still a Λ(2)-set (this follows from Minkowski's inequality for integrals). Hence, Λ k is a Λ(2)-set and we deduce that for any i

∈ N = N C k ,   j∈N C k |a i,j | 2   p k /2 ≤ κ G k j∈N C k a i,j γ j (g ′ ) p k dg ′ .
We sum over i ∈ N C k and we use that Λ k is p k -Sidon to deduce that

   i∈N C k   j∈N C k |a i,j | 2   p k /2    1/p k ≤ κ G k sup g∈G k |f (g, g ′ )| p k dg ′ 1/p k ≤ κ f ∞ .
The result now follows from Lemma 3.6. We postpone the proof of optimality to the last section.

6.2. Product of p-Rider sets. Beyond p-Sidon sets, L. Rodríguez-Piazza has introduced in [START_REF] Rodríguez-Piazza | Caractérisation des ensembles p-Sidon p.s[END_REF] another class of sets extending naturally that of Sidon sets. For G a compact abelian group with dual Γ, a subset Λ ⊂ Γ is called p-Rider (1 ≤ p < 2) if there is a constant κ > 0 such that each f ∈ C(G) with f supported on Λ satisfies

f ℓp ≤ κ[[f ]] := Ω γ∈Γ ε γ f (γ)γ ∞ dP
where (ε γ ) γ∈Γ is a sequence of independent Bernoulli variables. The terminology p-Rider comes from Rider's theorem which asserts that 1-Sidon sets and 1-Rider sets coincide.

Observe that it is easy to prove that a p-Sidon set is always a p-Rider set (see [START_REF] Lefèvre | p-Rider Sets are q-Sidon Sets[END_REF]), but the converse is an open question. It turns out that p-Rider sets are usually easier to manage than p-Sidon sets. This is due to the inconditionnality of the norm [[•]]. For instance, this last property implies immediately that the union of two p-Rider sets is still a p-Rider set, a fact which is unknown for p-Sidon sets. This is also the case for the direct product.

Theorem 6.1. Let G 1 , . . . , G m , m ≥ 2, be compact abelian groups with respective dual groups Γ 1 , . . . , Γ m . For 1 ≤ j ≤ m, let Λ j ⊂ Γ j be a p j -Rider set. Then

Λ 1 × • • • × Λ m is a p-Rider set in Γ 1 × • • • × Γ m for 1 p = 1 2 + 1 2R and R = m k=1 p k 2 -p k .
This result was already proved in [START_REF]Rango y propiedades de medidas vectoriales[END_REF] using an arithmetical characterization of p-Rider sets. We provide a new (and maybe more elementary) proof using our machinery.

Proof. Let G = G 1 × • • • × G m and f = i∈N m a i γ i be a polynomial with spectrum in Λ 1 × • • • × Λ m . Fix k ∈ {1, .
. . , m} and keep the notations of the proof of Theorem 1.3. Let (Ω, A, P) be a probability space and consider three sequences (ε i,j ) i∈N,j∈N C k , (δ j ) j∈N C k , (η i ) i∈N of independent Bernoulli variables on (Ω, A, P). Then, for any i ∈ N = N C k and any ω ∈ Ω, by the Khintchine inequalities,

  j∈N C k |a i,j | 2   p k /2 =   j |a i,j ε i,j (ω)| 2   p k /2 ≤ κ 1 Ω j a i,j ε i,j (ω)δ j (ω ′ ) p k dP(ω ′ ).
We sum over i and use that Λ k is a p k -Rider set to get

i∈N   j∈N C k |a i,j | 2   p k /2 ≤ κ 2 Ω   Ω sup g∈G k i,j a i,j ε i,j (ω)δ j (ω ′ )η i (ω ′′ )γ i (k)(g) dP(ω ′′ )   p k dP(ω ′ ) ≤ κ 3 Ω Ω sup g∈G k i,j a i,j ε i,j (ω)δ j (ω ′ )η i (ω ′′ )γ i (k)(g) p k dP(ω ′′ )dP(ω ′ )
where the last line comes from Kahane's inequalities. We then integrate over ω ∈ Ω, exchange integrals, apply the contraction principles to Bernoulli variables (see [

  j∈N C k |a i,j | 2   p k /2 ≤ κ 3 Ω sup g∈G k i,j a i,j ε i,j (ω)γ i (k)(g) p k dP(ω) ≤ κ 4 [[f ]] p k .
We conclude using Lemma 3.6.

7. About the optimality 7.1. Optimality for coordinatewise summability. We now discuss the optimality of our results. We first show that Theorem 1.1 is optimal when we restrict ourselves to cotype 2 spaces and 1 ≤ p ≤ 2.

Theorem 7.1. Let p ∈ [1, 2], r ≥ p satisfying 1 r ≥ 1 p -1 2
and m ≥ 1. Then the optimal s such that every m-linear map T :

X 1 × • • • × X m → ℓ 2 which is separately (r, p)-summing is automatically (s, p)-summing satisfies • 1 s = m-1 2m + 1 mr -m-1 p * provided 1 r -m-1 p * > 1 2 ; • 1 s = 1 r -m-1 p * provided 0 < 1 r -m-1 p * ≤ 1 2 .
It should be observed that the assumption 1 r ≤ 1 p -1 2 is not a restriction on the possible values of r. Indeed, a linear map with values in a cotype 2 space is always (2, 1)-summing, hence (r, p)-summing with 1 r = 1 p -1 2 .

Proof. We shall use the following result proved partly in [START_REF] Dimant | Summation of coefficients of polynomials on ℓp spaces[END_REF] and partly in [START_REF]Optimal Hardy-Littlewood type inequalities for polynomials and multilinear operators[END_REF]. Let 1 ≤ u ≤ 2. Define ρ as the best (=smallest) real number such that, for all m-linear maps A :

ℓ p * × • • • × ℓ p * → ℓ u , the composition I u,2
• A is multiple (ρ, p)-summing where I u,2 denotes the identity map from ℓ u into ℓ 2 . Then

• 1 ρ = 1 2 + 1 m 1 u -1 2 -m p * provided 0 < m p * < 1 u -1 2 ; • 1 ρ = 1 u -m p * provided 1 u -1 2 ≤ m p * < 1 u .
The real numbers r and p being fixed (and satisfying the assumptions of Theorem 7.1), we fix u ∈ [START_REF] Albuquerque | Sharp generalizations of the multilinear Bohnenblust-Hille inequality[END_REF][START_REF]Optimal Hardy-Littlewood type inequalities for polynomials and multilinear operators[END_REF] such that 1 r = 1 u + 1 p -1. By the Bennett-Carl inequalities, I u,2 is (r, p)summing with 1 r = 1 u + 1 p -1 so that I u,2 • A is separely (r, p)-summing. Then the optimal s in Theorem 7.1 must satisfy s ≥ ρ. But using the relation linking u, p and r, it is easy to see that the condition m

p * < 1 u -1 2 is equivalent to 1 r -m-1 p * > 1 2
and that the values of 1 ρ are exactly the optimal values appearing in Theorem 7.1.

7.2.

Optimality for the inclusion theorem. We now show that, in full generality, Theorem 1.2 is also optimal.

Theorem 7.2. Let r ≥ 2 and p = 2r r+1 . Then there exists a bilinear form T : ℓ 2 × ℓ 2 → C which is (r, p)-summing and such that, for every s ≥ 2 and q ≥ p, it is (s, q)-summing if and only if

1 s - 2 q ≤ 1 r - 2 p .
Proof. Let T (x, y) = +∞ i=1 x i y i , which has norm 1. Then by Corollary 2.7, as all bilinear forms, T is (r, p)-summing. Conversely, let us assume that it is also (s, q)-summing. We choose x = (e i ) i=1,...,n so that w q (x) = n max 1 q -1 2 ,0 . For this choice we get

n 1 s =   n i,j=1 |T (e i , e j )| s   1 s ≤ π s,q (T )w q (x) 2 ≤ π s,q (T )n max 2 q -1,0 .
This implies q ≤ 2 and

1 s ≤ 2 q -1 namely 1 s - 2 q ≤ 1 r - 2 p .
In view of this example and Pérez-García's result, it seems conceivable that something similar does not happen if we start with r ≤ s ≤ 2. This deserves further investigation.

7.3. Optimality for the product of p-Sidon sets. We finally conclude by proving the optimality of Theorem 1.3. To simplify the notations, we will only prove it for the product of two sets. We shall work with G = Ω = {-1, 1} N whose dual group Γ is the set of Walsh functions. Recall that if (r n ) n∈N is the sequence of Rademacher functions on Ω, defined by r n (ω) = ω n , ω ∈ Ω, then the Walsh functions are the functions w A = n∈A r n where A is any finite subset of N (in particular, w ∅ = 1). We will prove the following theorem, which clearly implies optimality in Theorem 1.3. Proof. The proof needs some preparation. First we recall a necessary condition for a subset Λ ⊂ Γ to be p-Sidon (see [START_REF]Analysis in integer and fractional dimensions[END_REF]Theorem VII.41]):

Lemma 7.4. Let Λ ⊂ Γ and assume that Λ is p-Sidon. Then there exists κ > 0 such that, for any polynomial f supported on Λ, for any s ≥ 1,

f L s √ s f 2p 3p-2 ≤ κ.
We write p 1 = 2m be pairwise disjoint infinite subsets of the Rademacher system and enumerate each E δ l , δ ∈ {0, 1}, l ∈ {1, . . . , n δ } by N k δ :

E δ l = γ δ l,j ; j ∈ N k δ .
Define Π S δ l as the projection from {1, . . . , m δ } onto S δ l . We finally consider

Λ δ = γ δ 1,Π S δ 1 j • • • γ δ n δ ,Π S δ n δ j ; j ∈ N m δ .
It is shown in [6, p. 465] that Λ δ is p δ -Sidon (and nothing better!). We shall prove that Λ 1 × Λ 2 is not p-Sidon for

1 p > 1 2 + 1 2R where R = p 1 2 -p 1 + p 2 2 -p 2 , namely 1 p > m 1 k 1 + m 2 k 1 + k 1 k 2 2(m 1 k 1 + m 2 k 2 ) .
To do this, we consider N a large integer and set N 1 = N k 2 and N 2 = N k 1 so that

N k 1 1 = N k 2 2 .
We then define

f N = j∈{1,...,N 1 } m 1 k∈{1,...,N 2 } m 2 γ 1 1,Π S 1 1 j • • • γ 1 n 1 ,Π S 1 n 1 j γ 2 1,Π S 2 1 k • • • γ 2 n 2 ,Π S 2 n 2 k
which is a polynomial supported on Λ 1 × Λ 2 , and the Riesz product (1 + γ 2 l,j ).

R N =
Then .

R N 1 = R N = 1 (recall that R N is positive) whereas R N 2 = 2 n 1 +N k 1 1 +n 2 +N
On the other hand, by the very definition of R N , R N = f N + Q N where the spectrum of Q N is disjoint from that of f N . Hence,

Ω×Ω R N f N = Ω×Ω f 2 N = j,k 1 2 = N m 1 1 N m 2 2 = N m 1 k 2 +m 2 k 1 .
Now, observe that Holder's inequality also yields

Ω×Ω R N f N ≤ R N s * f N s ≤ 2 n 1 +n 2 +2N k 1 k 2 s f N s .
We choose s = N k 1 k 2 so that one obtains

f N s ≥ κN m 1 k 2 +m 2 k 1 .
In order to apply Lemma 7.4 we just compute

f N 2p 3p-2 = (N m 1 1 N m 2 2 ) 3p-2 2p = N (m 1 k 2 +m 2 k 1 ) 3p-2 2p .
Thus,

f N L s √ s fN 2p 3p-2 ≥ κN (m 1 k 2 +m 2 k 1 ) 2-p 2p - k 1 k 2 2 .
If Λ 1 × Λ 2 is p-Sidon, then Lemma 7.4 tells us that

1 2 - 1 p (m 1 k 2 + m 2 k 1 ) - k 1 k 2 2 ≤ 0
which is exactly the desired inequality.

n 1 l=1 1 ( 1 + γ 1 l,j ) × n 2 l=1

 11112 j∈{1,...,N 1 } k j∈{1,...,N 2 } k 2

k 2 2 = 2 n

 22 1 +n 2 +2N k 1 k 2 . By interpolation, for any s > 2, R N s * ≤ 2 n 1 +n 2 +2N k 1 k 2 s

  Theorem 7.3. Let Ω = {-1, 1} N , Γ its dual group, p 1 , p 2 rational numbers in[START_REF] Albuquerque | Sharp generalizations of the multilinear Bohnenblust-Hille inequality[END_REF][START_REF]Optimal Hardy-Littlewood type inequalities for polynomials and multilinear operators[END_REF]. There exist two subsets Λ 1 , Λ 2 of Γ which are respectively p 1 -Sidon or p 2 -Sidon, and such that their direct product Λ 1 × Λ 2 is not p-Sidon for

	1 p	>	1 2	+	1 2R	where R =	p 1 2 -p 1	+	p 2 2 -p 2	.

  1 m 1 +k 1 and p 2 = 2m 2 m 2 +k 2 . Let S 1 1 , . . . , S 1 n 1 (resp. S 2 1 , . . . , S 2 n 2 ) the subsets of {1, . . . , m 1 } (resp. of {1, . . . , m 2 }) with cardinal k 1 (resp. k 2 ). Let E 1 1 , . . . , E 1 n 1 , E 2 1 , . . . , E 2

	n 2

We may also deduce from Corollary 2.6 a result of Praciano-Pereira [23] and Dimant/Sevilla-Peris [11] which is an m-linear version of a famous bilinear inequality of Hardy and Littlewood [13]. We state it in the spirit of [21].


Aurélie Lagoutte

Sébastien

S Tavenas

The complexity of Shortest Common Supersequence for inputs with no identical consecutive letters

come

The complexity of Shortest Common Supersequence for inputs with no identical consecutive letters

Introduction

Given two words u and v over an alphabet Σ, u is a supersequence of v if one can find in u a sequence of non-necessarily successive letters that spells v. The shortest supersequence of u is obviously u, but the problem becomes more difficult if the input is a set of words and one wants to find a common supersequence for these words as short as possible. The decision version of this problem, called SCS for Shortest Common Supersequence has been proven NP-complete in 1981 by Räihä and Ukkonen [START_REF] Räihä | The shortest common supersequence problem over binary alphabet is NP-complete[END_REF], even if the alphabet has size only 2. It is even NP-complete for some very restricted input, such as in the result of Middendorf [START_REF] Middendorf | More on the complexity of common superstring and supersequence problems[END_REF] on which our work deeply relies: the alphabet is Σ 2 = {0, 1}, and all the input words have the same length and each contains exactly two non-consecutive 1. However, another variant of SCS, which we will call Modified SCS (MSCS for short), appears very naturally in the study of combinatorial flood-filling games such as Flood-It and Honey-Bee (studied for example in [START_REF] Clifford | The complexity of flood filling games[END_REF][START_REF] Fleischer | An algorithmic analysis of the honey-bee game[END_REF][START_REF] Lagoutte | Flooding games on graphs[END_REF][START_REF] Meeks | Spanning trees and the complexity of flood-filling games[END_REF]). In particular in [START_REF] Lagoutte | Flooding games on graphs[END_REF], the authors show the NP-completeness of Flood-It, using a reduction to MSCS with an alphabet of size 3. This variant is stated as follows:

Modified Shortest Common Supersequence : MSCS -decision version Input: A set L = {w 1 , . . . , w n } of words on an alphabet Σ = {a 1 , a 2 , . . . , a d } such that no word w i contains two consecutive identical letters and no word w i starts with letter a 1 , and an integer k. Output: Does there exist a supersequence of L of size less than k?

At first sight, it can seem easy to reduce SCS with Σ 2 = {0, 1} to MSCS with Σ 3 = {0, 1, 2} by replacing every occurence of 0 by 02 in every word of the input set L, and doing the reverse operation on the solution to MSCS to get the shortest common supersequence of L. Unfortunately, this very natural idea does not work in general as shown on the following counter-example. Let L = {00111, 11100} be a input for SCS (in the minimization version), then the corresponding input for MSCS is L = {0202111, 1110202}. The shortest solution for MSCS is 1110202111 of length 10, and its corresponding candidate solution for SCS is 11100111 of length 8. However, the shortest solution for L has size 7: 0011100. The problem here is that the operation transforms 0 into a double-counting letter and looses the symmetry between the two letters.

The second idea that occurs to mind is then to transform every occurrence of 0 by 02, and also every occurrence of 1 by 12. Then one can hope solving the newly created instance of MSCS, and delete every 2 from the solution of MSCS to get the shortest solution to SCS. This does not work either: consider the instance of SCS (in its minimization version) with L = (Σ 2 ) 3 \ {111}, that is to say that L contains every word of length 3 on Σ 2 = {0, 1} except 111. The shortest supersequence for L is 01010 and is unique. Let L be the set of words obtained from L by replacing every occurrence of 0 by 02 and every occurrence of 1 by 12. There is no supersequence for L of length 9 obtained from 01010 by inserting some 2's (there is one of length 10: 0212021202). However there does exist a shortest supersequence for L of length 9, namely 012012012. Consequently, the very natural ideas do not work for reducing SCS to MSCS.

Note that Fleischer and Woeginger designed in [START_REF] Fleischer | An algorithmic analysis of the honey-bee game[END_REF] a reduction proving that MSCS is NP-complete when |Σ| ≥ 4 (the conference version of the paper states the result for |Σ| ≥ 3, but the very simple proof turned out to be false; the correct statement appears in the later-published journal version). One should also mention Darte's work [START_REF] Darte | On the complexity of loop fusion[END_REF] which does not focus directly on MSCS, but states a result about typed fusions for typed directed graphs in a compilation context. However, as he explains at the beginning of Section 3.5, when the directed graphs are disjoint union of chains, his problem is equivalent to SCS. Moreover the conditions over its typed fusions and digraphs implies that the SCS inputs equivalent to his digraph inputs, are words with no identical consecutive letters. Thus Proposition 3 in [START_REF] Darte | On the complexity of loop fusion[END_REF] can be interpreted as the fact that SCS for inputs with no identical consecutive letters is NP-complete. His reduction from Vertex Cover uses the alphabet Σ = {0, 1, ā} and a careful look shows that he generates SCS inputs where no word starts with ā. Consequently one could state that the NP-completeness of MSCS for three letters is shown there. His reduction is derived from a paper of Räihä and Ukkonen [START_REF] Räihä | The shortest common supersequence problem over binary alphabet is NP-complete[END_REF] as well as its proof. Unfortunately it is 10 pages long and hard to check.

The main purpose of our work is to provide a new NP-completeness reduction for MSCS when |Σ| ≥ 3, with a shorter proof, so that the result becomes undisputed. To this end, we introduce yet another variant of SCS, called ϕSCS. We first define the alphabets Σ 2 = {0, 1} and Σ 3 = {0, 1, 2}, and the word morphism ϕ : Σ * 2 → Σ * 3 by ϕ(0) = 0202 and ϕ(1) = 1. Shortest Common Supersequence for some inputs generated by ϕ : ϕSCS -decision version Input: A set L = {w 1 , . . . , w n } of words on the alphabet Σ 3 such that L ⊆ ϕ(Σ * ), each w i contains exactly two ones, which moreover are non consecutive, and an integer k. Output: Does there exist a supersequence of L of size less than k?

A careful look at those two problems shows that ϕSCS is a particular case of MSCS if |Σ| ≥ 3. The input words for ϕSCS are a concatenation of patterns 0202 and 1 with no consecutive ones, thus they do not contain consecutive identical letters. Moreover none of those input words starts with letter 2. Up to relabelling the letters, one may consider that a 1 = 2. Consequently, we will show that ϕSCS is NP-complete, which implies that MSCS is also NP-complete if |Σ| ≥ 3. One may wonder why we use the block 0202 instead of the more natural block 02 (that is to say, why ϕ(0) = 0202 and not 02). The key reason appears in the third item of Lemma 2 : the elementary technique we use to prove it does not work for the case of blocks 02.

Besides, observe that the threshold on |Σ| which involves NP-hardness is tight: when |Σ| = 2, MSCS is trivially polynomial. Finally, let us notice that our proof is a very close adaptation of the proof of Middendorf's result [START_REF] Middendorf | More on the complexity of common superstring and supersequence problems[END_REF]Theorem 4.2] mentioned in the first paragraph.

Notation Given two words over an alphabet Σ, u = u 1 . . . u p (u i ∈ Σ) and v = v 1 . . . v q (v i ∈ Σ), an embedding of u into v is an injection f from {1, . . . , p} into {1, . . . , q} such that u i = v f (i) . It tells that v is a supersequence of u and we also say that f maps letters of u onto letters of v. We will also use equivalently the terms pattern, block or factor to designate a sequence of consecutive letters in a word. A supersequence for a set of words is a word which is a supersequence for each of those words.

Result

The NP-completeness reduction will start from Vertex Cover, but we will need the next two lemmas.

Lemma 2.1. Let L be a set of words over Σ 3 , such that L ⊆ ϕ(Σ * ), and S = s 1 . . . s l be a supersequence of L. Then there exists a supersequence S of L of size ≤ |S| such that S ⊆ ϕ(Σ * ).

Proof.

• First step: Let S be a supersequence of L and let S be the string obtained from S after applying one of the following operations:

1. If S ends by 0, delete it. Then S is still a supersequence of L: indeed, item (i) and (ii) are obvious since no word of L starts by 2 nor ends by 0. For item (iii), observe that no embedding can map two 0 onto two consecutive 0, since no word contains two consecutive 0. Thus if S contains 00 at index i, and f is an embedding of w ∈ L so that f maps a zero of w onto s i+1 , we can modify f to map this zero onto s i . Then s i+1 is useless and we can delete it. The same argument applies for item (iv). For item (v), observe that no embedding can map a 0 and a 1 onto two consecutive 0 and 1 because this pattern does not appear in any word of L. Thus if S contains 01 at index i, and f is an embedding of w ∈ L so that f maps a zero of w onto s i (resp. a one of w onto s i+1 ), we can swap the 0 and the 1 in S and modify f to map the zero of w onto s i+1 (resp. the one of w onto s i ). The same argument applies for item (vi).

Consequently, starting from S, we can iterately "push" the zeros from left to right by deletion (transformation 00 into 0) or switching (01 into 10), and delete the last letter if it is a zero, until getting a supersequence S 1 where each 0 is followed by a 2. In the same manner, starting from S 1 , we can iterately "push" the 2's from right to left until getting a supersequence S 2 where each two is preceded by a zero. In other words, S 2 is formed by blocks of 02 and blocks of 1. Observe that for such supersequences and for every w ∈ L, there always exists an embedding f of w ∈ L such that for each block 02, either f maps two consecutive letters to this block or f maps no letter to this block. We will focus only on this type of embedding in the following. Observe moreover that |S 2 | ≤ |S|.

• Second step: The goal is to build a supersequence S 3 formed by blocks of 0202 and blocks of 1. Suppose first that S 2 starts by (02) 2k 1 for some k ∈ N. Consider the first apparition s i . . . s i+2k+2 , i ∈ [0 : |S 2 |] of a pattern 1(02) 2k+1 1 for any k ∈ N and call 2j the number of blocks of 02 before the pattern. Let S be the string obtained from S 2 by replacing this pattern by 1(02) 2k 102. Then S is a supersequence of each w ∈ L: let f be an embedding of w in S 2 . Either f does not map any letter to s i+2k+2 = 1, or f uses at most 2k blocks of 02 between s i = 1 and s i+2k+2 = 1, or there exists a block of 02 among the 2jth first blocks such that f maps no letter to this block and f maps no 1 between this block of 02 and s i+1 . Otherwise, w / ∈ ϕ(Σ * ). In each one of the three cases, we can easily modify f so that S is a supersequence of w. We can iterate the process until no odd block of 02 is found. Finally, if S ends with a pattern 1(02) 2k+1 , we can replace it by 1(02) 2k and still have a supersequence: if f is an embedding of w ∈ L, either f uses only 2k blocks among these 2k + 1, or there exists a block of 02 in S before the 1 which is not used by f and such that f maps no one after this block. Thus we can modify f as in the previous arguments. The last case if when S 2 starts with (02) 2k +1 1: we can replace this pattern at the very first step by (02) 2k 102 by the same arguments. Thus we obtain a supersequence S 3 of size ≤ |S| such that S 3 ∈ ϕ(Σ * ). Lemma 2.2. Let n be a positive even integer, L = {S 0 , . . . , S n 2 } be a set of strings with S i = (0202) i 1(0202) n 2 -i for i ∈ [0 : n 2 ]. Then let S be a supersequence of L such that S ∈ ϕ(Σ * ):

• If S contains exactly k ones, then S contains at least (n 2 + 1)/k -1 + n 2 blocks of 0202.

• If S contains exactly n 2 -1 + k blocks of 0202, then S contains at least (n 2 + 1)/k ones.

• The string S min = 1((02) n 1) 2n (02) n-2 is a shortest supersequence of L. It has length 4n 2 + 4n -3.

Proof.

• Let S containing k ones. There must be a subset L of L which contains at least (n 2 + 1)/k strings such that the strings in L can be embedded in S in such a way that the ones in these strings are mapped onto the same one of S. Let i max = max{i|S i ∈ L } and i min = min{i|S i ∈ L }. Since S i min and S imax are mapped onto the same one, S must contain at least i max + n 2 -i min zeros. Moreover, i max ≥ i min + (n 2 + 1)/k -1, so S contains at least (n 2 + 1)/k -1 + n 2 blocks of 0202.

• Let S containing n 2 -1 + k blocks of 0202. Consider a one in S and let L be the subset of L such that the one in the strings of L is mapped onto this one. Let j be the number of blocks of 0202 before this one in S.

Then S i ∈ L only if i ≤ j and n 2 -i ≤ n 2 -1 + k -j, i.e. only if j + 1 -k ≤ i ≤ j. Let i max = max{i|S i ∈ L } and i min = min{i|S i ∈ L }. Then |L | ≤ i max -i min + 1 ≤ j -j -1 + k + 1 ≤ k.
At most k strings are mapped onto the same one, thus there are at least (n 2 + 1)/k ones.

S l = ((02) 6n 1(02) 6n ) i-1 1((02) 6n 1(02) 6n ) j-i-1 (02) 6n 1(02) 6n ((02) 6n 1(02) 6n ) n+1-j (02) 6n . Now we can embed the prefix P l in S l by mapping its two ones onto the two underlined ones of S l and checking that the number of blocks of 0202 is enough.

• Case 2 : v j ∈ V . The suffixe (0202) 3n (0202) 36n 2 -1 of T l can be embedded in S . We can prove similarly to Case 1 that the prefix P l = (0202) 6n(i-1) 1(0202) 6n(j-i-1)+3n 1(0202) 6n(n+1-j)+3n can be embedded in S .

Finally, S is a supersequence of L of size 168n 2 + 37n -3 + k. Suppose now that L has a supersequence of length ≤ 168n 2 + 37n -3 + k. By Lemma 1, L has a supersequence S of size ≤ 168n 2 + 37n -3 + k such that S ∈ ϕ(Σ * ). Define S and S such that S = S S , where S is the shortest prefix of S that contains exactly 6n 2 + 3n blocks of 0202. Since each A i contains 6n 2 + 3n blocks of 0202, like S , and S is a supersequence of X j i , then S is a supersequence of {B j |j ∈ [0 : 36n 2 ]}. Let us state the following two claims: Claim 2.4. For each i ∈ [1 : n], S must contain a one between the (6n(i -1) + 3n)th block of 0202 and the (6in)th block of 0202. Consequently, S contains at least n ones.

Proof. Assume for contradiction that the claim does not hold for an i ∈ [1 : n]. Then the one in A i is mapped on a one in S which is after at least 6in blocks of 0202. Since S contains only 6n 2 +3n blocks of 0202, the suffix (0202) 3n of A i = (0202) 6n(i-1)+3n 1(0202) 6n 2 +3n-6ni (0202) 3n must be mapped onto S . Consequently, S is a supersequence of {(0202

) 3n B j |j ∈ [0 : 36n 2 ]}, thus by Lemma 2, |S | ≥ 4 • 3n + 144n 2 + 24n -3 = 144n 2 + 36n -3. Since |S | ≥ 4(6n 2 + 3n), we have |S| ≥ 24n 2 + 12n + 144n 2 + 36n -3 = 168n 2 + 48n -3 > 168n 2 + 37n -3 + k, a contradiction.
Claim 2.5. For l ∈ [1 : m] and e l = v i v j , i < j, T l cannot be embedded in S if S contains a one neither between the 6n(i -1)th block of 0202 and the (6n(i -1) + 3n)th block of 0202, nor between the 6n(j -1)th block of 0202 and the (6n(j -1) + 3n)th block of 0202.

Proof. Assume that the claim does not hold for an l ∈ [1 : m] with e l = v i v j , i < j. The suffix (0202) 6n+36n 2 -1 of T l must be mapped onto S : indeed, let P l = (0202) 6n(i-1) 1(0202) 6n(j-i-1)+3n 1(0202) 6n(n+1-j) 0 be a prefix of T l . The first one (resp. second one, last zero) of P l must be mapped to a one (resp. one, zero) of S, let t 1 (resp. t 2 , t 3 ) be the number of blocks of 0202 in S before this one (resp. one, zero). The assumption implies t 1 / ∈ [6n(i -1) : 6n(i -1) + 3n] and t 2 / ∈ [6n(j -1) : 6n(j -1) + 3n]. By definition of P l , t 1 ≥ 6n(i -1) thus, by assumption t 1 ≥ 6n(i -1) + 3n. By definition of P l again, t 2 ≥ t 1 + 6n(j -i -1) + 3n ≥ 6n(j -1). Consequently, t 2 ≥ 6n(j -1) + 3n. Finally, t 3 ≥ t 2 + 6n(n + 1 -j) ≥ 6n 2 + 3n. Since S contains exactly 6n 2 + 3n blocks of 0202, the last zero of P l is mapped onto S .

Consequently, S must contain at least 6n+36n 2 -1 blocks of 0202. Assume S contains 36n 2 +p blocks of 0202 with p ≥ 6n -1. By Lemma 2 (ii), |S | ≥ 4(36n 2 + p) + (36n 2 + 1)/(p + 1) ≥ f (p) where f is the function defined on R by f (x) = 4(36n 2 + x) + (36n 2 + 1)/(x + 1). But f is increasing on [3n : +∞[. Since p ≥ 6n -1, f (p) ≥ f (6n -1) = 4(36n 2 + 6n -1) + (36n 2 + 1)/(6n) > 144n 2 + 24n -4 + 6n. Thus |S | ≥ 144n 2 + 30n -3.

Since S contains 6n 2 + 3n blocks of 0202 and, as a consequence of Claim 4, at least n ones, we have |S | ≥ 4(6n 2 + 3n) + n = 24n 2 + 13n. Consequently, |S| ≥ 144n 2 + 30n -3 + 24n 2 + 13n = 168n 2 + 43n -3 > 168n 2 + 37n -3 + k, a contradiction.

Conclusion By Lemma 2, |S | ≥ 144n 2 + 24n -3. By definition, S contains 6n 2 + 3n blocks of 0202. Since |S| ≤ 168n 2 + 37n -3 + k, S can contain at most 168n 2 + 37n -3 + k -(144n 2 + 24n -3) -4(6n 2 + 3n) = n + k ones. By Claim 4, there is a one between the (6n(i -1) + 3n)th zero and the 6inth zero of S for each i ∈ [1 : n], which makes n ones. This implies that there can be at most k indices i ∈ [1 : n] such that there is a one between the 6n(i -1)th zero and the (6n(i -1) + 3n)th zero of S . Let i 1 , . . . i p be these indices, p ≤ k. Thanks to Claim 5, we see that {v i 1 , . . . , v i k } is a vertex cover of G of size p ≤ k.

As explained in the presentation of the two variants, inputs for ϕSCS have no identical consecutive letters and do not start with 2, thus we immediatly gain the following corollary.

Corollary 2.6. MSCS is NP-complete when |Σ| ≥ 3.

2 .

 2 If S starts by 2, delete it 3. If S contains 00, replace it by 0. 4. If S contains 22, replace it by 2. 5. If S contains 01, replace it by 10. 6. If S contains 12, replace it by 21.

• S min is indeed a supersequence of L: first, it is a supersequence of S 0 . Secondly, if i = 0, there exists j ∈ [1 : 2n] such that (j -1)n/2 + 1 ≤ i ≤ jn/2. Then the one in S i can be mapped to the (j + 1)th one, and there is jn/2 ≥ i blocks of 0202 before the one, and (2n-j)n/2+n/2-1 blocks of 0202 after the one, which is enough to map the suffix (0202

Let S be the shortest supersequence of L. By Lemma 1, S ∈ ϕ(Σ * ), so we can apply (i): if k is the number of ones of S , then |S | ≥ k + 4 (n 2 + 1)/k -4 + 4n 2 ≥ f (k) where f is the function defined on R by f (x) = x + 4(n 2 + 1)/x -4 + 4n 2 . However, f admits a minimum on R which is f (2

Proof. Obviously, ϕSCS is in NP. We reduce the Vertex Cover problem to it. Let G = (V, E) be a graph with vertices V = {v 1 , . . . , v n } and edge set E = {e 1 , . . . e m } and an integer k be an instance of Vertex Cover. Recall that the Vertex Cover problem asks whether G has a vertex cover of size ≤ k, i.e. a subset V ⊆ V with |V | ≤ k such that for each edge v i v j ∈ E, at least one of v i and v j is in V . Let us now construct our instance of ϕSCS:

For each edge e l = v i v j ∈ E, i < j, let T l = (0202) 6n(i-1) 1(0202) 6n(j-i-1)+3n 1(0202) 6n(n+2-j) (0202

Clearly, L can be constructed in polynomial time, each string in L is in ϕ(Σ * ) and has exactly two ones, which are non consecutive. We will now show that L has a supersequence of length ≤ 168n 2 + 37n -3 + k if and only if G has a vertex cover V of size ≤ k.

By Lemma 2, S is a supersequence of {B j |j ∈ [0 : 36n 2 ]}. Moreover, ((02) 6n 1(02) 6n ) n (02) 6n is a supersequence of {A i |i ∈ [1 : n]} thus S also is. From this we deduce that S is a supersequence of {X j i |i ∈ [1 : n], j ∈ [0 : 36n 2 ]}. Finally, let us prove that S is a supersequence of T l for l ∈ [1 : m]. Let e l = v i v j , i < j, and consider the two following cases:

• Case 1 : v i ∈ V , i.e. there exists t ∈ [1 : k] such that i = i t . The suffixe (0202) 36n 2 -1 of T l can be embedded in S . The goal is to prove that the prefix P l = (0202) 6n(i-1) 1(0202) 6n(j-i-1)+3n 1(0202) 6n(n+2-j) can be embedded in S . Observe that one can obtain the following subsequence S l of S by deleting a few ones: S l = ((02) 6n 1(02) 6n ) it-1 1((02) 6n 1(02) 6n ) n+1-it 1 (02) 6n . Now S l can be rewritten


A Lagoutte

H Salat

C Vachier

Alternative method for Hamilton-Jacobi PDEs in image processing

Keywords: Mathematical Morphology, Nonlinear PDEs, Adaptive Filtering

Multiscale signal analysis has been used since the early 1990s as a powerful tool for image processing, notably in the linear case. However, nonlinear PDEs and associated nonlinear operators have advantages over linear operators, notably preserving important features such as edges in images. In this paper, we focus on nonlinear Hamilton-Jacobi PDEs defined with adaptive speeds or, alternatively, on adaptive morphological fiters also called semi-flat morphological operators. Semi-flat morphology were instroduced by H. Heijmans and studied only in the case where the speed (or equivalently the filtering parameter) is a decreasing function of the luminance. It is proposed to extend the definition suggested by H. Heijmans in the case of non decreasing speeds. We also prove that a central property for defining morphological filters, that is the adjunction property, is preserved while dealing with our extended definitions. Finally experimental applications are presented on actual images, including connection of thin lines by semi-flat dilations and image filtering by semi-flat openings.

INTRODUCTION

In image processing important problems such as image smoothing, detecting events (e.g. edges, peaks) or removing noises from an image often require analysing a signal at multiple spatial or intensity scales. Until now, most of these problems have been addressed using linear filters or PDE. [START_REF] Guichard | Contrast invariant image analysis and PDEs[END_REF] There is however, a variety of nonlinear filters such as openings and closings that could be used providing some advantages over linear filters, notably leaving the edges unchanged.

Most nonlinear filters are based on a PDE whose role is to link scale shifting to spatial shifting. [START_REF] Brockett | Evolution equations for continuous-scale morphological filtering[END_REF][START_REF] Guichard | Partial differential equations for morphological operators[END_REF][START_REF] Crandall | Viscosity Solutions: A Primer[END_REF] For this purpose, Hamilton-Jacobi PDEs are a very productive tool. They are nonlinear differential equations of type ∂F ∂t = V (F (x, y, t)) • ∥∇F ∥ with V a function depending on the solution. Because of this dependence, V gives the PDE an adaptive characteristic.

It has been shown that solving the case V constant, namely the linear case of Hamilton-Jacobi PDEs, has the same effect as applying to a function some morphological operators, namely operators over a complete lattice. [START_REF] Guichard | Contrast invariant image analysis and PDEs[END_REF] A complete lattice is a set fitted with a total or partial order, whose every subset has an inferior and a superior bounds. The complete lattice is mainly used afterwards applied to the set of grey-scale images, which means the set of functions from a bounded subset of R 2 (or Z 2 ) in a bounded subset of R (or Z), fitted with the classical order on functions. [START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF] The case V = 1 and V = -1 match respectively the dilatation and erosion operators defined for numerical functions. [START_REF] Brockett | Evolution equations for continuous-scale morphological filtering[END_REF][START_REF] Guichard | Partial differential equations for morphological operators[END_REF] As illustrated in Fig 1, if X ⊆ R 2 and B is the unit ball, then the dilation of a set X by a ball B is obtained by taking the union of all points included in the ball placed successively in such a way that its center covers all elements in X. The erosion of a set X by B is obtained by keeping the points x of X such that the unit ball centered in x is entirely included in X. Formal definitions are: • Dilation:

X ⊕ B = b∈B X b • Erosion: X ⊖ B = b∈B X -b
Where X b is the set X translated by the vector b:

X b = {x + b | x ∈ X}
Now, dilations and erosions are defined for functions by the level set extension paradigm. [START_REF] Guichard | Partial differential equations for morphological operators[END_REF][START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF]6 This point will be detailed in the following section of this paper.

More elaborated useful cases of Hamilton-Jacobi are presented in. [7][START_REF] Maragos | Morphological scale-space representation with levelings[END_REF][START_REF]Méthodes à ensembles de niveau en analyse d'images[END_REF][START_REF] Tremblais | Shock filters and mathematical morphology[END_REF][START_REF] Aujol | Traitement d'images par approches variationnelles et équations aux dérivées partielles[END_REF] Relying on all these existing works, one can think solving Hamilton-Jacobi PDEs in the general nonlinear case also has the effect of other morphological operators, that can be used in image processing.

In this paper, the purpose of the first part is to introduce flat and classical semi-flat morphology, respectively operating with a constant and decreasing family of morphological operators. The second part is devoted to extending these tools in the general case of any family of operators, and showing that this transformation is adjunction-preserving. In the last part, the results of experimental applications of morphological filters to images are gathered.

FLAT AND SEMI-FLAT MORPHOLOGIES

Flat morphology

Flat morphology [START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF]6 consists in applying the same morphological operator to an indexed family of sets, for example the level sets of a function or the grey scales of an image. The morphological operator used will mostly be a dilation or an erosion.

To begin with, the notion of level set of a function should be introduced. Let L be a complete lattice and F : E → L a function. There are two ways to define the level sets of F :

X(F, s) = {x ∈ E | F (x) ≥ s} or Y (F, s) = {x ∈ E | F (x) > s}
X(F, s) and Y (F, s) define the part of E for which the function is above a certain value s. Their difference lies in whether the points of the function itself should be included or not. See Fig. 2 for an illustration of a function and its level sets.

For a given function F , we now apply a constant set dilation (or erosion) to its level sets to create a dilated (or eroded) function from F . The same can be done with a grey scale image by applying a constant set dilation (or erosion) to the sets formed by the level sets of the function (R 2 → R + or N 2 → N) representing the image.

A dilation δ applied to the function F level sets is shown on Fig. If δ is a set dilation, then the operator ∆ that transforms every function

F : x → F (x) into x → sup{s ∈ L | x ∈ δX(F, s)}
also defines a dilation. Of course the same holds for erosions. When applying flat dilations or erosions to functions, the dilations or erosions being defined using balls of increasing size t, we obtain the same results as resolving the Hamilton-Jacobi PDE special cases of V = 1 and V = -1 seen in the introduction. 2, 3

Semi-flat morphology with an ordinary decreasing family of morphological operators

Let L be a complete lattice and F : E → L a function. Adaptive morphology is defined by Heijmans in 6 for a decreasing family (ψ s ) s∈L of increasing operators (for all s ≤ s ′ ∈ L, ψ s ′ ≤ ψ s and for all s ∈ L, and ψ s is supposed to be an increasing operator. The semi-flat extension of the family (ψ s ) s∈L consists in applying for each s ∈ L the operator ψ s to the level set X(F, s) of F , then reconstructing the function whose level sets are ψ s (X(F, s)). 6 The resulting function is defined by

x → sup{s ∈ L | x ∈ ψ s X(F, s)}
We know for sure that we will be able to do this reconstruction because the images of stacked level sets by a decreasing family of operators are also stacked, which means that those images are still the level sets of a properly defined function.

We show in Fig. 4 the transformation of F by an adaptive morphology using a family (δ s ) s∈L such that δ s is a dilation by a ball whose radius gets smaller as s increases. Here lies one of the main goals of this paper: extending the notion of adaptive morphology to any family (ψ s ) s∈L of morphological operators. It implies as a first step that we should be able to apply the operator ψ s to X(F, s) for each s and still obtain a properly defined function. Unfortunately, as the family (ψ s ) is not supposed to be decreasing any more, the transformed sets ψ s (X(F, s)) may not remain stacked, as it is enhanced in Fig. 5.

Hence, the reconstruction of a function is not immediate.

Two solutions to this problem are graphically described on Fig. ?? : sup-envelope and inf-envelope. Intuitively, the sup-envelope acts as water falling in a fountain, following the borders delimited by the extremities of the transformed level sets. The inf-envelope is inferred by the same idea applied to the opposite function -F . The formal definitions of these envelopes are the following ones: if (Z(s)) s∈L is a family of subsets of E, then

• the sup-envelope is defined by

F : E → T x → sup{s ∈ L | x ∈ Z(s)}
• and the inf-envelope is defined by

F : E → T x → inf{s ∈ L | x / ∈ Z(s)}
Now, for defining semi-flat extensions of families of set operators, one can set Z(s) = ψ s (X(F, s)) or Z(s) = ψ s (Y (F, s)) in order to define transformed functions as inf-or sup-envelopes.

Special case of adaptive dilations and erosions

The semi-flat extension of families of set operators being defined for any family, let us prove now that some useful properties satisfied in the case of decreasing families are still true even if the family is not decreasing. We will focus on the adjunction property that plays a central role in mathematical morphology for defining morphological filters, that is, operators acting on images that are idempotent. [START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF] Let L, M be complete lattices, ε an operator from L to M, and δ an operator from M to L. The pair (ε, δ) is called an adjunction between L and M if

∀X ∈ L, ∀Y ∈ M, δ(X) ≤ X ⇔ Y ≤ ε(X)
Adjunctions are narrowly linked to dilations and erosions. Indeed, if the pair (ε, δ) is an adjunction, then ε must be an erosion and δ a dilation. But here dilations and erosions are to be understood in the broader sense of algebraic dilations and algebraic erosions.

An algebraic dilation is any operator which commutes with union (δ( i∈I Y i )= i∈I δ(Y i )) and an algebraic erosion is any operator which commutes with intersection (ε( i∈I Y i )= i∈I ε(Y i )). Given an adjunction (ε, δ), the products εδ and δε respectively define openings and closings. Let (ε s , δ s ) s∈R be a family of adjunctions on R 2 . Let us define Σ and ∆, two morphological operators such that for any function F from a compact subset of R 2 to R, Σ(F ) is the inf-envelope of the level sets of F eroded by the family (ε s ) s∈L and ∆(F ) is the sup-envelope of the level sets of F dilated by the family (δ s ) s∈L :

Σ : C(R 2 , R) → C(R 2 , R) F → Σ(F ) : x → ∧{s ∈ R | x / ∈ εsX(F, s)} ∆: C(R 2 , R) → C(R 2 , R) F → ∆(F ) : x → ∨{s ∈ R | x ∈ δsY (F, s)}
Strict and large level sets in the definition of Σ and ∆ are chosen in a way that makes the following property true and C(R 2 , R) is the subset formed by all functions of F(R 2 , R) with compact support. Then, as we have the following relation on the complementaries:

Theorem (Σ, ∆) is an adjunction on C(R 2 , R). Proof Let us prove that ∀F, G ∈ C(R 2 , R) , ∆(F ) ≤ G ⇐⇒ F ≤ Σ(G) Forward Let F, G ∈ C(R 2 , R). As ∀y ∈ R 2 , ∆(F )(y) ≤ G(y), then ∨{s | y ∈ δsY (F, s)} ≤ G(y), so ∀s ∈ T , y ∈ δsY (F, s) =⇒ s ≤ G(y).
εs(X(G, s)) c ⊆ Y (F, s) c
We deduce for the inferior bounds that ∀x,

∧{s | x ∈ εs(X(G, s)) c } Σ(G)(x) ≥ ∧{s | x ∈ Y (F, s) c } F (x)
Eventually, we obtain:

Σ(G) ≥ F Backward Let F, G ∈ C(R 2 , R). As ∀x ∈ R 2 F (x) ≤ Σ(G)(x), then F (x) ≤ ∧{s | y / ∈ εsX(G, s)}, so ∀s ∈ T , x / ∈ εsX(G, s) =⇒ F (x) ≤ s.
We deduce εs(X(G, s)

) c ⊆ {x | F (x) ≤ s}.
Moreover, as we obtain the following relation on the complementaries:

{x | F (x) ≤ s} c ⊆ εs(X(G, s)) so δs({x | F (x) > s}) ⊆ X(G, s)
Consequently, on the superior bounds we have the following :

∨{s | x ∈ δsY (F, s)} ∆(F )(x) ≤ ∨{s | x ∈ X(G, s)} G(x)
We finally deduce:

∆(F ) ≤ G

Adaptation of the definitions in Z

In numerical image processing, one deals with discrete functions. Thus, one has to make sure that the definitions and the properties that were given in the continuous case are still valid for discrete functions, that is, for any function F from a compact support of Z 2 to Z. First, note that the operators sup and inf behave differently in R and in Z:

if n ∈ Z then sup{s ∈ R |s < n} = n and sup{s ∈ Z |s < n} = n -1.
Consequently, the proof given in section 3.2 is not correct in Z.

So the definitions of Σ and ∆ have to be modified to fit in Z.

Let (εs, δs) s∈Z be a family of adjunctions on Z 2 , if

Σ : C(Z 2 , Z) → C(Z 2 , Z) F → Σ(F ) : x → ∧{s ∈ Z | x / ∈ εs+1Y (F, s)} ∆: C(Z 2 , Z) → C(Z 2 , Z) F → ∆(F ) : x → ∨{s ∈ Z | x ∈ δsX(F, s)} then Theorem (Σ, ∆) is an adjunction on C(Z 2 , Z).
Proof Let us prove that

∀F, G ∈ C(Z 2 , Z) , ∆(F ) ≤ G ⇐⇒ F ≤ Σ(G)
We may notice that the following definitions are equivalent:

• Σ(F )(x) :

⎧ ⎨ ⎩ = ∧{s ∈ Z| x / ∈ εs+1X(F -1, s)} = ∧{s ∈ Z| x / ∈ εs+1Y (F, s)} = ∧{s ∈ Z| x / ∈ εsY (F -1, s)} -1 • ∆(F )(x) : = ∨{s ∈ Z|x ∈ δsY (F + 1, s)} = ∨{s ∈ Z|x ∈ δsX(F, s)}
The proof below is very similar to the one using operators on R 2 . It aims at justifying the change of definitions of ∆ and Σ in order to keep the adjunction property true.

Forward

Let F, G ∈ C(Z 2 , Z). As ∀y ∈ Z 2 , ∆(F )(y) ≤ G(y), then ∨{s | y ∈ δsY (F + 1, s)} ≤ G(y), so ∀s ∈ Z, y ∈ δsY (F + 1, s) =⇒ s ≤ G(y). We deduce Y (F + 1, s) ⊆ εs({y | G(y) ≥ s}),
and by adjunction Y (F, s) ⊆ εs({y | G(y) ≥ s}),

which means Y (F + 1, s) ⊆ εs(X(G, s)).
Then, as we have the following relation on the complementaries:

εs(X(G, s)) c ⊆ Y (F + 1, s) c
Then, on the inferior bounds ∀x, it is successively true that

∧{s | x ∈ εs(X(G, s)) c } ≥ ∧{s | x ∈ Y (F + 1, s) c } ∧{s | x / ∈ εs(X(G -1, s -1))} ≥ ∧{s |F (x) + 1 ≤ s} ∧{s + 1 | x / ∈ εs+1(X(G -1, s))} ≥ ∧{s + 1 |F (x) ≤ s} ∧{s | x / ∈ εs+1(X(G -1, s))} Σ(G)(x) +1 ≥ ∧{s |F (x) ≤ s} F (x)

+1

Eventually, we obtain:

Σ(G) ≥ F Backward Let F, G ∈ C(Z 2 , Z). As ∀x ∈ Z 2 , F (x) ≤ Σ(G)(x), then F (x) ≤ ∧{s | y / ∈ εs+1X(G -1, s)}, so ∀s ∈ Z, x / ∈ εs+1X(G -1, s) =⇒ F (x) ≤ s. We deduce εs+1(X(G -1, s)) c ⊆ {x | F (x) ≤ s},
Consequently, we have the following relation on the complementaries:

{x | F (x) ≤ s} c ⊆ εs+1(X(G -1, s)) δs+1({x | F (x) > s}) ⊆ X(G -1, s)
Then, on the superior bounds, it is successively true that

∨{s | x ∈ δs+1Y (F, s)} ≤ ∨{s | x ∈ X(G -1, s)} ∨{s | x ∈ δs+1Y (F + 1, s + 1)} ≤ ∨{s |G(x) -1 ≥ s} ∨{s -1 | x ∈ δsY (F + 1, s)} ≤ ∨{s -1 |G(x) ≥ s} ∨{s | x ∈ δsY (F + 1, s)} ∆(F )(x) -1 ≤ ∨{s |G(x) ≥ s} G(x) -1
We eventually obtain:

∆(F ) ≤ G

EXPERIMENTAL APPLICATIONS

We first show how adaptive operators work on numerical images for various structuring elements. Then, we illustrate two applications of adaptive closings and openings. Finally we present an idea of how to remove noises from images using adaptive morphology.

Effect of diverse semi-flat dilations and erosions

The classical grey-tone image "Lena" is used as reference image for all the transformations. The dynamic of the image were reduced to 128 (instead of 256) for implementation reasons.

In Fig. 6, a square structuring element of size 11 -(2f loor((s -1)/20) + 1)), for s ≤ 101 (where s is the grey level) were used. The effect of the associated semi-flat closing is presented: only the zones of low grey levels are closed ; zones of highest grey-levels are left unchanged. In, the example of Fig. ??, the size of the structuring element is now increasing with the intensity: zones of highest grey-levels are dilated, eroded or closed.

Connection of thin lines by semi-flat dilation

The fig. 8 illustrates the behavior of a semi-flat dilation of type 1 (the type as the one presented in figure 6) and its use for reconnecting thin contours lines. Here the goal is to extract the roads in the air image. The semi-flat operator preserves high intensities while dilating points of lowest intensity. The result is that crest lines of the original image are preserved while holes (due to noise, umbra or vegetation) are filled. In the example of figure 9, a color image is processed. As classically in mathematical morphology, the function values of the color map are ordered. The ordering is shown as a grey-tone image. In this example, the ordering is defined as a distance map, the colors set of reference containing the colors of the flowers. Semi-flat filters are then applied on the color image. The structuring element is of type 2 (see figure 7). Thus, the zones of high distance from the reference are hardly filtered while the flowers (as every point of low distance) are preserved.

Here openings and closings have been sequentially applied on the image in order to process white and dark zones as well.

CONCLUSION

In this paper, semi-flat morphological transformations of grey-scale images were proposed that are valid when applying any kind of set operators on the level sets of the image. One important result is that couples of operators defining adjunctions can be defined using the proposed paradigm. This guarantees that idempotent operators can be obtained if the family of set operators is chosen in this perspective.

Semi-flat transformations are intensity-adaptive transformations: the image shapes are processed according to their grey-levels. Usefulness of such kind of transformations were illustrated by some examples. Other applications could involve image denoising (for radar images for instance as the local noise intensity is linked to the local luminance in the image), image simplification (if the intensity 0 is redefined as a reference luminance) and contrast enhancement (see intensity-adaptive filters as a variant of the shock filters).

One key point of the work on that subject will be the implementation. As suggested in, 12 numerical implementations of PDE governing multi-scale adaptive dilations and erosions could be useful.

Figure 1 .Figure 2 .

 12 Figure 1. Erosion and dilation in R 2

3

 3

Figure 3 .

 3 Figure 3. Dilation of F

Figure 4 .Figure 5 .

 45 Figure 4. The semi-flat extension paradigm

  We deduce δsY (F, s) ⊆ {y | G(y) ≥ s}, and by adjunction Y (F, s) ⊆ εs({y | G(y) ≥ s}), which means Y (F, s) ⊆ εs(X(G, s)).

  Figure 6. Example of semi-flat operators in the case of a non decreasing family of set operators.

  Figure 7. The same as figure 6 using a "reverse" structuring element.

Figure 8 .

 8 Figure 8. Connection of thin lines by semi-flat dilation

Figure 9 .

 9 Figure 9. Simplification of a color image by adaptive filtering of a distance map.


Estelle DUCOM Université Rennes 2 Haute Bretagne

Fringe belts in French cities : Comparative study of Rennes, Nantes, Tours.

Urban morphology has been neglected by the French nouvelle géographie, having been adjudged too traditional and empirical. A notable instance of this is the fringe-belt concept, which has been almost unexplored in France. But this concept has theoretical -including deductive -dimensions that could help to revive urban morphology within francophone geography (Ducom, 2003[START_REF] Ducom | Le modèle des fringe belts: la forme urbaine revisitée. Pour une compréhension des processus de renouvellement physique des villes[END_REF]. Three aspects will be considered in this paper. First, the pertinence of the fringe-belt model to French cities, which has become evident in my current comparative study of Rennes, Nantes and Tours, three medium size French cities not too damaged by the air raids of the Second World War.

Fig. 1: Three cities in West France.

It underscores the importance of embedded fringe belts in the current cities' form, even if there are morphological differences du to each city's site, history, functions and size [START_REF] Michael | Morphogenesis, fringe belts and urban size: an exploratory essay[END_REF]. Second, the processes of fringe-belts formation will be analysed. This will eventually bring to the fore the issue of the validity of the model in a current context of strong public planning, since the land occupation is now decided by the public authorities and not by spontaneous economic processes any more.

I-

The memory of forms M.R.G. [START_REF] Conzen | Alnwick, Northumberland: a study in town-plan analysis Institute of British Geographers Publication[END_REF] defined the fringe belt as "a belt-like zone originating from the temporarily stationary or very slowly advancing of a town and composed

1 2 3 4
of a characteristic mixture of land-use units initially seeking a peripheral location". Institutions like hospitals, universities, parks, cemeteries, jails, military barracks or large houses isolated on large plots are typical of the type of land uses that would locate at the urban fringe during periods of slow urban growth. When the urban growth resumes, the hiatus leaves a permanent mark in that the fringe belt becomes embedded in the urban area. Such marks have remained very obvious and can be observed in Rennes, Nantes and Tours. The observation of maps of the eighteenth century (fig. 2-3-4.1) shows the burgeoning of institutions outside the townwalls. Most of them are religious, but there are also a few health and military institutions outside the town walls, still in the country. These zones have remained after started urban growth beyond the walls and form the current inner fringe belt.

But the medium belt mostly developed at the beginning of the nineteenth century (fig. 2-3-4.2). Several types of fringe belts can be distinguished at this time, corresponding to the cities' functions. Thus, whereas Rennes's and Tours's nineteenth century fringe belts are mostly composed of schools (picture 1), military barracks (picture 2) and jails, large houses (picture 3), hospitals, sportyards, parcs (picture 4), railwaystations, Nantes's fringe belt is occupied by the same heterogeneous land use and also by many industrial buildings and plots (pictures 5 and 6).

Picture 1 picture 2 Ecole d'agriculture des trois croix, Rennes.

Military barracks, Tours.

Picture 3 picture 4 Manoir de la Touche, Rennes.

Jardin botanique, Tours.

Picture 5 picture 6 Maison des syndicats, Nantes.

Manufactures de tabac, Nantes.

Parts of these belts became embedded in the urban fabric (fig. 5), whereas others were alienated by the urban growth (fig. 6). 3). Thus, the fringe belt has partly remained and a density map illustrates that high density urban extension have develop beyond this area (5.4, 2002).

On the contrary, fig. 6 illustrates the case of an alienated part of the same nineteenth century fringe belt. The aerial photo (6.1, 1885) shows Rennes's railway. The city has not yet grown beyond the railway to the South, and all we notice is the jail and a manor called Villeneuve. The Sacré Coeur church was built from 1908 to 1911 (6.2), in the country, preparing the development of the city to the south. Nowadays, it is embedded in a residential area (6.3, 2002). At the background, we can see the steeple of the church surrounded by houses from the 1930'. In this example, the fringe belt was alienated by the residential growth of the 1930', and the density map (6.4, 2002) shows the densification phenomena that happened in this area.

Nowadays, major differences distinguish those three cities' fringes. Rennes has a very obvious outer fringe belts corresponding to the green belt and the ring road.

There is no similar fringe belt in Nantes and Tours, whose suburbs spread without any morphological rupture.

II-Processes of fringe belts formation

The fringe-belt concept was linked to land-rent theory by J.W.R. [START_REF] Whitehand | Urban-rent theory, time series and morphogenesis: an example of eclecticism in geographical research[END_REF] who associated the creation of fringe belts with slumps in residential building and periods of low land values. It has been shown that these dynamics, combined with geographical obstacles, generate an urban area in which compact residential growth zones alternate with more loosely-structured fringe belts.

Concerning the building fluctuations, heterogeneous sources were available. First, statistics stemming from the different censuses (municipal censuses from 1822 to 1930 and INSEE censuses from 1946 to 1999), then the number of authorised and built houses and flats during the 25 last years obtained from the Direction régionale de l'équipement. Finally, statistics concerning the year of construction of houses and flats, which must be specified by the owners when paying the land tax.

Comparing the building cycles from 1800 to 2000 of our three cities (fig. 7) lays emphasis on important simultaneous hiatus in house and flat building, first in the first half of the nineteenth century, then at the very beginning of the twentieth century and of course during the Second World War, and finally between 1975 and 1990. At the same time, comparing ancient maps of the cities, those periods seem to be those of the creation of inner fringe belts, which had begun to form well before the nineteenth century, and medium fringe belts, which correspond to Edwardian fringe belts in the English speaking world, nevertheless with an important scale difference. Edwardian fringe belts are large and remain obviously in the townscape, whereas nineteenth century fringe belts in France contain very fewer openlands, which contributed to their alienation. They are also situated much nearer the city center than Edwardian fringe belts. These belts, formerly at the edge of the built up area and then embedded within it, survived long after renewed residential growth, despite the fact that parts of these fringe belts were alienated. Thus, they are nowadays discontinuous.

According to these observations, there seem to be an obvious link between the building cycles and the formation of fringe belts. But other factors than the housebuilding slumps have contributed to the development of fringe belts, especially the presence of fixation lines like townwalls, railways, rivers, presence of poorly drained zones to the south of Rennes and around the Loire in Nantes and Tours, where the river constituted an important obstacle to the urbanisation.

Moreover, the link between the fringe belt at the current edge of the agglomeration of Rennes and a recent house building slump is harder to prove. This slump did not lead to the creation of an outer fringe belt in Nantes or Tours… Whereas the inner fringe belts were obviously to a considerable extent the product of economic factors, the fringe belt at Rennes' current urban fringe seems to have been strongly influenced by the city green belt policy from about 1960. This brings to the fore the question of the validity of the model in a current context of strong public planning, since the land occupation is now decided by the public authorities and not by spontaneous economic processes any more.

III-Is the fringe-belt model still valid?

Until the beginning of the twentieth century, urban areas were very limited in space. The progressive urban growth was mostly the result of individual initiatives.

Put simply, there was almost no urban planning policy until the Second World War. If the law "Le Cornudet" (March 1919) dealt with the "Plans d'aménagement, d'embellissement et d'extension", the first plans were vague and mostly limited to the city centre. There was no global extension project.

The municipal authorities just accompanied the urban growth or even tried to further its spontaneous development, and never tried to control or limit it.

However, from the Second World War and the reconstruction onwards, the first planning policies were established very differently in Rennes, Nantes and Tours. The "plan Lefort" was Rennes's first global extension and town planning. The planners tried to densify the inner urban area to limit its outward extension on the one hand, and to favour the development of the surrounding towns on the other, with a view to making a polycentric city where mobility was strongly facilited. As a result, it is often said that until the 1960's, Rennes was a city without suburbs. It is significant to notice that the "Plan Lefort" already reserved large zones for public services, sports yards, cemeteries and a non aedificandi zone surrounding the built up area.

In the same way, a successful green belt policy associated with the presence of a ring road (progressive construction from 1968 to 1995) strongly influenced the formation of a fringe belt at the current edge of the urban area. The green belt and the ring road play the role of a fixation line, like the boulevards in the nineteenth century [START_REF] Darin | French belt boulevards[END_REF]. This outer fringe belt is composed of large military zones, allotments, and green open spaces. This fringe belt acts like a barrier containing the urban sprawl.

On the contrary, Tours and Nantes spread considerably in the absence of an outer green belt. It is significant to notice that in the same building cycle conditions, Nantes and Tours don't have a proper outer fringe belt. Nevertheless, Rennes's planned fringe belt has been contested for a few years, as it represents an important land stock. (Ducom, 2003). First alienations are planned, for instance on ancient military zones where residential extensions are in progress. But the strongest pressure for change and intensification concerns the surviving inner and medium fringe belts (picture 7), which are parts of the historico-geographical development of cities but which are rarely taken in account as entities by planners [START_REF] Whitehand | Fringe belts and the recycling of urban land: an academic concept and planning practice[END_REF]. Thus, within the framework of "renouvellement urbain", one of the burning issues of urban planning is the problem of densification of certain parts of the cities, precisely inner and medium fringe belts, which resist quiet well to intensification. Some sites of these remaining fringe belts have become deeply rooted in mental maps.

To that point of view, the fringe belt model could help the planners in their decision making.

Picture 7: Rennes: Construction of a shopping center in the inner fringe belt.

Fig. 2 :

 2 Fig. 2 : Rennes (1-1720, 2-1879, 3-2002, 4-2003)

  Fig. 5 fig. 6 Partly remaining fringe belt, West Rennes Alienated fringe belt, South Rennes

Fig. 5 .

 5 Fig.5.1 was taken in 1885 from an airship at 800 meters high. The hospital Pontchaillou was just a farm, the "Boulevard de l'Ouest", now in the city and named Bd de Verdun, was in the country, like the railway. There was only a barrack (caserne Mac Mahon) which still exists and a manor. In 1900, the military barrack and the first construction of the hospital Pontchaillou are visible (5.2). Those huge plots have remained and are still visible in the area in 2000 (5.3). Thus, the fringe belt has partly remained and a density map illustrates that high density urban extension have develop beyond this area(5.4, 2002).

Fig. 9 :Fig. 7 :

 97 Fig. 9: Building cycle in Nantes from 1800 to 2002