Paul-Marie Samson

TRANSPORT-ENTROPY INEQUALITIES ON LOCALLY ACTING GROUPS OF PERMUTATIONS

Keywords: Mathematics Subject Classification. 60E15, 32F32, 39B62, 26D10 Concentration of measure, Random permutation, Symmetric group, Slices of the discrete cube, Transport inequalities, Ewens distribution, Chinese restaurant process, Deviation's inequalities for configuration functions

Transport-entropy inequalities on locally acting groups of permutations

Introduction

Let S n denote the symmetric group of permutations acting on a set Ω of cardinality n, and µ o denote the uniform law on S n , µ o (σ) := 1 n! , σ ∈ S n . A seminal concentration result on S n obtained by Maurey is the following.

Theorem 1.1. [START_REF] Maurey | Construction de suites symétriques[END_REF] Let d H be the Hamming distance on the symmetric group, for all σ, τ ∈ S n , d H (σ, τ) := i∈Ω 1 σ(i) τ(i) .

Then for any subset A ⊂ S n such that µ o (A) ≥ 1/2, and for all t ≥ 0, one has

µ o (A t ) ≥ 1 -2e -t 2 64n
, where A t := {y ∈ S n , d H (x, A) ≤ t}.

Milman and Schechtman [START_REF] Milman | Asymptotic theory of finite-dimensional normed spaces[END_REF] generalized this result to some groups whose distance is invariant by translation. For example, in the above result we may replace (up to constants) the Hamming distance by the transposition distance d T (σ, τ) that corresponds to the minimal number of transpositions t 1 , ..., t k such that σt 1 • • • t k = τ. The distances d T and d H are comparable, 1 2 d H (σ, τ) ≤ d T (σ, τ) ≤ d H (σ, τ) -1, ∀σ τ.

(We refer to [START_REF] Bobkov | The subgaussian constant and concentration inequalities[END_REF] for comments about these comparison inequalities).

Let us also observe that Theorem 1.1 can be also recover from the transportation cost inequality approach of Theorem 1 of [START_REF] Marton | Measure concentration and strong mixing[END_REF].

A few years later, a stronger concentration property in terms of dependence in the parameter n, has been settled by Talagrand using the so-called "convex-hull" method [START_REF] Talagrand | Concentration of measure and isoperimetric inequalities in product spaces[END_REF] (see also [START_REF] Ledoux | The concentration of measure phenomenon[END_REF]). This property implies Maurey's result with a slightly worse constant. Let us recall some notations from [START_REF] Talagrand | Concentration of measure and isoperimetric inequalities in product spaces[END_REF]. For each A ⊂ S n and σ ∈ S n , let V(σ, A) ⊂ R Ω be the set of vectors z = (z j ) j∈Ω ∈ R Ω with z j := 1 σ( j) y( j) for y ∈ A. Let conv(V(σ, A)) denote the convex hull of V(σ, A) in R Ω , V(σ, A) := ß x = (x j ) j∈Ω , ∃p ∈ P(A), ∀ j ∈ Ω, x j = 1 σ( j) y( j) dp(y) ™ , where P(A) denotes the set of probability measures on A. Talagrand introduced the quantity f (σ, A) := inf{ x 2 2 ; x ∈ conv(V(σ, A))}. with x 2 2 := i∈Ω x 2 i , that measures the distance from σ to the subset A. Theorem 1.2. [START_REF] Talagrand | Concentration of measure and isoperimetric inequalities in product spaces[END_REF] For any subset A ⊂ S n , S n e f (σ,A)/16 dµ o (σ) ≤ 1 µ o (A) .

Maurey's concentration result easily follows by observing that

f (σ, A) ≥ 1 n inf i∈Ω x i ; x ∈ conv(V(σ, A)) 2 = 1 n d 2 H (σ, A)
and applying Tchebychev inequality with usual optimization arguments. Talagrand's result has been first extended to the uniform probability measure on product of symmetric groups by McDiarmid [START_REF] Mcdiarmid | Concentration for independent permutations[END_REF], and then further by Luczak and McDiarmid to cover more general permutation groups which act suitably "locally" [START_REF] Luczak | Concentration for locally acting permutations[END_REF].

For any finite subset A, let #A denote the cardinality of A. For any σ ∈ S n , the support of σ, denoted by supp(σ), is the set {i ∈ Ω, σ(i) i} and the degree of σ, denoted by deg(σ), is the cardinality of supp(σ), deg(σ) := # supp(σ).

By definition, according to [START_REF] Luczak | Concentration for locally acting permutations[END_REF], a group of permutations G is ℓ-local, ℓ ∈ {2, . . . , n}, if for any σ ∈ G and any i, j ∈ Ω with σ(i) = j, there exists τ ∈ G such that supp(τ) ⊂ supp(σ), deg(τ) ≤ ℓ and τ(i) = j.

The orbit of an element j ∈ Ω, denoted by orb( j), is the set of elements in Ω connected to j by a permutation of G, orb( j) := σ( j), σ ∈ G .

The set of orbits provides a partition of G.

As explained in [START_REF] Luczak | Concentration for locally acting permutations[END_REF], any 2-local group is a direct product of symmetric groups on its orbits, the alternating group (consisting of even permutations) is 3local, and any 3-local group is a direct product of symmetric or alternating groups on its orbits.

In the present paper, the concentration result by Luczak-McDiarmid and Talagrand is a consequence of a weak transport-entropy inequality satisfied by the uniform law on G, µ o . We also prove weaker types of transport entropy inequalities. Moreover we extend the results to a larger class of probability measures on G, denoted by M.

For a better comprehension of the class of measures M, let us first consider the case of the symmetric group S n on [n] := {1, . . . , n}. Let (i, j) denote the transposition in S n that exchanges the elements i and j in [n]. It follows by induction that the map

{1, 2} × {1, 2, 3} × • • • × {1, . . . , n} → S n U : i 2 , i 3 , . . . , i n → (i 2 , 2)(i 3 , 3) • • • (i n , n),
is one to one. The set of measures M consists of probability measures on S n which are pushed forward by the map U of product probability measures on {1, 2} × {1, 2, 3} × • • • × {1, . . . , n},

M := U#ν, ν = ν2 ⊗ • • • ⊗ νn with ν j ∈ P([ j]), ∀ j ∈ {2, . . . , n} , (1)
where by definition U#ν(C) = ν(U -1 (C)) for any subset C in S n .

The uniform measure µ o on S n belongs to the set M since µ o = U# μ with μ = μ2 ⊗ • • • ⊗ μn , where for each i, μi denotes the uniform law on [i].

The Ewens distribution of parameter θ > 0, denoted by µ θ , is also an example of measure of M. Indeed, it is well known (see [START_REF] Arratia | Logarithmic combinatorial structures: a probabilistic approach[END_REF] Chapter 5], [START_REF] Johnson | Discrete multivariate distributions[END_REF]) that µ θ = U# μθ with μθ = μθ 2 ⊗ • • • ⊗ μθ n , where for any j ∈ {2, . . . , n}, the measure μθ j ∈ P([ j]) is given by

μθ j ( j) = θ θ + j -1 , , μθ j (1) = • • • = μθ j ( j -1) = 1 θ + j -1 .
This definition provides an easy algorithm for simulating a random permutation with law µ θ . This procedure is known as a Chinese restaurant process (see [START_REF] Arratia | Logarithmic combinatorial structures: a probabilistic approach[END_REF] Chapter 2], [START_REF] Pitman | Combinatorial stochastic processes[END_REF]).

Let us observe that the uniform distribution µ o corresponds to the Ewens distribution with parameter 1, µ 1 .

The Ewens distribution is also given by the following expression (see [ABT03, Chapter 5]),

µ θ (σ) := θ |σ| θ (n) , σ ∈ S n , (2)
where |σ| denotes the number of cycles in the cycle decomposition of σ and θ (n) is the Pochhammer symbol defined by

θ (n) := Γ(θ + n) Γ(θ) , with Γ(θ) := +∞ 0 s θ-1 e -s ds.
Let us now construct the class of measures M for any group G of permutations. To clarify the notations, the elements of Ω are labelled with integers, Ω = [n]. Let G n := G and for any j ∈ [n -1], let G j denotes the subgroup of G defined by

G j := {σ ∈ G, σ( j + 1) = j + 1, . . . , σ(n) = n} ,
We denote by O j the orbit of j in G j ,

O j := σ( j), σ ∈ G j . Let us observe that { j} ⊂ O j ⊂ [ j].
Definition 1.1. Let G be a group of permutations. A family T = (t i j , j ) of permutations of G, indexed by j ∈ {2, . . . , n} and i j ∈ O j , is called "ℓ-local base of G" if for every j ∈ {2, . . . , n}, t j, j := id, for every i j j, t i j , j ∈ G j and t i j , j (i j ) = j, and deg(t i j j ) ≤ ℓ.

Lemma 1.1. Let T = (t i j , j ) be a ℓ-local base of a group of permutations G. Then the map O 2 × O 3 × • • • × O n → G U T : i 2 , i 3 , . . . , i n → t i 2 ,2 t i 3 ,3 • • • t i n ,n , (3)
is one to one. Lemma 1.2. Any ℓ-local group of permutations admits a "ℓ-local base".

For completeness, a proof of these two lemmas is given in the Appendix. As a consequence of these lemmas, if G is a ℓ-local group, then there exists a ℓ-local base T , such that the uniform probability measure µ o satisfies µ o = U T # μ, with μ = μ2 ⊗ • • • ⊗ μn , where for each j, μ j is the uniform law on O j .

As for the symmetric group, given a ℓ-local base T of a group G, the class of measures M = M T on G is made up of all probability measures on G which are pushed forward of product probability measures on

O 2 × O 3 × • • • × O n by the map U T defined by (37), M T := U T #ν, ν = ν2 ⊗ • • • ⊗ νn with ν j ∈ P(O j ), ∀ j ∈ {2, . . . , n} . (4)
As explained above, if G is a ℓ-local group, the class M T contains the uniform law µ o on G for a well choosen ℓ-local base T .

In this paper, the concentration results are derived from weak transport-entropy inequalities, involving the relative entropy H(ν|µ) between two probability measures µ, ν on G given by

H(ν|µ) := log Å dν dµ ã dν,
if ν is absolutely continuous with respect to µ and H(ν|µ) := +∞ otherwise.

The terminology "weak transport-entropy" introduced in [GRST15], encompass many kinds of transport-entropy inequalities from the well-known Talagrand's transport inequality satisfied by the standard Gaussian measure on R n [START_REF] Talagrand | Transportation cost for Gaussian and other product measures[END_REF], to the usual Csizár-Kullback-Pinsker inequality [Pin64, Csi67, Kul67] that holds for any (reference) probability measure µ on a Polish metric space X, namely

µ -ν 2 T V ≤ 2 H(ν|µ), ∀ν ∈ P(X). ( 5
)
where µν T V denotes the total variation distance between µ and ν,

µ -ν T V := 2 sup A |µ(A) -ν(A)|.
Above, the supremum runs over all measurable subset A of X. We refer to the survey [START_REF] Samson | High dimensionnal concentration phenomena, transport of measure and functional inequalities[END_REF][START_REF] Samson | Concentration of measure principle and entropy-inequalities[END_REF] for other examples of weak transport-entropy inequalities and their connections with the concentration of measure principle.

The next theorem is one of the main result of this paper. It presents new weak transport inequalities for the uniform measure on G or any measure in the class M T , that recover the concentration results of Theorems 1.1 and 1.2.

We also denote by d H the Hamming distance on G:

for any σ, τ ∈ G, d H (σ, τ) := deg(στ -1 ) = n i=1 1 σ(i) τ(i) ,
and the distance d T (σ, τ) is defined as the minimal number of elements of G, t 1 , ..., t k , with degree less than ℓ, such that

σt 1 • • • t k = τ.
For any measures ν 1 , ν 2 ∈ P(G), the set Π(ν 1 , ν 2 ) denotes the set of all probability measures on G × G with first marginal ν 1 and second marginal ν 2 . The Wasserstein distance between ν 1 and ν 2 , according to the distance d = d H or d = d T , is given by

W 1 (ν 1 , ν 2 ) := inf π∈Π(ν 1 ,ν 2 ) d(σ, τ) dπ(σ, τ).
We also consider two other optimal weak transport costs, T 2 (ν 2 |ν 1 ) and Û T 2 (ν 2 |ν 1 ) defined by

T 2 (ν 2 |ν 1 ) := inf π∈Π(ν 1 ,ν 2 ) Å d(σ, τ) dp σ (τ) ã 2 dν 1 (σ), (6) and Û T 2 (ν 2 |ν 1 ) := inf π∈Π(ν 1 ,ν 2 ) n i=1 Å 1 σ(i) τ(i) dp σ (τ) ã 2 dν 1 (σ),
where p σ represents any probability measure such that π(σ, τ) = ν 1 (σ)p σ (τ) for all σ, τ ∈ G. By Jensen's inequality, these weak transport costs are comparable, namely

W 2 1 (ν 1 , ν 2 ) ≤ T 2 (ν 2 |ν 1 ) ≤ n Û T 2 (ν 2 |ν 1 )
, where the last inequality only holds for d = d H .

By definition a subgroup G of S n is normal if for any t ∈ S n ,t -1 Gt = G.

In the next theorem the constant K n is the cardinality of the set j ∈ {2, . . . , n}, O j { j} . It follows that 0 ≤ K n ≤ (n -1) and K n = 0 if and only if G = {id}.

Theorem 1.3. Let G be a group of permutations with ℓ-local base T . Let µ ∈ P(G) be a measure of the set M T defined by (4).

(a) For all probability measures ν 1 and ν 2 on G, one has

2 c(ℓ) 2 W 2 1 (ν 1 , ν 2 ) ≤ K n » H(ν 1 |µ) + » H(ν 2 |µ) 2 , (7) and 1 2c(ℓ) 2 T 2 (ν 2 |ν 1 ) ≤ K n » H(ν 1 |µ) + » H(ν 2 |µ) 2 , ( 8
)
where c(ℓ) := min(2ℓ -1, n) if d = d H , 2 if d = d T . When µ = µ o is the uniform law of a ℓ-local group G, inequalities (7) and (8) hold with c(ℓ) := ℓ if d = d H , 1 if d = d T . (b) • Assume that µ = µ o is the uniform law of a ℓ-local group G.
Then, for all probability measures ν 1 and ν 2 on G,

(9) 1 2c(ℓ) 2 Û T 2 (ν 2 |ν 1 ) ≤ » H(ν 1 |µ) + » H(ν 2 |µ) 2 , with c(ℓ) 2 = 2(ℓ -1) 2 + 2.
• Assume that G is a normal subgroup of S n , and that µ satisfies for all σ ∈ G, t ∈ S n µ(σ) = µ(σ -1 ) and µ(σ) = µ(t -1 σt). (10) Then, the inequality (9) holds with c(ℓ) 2 = 8(ℓ -1) 2 + 2.

The proofs of these results, given in the next section, are inspired by Talagrand seminal work on S n [START_REF] Talagrand | Concentration of measure and isoperimetric inequalities in product spaces[END_REF], and Luczak-McDiarmid extension to ℓ-local groups [START_REF] Luczak | Concentration for locally acting permutations[END_REF].

Comments :

• If G = S n and the class of measure M is given by (1), the Ewens distribution µ θ introduced before, is an interesting example of measure in M, satisfying condition (10). This simply follows from its expression given by (2), since for any σ,

t ∈ S n , |σ -1 | = |σ| and |t -1 σt| = |σ|.
An open question is to generalize the above transport-entropy inequalities to the generalized Ewens distribution (see the definition in [START_REF] Maples | On the number of cycles in a random permutation[END_REF][START_REF] Hughes | Random permutation matrices under the generalized Ewens measure[END_REF]). This measure no longer belongs to the class of measure M. In other words, no Chinese restaurant process are known for simulating the generalized Ewens distribution.

• From the triangular inequality satisfied by the Wasserstein distance W 1 , the transport-entropy inequality (7) is clearly equivalent to the following transport-entropy inequality, for all probability measure ν on G,

2 c(ℓ) 2 W 2 1 (ν, µ) ≤ K n H(ν|µ).
Here is a popular dual formulation of this transport-entropy inequality: for all 1-Lipschitz functions ϕ : G → R (with respect to the distance d), e ϕ dµ ≤ e ϕ dµ+K n c(ℓ) 2 t 2 /8 , ∀t ≥ 0. (11)

For the uniform measure on S n , K n = n -1 and this property is widely commented in [START_REF] Bobkov | The subgaussian constant and concentration inequalities[END_REF]; it is also a consequence of Hoeffding inequalities for bounded martingales (see page 18 of [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF]). The concentration result derived from item (a) are of the same nature as the one obtained by the "bounded differences approach" in [Mau79, [START_REF] Mcdiarmid | On the method of bounded differences[END_REF][START_REF] Mcdiarmid | Concentration for independent permutations[END_REF][START_REF] Luczak | Concentration for locally acting permutations[END_REF][START_REF] Bercu | Concentration inequalities for sums and martingales[END_REF].

• Similarly, by Proposition 4.5 and Theorem 2.7 of [START_REF] Gozlan | Kantorovich duality for general transport costs and applications[END_REF] and using the identity

Ä √ u + √ v ä 2 = inf α∈(0,1) ß u α + v 1 -α ™ ,
we may easily show that the weak transport-entropy inequality (8) is equivalent to the following dual property: for any real function ϕ on G and for any 0

< α < 1, Å e α Q Kn ϕ dµ ã 1/α Å e -(1-α)ϕ dµ ã 1/(1-α) ≤ 1, ( 12
)
where the infimum-convolution operator ‹ Q t ϕ, t ≥ 0, is defined by

‹ Q t ϕ(σ) := inf p∈P(G) ® ϕ dp + 1 2c 2 (ℓ)t Å d(σ, y) dp(y) ã 2
´, σ ∈ G.

Moreover, let us observe that following our proof of (12) in the next section, for each α ∈ (0, 1) the inequality (12) can be improved by replacing the square cost function by the convex cost c α (u) ≥ u 2 /2, u ≥ 0 given in Lemma 2.2. More precisely, (12) holds replacing

‹ Q K n ϕ by ‹ Q α K n ϕ defined by ‹ Q α t ϕ(σ) := inf p∈P(S n ) ® ϕ dp + tc α Å 1 c(ℓ)t d(σ, y) dp(y) ã 2 ´,
for any σ ∈ G, t > 0. • Proposition 4.5 and Theorem 9.5 of [START_REF] Gozlan | Kantorovich duality for general transport costs and applications[END_REF] also provide a dual formulation of the weak transport-entropy inequality (9): for any real function ϕ on G and for any 0

< α < 1, Å e α Û Qϕ dµ ã 1/α Å e -(1-α)ϕ dµ ã 1/(1-α) ≤ 1, ( 13
)
where the infimum convolution operator Ù Qϕ is defined by

Ù Qϕ(σ) = inf p∈P(G) ϕ dp + 1 2c(ℓ) 2 n k=1 Å 1 σ(k) y(k) dp(y) ã 2 , σ ∈ G.
As explained at the end of this section, the property (13) directly provides the following version of the Talagrand's concentration result for any measure on G of the set M T .

Corollary 1.1. Let G be a group of permutations with ℓ-local base T . Let µ ∈ P(G) be a measure of the set M T defined by (4). Assume that µ and G satisfy the conditions of (b) in Theorem 1.3. Then, for all A ⊂ G and all α ∈ (0, 1), one has

e α 2c(ℓ) 2 f (σ,A) dµ(σ) ≤ 1 µ(A) α/(1-α) ,
with the same definition for c(ℓ) 2 as in part (b) of Theorem 1.3. As a consequence, by Tchebychev inequality, for any α ∈ (0, 1) and all t ≥ 0,

µ {σ ∈ G, f (σ, A) ≥ t} ≤ e -αt 2c(ℓ) 2 µ(A) α/(1-α) .
For α = 1/2 and µ = µ o the uniform law on a ℓ-local group of G, this result is exactly Theorem 2.1 by , that generalizes Theorem 1.2 on S n (since S n is a 2-local group). By projection arguments, Theorem 1.3 applied with the uniform law µ o on the symmetric group S n , also provides transport-entropy inequalities for the uniform law on the slices of the discrete cube {0, 1} n . Namely, for n ≥ 1, let us denote by X k,n-k , k ∈ {0, . . . , n}, the slices of discrete cube defined by

X k,n-k := x = (x 1 , . . . , x n ) ∈ {0, 1} n , n i=1 x i = k .
The uniform law on X k,n-k , denoted by µ k,n-k , is the pushed forward of µ o by the projection map

S n → X k,n-k P : σ → 1 σ([k]) , where σ([k]) := {σ(1), . . . , σ(k)} and for any subset A of [n], 1 A is the vector with coordinates 1 A (i), i ∈ [n]. In other terms, µ k,n-k = P#µ o and µ k,n-k (x) = n k -1 for all x ∈ X k,n-k . Let d h denotes the Hamming distance on X k,n-k defined by d h (x, y) := 1 2 n i=1 1 x i y i , x, y ∈ X k,n-k .
Theorem 1.4. Let µ k,n-k be the uniform law on X k,n-k , a slice of the discrete cube. (a) For all probability measures ν 1 and ν 2 on X k,n-k ,

2 C k,n-k W 2 1 (ν 1 , ν 2 ) ≤ » H(ν 1 |µ k,n-k ) + » H(ν 2 |µ k,n-k ) 2 , and 1 2C k,n-k T 2 (ν 2 |ν 1 ) ≤ » H(ν 1 |µ k,n-k ) + » H(ν 2 |µ k,n-k ) 2 ,
where W 1 is the Wasserstein distance associated to d h , T 2 is the weak optimal transport cost defined by (6) with d = d h , and C k,n-k = min(k, nk). (b) For all probability measures ν 1 and ν 2 on X k,n-k ,

(14) 1 8 T 2 (ν 2 |ν 1 ) ≤ » H(ν 1 |µ k,n-k ) + » H(ν 2 |µ k,n-k ) 2 ,
where

T 2 (ν 2 |ν 1 ) := inf π∈Π(ν 1 ,ν 2 ) n i=1 Å 1 x i y i dp x (y) ã 2 dν 1 (x), with π(x, y) = ν 1 (x)p x (y) for all x, y ∈ X k,n-k .
Up to constants, the weak transport inequality ( 14) is the stronger one since for all ν 1 , ν 2 ∈ P(X k,n-k ),

W 2 1 (ν 1 , ν 2 ) ≤ T 2 (ν 2 |ν 1 ) ≤ n 4 T 2 (ν 2 |ν 1 ).
The proof of Theorem 1.4 is given in section 3. The transport-entropy inequality ( 14) is derived by projection from the transport-entropy inequality (9) for the uniform measure µ o on S n . The same projection argument could be used to reach the results of (a) from the transport-entropy inequality of (a) in Theorem 1.3, but it provides worse constants. The constant C k,n-k is obtained by working directly on X k,n-k and following similar arguments as in the proof of Theorem 1.3.

Remark :

The results of Theorem 1.4 also extend to the multinomial law. Let E = {e 1 , . . . , e m } be a set of cardinality m and let k 1 , . . . , k m be a collection of non-zero integers satisfying k 1 + • • • + k m = n. The multinomial law µ k 1 ,...,k m is by definition the uniform law on the set

X k 1 ,...,k m := ß x ∈ E n , such that for all l ∈ [m], # i ∈ [n], x i = e l = k l ™ . For any x ∈ X k 1 ,...,k m , one has µ k 1 ,...,k m (x) = k 1 !•••k m ! n! .
As a result, the weak transportentropy inequality (14) holds on X k 1 ,...,k m replacing the measure µ k,n-k by the measure µ k 1 ,...,k m . The proof of this result is a simple generalization of the one on X k,n-k , by using the projection map P : S n → X k 1 ,...,k m defined by: P(σ) = x if and only if

x i = e l , ∀l ∈ [m], ∀i ∈ J l , where J l := i ∈ [n], k 0 + • • • + k l-1 < i ≤ k 0 + • • • + k l , with k 0 = 0.
The details of this proof are left to the reader.

A straightforward application of transport-entropy inequalities is deviation's bounds for different classes of functions. For more comprehension, we present below deviations bounds that can be reached from Theorem 1.3 for any measure in M T . A similar corollary can be derived from Theorem 1.4 on the slices of the discrete cube.

For any h : G → R, the mean of h is denoted by µ(h) := h dµ.

Corollary 1.2. Let G be a group of permutations with ℓ-local base T , G {id}. Let µ ∈ P(G) be a measure of the set M T defined by (4). Let g be a real function on G.

(a) Assume that there exists a function β :

G → R + such that for all τ, σ ∈ G, g(τ) -g(σ) ≤ β(τ)d(τ, σ)
,

where d = d T or d = d H .
Then for all u ≥ 0, one has

µ (g ≥ µ(g) + u) ≤ exp Ç - 2u 2 K n c(ℓ) 2 sup σ∈G β(σ) 2 å . and µ (g ≤ µ(g) -u) ≤ exp Ç - 2u 2 K n c(ℓ) 2 min(sup σ∈G β(σ) 2 , 4µ(β 2 )) å ,
where the constants c(ℓ) and K n are defined as in part (a) of Theorem 1.3. (b) Assume that µ and G satisfy the conditions of (b) in Theorem 1.3. Let g be a so-called configuration function. This means that there exist functions

α k : G → R + , k ∈ {1, . . . , n} such that for all τ, σ ∈ G, g(τ) -g(σ) ≤ n k=1 α k (τ)1 τ(k) σ(k) .
Then, for all v ≥ 0, λ ≥ 0, one has

µ Ç g ≥ µ(g) + v + λc(ℓ) 2 |α| 2 2 å ≤ e -λv ,
and for all u ≥ 0,

µ (g ≤ µ(g) -u) ≤ exp Ç - u 2 2c(ℓ) 2 µ |α| 2 2 å , where |α(σ)| 2 2 := n k=1 α 2 k (σ) and c(ℓ) is defined as in part (b) of Theorem 1.3.
We also have, for all u ≥ 0

µ (g ≥ µ(g) + u) ≤ exp Ç - u 2 2c(ℓ) 2 sup σ∈G |α(σ)| 2 2 å , and if there exists M ≥ 0 such that |α| 2 2 ≤ Mg, then for all u ≥ 0 µ (g ≥ µ(g) + u) ≤ exp Ç - u 2 2c(ℓ) 2 M(µ(g) + u) å ,

Comments and examples:

• The above deviation's bounds of g around its mean µ(g) are directly derived from the dual representations (11),( 12),(13) of the transport-entropy inequalities of Theorem 1.3, when α goes to 0 or α goes to 1. By classical arguments (see [START_REF] Ledoux | The concentration of measure phenomenon[END_REF]), Corollary 1.2 also implies deviation's bounds around a median M(g) of g, but we loose in the constants with this procedure. However, starting directly from Corollary 1.1, we get the following bound under the assumption of (b): for all u ≥ 0,

µ(g ≥ M(g) + u) ≤ 1 2 exp Ç -w Ç u √ 2c(ℓ) sup σ∈G |α(σ)| 2 åå , (15)
where

w(u) = u(u -2 √ log 2), u ≥ 0. The idea of the proof is to choose the set A = {σ ∈ G, g(σ) ≤ M(g)} of measure µ(A) ≥ 1/2 and to show that the asumption of (b) implies σ ∈ G, f (σ, A) < t ⊂ ® σ ∈ G, g(σ) < M(g) + t sup σ∈G |α(σ)| 2 ´, t ≥ 0.
Then, the deviation bound above the median directly follows from Corollary 1.1 by optimizing over all α ∈ (0, 1). With identical arguments, the same bound can be reached for µ(g ≤ M(g)u).

• In (a), the bound above the mean is a simple consequence of (11). As settled in (a), this bound also holds for the deviations under the mean, and it can be slightly improved by replacing sup σ∈G β(σ) 2 by 4µ(β 2 ). This small improvement is a consequence of the weak transport inequality with stronger cost T 2 . The same kind of improvement could be reached for the deviations above the mean under additional Lipschitz regularity conditions on the function β.

• Let ϕ : [0, 1] n → R be a 1-Lipschitz convex function and let x = (x 1 , . . . , x n ) be a fixed vector of [0, 1] n . For any σ ∈ G, let x σ := (x σ(1) , . . . , x σ(n) ).
By applying the results of (b) (or even (15)) to the particular function g x (σ) = ϕ(x σ ), σ ∈ G, we recover and extend to any group G with ℓ-local base T and to any measure in M T satisfying (10), the deviation inequality by Adamczak, Chafaï and Wolff [ACW14] (Theorem 3.1) obtained from Theorem 1.2 by Talagrand. Namely, since for any σ, τ ∈ G,

ϕ(x τ ) -ϕ(x σ ) ≤ n k=1 ∂ k ϕ(x τ )(x τ(k) -x σ(k) ) ≤ n k=1 |∂ k ϕ(x τ )|1 τ(k) σ(k) , with n k=1 |∂ k ϕ(x τ )| 2 = |∇ϕ(x τ )| 2 ≤ 1, Corollary 1.2 implies, for any choice of vector x = (x 1 , . . . , x n ) ∈ [0, 1] n , µ(|g x -µ(g x )| ≥ u) ≤ 2 exp Ç - u 2 2c(ℓ) 2 å , u ≥ 0.
This concentration property on S n (with ℓ = 2) plays a key role in the approach by Adamczak and al. [START_REF] Adamczak | Circular law for random matrices with exchangeable entries[END_REF], to study the convergence of the empirical spectral measure of random matrices with exchangeable entries, when the size of the matrices is increasing. • As a second example, for any t in a finite set F , let (a t i, j ) 1≤i, j≤n be a collection of non negative real numbers and consider the function

g(σ) = sup t∈F n k=1 a t k,σ(k) , σ ∈ G.
This function satisfies, for any σ, τ ∈ G,

g(τ) -g(σ) ≤ n k=1 Ä a t(τ) k,τ(k) -a t(τ) k,σ(k) ä 1 τ(k) σ(k) ≤ n k=1 a t(τ) k,τ(k) 1 τ(k) σ(k) ,
where t(τ) ∈ F is chosen so that

g(τ) = n k=1 a t(τ) k,τ(k) .
Let us consider the function

h(σ) = sup t∈F n k=1 (a t k,σ(k) ) 2 , σ ∈ G.
The mean of h, µ(h), can be interpreted as a variance term as regards to g. Observing that g satisfies the condition of (b) with

α k (τ) := a t(τ) k,τ(k)
, and |α| 2 2 ≤ h, Corollary 1.2 provides the following Bernstein deviation's bounds, for all u ≥ 0,

µ (g ≤ µ(g) -u) ≤ exp Ç - u 2 2c(ℓ) 2 µ (h) å ,
and for all λ, v ≥ 0,

µ Ç g ≥ µ(g) + v + λc(ℓ) 2 h 2 å ≤ e -λv .
If the real numbers a i, j are bounded by M, then |α| 2 2 ≤ Mg and therefore Corollary 1.2 also provides for all u ≥ 0,

µ (g ≥ µ(g) + u) ≤ exp Ç - u 2 2c(ℓ) 2 M(µ(g) + u) å .
If we want to bound the deviation above the mean in terms of the variance term µ(h), it suffises to observe that the last inequality provides deviations bounds for the function h, replacing g by h and M by M 2 . Then, as a consequence of all the above deviation's results, it follows that for all λ, v, γ ≥ 0,

µ Ç g ≥ µ(g) + v + λc(ℓ) 2 (µ(h) + γ) 2 å ≤ µ Ç g ≥ µ(g) + v + λc(ℓ) 2 h 2 å + µ(h ≥ µ(h) + γ) ≤ e -λv + exp Ç - γ 2 2c(ℓ) 2 M 2 (µ(h) + γ) å . By choosing γ = Mu, λ = u c(ℓ) 2 M 2 (µ(h)+Mu)
, and v = u/2, we get the following Bernstein deviation inequality for the deviation of g above its mean, for all u ≥ 0

µ(g ≥ µ(g) + u) ≤ 2 exp Ç - u 2 2c(ℓ) 2 (µ(h) + Mu) å .
All the previous deviation's inequalities extend to countable sets F by monotone convergence.

When F is reduced to a singleton, these deviation's results simply implies Bernstein deviation's results for g(σ) = n k=1 a k,σ(k) when -M ≤ a i, j ≥ M for all 1 ≤ i, j ≤ n, by following for example the procedure presented in [BDR15, Section 4.2]. Thus, we extend the deviation's results of [START_REF] Bercu | Concentration inequalities for sums and martingales[END_REF] to probability measures in M T . • As a last example, let g(σ) = |σ| l denotes the number of cycles of lenght l in the cycle decomposition of a permutation σ. Let us show that g is a configuration function. Let C l (τ) denotes the set of cycles of lenght l in the cycle decomposition of a permutation τ. One has

|τ| l = #{C l (τ) ∩ C l (σ)} + #{c ∈ C l (τ), such that c C l (σ)} ≤ |σ| l + #{c ∈ C l (τ), such that c C l (σ)}.
If c ∈ C l (τ) and c C l (σ) then there exists k in the support of c such that τ(k) σ(k). As a consequence, one has

#{c ∈ C l (τ), such that c C l (σ)} ≤ n k=1 α k (τ)1 σ(k) τ(k) ,
where α k (τ) = 1 if k is in the support of a cycle of lenght l of the cycle decomposition of τ, and α l (τ) = 0 otherwise. Thus, we get that the function g satisfies the condition of (b), g is a configuration function. Finally, observing that |α| 2 2 = lg, Corollary 1.2 provides for any measure µ ∈ M T satisfying (10), for all u ≥ 0,

µ (g ≤ µ(g) -u) ≤ exp Ç - u 2 2c(ℓ) 2 lµ (h) å , and
µ (g ≥ µ(g) + u) ≤ exp Ç - u 2 2c(ℓ) 2 l(µ(g) + u) å .
• The aim of this paper is to clarify the links between Talagrand's type of concentration results on the symmetric group and functional inequalities derived from the transport-entropy inequalities. For brevity's sake, applications of these functional inequalities are not fully developped in the present paper. However, let us briefly mention some other applications using concentration results on the symmetric group: the stochastic travelling salesman problem for sampling without replacement (see Appendix [START_REF] Paulin | The convex distance inequality for dependent random variables, with applications to the stochastic travelling salesman and other problems[END_REF]), graph coloring problems (see [START_REF] Mcdiarmid | Concentration for independent permutations[END_REF]). We also refer to the surveys and books [START_REF] Dubhashi | Concentration of Measure for the Analysis of Randomized Algorithms[END_REF][START_REF] Molloy | Graph Colouring and the Probabilistic Method[END_REF] for other numerous examples of application of the concentration of measure principle in randomized algorithms.

Proof of Corollary 1.2. We start with the proof of (b). From the assumption on the function g, we get that for any p ∈ P(G)

g dp ≥ g(σ) - n k=1 Å α k (σ) 1 σ(k) τ(k) dp(τ) ã ≥ g(σ) -|α(σ)| 2 n k=1 Å 1 σ(k) τ(k) dp(τ) ã 2 1/2 . Let λ ≥ 0. Plugging this estimate into the definition of Ù Q(λg), it follows that for any σ ∈ G Ù Q(λg)(σ) ≥ λg(σ) -sup u≥0 ® λ|α(σ)| 2 u - u 2 2c(ℓ) 2 ´= λg(σ) - λ 2 |α(σ)| 2 2 c(ℓ) 2 2 .
As α goes to 1, (13) applied to the function λg yields

e Û Q(λg) dµ ≤ e λµ(g) ,
and therefore

exp Ç λg - λ 2 c(ℓ) 2 |α| 2 2 2 å dµ ≤ e λµ(g) , (16)
e λg dµ ≤ exp Ç λµ(g) + λ 2 c(ℓ) 2 sup σ∈G |α(σ)| 2 2 2 å , (17)
and if |α| 2 2 ≤ Mg, exp Ç λ Ç 1 - λc(ℓ) 2 M 2 å g å dµ ≤ e λµ(g) . ( 18
)
As α goes to 0, (13) yields

e -λg dµ ≤ e λµ( Û Q(λg)) ,
and therefore

e -λg dµ ≤ exp Ç -λµ(g) + λ 2 c(ℓ) 2 µ(|α| 2 2 ) 2 å . ( 19
)
The deviation bounds of (b) follows from ( 16), ( 19), ( 17), (18) by Tchebychev inequality, and by optimizing over all λ ≥ 0.

The deviation bounds of (a) are similarly obtained from (12) by Tchebychev inequality. As above, the improvement for the deviation under the mean is a consequence of (12) applied to λg, as α goes to 0, and using the estimate

‹ Q K n (λg)(σ) ≥ λg(σ) - λ 2 β(σ) 2 c(ℓ) 2 K n 2 .
Proof of Corollary 1.1. Take a subset A ⊂ G and consider the function ϕ λ which takes the values 0 on A and λ > 0 on G \ A. It holds

Ù Qϕ λ (σ) = inf p∈P(G)    λ(1 -p(A)) + 1 2c(ℓ) 2 n j=1 Å 1 σ( j) y( j) dp(y) ã 2    = inf β∈[0,1] {λ(1 -β) + ψ(β, σ)},
denoting by

ψ(β, σ) = inf    1 2c(ℓ) 2 n j=1 Å 1 σ( j) y( j) dp(y) ã 2 ; p(A) = β    . So it holds Ù Qϕ λ (σ) = min Å inf β∈[0,1-ε] {λ(1 -β) + ψ(β, σ)}; inf β∈[1-ε,1] {λ(1 -β) + ψ(β, σ)}, ã ≥ min Å λε; inf β≥1-ε ψ(β, σ) ã → inf β≥1-ε ψ(β, σ),
as λ → ∞. It is easy to check that for any fixed σ, the function ψ( • , σ) is continuous on [0, 1], so letting ε go to 0, we get lim inf λ→∞ Ù Qϕ λ (σ) ≥ ψ(1, σ). On the other hand, Ù Qϕ λ (σ) ≤ ψ(1, σ) for all λ > 0. This proves that lim λ→∞ Ù Qϕ λ (σ) = ψ(1, σ). Applying (13) to ϕ λ and letting λ go to infinity yields to

e αψ(1,σ) dµ • µ(A) α/(1-α) ≤ 1. It remains to observe that ψ(1, σ) = f (σ,A) 2c(ℓ) 2 .
2. Proof of Theorem 1.3

Let T n = (t i j , j , j ∈ {2, . . . , n}, i j ∈ O j ) be a ℓ-local base of G. Let µ be a probability measure of the set M T n given by (4). Then, there exists a product probability measure ν = ν1 ⊗ • • • ⊗ νn such that µ = U T n #ν where the map U T n is given by (37).

Each transport-entropy inequality of Theorem 1.3 is obtained by induction over n and using the partition (H i ) i∈orb(n) of the group G defined by: for any

i ∈ orb(n) = O n , H i := {σ ∈ G, σ(i) = n} . ( 20
)
According to our notations, H n = G n-1 is a subgroup of G, and we may easily check that T n-1 is a ℓ-local base of this subgroup. We also observe that if G is a normal subgroup of S n then G n-1 is a normal subgroup of S n-1 .

Moreover, for any i ∈ O n , H i is the coset defined by

H i = H n t in . From the def- inition of µ, if σ ∈ H i , then there exist i 2 , . . . , i n-1 such that σ = t i 2 ,2 • • • t i n-1 ,n-1 t i,n and therefore µ(σ) = ν2 (i 2 ) • • • νn-1 (i n-1 )ν n (i).
As a consequence, one has µ(H i ) = νn (i). Let µ i denote the restriction of µ to H i defined by

µ i (σ) = µ(σ) µ(H i ) 1 σ∈H i .
From the construction of µ,

µ n = U T n-1 #(ν 1 ⊗ • • • ⊗ νn-1 ).
Moreover, for all σ ∈ H n , one has σt i,n ∈ H i and

µ n (σ) = µ(σ) µ(H n ) = µ(σt i,n ) µ(H i ) = µ i (σt i,n ). ( 21
)
Moreover if µ satisfies the condition (10), then µ n ∈ P(G n-1 ) satisfies the same condition at rank n -1: namely, for any σ

∈ G n-1 , t ∈ S n-1 , µ n (σ) = µ n (σ -1 ) and µ n (σ) = µ n (t -1 σt).
These properties are needed in the induction step of the proofs.

When G is a ℓ-local group, let us note that if i and l are elements of O n = orb(n), then from the ℓ-local property, there exists t i,l ∈ G such that t i,l (i) = l and deg(t i,l ) ≤ ℓ. We also have

H l = H i t i,l . If moreover µ = µ o is the uniform law on G, then for any i, l ∈ O n , µ i (H i ) = µ l (H l ) = 1 #O n .
In that case we will use in the proofs the following property: for any σ ∈ H n , one has σt i,n ∈ H i , σt i,n t -1 i,l ∈ H l , and

µ n (σ) = #O n #G = µ i (σt i,n ) = µ l (σt i,n t -1 i,l ). (22)
The measure µ n is the uniform measure on the ℓ-local subgroup

H n = G n-1 .
Proof of (a) in Theorem 1.3. As already mentioned, since W 1 satisfies a triangular inequality, the transport-entropy inequality (7) is equivalent to the following one: for all ν ∈ P(G), 2 c(ℓ) 2 W 2 1 (ν, µ) ≤ K n H(ν|µ). A dual formulation of this property given by Theorem 2.7 in [START_REF] Gozlan | Kantorovich duality for general transport costs and applications[END_REF] and Proposition 3.1 in [START_REF] Samson | Concentration of measure principle and entropy-inequalities[END_REF] is the following: for all functions ϕ on G and all λ ≥ 0,

e λQϕ dµ ≤ e λϕ dµ+K n c(ℓ) 2 λ 2 /8 , (23)
Qϕ(σ) = inf p∈P(S 2 ) ß ϕdp + c(2) 1 σ τ dp(τ) ™ .
In that case, (23) exactly corresponds to the following dual form of the Csiszar-Kullback-Pinsker inequality (5) (see Proposition 3.1 in [START_REF] Samson | Concentration of measure principle and entropy-inequalities[END_REF] ): for any probability measure ν on a Polish space X, for any measurable function f : X → R,

e λR c f dν ≤ e λ f dν+λ 2 c 2 /8 , ∀λ, c ≥ 0, (24) with R c f (x) = inf p∈P(X) ß f dp + c 1 x y dp(y) ™ , x ∈ X.
The induction step will be also a consequence of (24). Let (H i ) i∈O n be the partition of G defined by (20). Any p ∈ P(G) admits a unique decomposition defined by

p = i∈O n p(i)p i , with p i ∈ P(H i ) and p(i) = p(H i ). ( 25
)
This decomposition defines a probability measure p on O n . In particular, according to the definition of the measure µ ∈ M T n and since νn (i) = µ(H i ), one has

µ = i∈O n νn (i) µ i .
It follows that

e λQϕ dµ = i∈O n νn (i) e λQϕ(σ) dµ i (σ) = i∈O n νn (i) e λQϕ(σt i,n ) dµ n (σ),
where the last equality is a consequence of property (21). Now, we will bound the right-hand side of this equality by using the induction hypotheses.

For any function g : G → R and any t ∈ G, let g t : G → R denote the function defined by g t (σ) := g(σt).

For any function f : H n → R and any σ ∈ H n , let us note

Q H n f (σ) := inf p∈P(H n ) ß f dp + d(σ, τ) dp(τ) ™ .
The next step of the proof relies on the following Lemma.

Lemma 2.1. Let i ∈ O n , for any function ϕ : H i → R and any σ ∈ H n , one has

(1) Qϕ(σt i,n ) ≤ inf p∈P(O n )    l∈O n Q H n ϕ t n,l (σ) p(l) + c(ℓ) l∈O n 1 l i p(l)    , where c(ℓ) = min(2ℓ -1, n) if d = d H and c(ℓ) = 2 if d = d T . (2) Qϕ(σt i,n ) ≤ inf p∈P(O n )    l∈O n Q H n ϕ t i,n t -1 i,l (σ) p(l) + c(ℓ) l∈O n 1 l i p(l)    , where c(ℓ) = ℓ if d = d H and c(ℓ) = 1 if d = d T ,

and t i,l denotes an element of G with deg(t i,l

) ≤ ℓ and such that t i,l (i) = l.

This lemma is obtained using the decomposition (25) of the measures p ∈ P(G) on the H j 's. Let σ ∈ H n . By the triangular inequality and using the invariance by translation of the distance d, one has

d(σt i,n , τ) dp(τ) = l∈O n H l d(σt i,n , τ)dp l (τ) p(l) ≤ l∈O n d(σt i,n , σt l,n ) p(l) + l∈O n H l d(σt l,n , τ)dp l (τ) p(l) = l∈O n d(t i,n , t l,n ) p(l) + l∈O n H l d(σ, τt -1 l,n )dp l (τ) p(l)
and therefore, since

d(t i,n , t l,n ) ≤ c(ℓ) with c(ℓ) = min(2ℓ -1, n) if d = d H and c(ℓ) = 2 if d = d T , d(σt i,n , τ) dp(τ) ≤ l∈O n H l d(σ, τt -1 l,n )dp l (τ) p(l) + c(ℓ) l∈O n 1 l i p(l). (26) It follows that Qϕ(σt i,n ) ≤ inf p∈P(O n ) inf p l ∈P(H l ),l∈O n    l∈O n ñ ϕ dp l + H l d(σ, τt -1 l,n )dp l (τ) ô p(l) + c(ℓ) l∈O n 1 l i p(l)    = inf p∈P(O n ) inf q l ∈P(H n ),l∈O n    l∈O n ñ ϕ t l,n dq l + H n d(σ, τ)dq l (τ) ô p(l) + c(ℓ) l∈O n 1 l i p(l)    = inf p∈P(O n )    l∈O n Q H n ϕ t l,n (σ) p(l) + c(ℓ) l∈O n 1 l i p(l)    .
The proof of the second inequality of Lemma 2.1 is similar, starting from the following triangular inequality

d(σt i,n , τ) dp(τ) = l∈O n H l d(σt i,n , τ)dp l (τ) p(l) ≤ l∈O n d(σt i,n , τt i,l )dp l (τ) p(l) + l∈O n H l d(τt i,l , τ)dp l (τ) p(l) = l∈O n d(σ, τt i,l t -1 i,n )dp l (τ) p(l) + l∈O n d(t i,l , id) p(l) ≤ l∈O n H l d(σ, τt i,l t -1 i,n )dp l (τ) p(l) + c(ℓ) l∈O n 1 l i p(l), (27) with c(ℓ) = ℓ if d = d H and c(ℓ) = 1 if d = d T .
The end of the proof of the second inequality of Lemma 2.1 is left to the reader.

The induction step of the proof of (23) continues by applying consecutively Lemma 2.1 (1), the Hölder inequality, and the induction hypotheses to the measure µ n on the subgroup H n = G n-1 with ℓ-local base T n-1 .

If O n = {n} then K n = K n-1 and e λQϕ dµ = e λQϕ(σ) dµ n (σ) ≤ e λϕdµ n +K n-1 c(ℓ) 2 /8 = e λϕdµ+K n c(ℓ) 2 /8

If O n {n} then K n = K n-1 + 1 and for any i ∈ O n ,

e λQϕ(σt i,n ) dµ n (σ) ≤ inf p∈P(O n )    l∈O n Å e λQ Hn ϕ t l,n dµ n ã p(l) e c(ℓ)λ n l=1 1 l i p(l)    ≤ exp   inf p∈P(O n )    λ l∈O n Å ϕ t l,n dµ n ã p(l) + K n-1 c(ℓ) 2 λ 2 8 + c(ℓ)λ l∈O n 1 l i p(l)      = exp   λ inf p∈P(O n )    l∈O n φ(l) p(l) + c(ℓ) l∈O n 1 l i p(l)    + K n-1 c(ℓ) 2 λ 2 8   ,
where, by using property (21), φ(l) := ϕdµ l = ϕ t l,n dµ n . Let us consider again the above infimum-convolution R c φ defined on the space X = O n , with c = c(ℓ), one has

R c φ(i) = inf p∈P(O n )    l∈O n φ(l) p(l) + c l∈O n 1 l i p(l)    .
By applying (24) with the probability measure ν = νn on O n , the previous inequality gives

e λQϕ dµ = i∈O n νn (i) e λQϕ(σt i,n ) dµ n (σ) ≤ Ñ i∈O n e λR c(ℓ) φ(i) νn (i) é e K n-1 λ 2 /8 ≤ exp n i=1 φ(i)ν n (i) + λ 2 c(ℓ) 2 8 + K n-1 c(ℓ) 2 λ 2 8 = exp ñ λ ϕ dµ + K n c(ℓ) 2 λ 2 8 ô .
This ends the proof of (23) for any µ ∈ M T n . The scheme of the induction proof of (23), with a better constant c(ℓ) when µ = µ o is the uniform measure on a ℓ-local group G, is identical, starting from the second result of Lemma 2.1 and using the property (22). This is left to the reader.

We now turn to the induction proof of the dual formulation (12) of the weak transport-entropy inequality (8). The sketch of the proof is identical to the one of (23).

For the initial step n = 2, one has G = S 2 and ℓ = 2, and one may easily check that

‹ Q 1 ϕ(σ) = inf p∈P(S 2 ) ® ϕdp + 1 2 Å 1 σ τ dp(τ) ã 2
´.

In that case, the result follows from the following infimum-convolution property.

Lemma 2.2. For any probability measure ν on a Polish metric space X, for all α ∈ (0, 1) and all measurable functions f : X → R, bounded from below

Å e α R α f dν ã 1/α Å e -(1-α) f dν ã 1/(1-α) ≤ 1,
where for all x ∈ X,

R α f (x) = inf p∈P(X) ® f (y)dp(y) + c α Å 1 x y dp(y) ã 2 ´,
and c α is the convex function defined by

c α (u) = α(1 -u) log(1 -u) -(1 -αu) log(1 -αu) α(1 -α) , u ∈ [0, 1].
Observing that c α (u) ≥ u 2 /2 for all u ∈ [0, 1], the above inequality also holds replacing R α f by

R f (x) = inf p∈P(X) ® f (y)dp(y) + 1 2 Å 1 x y dp(y) ã 2 ´, x ∈ X. ( 28
)
The proof of this Lemma can be found in [START_REF] Samson | Infimum-convolution description of concentration properties of product probability measures, with applications[END_REF] (inequality (4)). For a sake of completeness, we give in the Appendix a new proof of this result on finite spaces X by using a localization argument (Lemma 4.1).

Let us now present the key lemma for the induction step of the proof. For any function f : H n → R and any σ ∈ H n , we define

‹ Q H n t f (σ) := inf p∈P(H n ) ® f dp + 1 2c(ℓ) 2 t Å d(σ, τ) dp(τ) ã 2
´.

Here, writing Q H n t f , we omit the dependence in c(ℓ) to simplify the notations. The proof relies on the following Lemma.

Lemma 2.3. Let i ∈ O n . For any function ϕ : H i → R and any σ ∈ H n , one has

(1) ‹ Q K n ϕ(σt i,n ) ≤ inf p∈P(O n )    l∈O n ‹ Q H n K n-1 ϕ t l,n (σ) p(l) + 1 2 Å l∈O n 1 l i p(l) ã 2    , with c(ℓ) = min(2ℓ -1, n) if d = d H and c(ℓ) = 2 if d = d T .
(2

) ‹ Q K n ϕ(σt i,n ) ≤ inf p∈P(O n )    l∈O n ‹ Q H n K n-1 ϕ t i,n t -1 i,l (σ) p(l) + 1 2 Å l∈O n 1 l i p(l) ã 2    , where c(ℓ) = ℓ if d = d H and c(ℓ) = 1 if d = d T ,

and t i,l denotes an element of G with deg(t i,l

) ≤ ℓ and such that t i,l (i) = l.

The proof of this lemma is similar to the one of Lemma 2.1. By (26) and the inequality

(u + v) 2 ≤ u 2 s + v 2 1 -s , u, v ∈ R, s ∈ (0, 1),
we get for any s ∈ (0, 1),

Å d(σt l,n , τ) dp(τ) ã 2 ≤ Ñ l∈O n H l d(σ, τt -1 l,n )dp l (τ) p(l) + c(ℓ) l∈O n 1 l i p(l) é 2 ≤ 1 s Ñ l∈O n H l d(σ, τt -1 l,n )dp l (τ) p(l) é 2 + c(ℓ) 2 1 -s Å l∈O n 1 l i p(l) ã 2 ≤ 1 s l∈O n Ç H l d(σ, τt -1 l,n )dp l (τ) å 2 p(l) + c(ℓ) 2 1 -s Å l∈O n 1 l i p(l) ã 2 . It follows that for any σ ∈ H n , ‹ Q K n ϕ(σt l,n ) ≤ inf p∈P(O n ) inf p l ∈P(H l ),l∈O n    l∈O n ϕ dp l + 1 2c(ℓ) 2 sK n Ç H l d(σ, τt -1 l,n )dp l (τ) å 2 p(l) + 1 2(1 -s)K n Å l∈O n 1 l i p(l) ã 2    = inf p∈P(O n ) inf q l ∈P(H n ),l∈O n    l∈O n ϕ t l,n dq l + 1 2c(ℓ) 2 sK n Ç H n d(σ, τ)dq l (τ) å 2 p(l) + 1 2(1 -s)K n Å l∈O n 1 l i p(l) ã 2    = inf p∈P(O n )    l∈O n ‹ Q H n K n-1 ϕ t l,n (σ) p(l) + 1 2 Å l∈O n 1 l i p(l) ã 2    ,
where the last equality follows by choosing s = K n-1 /K n , which ends the proof of the first inequality of Lemma 2.3. The second inequality of Lemma 2.3 is obtained identically starting from (27). We now turn to the induction step of the proof. By the decomposition of the measure µ on the H i 's, we want to bound

e α Q Kn ϕ dµ = i∈O n νn (i) e α Q Kn ϕ(σ) dµ i (σ) = i∈O n νn (i) e α Q Kn ϕ(σt i,n ) dµ n (σ),
where the last equality is a consequence of property (21).

If O n = {n}, then the result simply follows from the induction hypotheses applied to the measure µ n .

If O n {n}, then applying successively Lemma 2.3 (1), the Hölder inequality, and the induction hypotheses, we get

e α Q Kn ϕ(σt i,n ) dµ n (σ) ≤ inf p∈P(O n )    l∈O n Å e α Q Hn K n-1 ϕ t l,n dµ n ã p(l) exp   1 2 Å l∈O n 1 l i p(l) ã 2      ≤ inf p∈P(O n )    l∈O n Å e -(1-α)ϕ t l,n dµ n ã -p(l)α 1-α exp   1 2 Å l∈O n 1 l i p(l) ã 2      = exp   α inf p∈P(O n )    l∈O n φ(l) p(l) + 1 2 Å l∈O n 1 l i p(l) ã 2      ,
where by property (21), we set

φ(l) := log Å e -(1-α)ϕ dµ l ã -1 1-α = log Å e -(1-α)ϕ t l,n dµ n ã -1 1-α .
According to the definition of the infimum convolution R φ on the space X = O n given in Lemma 2.2, the last inequality is

e α Q Kn ϕ(σt i,n ) dµ n (σ) ≤ e α R φ(i) ,
and therefore Lemma 2.2, applied with the measure ν = νn , provides

e α Q Kn ϕ dµ = i∈O n e α R φ(i) νn (i) ≤ Å i∈O n e -(1-α) φ(i) νn (i) ã -α 1-α = Å i∈O n νn (i) e -(1-α)ϕ dµ i ã -α 1-α = Å e -(1-α)ϕ dµ ã -α 1-α .
The proof of ( 12) is completed for any measure µ ∈ M. To improve the constant when µ = µ o is the uniform law on a ℓ-local group G, the proof is similar using the second inequality of Lemma 2.3 together with property (22).

Proof of (b) in Theorem 1.3. We prove the dual equivalent property (13) as a consequence of the stronger following result: for any real function ϕ on G, for any j ∈ {1, . . . , n} Å e αQ j ϕ dµ

ã 1/α Å e -(1-α)ϕ dµ ã 1/(1-α) ≤ 1, ( 29
)
where the infimum convolution operator Q j ϕ is defined as follows, for σ ∈ G

(30) Q j ϕ(σ) = inf p ∈ P(G) ® ϕdp + 1 c(ℓ) 2 Å 1 σ( j) y( j) dp(y) ã 2 + 1 2c(ℓ) 2 k∈[n]\{ j} Å 1 σ(k) y(k) dp(y) ã 2    .
The proof of (29) relies on Lemma 2.2 and the following ones. For any σ ∈ G, we define

Q H n ϕ(σ) = inf p∈P(H n ) ϕdp + 1 2c(ℓ) 2 n-1 k=1 Å 1 σ(k) y(k) dp(y) ã 2 , and for j ∈ [n -1], Q H n , j ϕ(σ) = inf p∈P(H n ) ® ϕdp + 1 c(ℓ) 2 Å 1 σ( j) y( j) dp(y) ã 2 + 1 2c(ℓ) 2 k∈[n-1]\{ j} Å 1 σ(k) y(k) dp(y) ã 2    . Lemma 2.4. Let j ∈ [n].
For any σ ∈ G, one has

Q j ϕ(σ) = Q σ( j) ϕ {-1} (σ -1 )
,

where ϕ {-1} (z) = ϕ(z -1 ), z ∈ G.
This result follows from the change of variables σ(k) = l in the definition (30) of Q j ϕ(σ), one has

Q j ϕ(σ) = inf p∈P(G) ® ϕdp + 1 c(ℓ) 2 Å 1 y -1 (σ( j)) σ -1 (σ( j)) dp(y) ã 2 + 1 2c(ℓ) 2 l,l σ( j) Å 1 l y(σ -1 (l)) dp(y) ã 2    = inf q∈P(G) ® ϕ(z -1 ) dq(z) + 1 c(ℓ) 2 Å 1 z(σ( j)) σ -1 (σ( j)) dq(z) ã 2 + 1 2c(ℓ) 2 l,l σ( j) Å 1 z(l) σ -1 (l) dq(z) ã 2    ,
where for the last equality, we use the fact that the map that associates to any measure p ∈ P(G) the image measure q := R#p with R : σ ∈ G → σ -1 ∈ G, is one to one from P(G) to P(G).

Here is the key lemma for the induction step of the proof of (29).

Lemma 2.5.

(1) Let j ∈ O n . For any σ ∈ H n , one has

Q j ϕ(σt j,n ) ≤ Q H n ϕ t j,n (σ).
(2) For any ℓ ≥ 2, let c 2 (ℓ) := 8(ℓ -1) 2 + 2. Assume that O n {n} and let i, j ∈ O n , i j. We note

D i = supp(t -1 j,n t i,n ) \ {i} and d = |D i |. For any σ ∈ H n , for any θ ∈ [0, 1] one has Q i ϕ(σt i,n ) ≤ 1 d l∈t i,n (D i ) î θQ H n ,l ϕ t i,n (σ) + (1 -θ)Q H n ϕ t j,n (σ) ó + 1 2 (1 -θ) 2 .
(3) For any ℓ ≥ 2, let c 2 (ℓ) := 2(ℓ -1) 2 + 2. Assume that O n {n} and let i, j ∈ O n , i j. Let t i, j ∈ G such that t i, j (i) = j and deg(t i, j ) ≤ ℓ. We note D i = supp(t i, j ) \ {i} and d = |D i |. For any σ ∈ H n , for any θ ∈ [0, 1] one has

Q i ϕ(σt i,n ) ≤ 1 d l∈t i,n (D i ) θQ H n ,l ϕ t i,n (σ) + (1 -θ)Q H n ϕ t i,n t -1 i, j (σ) + 1 2 (1 -θ) 2 .
Proof. The first part of this Lemma follows from the fact that P(H j ) ⊂ P(G) and the fact that 1 σt j,n ( j) y( j) dp(y) = 0 for σ ∈ H n and p ∈ P(H j ). Therefore, according to the definition of Q j ϕ, one has for σ ∈ H j ,

Q j ϕ(σt j,n ) ≤ inf p∈P(H j )    ϕdp + 1 2c(ℓ) 2 k∈[n]\{ j} Å 1 σt j,n (k) y(k) dp(y) ã 2    = inf q∈P(H n )    ϕ t j,n dq + 1 2c(ℓ) 2 k∈[n]\{ j} Å 1 σt j,n (k) yt j,n (k) dq(y) ã 2    = Q H n ϕ t j,n (σ).
For the proof of the second part of Lemma 2.5, we set ti, j := t -1 j,n t i,n .

Let us consider p l i , l ∈ D i , a collection of measures in P(H i ), and p j ∈ P(H j ) ( j i). For θ ∈ [0, 1],

p := 1 d l∈D i [θp l i + (1 -θ)p j ],
is a probability measure on G. Therefore, according to the definition of Q i ϕ, for any σ ∈ H n ,

Q i ϕ(σt i,n ) ≤ 1 d l∈D i ï θ f dp l i + (1 -θ) f dp j ò + 1 2c(ℓ) 2 (A + B + C), with A = k∈[n]\ supp(t i, j ) Å 1 σt i,n (k) y(k) dp(y) ã 2 , B = k∈D i Å 1 σt i,n (k) y(k) dp(y) ã 2 , and C = 2 Å 1 σt i,n (i) y(i) dp(y) ã 2 . Since σ ∈ H n and p l i ∈ P(H i ), one has 1 σt i,n (i) y(i) dp l i (y) = 0 and 1 σt i,n (i) y(i) dp j (y) = 1. It follows that C = 2(1 -θ) 2 .
For any k ∈ [n] and l ∈ D i , let us note

U i (k, l) := 1 σt i,n (k) y(k) dp l i (y), and U j (k) := 1 σt i,n (k) y(k) dp j (y).
By the Cauchy-Schwarz inequality, one has

A ≤ 1 d l∈D i   θ k∈[n]\ supp(t i, j ) U 2 i (k, l) + (1 -θ) k∈[n]\ supp(t i, j ) U 2 j (k)   .
We also have

B = k∈D i Ñ θ d U i (k, k) + (1 -θ)U j (k) + θ d l∈D i \{k} U i (k, l) é 2 ≤ k∈D i   d Å θ d U i (k, k) + (1 -θ)U j (k) ã 2 + θ 2 d l∈D i \{k} U 2 i (k, l)   ≤ k∈D i   2θ 2 d U 2 i (k, k) + 2d(1 -θ) 2 + θ 2 d l∈D i \{k} U 2 i (k, l)   ≤ 2d 2 (1 -θ) 2 + θ d l∈D i   2U 2 i (l, l) + k∈D i \{l} U 2 i (k, l)  
All the above estimates together provide

A + B + C ≤ (2d 2 + 2)(1 -θ) 2 + 1 d l∈D i   θ Ñ 2U 2 i (l, l) + k∈[n]\{i,l} U 2 i (k, l) é + (1 -θ) k∈[n]\ supp(t i, j ) U 2 j (k)   .
Observe that

d = deg( ti, j ) -1 = deg(t -1 j,n t i,n ) -1 ≤ 2ℓ -2.
Therefore, according to the definition of c(ℓ), one has 2d 2 + 2 ≤ c(ℓ) 2 . As a consequence we get from all estimates above, by optimizing over all p l i ∈ P(H i ) and all p j ∈ P(H j ),

Q i ϕ(σt i,n ) ≤ 1 d l∈D i θV l + (1 -θ)W j + 1 2 (1 -θ) 2 , with V l := inf p i ∈P(H i ) ® ϕdp i + 1 c(ℓ) 2 Å 1 σt i,n (l) y(l) dp i (y) ã 2 + 1 2c(ℓ) 2 k∈[n]\{i,l} Å 1 σt i,n (k) y(k) dp i (y) ã 2    = inf q i ∈P(H n ) ® ϕ t i,n dq i + 1 c(ℓ) 2 Å 1 σ(t i,n (l)) y(t i,n (l)) dq i (y) ã 2 + 1 2c(ℓ) 2 k∈[n-1]\{t i,n (l)} Å 1 σ(k) y(k) dq i (y) ã 2    = Q H n ,t i,n (l) ϕ t i,n (σ)
and

W j := inf p j ∈P(H j )    ϕdp j + 1 2c(ℓ) 2 k∈[n]\ supp(t i, j ) Å 1 σt i,n (k) y(k) dp j (y) ã 2    = inf q j ∈P(H n )      ϕ t j,n dq j + 1 2c(ℓ) 2 k∈[n]\ supp(t -1 j,n t i,n ) Å 1 σt i,n (k) yt j,n (k) dq j (y) ã 2      ≤ inf q j ∈P(H n )    ϕ t j,n dq j + 1 2c(ℓ) 2 k∈[n]\{i} Å 1 σt i,n (k) yt i,n (k) dq j (y) ã 2    = inf q j ∈P(H n )    ϕ t j,n dq j + 1 2c(ℓ) 2 k∈[n-1] Å 1 σ(k) y(k) dq j (y) ã 2    = Q H n ϕ t j,n (σ)
where we used successively the following arguments:

H n t j,n = H j ; if k ∈ [n] \ supp(t -1 j,n t i,n ) then t i,n (k) = t j,n (k); [n] \ supp(t -1 j,n t i,n ) ⊂ [n] \ {i}.
This ends the proof of part (2) of Lemma 2.5.

The proof of part (3) Lemma 2.5 is identical replacing ti, j by t i, j . In that case

2d 2 + 2 ≤ 2(ℓ -1) 2 + 2 = c 2 (ℓ).
Then, the only minor change is for the last step

W j := inf p j ∈P(H j )    ϕdp j + 1 2c(ℓ) 2 k∈[n]\ supp(t i, j ) Å 1 σt i,n (k) y(k) dp j (y) ã 2    = inf q j ∈P(H n )    ϕ t i,n t -1 i, j dq j + 1 2c(ℓ) 2 k∈[n]\ supp(t i, j ) Å 1 σt i,n (k) yt i,n t -1 i, j (k) dq j (y) ã 2    ≤ inf q j ∈P(H n )    ϕ t i,n t -1 i, j dq j + 1 2c(ℓ) 2 k∈[n]\{i} Å 1 σt i,n (k) yt i,n (k) dq j (y) ã 2    = inf q j ∈P(H n )    ϕ t i,n t -1 i, j dq j + 1 2c(ℓ) 2 k∈[n-1] Å 1 σ(k) y(k) dq j (y) ã 2    = Q H n ϕ t i,n t -1 i, j (σ)
where we used successively the following arguments:

H n t i,n t -1 i, j = H j ; if k ∈ [n] \ supp(t i, j ) then t i, j (k) = k; [n] \ supp(t i, j ) ⊂ [n] \ {i}.
The proof of Lemma 2.5 is completed.

We will now prove (29) by induction over n. For n = 2, G is the two points space S 2 which is 2-local. For i ∈ {1, 2}, and for any p ∈ P(G),

1 c(2) 2 Å 1 σ(i) y(i) dp(y) ã 2 + 1 2c(2) 2 k,k i Å 1 σ(k) y(k) dp(y) ã 2 = 3 8 Å 1 σ y dp(y) ã 2 ≤ 1 2 Å 1 σ y dp(y) ã 2 .
As a consequence, we get the expected result from Lemma 2.2 applied with X = G.

We will now present the induction step. We assume that (29) holds at the rank n -1 for all j ∈ {1, . . . , n -1}.

Let us first explain that it suffices to prove (29) for j = n. For any t ∈ S n , let G (t) = t -1 Gt. The isomorphism c t : G → G (t) , σ → t -1 σt pushes forward the measure µ on the measure µ (t) := c t #µ ∈ P(G (t) ), and conversely µ = c t -1 #µ (t) . Let j ∈ [n]. For any σ ∈ G (t) and any real function ϕ on G, one has

(Q j ϕ) • c t -1 (σ) = inf p∈P(G) ® ϕ dp + 1 c(ℓ) 2 Å 1 tσt -1 ( j) y( j) dp(y) ã 2 + 1 2c(ℓ) 2 k∈[n] Å 1 tσt -1 (k) y(k) dp(y) ã 2    = inf q∈P(G (t) ) ® ϕ • c t -1 dq + 1 c(ℓ) 2 Å 1 tσt -1 ( j) tyt -1 ( j) dq(y) ã 2 + 1 2c(ℓ) 2 k∈[n] Å 1 tσt -1 (k) tyt -1 (k) dq(y) ã 2    = inf q∈P(G (t) ) ® ϕ • c t -1 dq + 1 c(ℓ) 2 Å 1 σt -1 ( j) yt -1 ( j) dq(y) ã 2 + 1 2c(ℓ) 2 k∈[n] Å 1 σ(k) y(k) dq(y) ã 2    = Q t -1 ( j) (ϕ • c t -1 )(σ).
From this observation, by choosing t -1 = t jn , and setting ψ ϕ

• c t -1 , one has Å G e αQ j ϕ dµ ã 1/α Å G e -(1-α)ϕ dµ ã 1/(1-α) = Å G (t) e α(Q j ϕ)•c t -1 dµ (t) ã 1/α Å G (t) e -(1-α)ϕ•c t -1 dµ (t) ã 1/(1-α) = Å G (t)
e αQ n ψ dµ (t)

ã 1/α Å G (t)
e -(1-α)ψ dµ (t) ã 1/(1-α)

If we assume that G is a normal subgroup of S n and that µ satisfies the second property of (10), then G (t) = G and µ (t) = µ. Therefore the above expression is bounded by 1 as soon as (29) holds for j = n. If we assume G is a ℓ-local group and µ = µ o is the uniform law on G, then G (t) is also a ℓ-local group and µ (t) is exactly the uniform law on G (t) . Therefore the last expression is bounded by 1 as soon as (29) holds with j = n for any uniform law on a ℓ-local group. As a conclusion, it remains to prove inequality (29) for j = n.

We may assume that O n {n}, otherwise the induction step is obvious. We first apply Lemma 2.4, by the first property of (10) satisfied by µ, By property (21) and then applying Lemma 2.5 (1), we get e αQ j g dµ j = e αQ j g(σt i,n ) dµ n (σ) ≤ e αQ Hn g t j,n dµ n .

e αQ n ϕ dµ = e αQ σ(n) ϕ {-1} (σ -1 ) dµ(σ) = e αQ σ -1 (n) ϕ {-1} (σ) dµ(σ).
By the induction hypotheses applied to the measure µ n on the subgroup

H n = G n-1 , it follows that e αQ j g dµ j ≤ Å e -(1-α)g t jn dµ n ã -α/(1-α) = Å e -(1-α)g dµ j ã -α/(1-α) = e αĝ( j) . ( 32
)
Let us now consider i j, i ∈ O n . When G is a normal subgroup of S n , property (21), the second part of Lemma 2.5 and Jensen's inequality yield: for any θ ∈ [0, 1], e αQ i g dµ i = e αQ i g(σt i,n ) dµ n (σ)

≤ exp    1 d l∈t i,n (D i ) ï
θ log e αQ Hn ,l g t i,n dµ n + (1θ) log e αQ Hn g t j,n dµ n ò

+ α 2 (1 -θ) 2   
By the induction hypotheses applied with the measure µ n on the normal subgroup G n-1 = H n of S n-1 , and from property (21), it follows that

e αQ i g dµ i ≤ exp ß θαĝ(i) + (1 -θ)αĝ( j) + α 2 (1 -θ) 2 ™ . (33)
We get the same inequality when G is a ℓ-local group and µ = µ o is the uniform law on G, by using property (22), the third part of Lemma 2.5 and the induction hypotheses applied to the uniform measure µ n on the ℓ-local subgroup G n-1 = H n .

According to the definition (28) of the infimum-convolution operator Rĝ defined on the space X = O n , we may easily check that for every i ∈ O n ,

Rĝ(i) = inf θ∈[0,1] ß θ ĝ(i) + (1 -θ) min k∈O n ĝ(k) + 1 2 (1 -θ) 2 ™ .
Therefore optimizing over all θ ∈ [0, 1], we get from (32) and (33): for all i ∈ O n , e αQ i g dµ i ≤ e α Rĝ(i) .

Finally, from Lemma 2.2 applied with the measure ν = νn on O n , the equality (31) gives

e αQ n ϕ dµ ≤ e α R ĝ dν n ≤ Å e -(1-α)ĝ dν n ã -α/(1-α) = Ñ i∈O n νn (i) e -(1-α)g dµ i é -α/(1-α) = Å e -(1-α)g dµ ã -α/(1-α) = Å e -(1-α)ϕ dµ ã -α/(1-α)
.

The proof of (29) is completed.

3. Transport-entropy inequalities on the slice of the cube.

Proof of (a) in Theorem 1.4. We adapt to the space X k,n-k the proof of (a) in Theorem 1.3. In order to avoid redundancy, we only present the main steps of the proof.

By duality, it suffices to prove that for all functions ϕ on X k,n-k and all λ ≥ 0,

e λQϕ dµ k,n-k ≤ e λϕ dµ k,n-k +C k,n-k λ 2 /2 , ( 34
)
where

Qϕ(x) = inf p∈P(X k,n-k ) ß ϕdp + d h (x, y) dp(x) ™ , x ∈ X k,n-k ,
and for any 0

< α < 1, Å e α Q C k,n-k ϕ dµ ã 1/α Å e -(1-α)ϕ dµ ã 1/(1-α) ≤ 1, ( 35
)
where for t > 0,

‹ Q t ϕ(x) = inf p∈P(X k,n-k ) ® ϕ dp + 1 2t Å d h (x, y) dp(y) ã 2 ´, x ∈ X k,n-k .
The proof is by induction over n and 0 ≤ k ≤ n.

For any n ≥ 1, if k = n or k = 0, the set X k,n-k is reduced to a singleton and the inequalities (34) or (35) are obvious.

For n = 2 and k = 1, X k,n-k is a two points set, (34) and (35) directly follows from property (24) and Lemma 2.2 on X = X 1,1 .

For the induction step, we consider the collection of subset Ω i, j , with i, j ∈ {1, . . . , n}, i j, defined by

Ω i, j := x ∈ X k,n-k , x i = 0, x j = 1 . Since for any x ∈ X k,n-k , (i, j),i j 1 Ω i, j (x) = k(n -k),
any probability measure p on X k,n-k admits a unique decomposition defined by p = (i, j),i j p(i, j)p i, j , with p i, j = 1 Ω i, j p p(Ω i, j ) and p(i, j) = p(Ω i, j ) k(nk) .

Thus, we define probability measures p i, j ∈ P(Ω i, j ) and a probability measure p on the set I(n) = {(i, j) ∈ {1, . . . , n} 2 , i j}. For the uniform law µ on X k,n-k , one has

µ = 1 n(n -1) (i, j)∈I(n) µ i, j ,
where µ i, j is the uniform law on Ω i, j , µ i, j (x) = n-2 k-1 , for any x ∈ Ω i, j . For any (i, j), (l, m) ∈ I(n), let s (i, j),(l,m) : X k,n-k → X k,n-k denote the map that exchanges the coordinates x i by x l and x j by x m for any point x ∈ X k,n-k . This map is one to one from Ω i, j to Ω l,m . For any (i, j) ∈ I(n), the set Ω i, j can be identify to X k-1,n-k-1 and therefore the induction hypotheses apply for the uniform law µ i, j on Ω i, j with Hamming distance

d i, j h (x, y) = 1 2 k∈[n]\{i, j} 1 x k y k , x, y ∈ Ω i, j .
For any function f : Ω i, j → R and any x ∈ Ω i, j , we define

Q Ω i, j f (x) := inf p∈P(Ω i, j ) ß f dp + d i, j h (x, y) dp(y) ™ , and
‹ Q Ω i, j t f (x) := inf p∈P(H n ) ® f dp + 1 2t Å d i, j h (x, y) dp(x) ã 2
´.

The key lemma of the proof that replaces Lemma 2.1 and 2.3 is the following.

Lemma 3.1. For any function ϕ : Ω i, j → R and any x ∈ Ω i, j , one has

Qϕ(x) ≤ inf p∈P(I(n))    (l,m)∈I(n) Q Ω i, j (ϕ • s (i, j),(l,m) )(x) p(l, m) + (l,m)∈I(n) 1 (l,m) (i, j) p(l, m)    , and
‹ Q C k,n-k ϕ(x) ≤ inf p∈P(I(n))    (l,m)∈I(n) ‹ Q Ω i, j C k-1,n-k-1 (ϕ • s (i, j),(l,m) )(x) p(l, m) + 1 2 Å (l,m)∈I(n) 1 (l,m) (i, j) p(l, m) ã 2    .
The proof of this lemma is obtained by decomposition of the measures p ∈ P(X k,n-k ) on the sets Ω i, j , and using the following inequality

d h (x, y) ≤ d i, j h (x, s (i, j),(l,m) )(y)) + d h (s (i, j),(l,m) )(y), y) ≤ d i, j h (x, s (i, j),(l,m) )(y)) + 2, for any x ∈ Ω i, j , y ∈ Ω l,m .
Finally, the proof of the induction step based on Lemma 3.1 and the identity

C k,n-k = C k-1,n-k-1 + 1, is left to the reader.
Proof of (b) in Theorem 1.4. We will explain the projection argument on the dual formulations of the transport-entropy inequalities. According to Proposition 4.5 and Theorem 9.5 of [START_REF] Gozlan | Kantorovich duality for general transport costs and applications[END_REF], the weak transport-entropy inequality ( 14) is equivalent to the following property that we want to establish: for any real function f on X k,n-k and for any 0

< α < 1, Å e α Q f dµ k,n-k ã 1/α Å e -(1-α) f dµ k,n-k ã 1/(1-α) ≤ 1, (36)
where

" Q f (x) := inf p∈P(X k,n-k ϕ dp + 1 8 n k=1 Å 1 x k y k dp(y) ã 2 , x ∈ X k,n-k .
Let us apply property (13) to the function f

• P : S n → R. Since µ k,n-k = P#µ, we get Å e α Û Q( f •P) dµ ã 1/α Å e -(1-α) f dµ k,n-k ã 1/(1-α) ≤ 1.
The inequality (36) is an easy consequence of the following result.

Lemma 3.2. For any σ ∈ S n , Ù Q( f • P)(σ) ≥ " Q f (P(σ)).
It remains to prove this lemma. By definition, one has

Ù Q( f • P)(σ) = inf p∈P(S n )    f • P dp + n j=1 Å 1 σ( j) τ( j) dp(τ) ã 2    = inf q∈P(X k,n-k ) inf p∈S n ,P#p=q    f • P dp + n j=1 Å 1 σ( j) τ( j) dp(τ) ã 2    = inf q∈P(X k,n-k )    f dq + inf p∈S n ,P#p=q   n j=1 Å 1 σ( j) τ( j) dp(τ) ã 2      .
Let p ∈ S n such that P#p = q.

1 σ( j) τ( j) dp(τ) = y∈X k,n-k τ∈S n 1 P(τ)=y,σ( j) τ( j) p(τ). For y ∈ X k,n-k , let us note Y = {i ∈ [n], y i = 1}. Then P(τ) = y if and only if τ([k]) = Y. Assume that j ∈ [k], if τ([k]) = Y and σ( j) Y then τ( j) σ( j). Therefore one has τ, τ([k]) = Y, σ( j) Y ⊂ τ, P(τ) = y, σ( j) τ( j) . Assume now that j [k], if τ([k]) = Y and σ( j) ∈ Y then we also have τ( j) σ( j). It follows that τ, τ([k]) = Y, σ( j) ∈ Y ⊂ τ, P(τ) = y, σ( j) τ( j) .
From these observations, we get

n j=1 Å 1 σ( j) τ( j) dp(τ) ã 2 ≥ j∈[k] Å 1 P(τ)=y,σ( j) Y dp(τ) ã 2 + j∈[n]\[k] Å 1 P(τ)=y,σ( j)∈Y dp(τ) ã 2 = j∈[k] Å 1 σ( j) Y dq(y) ã 2 + j∈[n]\[k] Å 1 σ( j)∈Y dq(y) ã 2 = i∈σ([k]) Å 1 i Y dq(y) ã 2 + i σ([k]) Å 1 i∈Y dq(y) ã 2 = i∈σ([k]) Å 1 y i =0 dq(y) ã 2 + i σ([k]) Å 1 y i =1 dq(y) ã 2 Setting x = P(σ), it follows that n j=1 Å 1 σ( j) τ( j) dp(τ) ã 2 ≥ n i=1 ñ 1 x i =1 Å 1 y i =0 dq(y) ã 2 + 1 x i =0 Å 1 y i =1 dq(y) ã 2 ô = n i=1 Å 1 y i x i dq(y) ã 2 . This inequality provides Ù Q( f • P)(σ) ≥ " Q f (x) = " Q f (P(σ)).
The proof of Lemma 3.2 and (b) in Theorem 1.4 is completed.

Appendix

Proof of Lemma 1.1. Let T = (t i j , j ) be a ℓ-local base of a group of permutations G = G n . In order to prove that the map

O 2 × O 3 × • • • × O n → G U T : i 2 , i 3 , . . . , i n → t i 2 ,2 t i 3 ,3 • • • t i n ,n , (37)
is one to one, it suffises to construct its inverse.

For any j ∈ {2, . . . , n}, let U j denotes the map defined by

U j (i 2 , i 3 , . . . , i j ) = t i 2 ,2 t i 3 ,3 • • • t i j , j . Let σ = σ (n) ∈ G.
We want to find the unique vector (i 1 , . . .

, i n ) ∈ O 1 × • • • × O n such that U n (i 1 , . . . , i n ) = U T (i 1 , . . . , i n ) = σ. Since U n (i 1 , . . . , i n )(i n ) = n,
necessarily, one has to fixe i n = (σ (n) ) -1 (n). i n belongs to O n . Let σ (n-1) = σ (n) t -1 (σ (n) ) -1 (n),n . On has σ (n-1) ∈ G n-1 . Then, since n -1 = U n-1 (i 1 , . . . , i n-1 )(i n-1 ) = σ (n-1) (i n-1 ), we necessarily have i n-1 = (σ (n-1) ) -1 (n -1) ∈ O n-1 . We set σ (n-2) = σ (n-1) t -1 (σ (n-1) ) -1 (n-1),n-1 ∈ G n-2 .

Following this induction procedure, we construct a family of permutations σ ( j) ∈ G j for j ∈ [n], such that i j = (σ ( j) ) -1 ( j) ∈ O j for all j ∈ {2, . . . , n}. Observing that G 1 = {Id}, it follows that σ (1) = id and therefore

σ = σ (n) = t i 2 ,2 t i 3 ,3 • • • t i n ,n .
This ends the proof of Lemma 1.1.

Proof of Lemma 1.2. Let G = G n be a ℓ-local group. From the definition of the ℓ-local property, it is clear that any of the subgroup G j , j ∈ {2, . . . , n} is ℓ-local. As a consequence, for any i j ∈ O j , i j j, there exists t i j , j ∈ G j such that t i j , j (i j ) = j, and deg(t i j j ) ≤ ℓ.

This completes the proof of Lemma 1.2.

Proof of Lemma 2.2. Let α ∈ (0, 1) and f be a real function on the finite set X. We want to show that for any probability measure ν on X, Å e α R α f dν

ã 1/α Å e -(1-α)h dν ã 1/(1-α)
≤ 1.

We will apply the following lemma whose proof is given at the end of this section. (1λ)e α R α f (x) + λe α R α f (y) 1/α Ä (1λ)e -(1-α) f (x) + λe -(1-α) f (y)

ä 1/(1-α)
Now, let x and y be some fixed points of X. It remains to show that for any real function f on E and for any x, y ∈ X,

(1λ)e α R α f (x) + λe α R α f (y) 1/α Ä (1λ)e -(1-α) f (x) + λe -(1-α) f (y) ä 1/(1-α) ≤ 1.

The left-hand side of this inequality is invariant by translation of the function f by a constant. Therefore, by symmetry, we may assume that 0 = f (y) ≤ f (x). It follows that R α f (y) = 0. Therefore we want to check that for any non-negative function f on {x, y}, for any λ ∈ [0, 1],

(1λ)e α R α f (x) + λ So, it suffices to check that R α f (x) ≤ φ( f (x)), where

φ(h) = 1 α log Å α 1 -α Ä 1 -e -(1-α)h ä + 1 ã , h ≥ 0.
The function φ is concave and φ(0) = 0. For all h ≥ 0, one has and therefore we exactly have for any x ∈ X,

φ ′ (h) = 1 -α e (1-α)h -α .
φ( f (x)) = inf θ∈[0,1] {θ f (x) + c α (1 -θ)} = R α f (x).
The proof of Lemma 2.2 is completed.

Proof of Lemma 4.1. We will show that, if ν ∈ C is a convex combination of three probability measures ν 1 , ν 2 , ν 3 ,

ν = α 1 ν 1 + α 2 ν 2 + α 3 ν 3 ,
with α 1 0, α 2 0, α 3 0, and α 1 + α 2 + α 3 = 1, and ν 1 (X) > 0, ν 2 (X) > 0, ν 3 (X) > 0, then there exists two measures ν1 , ν2 in C and λ ∈ [0, 1] such that ν = λν 1 + (1λ)ν 2 .

Setting F i = Fdν i , for i = 1, 2, 3, we may assume, without loss of generality, that F 1 ≤ F 2 ≤ F 3 . Then one has either F 1 ≤ K ≤ F 2 , either F 2 ≤ K ≤ F 3 .

We will assume that F 1 ≤ K ≤ F 2 . The case F 2 ≤ K ≤ F 3 can be treated identically and the proof in that case is let to the reader. Since F 1 ≤ K ≤ F 2 and F 1 ≤ K ≤ F 3 , there exists β, γ ∈ [0, 1] such that K = βF 1 + (1β)F 2 and K = γF 1 + (1γ)F 3 . (38)

If F 1 = F 3 then F 1 = F 2 = F 3 = K and therefore ν 1 , ν 2 , ν 3 ∈ C. We may choose λ = α 1 , ν1 = ν 1 and ν2 = α 2 ν 2 +α 3 ν 3 α 2 +α 3 . If F 1 = F 2 then necessarily F 1 = F 2 = F 3 = K and we are reduced to the previous case.

So, we may now assume that F 1 F 3 and F 1 F 2 and therefore F 1 < K ≤ F 2 ≤ F 3 . In that case, we exactly have

β = F 2 -K F 2 -F 1 and γ = F 3 -K F 3 -F 1 .
Let us choose

λ = α 2 1 -β = α 2 F 2 -F 1 K -F 1 , ν1 = βν 1 + (1 -β)ν 2 , ν2 = γν 1 + (1 -γ)ν 2 .
The equalities (38) ensure that ν1 ∈ C and ν2 ∈ C. The proof of Lemma 4.1 ends by checking that λν 1 + (1λ)ν 2 = μ. One has

λν 1 + (1 -λ)ν 2 = (λβ + (1 -λ)γ)ν 1 + λ(1 -β)ν 2 + (1 -λ)(1 -γ)ν 3 . (39)
According to the definitions of λ, β, γ, we may easily check that λ(1β) = α 2 , and

(1 -λ)(1 -γ) = K -F 1 F 3 -F 1 -α 2 F 2 -F 1 F 3 -F 1 .
Since μ ∈ C, one has (1 -(α 2 + α 3 ))F 1 + α 2 F 2 + α 3 F 3 and therefore

(1λ)(1γ) = α 3 .

As a consequence λβ + (1λ)γ = 1α 2α 3 = α 1 and according to (39), we get λν 1 + (1λ)ν 2 = α 1 ν 1 + α 2 ν 2 + α 3 ν 3 = ν.

with

  Qϕ(σ) = inf p∈P(S n ) ß ϕdp + d(σ, τ) dp(τ) ™ We will prove the inequality (23) by induction on n. Assume that n = 2. If G = {id} then K n = 0 and the inequality (23) is obvious. If G {id}, then G is the two points space, G = S 2 , ℓ = 2 and one has

  Let g = ϕ {-1} . According to the decomposition of the measure µ on the setsH i , i ∈ O n , e αQ n ϕ dµ = i∈O n νn (i) e αQ i g dµ i . (31) For k ∈ O n , let us note ĝ(k) := log Å e -(1-α)g dµ k ã -1/(1-α).We choose j ∈ O n such that min k∈O n ĝ(k) = ĝ( j).

Lemma 4. 1 .

 1 Let F be a real function on X and K ∈ R. Let us consider the setC := ß ν ∈ P(X), F dν = K ™ .If C is not empty, then the extremal points of this convex set are Dirac measures or convex combinations of two Dirac measures on X.Given a real function f on X, for any K ∈ R, letC K = ß ν ∈ P(X), e -(1-α) f dν = K α R α f dν å 1/α K 1/(1-α)The supremum of the linear function ν → e α R α f dν on the non empty convex set C K is reached at an extremal point of C K . Therefore, by Lemma 4.1, we get sup

  λ)e -(1-α) f (x) + λ ä 1/(1-α) ≤ 1, or equivalently, setting ψ(λ) = Ä (1λ)e -(1-α) f (x) + λ ä -α/(1-α)λ, e α R α f (x) ≤ inf λ∈[0,1) ψ(λ)ψ(1) 1λ = -ψ ′ (1) = α 1α Ä 1e -(1-α) f (x) ä + 1, since ψ is a convex function on [0, 1].

  The function φ ′ is a bijection from [0, +∞) to (0, 1]. It follows thatφ(h) = inf θ∈(0,1] {θh + c α (1θ)} , h ≥ 0,where c α is the convex function defined byc α (1θ) = sup h∈[0,+∞) {-θh + φ(h)} , θ ∈ (0, 1].After computations, we getc α (u) := α(1u) log(1u) -(1αu) log(1αu) α(1α) ,

Acknowledgements. The author thanks R. Adamczak and D. Chafaï for useful discussions, that lead to consider the Ewens distribution, and the number of cycles of given lenght, as examples to illustrate the results of this paper.

Supported by the grants ANR 2011 BS01 007 01, ANR 10 LABX-58.