Adrian Kosowski

Marcin Markiewicz

Lower Bounds on the Communication Complexity of Binary Local Quantum Measurement Simulation

 have presented a 2-bit protocol which simulates one particular correlation function arising from binary projective quantum measurements on arbitrary state, and in particular does not preserve local averages. The question of simulating other correlation functions using a protocol with bounded communication, or preserving local averages, has been posed as an open one. Within this paper we resolve it in the negative: we show that any such protocol must have unbounded communication for some subset of executions. In particular, we show that for any protocol, there exist inputs for which the random variable describing the number of communicated bits has arbitrarily large variance.

Introduction. It is known since Bell's seminal paper [1], that quantum mechanics of many parties predicts correlations of measurement outcomes that cannot be reconstructed using only locally computable functions without any communication between the parties. This property is commonly referred to as quantum nonlocality (not to be confused with nonlocality in the sense of special relativity, cf. [2] for a comprehensive discussion of the topic). The degree of quantum nonlocality in a computational setting can be intuitively described using the scenario of communication complexity, in which one asks how much communication is needed to perform some distributed task. From this perspective, the communication cost of classically simulating quantum measurements is one of the most important approaches to characterizing the fundamental difference between classical and quantum correlations [3].

All further considerations are performed using the scenario of randomized communication complexity proposed by Yao [START_REF] Yao | Proceedings of the 11th Annual ACM Symposium on Theory of Computing[END_REF]. In a bipartite version of this scenario, two separate processors with no bounds on local memory and computational efficiency are considered. They can share random numbers (a so-called public coin), and can exchange bits with each other. They are given inputs (which in case of Bell inequalities scenario correspond to measurement settings), and their task is to produce discrete outputs. The statistical distribution of the outputs with respect to used random resources is required to fulfill some task distribution and the algorithm should be performed with minimal possible amount of communicated bits.

Within the scenario of randomized bipartite communication complexity we consider the problem of simulating local quantum measurements, in which Alice and Bob are given as an input the classical description of their own local observable and of the entire quantum state, and their task is to output some numbers, whose statistical distri-bution is to some extent consistent with the distribution of measurement outcomes predicted by quantum theory. The problem can be treated in two different variants. In the first one (CS -Correlation Simulation) the task is to perfectly simulate correlations of outcomes of all possible quantum measurements, whereas no restrictions are imposed on local averages of outputs. The second approach (LQM S -Local Quantum Measurement Simulation) demands both the perfect simulation of correlations and the perfect simulation of local quantum averages.

The communication complexity of the above-defined problems is not known in general, and only partial results have been proposed. In the case of the first approach (CS), the problem has been solved in general for binary (two-outcome) projective measurements on an arbitrary quantum state by Regev and Toner [START_REF] Regev | Annual IEEE Symposium on Foundations of Computer Science[END_REF], who proposed a bounded-worst-case randomized protocol which solves the problem with two bits of one-way communication. This result saturates the lower bound derived in [START_REF] Vertesi | [END_REF], who showed that one bit is not sufficient. In the case of d-outcome projective measurements, a lower bound of Ω(d) bits of communication is known [7], whereas for the special case of arbitrary POVM measurements on n Bell states shared between Alice and Bob a protocol exists which uses O(n2 n ) bits of communication on average [8]. In the case of LQM S only the case of a maximally entangled state of two qubits has been solved. Toner and Bacon [9] have shown that in case of projective measurements on such a state, there exists a bounded-worstcase one-bit protocol, whereas in case of aribtrary POVM measurements there exists a protocol which uses six bits in expectation [10].

In this paper we focus on the LQM S problem for binary (two-outcome) observables, which we refer to as BLQM S. We construct a lower bound on all the statistical moments of the random variable describing the number of communicated bits in any protocol which ex-actly performs BLQM S. This lower bound implies that for any protocol solving BLQM S, the number of communicated bits has unbounded variance (as well as all higher moments) with respect to the dimension of the state space. This implies not only that there is no boundedworst-case protocol for BLQM S which works for arbitrary dimension of the state space, but also that for any BLQM S protocol working in finite time the expected number of bits has a large dispersion. To the best of our knowledge, the presented characterization of communication complexity of BLQM S is the most general among all already proposed, and gives an important insight into the characterization of quantum nonlocality from the perspective of communication complexity.

Basic concepts and methods. We formally define the Binary Local Quantum Measurement Simulation (BLQM S) problem as follows. The inputs of Alice and Bob are the pairs (A, σ) and (B, σ), where σ is a density matrix of dimension n 2 × n 2 , representing an arbitrary state of two n-dimensional quantum systems, and A and B are Hermitian operators with spectrum {-1, 1}. Alice and Bob are equipped with an infinite source of shared randomness. The protocol is randomized and the task of Alice and Bob is to output values y A , y B ∈ {-1, 1}, respectively, such that the corresponding random variables y A , y B , taken over multiple runs of the protocol, have correlations and local averages statistically indistinguishable from those resulting from a quantum measurement of state σ with the measurement operator A ⊗ B, i.e.:

E(y A y B ) = Tr((A ⊗ B)σ), E(y A ) = Tr((A ⊗ 1 1)σ), E(y B ) = Tr((1 1 ⊗ A)σ). (1)
For our purposes the above requirements for expected values can be equivalently reformulated as conditions on joint probabilities. Indeed, any Hermitian operator with spectrum {-1, 1} can be represented in terms of multidimensional projectors:

A = 2P A -1 1 B = 2P B -1 1. (2)
Denoting by p α,β , α, β = {-1, +1}, the joint probability:

p α,β ≡ Pr[y A = α ∧ y B = β], (3)
we can formulate the following set of conditions:

p 1,1 = Tr((P A ⊗ P B )σ) p -1,1 = Tr(((1 1 -P A ) ⊗ P B )σ) p 1,-1 = Tr((P A ⊗ (1 1 -P B )σ) p -1,-1 = 1 -p 1,1 -p -1,1 -p 1,-1 . (4)
Note that by ( 1)-( 4), we have

E(y A y B ) = 1 -2p -1,1 -2p 1,-1 E(y A ) = -1 + 2p 1,1 + 2p 1,-1 E(y B ) = -1 + 2p 1,1 + 2p -1,1 . (5)
Thus, the tuples (E(y A y B ), E(y A ), E(y B )) and (p 1,1 , p -1,1 , p 1,-1 ) can be uniquely determined from each other by linear transformation, and we have the following claim.

Proposition 1. For any given inputs (A, σ) and (B, σ), a BLQM S protocol preserves the set of conditions (1) on expected values of outcomes in quantum measurement simulation if and only if it preserves the set of conditions (4) on joint probabilities.

In the proof of the main result we make use of the lower bound for nondeterministic communication complexity of the Deutsch-Jozsa problem [11], which in the vectorbased representation can be formulated as follows. Alice and Bob are given an n-bit vector a and b respectively, with each coordinate equal to -1 or +1: a, b ∈ {-1, 1} n , with n even. A promise is made on the value of the scalar product of the inputs, which may take one of two values: a • b ∈ {0, n}. The task of Alice and Bob is to decide which of the two cases holds, i.e., whether a•b = 0 (equivalently, if a and b are equal on exactly n/2 coordinates) or a • b = n (equivalently, if a and b are equal on all n coordinates). Formally, we can define the task function:

f (a, b) = [a • b = n], (6)
where the square bracket denotes the logical value. We recall that the nondeterministic communication complexity of the function f for accepting (rejecting), denoted N 1 (f ) (respectively, N 0 (f )), is the size of the smallest string which can be provided by an oracle to both Alice and Bob to convince them with certainty that f (a, b) = 1 (respectively, f (a, b) = 0). The following lower bound on N 1 (f ) holds.

Proposition 2. N 1 (f ) ≥ 0.007n/(log 2 n + 3) -1.
Proof. By the classic theorem of Aho, Ullman, and Yannakakis [START_REF] Aho | Proceedings of the 15th ACM Symposium on Theory of Computing[END_REF], we have:

D(f ) ≤ (N 0 (f ) + 1)(N 1 (f ) + 1),
where D(f ) is the deterministic two-party communication complexity of the function f . It is known [START_REF] Buhrman | Proceedings of the 30th ACM Symposium on Theory of Computing[END_REF] that for the considered function f , D(f ) ≥ 0.007n. Moreover, we trivially have N 0 (f ) ≤ ⌈log 2 n⌉ + 1, since for a rejecting input (with vectors a and b differing on exactly half of the coordinates), the oracle can communicate to Alice and Bob the pair (i, α), with i ∈ {1, . . . , n}, α ∈ {-1, 1}, representing a coordinate i such that a i = α and b i = -α; the existence of such a coordinate can be verified by Alice and Bob for each of these two equalities, respectively. The claim follows.

We proceed to show that any protocol which solves BLQM S for dimension n can be used as a black-box for designing an oracle verification protocol in the nondeterministic accepting Deutsch-Jozsa problem. More precisely, we will show that for any protocol BLQM S which communicates Ω(n/ log 2 n) bits with small probability (o(1/n) for all inputs), there would exist sets of inputs of dimension n and corresponding initializations of the (shared) randomness of this protocol which could be used to solve Deutsch-Jozsa on all n-bit vectors with nondeterministic communication complexity

N 1 (f ) = o(n/ log 2 n), a contradiction with Proposition 2.
Construction of the lower bound. Using the equivalent characterization of the BLQM S (Proposition 1), for the purpose of the lower bound we define a restricted version BLQM S of the protocol, in which we only require that the first of the conditions ( 4) is preserved, namely that:

Pr [y A = 1 ∧ y B = 1] = Tr((P A ⊗ P B )σ). ( 7
)
We consider the special class of inputs by adding the promise that σ is a maximally entangled n-dimensional state, whereas P A and P B are 1-dimensional projectors, of the form P A = 1 n |a a| and P B = 1 n |b b|, where (a, b) is a valid pair of inputs to the vector version of the Deutsch-Jozsa problem, i.e., satisfying a, b ∈ {-1, +1} n and a • b ∈ {0, n}. For the maximally entangled state, the constraint (7) can be rewritten as:

Pr [y A = 1 ∧ y B = 1] = 1 n 2 (a • b) = 1 n f (a, b), (8)
where the function f corresponds to a solution to the Deutsch-Jozsa problem.

In the above, the probability distribution is governed by the choice of randomness: the shared randomness accessible to Alice and Bob, and the private randomness ("coin tosses") used by Alice and Bob individually during the execution of their protocol. Without loss of generality, we can in fact assume that all randomness is shared, and that the random choices made during an execution of the protocol are parameterized by a random vector λ ∈ X, where λ is sampled uniformly from some probabilistic space X with measure µ, independent of the inputs a and b. The pairs (a, λ) and (b, λ), satisfying a, b ∈ {-1, +1} n , a • b ∈ {0, n}, and λ ∈ X, will now be treated as the inputs of our restricted version BLQM S of the BLQM S problem. The deterministic protocol solving BLQM S must decide on a value g(a, b, λ) = [y A = 1 ∧ y B = 1] ∈ {0, 1}, and it will be considered correct if it achieves the correct probability distribution of outputs over choices of λ:

E λ g(a, b, λ) = 1 n f (a, b),
where we use the notation: E λ • ≡ λ∈X • dµ. We make the technical assumption that the considered protocols are always such that the function g is measurable; otherwise, the concept of expectation of outcomes is hard to define.

Fix a deterministic protocol solving BLQM S. Let T (a, b, λ) be the number of bits communicated by Alice and Bob in total during the execution of this protocol for inputs (a, λ) and (b, λ). We will now show that the the probability distribution of T (a, b, λ) has a heavy tail over λ for some input pairs, regardless of the considered protocol for BLQM S.

We first show that the "power" of the shared randomness of BLQM S in the context of our lower-bound argument is limited, and corresponds, roughly speaking, to O(log n) bits of additional information received from the oracle. We start with a lemma which provides a convenient partition of the set of input vectors {-1, 1} n for BLQM S into O(n 2 ) subsets, given a bound on the tail of the communication complexity of the BLQM S protocol. Each of the subsets of the partition will be associated with a corresponding random vector λ for which the output of the BLQM S protocol is "useful" from the perspective of simulating Deutsch-Jozsa. Since the number of subsets in the partition is polynomial in n, given any input for Alice and Bob, an oracle for Deutsch-Jozsa will be able to prompt the right value of λ to Alice and Bob using O(log n) bits of additional information. (We remark that eliminating shared randomness is a well-known concept in communication complexity [START_REF] Newman | [END_REF], but our case concerns a different scenario of non-deterministic communication complexity.) Lemma 1. Assume that for some input size n and some M > 0, the considered protocol for BLQM S on any pair of input vectors will have a message complexity not smaller than M with probability at most 1 2n :

∀ a,b∈{-1,+1} n µ({λ : T (a, b, λ) ≥ M }) < 1 2n .
Then there exists a partition of the set of n-dimensional input vectors: {-1, 1} n = S 1 ∪ . . . ∪ S 2n 2 , such that each of the sets of inputs S j is associated with a fixed vector λ j ∈ X such that the following properties are fulfilled:

1. g(a, a, λ j ) = 1, for all a ∈ S j .

2. T (a, a, λ j ) < M, for all a ∈ S j .

In other words, λ j ∈ X leads to an "accepting" outcome to BLQM S within less than M communicated bits when Alice and Bob both receive the same input vector from S j .

Proof. Let A 0 = {-1, 1} n be the set of n-dimensional vectors, with |A 0 | = 2 n . Consider any input to the BLQM S with f (a, b) = 1, i.e., with a = b ∈ A 0 . Let:

Λ(a) = {λ ∈ X : g(a, a, λ) = 1 ∧ T (a, a, λ) < M }.
We have:

µ({λ ∈ X : g(a, a, λ) = 1}) = E λ g(a, a, λ) = 1 n
and by the assumption of the Lemma:

µ({λ ∈ X : T (a, a, λ) ≥ M }) < 1 2n , hence µ(Λ(a)) ≥ 1 n -1 2n = 1 2n
. Let c 0 : X → {0, . . . , 2 n } be a function which assigns to each λ the number of inputs a ∈ A 0 for which randomness λ leads to an "accepting" outcome, formally, c 1 = |S 1 (λ)| with S 1 (λ) = {a ∈ A 0 : λ ∈ Λ(a)}. Function c 1 is clearly measurable, and:

E λ c 1 = a∈A0 µ(Λ(a)) = |A 0 |/n = 2 n /(2n).
By the pigeon-hole principle, it follows that there exists λ 1 ∈ X with c 1 (λ 1 ) ≥ 2 n /(2n) and so |S 1 (λ 1 )| ≥ 2 n /(2n). Let A 1 be defined as the set of inputs for which randomness λ 1 does not lead to an accepting outcome,

A 1 = A 0 \ S 1 (λ 1 ), with |A 1 | ≤ |A 0 |(1 -1/(2n)
). We iterate the process, defining in general 2n) . The process is completed when |A i | < 1, i.e., (2 ln 2)n -i/n < 0, or i > (2 ln 2)n 2 (where 2 ln 2 < 2). Thus, the family of sets S 1 (λ 1 ), . . . , S i (λ i ), for i = 2n 2 , constitutes a partition of the set A 0 of n-dimensional vectors.

A i = A i-1 \ S i (λ i ), where S i (λ i ) = {a ∈ A i-1 : λ i ∈ Λ(a)} and λ i is chosen so that |S i (λ i )| ≥ |A i-1 |/(2n). It follows that |A i | ≤ |A i-1 |(1 -1/(2n)), and so |A i | ≤ |A 1 |(1 - 1/(2n)) i-1 < 2 n e -i/(2n) = e n ln 2-i/(
We are now ready to provide our main technical theorem, showing that communication complexity distribution of any BLQM S protocol has a heavy tail.

Theorem 1. Fix any even value n > 10 7 and let M (n) = 0.003n/ log 2 n. For any protocol for BLQM S, there exists a pair of input vectors (a, b) of length n for such that the protocol requires at least M (n) communicated bits for this input pair with probability at least 1 2n , taken over the shared randomness, i.e.:

µ({λ : T (a, b, λ) ≥ M (n)}) ≥ 1 2n .
Proof. The proof proceeds by contradiction. Suppose that the claim of the Theorem is not true for some value of n, and consider a protocol for BLQM S which violates the claim for this value of n. This means that the assumptions of Lemma 1 hold for the considered protocol on inputs of dimension n and M ≡ M (n).

To complete the proof, we will now show that the existence of such a protocol can be used to construct a nondeterministic accepting-outcome oracle and verifier for the Deutsch-Jozsa problem on vectors of size n having nondeterministic-accepting communication complexity violating the lower bound on N 1 (f ). Consider the following oracle-verifier pair for the Deutsch-Jozsa problem:

The oracle: For a given accepting input (a, b) with vectors of length n satisfying the Deutsch-Jozsa promise (i.e., a = b), the oracle finds the set S j ⊆ A 0 , which satisfies a ∈ S j in the partition given by Lemma 1, and the corresponding randomness λ j ∈ X. It then performs a simulation of the execution of the BLQM S according to the considered protocol, achieving an accepting outcome (g(a, a, λ j ) = 1.) Finally, the oracle communicates the following string to both Alice and Bob:

1. The integer value j ∈ {1, . . . , 2n 2 }.

2. A complete transcript of the messages communicated between Alice and Bob in the simulation of the BLQM S protocol for Alice's input (a, λ j ) and Bob's input (a, λ j ).

The verifier: Alice and Bob both receive the value of j from the oracle, and use it to compute the corresponding randomness λ j ∈ X. Then, Alice initializes a simulation of her part of the BLQM S protocol assuming her input as (a, λ j ). Whenever the BLQM S protocol would require her to receive a message from Bob, she reads the treats the corresponding part of the transcript received from the oracle as the message received from Bob. Whenever Alice sends a message in the protocol, she verifies if the message she sent corresponds to that written in the transcript provided by the oracle. If and only if there are no discrepancies and the outcome of Alice in the BLQM S protocol is 1, the Deutsch-Jozsa verifier returns in "accepting" state. Bob simulates the BLQM S protocol likewise for the input (a, λ j ), trusting messages provided by the oracle for the communication from Alice to Bob, verifying all messages sent from Bob to Alice, and signaling "accepting" state if and only if there are no discrepancies and the outcome of Bob in the BLQM S protocol is 1.

We now proceed to show the correctness of the oracle-verifier construction for the Deutsch-Jozsa problem. First, observe that for any n-bit Deutsch-Jozsa input (a, b) satisfying a = b, the value of λ j prompted by the oracle satisfies g(a, a, λ j ) = 1, hence both Alice and Bob obtain an outcome of 1 in the BLQM S protocol. The verification process proceeds successfully, and the verifier returns in accepting state for both Alice and Bob. Conversely, suppose that the Deutsch-Jozsa input (a, b) satisfies a • b = 0, and that the oracle provides some integer value j ′ and some message transcript to Alice and Bob. Alice and Bob both compute λ j ′ and perform the simulation of the BLQM S protocol for respective inputs (a, λ j ′ ) and (b, λ j ′ ). If the transcript provided by the oracle corresponds precisely to a simulation of the considered BLQM S protocol for these inputs, then Alice and Bob do not detect any errors and compute their BLQM S outputs. Since g(a, b, λ j ′ ) = 1 n f (a, b) = 0, at least one of the parties must return an output of -1 in BLQM S, thus signaling a non-accepting outcome of the verification process. Now, consider the length of the string communicated by the (correctly functioning) oracle to Alice and Bob for an accepting input (a, b), with a = b. Encoding the value of j requires log 2 (2n 2 ) = 2 log 2 n + 1 bits. By Lemma 1, the total number of bits exchanged in the simulation of the BLQM S protocol is less than M (n) bits, thus the transcript can be easily encoded using less than 2M (n) bits (including markers describing which parts of the message were communicated by Alice and which were communicated by Bob). It follows that the total length of the string provided by the oracle to the verifier is at most 2 log 2 n + 2M (n), and therefore this value is lowerbounded by the nondeterministic-accepting communication complexity of the Deutsch-Jozsa problem for inputs of length n:

2 log 2 n + 2M (n) ≥ N 1 (f ) ≥ 0.007n/(log 2 n + 3) -1, hence: M (n) ≥ 0.0035n/(log 2 n + 3) -log 2 n -0.5.
However, we have M (n) = 0.003n/ log 2 n by definition, and we obtain a contradiction for all n > 10 7 , which completes the proof.

The lower bound on the tail of the number of communicated bits in the protocol, given by the above theorem, obviously also applies to the BLQM S problem, of which BLQM S was a restricted case. Thus, we directly obtain lower bounds on the variance and higher moments of the communication complexity of any protocol for BLQM S.

Theorem 2 (Lower bound on BLQMS). For any protocol solving exactly the BLQM S problem, let T (k) (n) = max a,b∈{-1,+1} n E λ T k (a, b, λ) be the k-th (non-central) moment of the random variable describing the number of communicated bits, taken over the probability distribution of λ, for a worst-case pair of inputs a, b of length n. Then for any even n > 10 7 the following lower bound holds:

T (k) (n) ≥ 1 2n M k (n) = 0.5 (0.003n) k-1 log k 2 n
.

In particular, it follows that the second non-central moment has an asymptotic growth rate of T (2) (n) = Ω(n/ log 2 n), and lim sup n→+∞ T (2) n = +∞. In this way, we obtain the main result of our paper: Theorem 3. If for some protocol for the BLQM S problem the random variable describing the number of communicated bits has finite expectation for any input pair of arbitrary dimension, its variance must be unbounded.

Conclusions. Using the methods of nondeterministic communication complexity, we have derived a lower bound on the communication complexity of the Binary Local Quantum Measurement Simulation, showing that any protocol solving this problem exactly can at most have a finite expected number of communicated bits, whereas all higher statistical moments of this quantity are necessarily unbounded with respect to the input size (which is directly related to the dimension of the space of quantum states, on which the measurements are performed). We pose as an open question whether there exists such a protocol working with finite expected communication for an arbitrary quantum state.

Acknowledgements. We would like to thank Caslav Brukner and Marek Żukowski for helpful discussions. MM is supported by the International PhD Project: "Physics of future quantum based information technologies" grant MPD/2009-3/4, the NCN grant No. 2012/05/E/ST2/02352 and by the project QUASAR.


Nathael Gozlan
email: nathael.gozlan@univ-mlv.fr

Cyril Roberto
email: croberto@math.cnrs.fr

Paul-Marie Samson
email: paul-marie.samson@univ-mlv.fr

P-M Samson

From dimension free concentration to Poincaré inequality

Keywords: . 1991 Mathematics Subject Classification. 60E15, 32F32 and 26D10 Poincaré inequality, concentration of measure, metric spaces, Hamilton-Jacobi equation

Introduction

Throughout the paper (X, d) denotes a polish metric space and P(X) the set of Borel probability measures on X. On the product space X n , we consider the following ℓ p product distance d p defined by

d p (x, y) =        n i=1 d p (x i , y i )        1/p , x, y ∈ X n , p ≥ 1.
(Note that the dependence on the dimension n is understood.) If A is a Borel subset of X n , we define its enlargement A r,p (simply denoted by A r when n = 1), r ≥ 0 as follows A r,p = {x ∈ X n ; d p (x, A) ≤ r}.

Also, in all what follows, α : R + → R + will always be a non increasing function. One will say that µ ∈ P(X) satisfies the dimension free concentration property with the concentration profile α and with respect to the ℓ p product structure if (1.1) µ n (A r,p ) ≥ 1α(r), ∀r ≥ 0, for all A ⊂ X n , with µ n (A) ≥ 1/2. For simplicity, we will often say that µ satisfies the dimension free concentration inequality CI ∞ p (α), and, if µ satisfies (1.1) only for n = 1, we will say that µ satisfies CI(α). We refer to [START_REF] Ledoux | The concentration of measure phenomenon[END_REF] for an introduction on the notion of concentration of measure.

The general problem considered in this paper is to give a characterization of the class of probability measures satisfying CI ∞ p (α). Our main result shows that the class of probability measures satisfying CI ∞ 2 (α), for some non trivial α, always contains the class of probability measures satisfying the Poincaré inequality. Moreover, these two classes coincide when α is exponential: α(r) = be -ar , for some a, b > 0.

Before stating this result, let us recall the definition of the Poincaré inequality: one says that µ ∈ P(X) satisfies the Poincaré inequality with the constant λ ∈ R + ∪ {+∞}, if

(1.2) λVar µ ( f ) ≤ |∇ -f | 2 dµ,
for all Lipschitz function f : X → R, where by definition

|∇ -f |(x) = lim sup y→x [ f (y) -f (x)] - d(y, x) , (with [
X] -:= max(-X, 0)) when x is not isolated in X (we set |∇ -f |(x) = 0, when x is isolated in X). By convention ∞×0 = 0, so that λ = +∞ if and only if µ is a Dirac measure.

Remark 1.3. Let us make a few comments about the definition of the Poincaré inequality.

(1) Since the right hand side of (1.2) is always finite when f is Lipschitz, it follows in particular that Lipschitz functions always have finite variance when Poincaré inequality holds. ( 2) When (X, d) is a smooth Riemannian manifold equipped with its geodesic distance and f : X → R, it is not difficult to check that if f is differentiable at a point x, then |∇ -f |(x) coincides with the norm of the vector ∇ f (x) (belonging to the tangent space at x). If (X, d) = (B, • ) is a Banach space, and f : B → R is differentiable at x ∈ B, then 2) and (1.4) both imply yet another version of Poincaré inequality (considered for instance in [START_REF] Ledoux | The concentration of measure phenomenon[END_REF] or [START_REF] Bobkov | Poincaré's inequalities and Talagrand's concentration phenomenon for the exponential distribution[END_REF]):

|∇ -f |(x) is equal to D f (x) * ,
(1.5)

λVar µ ( f ) ≤ |∇ f | 2 dµ,
for all Lipschitz function f : X → R. That (1.5) also implies (1.2) is not obvious. A proof of this fact can be found in [START_REF] Gigli | From log Sobolev to Talagrand: a quick proof[END_REF]Proposition 5.1] (the result is stated for the logarithmic Sobolev inequality but the same conclusion holds for the Poincaré inequality). The proof relies on a technique, developed in [START_REF] Ambrosio | Calculus and heat flow in metric measure spaces and applications to spaces with Ricci bounds from below[END_REF], consisting in relaxing the right hand side of (1.5) and yielding to the notion of Cheeger energy.

1.1. Main results. Denote by Φ the tail distribution function of the standard Gaussian measure γ(dx) = (2π) -1/2 e -x 2 /2 dx on R defined by

Φ(x) = 1 √ 2π +∞ x e -u 2 /2 du, x ∈ R.
The main result of this paper is the following theorem.

Theorem 1.6. If µ satisfies the dimension free concentration property CI ∞ 2 (α), then µ satisfies the Poincaré inequality (1.2) with the constant λ defined by

√ λ = sup        Φ -1 (α(r)) r ; r > 0 s.t α(r) ≤ 1/2        .
Moreover, if α is convex decreasing and such that α(0) = 1/2, then λ = (2πα ′ + (0) 2 ), where α ′ + (0) ∈ [-∞, 0) is the right derivative of α at 0. Conversely, it is well known -since the work by Gromov and Milman [START_REF] Gromov | A topological application of the isoperimetric inequality[END_REF] (see also [START_REF] Aida | Moment estimates derived from Poincaré and logarithmic Sobolev inequalities[END_REF], [START_REF] Bobkov | Poincaré's inequalities and Talagrand's concentration phenomenon for the exponential distribution[END_REF], [START_REF] Schmuckenschläger | Martingales, Poincaré type inequalities, and deviation inequalities[END_REF], [START_REF] Gozlan | Poincaré inequalities and dimension free concentration of measure[END_REF] for related results) -that a probability measure µ verifying the Poincaré inequality satisfies a dimension free concentration property with a profile of the form α(r) = be -ar , for some a, b > 0. We recall this property in the following theorem and refer to Section 5 for a proof. Theorem 1.7 (Gromov and Milman). Suppose that µ satisfies the Poincaré inequality (1.2) with a constant λ > 0, then it satisfies the dimension free concentration property with the profile

α(r) = b exp(-a √ λr), r ≥ 0,
where a, b are universal constants.

Thus, Theorem 1.6 and Theorem 1.7 give a full description of the set of probability distributions verifying a dimension free concentration property with a concentration profile α such that {r : α(r) < 1/2} ∅ : this set coincides with the set of probability measures verifying the Poincaré inequality. An immediate corollary of Theorem 1.6 and Theorem 1.7 (see Corollary 4.4 below) is that any type of dimension free concentration inequality can always be improved into a dimension free concentration inequality with an exponential profile (up to universal constants). This was already noticed by Talagrand in [START_REF] Talagrand | A new isoperimetric inequality and the concentration of measure phenomenon[END_REF]. See Section 4.3 for a further discussion.

Remark 1.8. Let us make some comments on the constant λ appearing in Theorem 1.6.

(1) We observe first that λ > 0 if and only if there is some r o > 0 such that α(r o ) < 1/2. In particular, Theorem 1.6 applies in the case of the following "minimal" profile α = β a o ,r o , defined as follows

(1.9) β a o ,r o (r) = 1/2, if r < a o and β a o ,r o (r) = a o , if r ≥ r o , where a o ∈ [0, 1/2), r o > 0. If a probability measure satisfies CI ∞ 2 (β a o ,r o )
, then it satisfies the Poincaré inequality with the constant

λ a o ,r o := Φ -1 (a o ) r o
(2) Then we notice that any non increasing function α : R + → R + , with α(0) = 1/2, can be written as an infimum of minimal profiles:

α = inf r>0 β α(r),r .
Therefore, the constant λ given in Theorem 1.6 is the supremum of the constants λ α(r),r r > 0 defined above. This shows that the information contained in the concentration profile α is treated pointwise, and that the global behavior of α is not taken into account. (3) It is well known that the standard Gaussian measure γ satisfies the dimension free concentration property with the profile α = Φ (this follows from the Isoperimetric theorem in Gauss space due to Sudakov-Cirelson [START_REF] Sudakov | Extremal properties of half-spaces for spherically invariant measures[END_REF] and Borell [START_REF] Borell | The Brunn-Minkowski inequality in Gauss space[END_REF], see e.g. [START_REF] Ledoux | The concentration of measure phenomenon[END_REF]). Hence, applying Theorem 1.6, we conclude that γ satisfies the Poincaré inequality with the constant λ = 1, which is well known to be optimal (see e.g. [START_REF] Ané | Sur les inégalités de Sobolev logarithmiques, volume 10 of Panoramas et Synthèses [Panoramas and Syntheses[END_REF]Chapter 1]). (4) Finally we observe that, if the concentration profile α(r) goes to zero too fast when r → ∞, then λ = +∞ and so µ is a Dirac measure. This happens for instance when α(r) = be -ar k , r ≥ 0, with k > 2 and a, b > 0.

Theorem 1.6 completes a previous result obtained by the first author [START_REF] Gozlan | A characterization of dimension free concentration in terms of transport inequalities[END_REF] (see also [START_REF] Gozlan | From concentration to logarithmic Sobolev and Poincaré inequalities[END_REF]), namely that the Gaussian dimension free concentration is characterized by a transport-entropy inequality. We now state this result and start by recalling some notation. The Kantorovich-Rubinstein distance W p , p ≥ 1, between ν, µ ∈ P(X) is defined by

W p p (ν, µ) = inf Π(ν,µ) E[d p (X, Y)],
where the infimum runs over the set Π(ν, µ) of couples of random variables (X, Y) such that Law(X) = µ and Law(Y) = ν. Then, a probability measure is said to satisfy the p-Talagrand transport-entropy inequality with constant C > 0, if it holds

(1.10) W p p (ν, µ) ≤ CH(ν|µ), ∀ν ∈ P(X),
where the relative entropy functional is defined by H(ν|µ) = log dν dµ dν if ν is absolutely continuous with respect to µ, and H(ν|µ) = +∞ otherwise. Inequalities of this type were introduced by Marton and Talagrand in the nineties [START_REF] Marton | A simple proof of the blowing-up lemma[END_REF][START_REF] Talagrand | Transportation cost for Gaussian and other product measures[END_REF]. We refer to the survey [START_REF] Gozlan | Transport inequalities. A survey. Markov Process[END_REF] for more informations on this topic. Theorem 1.11 ([17]). Fix p ≥ 2 and C > 0. Then, a probability measure µ satisfies the p-Talagrand transport inequality (1.10) with constant C if and only if it satisfies the dimension free concentration inequality CI ∞ p (α), with a concentration profile of the form

α(r) = exp - 1 C [r -r o ] p + , r ≥ 0,
for some r o ≥ 0 (with [X] + := max(X, 0)).

As we will see, the proofs of Theorem 1.6 and 1.11 are very different. Both make use of probability limit theorems, but not at the same scale: Theorem 1.11 used Sanov's large deviations theorem, whereas Theorem 1.6 is an application of the central limit theorem. Moreover, contrary to what happens in Theorem 1.6 (see Item (2) of Remark 1.8), the global behavior of the concentration profile is used in Theorem 1.11.

In view of Theorems 1.6 and 1.11, it is natural to formulate the following general question:

(Q) Which functional inequality is equivalent to CI ∞ p (α) for a concentration profile of the form α(r) = exp(-a[r -r o ] k + ), r ≥ 0,
where a > 0, r o ≥ 0 and k > 0 ?

Remark 1.12. It is easy to see, using the Central Limit Theorem, that for p ∈ [1, 2) the only probability measures verifying CI ∞ p (α), for some α such that α(r o ) < 1/2 for at least one r o > 0, are Dirac masses. Thus the question (Q) is interesting only for p ≥ 2.

To summarize, Theorem 1.11 shows that the answer to (Q) is the p-Talagrand inequality for k = p and p ≥ 2. Theorem 1. [START_REF] Bobkov | Hypercontractivity of Hamilton-Jacobi equations[END_REF] shows that the answer is the Poincaré inequality for p = 2 and for k ∈ (0, 1]. Moreover Point (4) of Remark 1.8 above shows that for p = 2, the question is interesting only for

k ∈ [1; 2]. The case k ∈ (1; 2) is still open.
Finally, we mention that some partial results are known for p = ∞. Indeed, in [START_REF] Bobkov | Weak dimension-free concentration of measure[END_REF], Bobkov and Houdré characterized the set of probability measures on R satisfying CI ∞ ∞ (β a o ,r o ), with a o ∈ [0, 1/2), where β a o ,r o is the minimal concentration profile defined by (1.9). They showed that a probability measure µ belongs to this class if and only if the map U µ defined by

U µ (x) = F -1 µ 1 1 + e -x , x ∈ R,
where

F µ (x) = µ((-∞, x]) and F -1 µ (p) = inf{x ∈ R; F µ (x) ≥ p}, p ∈ (0, 1)
, satisfies the following inequality on the interval where it is defined:

|U µ (x) -U µ (y)| ≤ a + b|x -y|, for some a, b ≥ 0.
Finally, we mention that, under additional assumptions, Theorem 1.6 extends to convex sets. More precisely, we will prove that, inter alia, in geodesic spaces in which the distance function is convex (Busemann spaces), a probability measure satisfies CI ∞ 2 (α) restricted to convex sets, with a non trivial profile α, if and only if it satisfies the Poincaré inequality restricted to convex functions (see Section 6 for a precise statement). This generalizes a previous result by Bobkov and Götze that was only valid for probability on the real line [7, Theorem 4.2]. 1.2. Alternative formulation in terms of observable diameters. It is possible to give an alternative formulation of Theorem 1.6 and Theorem 1.7 using the notion of observable diameter introduced by Gromov ([23, Chapter 3.1/2]). Recall that, if (X, d, µ) is a metric space equipped with a probability measure and t ∈ [0, 1], the partial diameter of (X, d) is defined as the infimum of the diameters of all the subsets A ⊂ X satisfying µ(A) ≥ 1t. It is denoted by Part Diam(X, d, µ, t). If f : X → R is some 1-Lipschitz function, we denote by µ f ∈ P(R) the push forward of µ under f . Then, the observable diameter of (X, d, µ) is defined as follows Obs Diam(X, d, µ, t) = sup

f 1-Lip Part Diam(R, | • |, µ f , t) ∈ R + ∪ {+∞}.
We define accordingly the observable diameters of (X n , d 2 , µ n , t) for all n ∈ N * .

The observable diameters are related to concentration profiles by the following lemma (see e.g. [START_REF] Funano | Concentration, Ricci curvature and laplacian[END_REF]Lemma 2.22]).

Lemma 1.13. If µ satisfies CI(α), then Obs Diam(X, d, µ, 2α(r)) ≤ 2r, for all r ≥ 0 such that α(r) ≤ 1/2. Conversely, for all t ∈ [0, 1/2], for all A ⊂ X, with µ(A) ≥ 1/2, it holds

µ(A r(t) ) ≥ 1 -t with r(t) = Obs Diam(X, d, µ, t).
The following corollary gives an interpretation of the Poincaré inequality in terms of the boundedness of the observable diameters of the sequence of metric probability spaces (X n , d 2 , µ n ) n∈N * .

Corollary 1.14. A probability measure µ on (X, d) satisfies the Poincaré inequality (1.2) with the optimal constant λ if and only if for some t ∈ (0, 1/2)

r ∞ (t) := sup n∈N * Obs Diam(X n , d 2 , µ n , t) < ∞. Moreover, Φ -1 (t) ≤ r ∞ (t) √ λ ≤ a log b t , ∀t ∈ (0, 1/2)
where a > 0 and b ≥ 1 are some universal constants.

1.3. Tools. In this section, we briefly introduce the main tools that will be used in the proof of Theorem 1.6: inf-convolution operators, related to both concentration and to Hamilton-Jacobi equations, and the Central Limit Theorem. The first main tool in the proof of Theorem 1.6 is a new alternative formulation of concentration of measure CI ∞ p (α) in terms of deviation inequalities for inf-convolution operators that was introduced in [START_REF] Gozlan | From concentration to logarithmic Sobolev and Poincaré inequalities[END_REF]. Recall that for all t > 0, the infimum convolution operator f → Q t f is defined for all f : X n → R ∪ {+∞} bounded from below as follows

(1.15) Q t f (x) = inf y∈X n f (y) + 1 t p-1 d p p (x, y) , x ∈ X n (we should write Q p,(n) t
, but we will omit, for simplicity, the superscripts p and (n) in the notation). In the next proposition, we recall a result from [START_REF] Gozlan | From concentration to logarithmic Sobolev and Poincaré inequalities[END_REF] that gives a new way to express concentration of measure (our first main tool). Proposition 1.16. Let µ ∈ P(X); µ satisfies CI ∞ p (α) if and only if for all n ∈ N * and for all measurable function f : X n → R ∪ {+∞} bounded from below and such that µ n ( f = +∞) < 1/2, it holds

(1.17) µ n (Q t f > m( f ) + r) ≤ α(r 1/p t 1-1/p ), ∀r, t > 0,
where m( f

) = inf{m ∈ R; µ n ( f ≤ m) ≥ 1/2}.
The second main tool is the well known fact that the function u : (t, x) → Q t f (x) is, in some weak sense, solution of the Hamilton-Jacobi equation

∂u ∂t = - 1 4 |∇ x u| 2 .
This result is very classical on R k (see e.g [START_REF] Evans | Partial differential equations[END_REF]); extensions to metric spaces were proposed in [START_REF] Lott | Hamilton-Jacobi semigroup on length spaces and applications[END_REF], [START_REF] Balogh | Functional inequalities and Hamilton-Jacobi equations in geodesic spaces[END_REF], [START_REF] Ambrosio | Calculus and heat flow in metric measure spaces and applications to spaces with Ricci bounds from below[END_REF] or [START_REF] Gozlan | Characterization of Talagrand's transport-entropy inequalities on metric spaces[END_REF]. This will be discussed in the next section. The third tool is the Central Limit Theorem for triangular arrays of independent random variables (see e.g. [14, p. 530]).

Theorem 1.18. For each n, let X 1,n , X 2,n , . . . , X n,n be independent real random variables and define

T n = X 1,n + . . . + X n,n . Assume that E[T 2 n ] = 1, E[X k,n ] = 0 for all k ∈ {0, . . .

, n}, and that the following Lindeberg condition holds, for all t

> 0 n k=1 E X 2 k,n 1 |X k,n |>t → 0 as n → +∞. (1.19)
Then the distribution of T n converges weakly to the standard normal law.

We end this introduction with a short roadmap of the paper. In Section 2 we make some comments on Theorem 1.6. In particular, we compare Theorem 1.6 to a result by E. Milman on the Poincaré inequality in spaces with non-negative curvature and show, as an immediate consequence of our main result as well as E. Milman's result, that the celebrated KLS conjecture for isotropic log-concave probability measures can be reduced to some universal concentration inequalities (for isotropic log-concave probability measures). In Section 3, we recall some properties of the infimum convolution operators that will be used in the proofs. Section 4 is dedicated to the proof of Theorem 1.6 and Section 5 to the proof of Theorem 1.7, by means of the Herbst argument (the latter is somehow classical (see e.g. [START_REF] Ané | Sur les inégalités de Sobolev logarithmiques, volume 10 of Panoramas et Synthèses [Panoramas and Syntheses[END_REF][START_REF] Ledoux | The concentration of measure phenomenon[END_REF]) but requires some care due to our general framework). Finally Section 6 deals with the case of convex sets and the Poincaré inequality restricted to convex functions.

Acknowledgements. The authors would like to thank Emanuel Milman for commenting the main result of this paper and for mentioning to them that the method of proof used by Talagrand in [START_REF] Talagrand | A new isoperimetric inequality and the concentration of measure phenomenon[END_REF], to prove Corollary 4.4, could be extended to cover general situations.

Comparison with other results

In this section we collect some remarks and consequences of our main theorem. First we shall compare our result to one of E. Milman, in Riemannian setting. Then, we state the celebrated KLS conjecture and give an equivalent formulation in terms of dimension free concentration property. Finally, we may comment on other type of dimension free concentration properties involving a different definition of enlargement.

2.1. Dimension free concentration v.s non negative curvature. In Riemannian setting, Theorem 1.6 is reminiscent of the following recent result by E. Milman showing that under non-negative curvature the Poincaré constant of a probability measure can be expressed through very weak concentration properties of the measure [START_REF] Milman | On the role of convexity in isoperimetry, spectral gap and concentration[END_REF][START_REF] Milman | Isoperimetric and concentration inequalities: equivalence under curvature lower bound[END_REF].

We recall that the Minkowski content of a set A ⊂ X is defined as follows

µ + (A) := lim inf r→0 µ(A r ) -µ(A) r .
Theorem 2.1 (Milman [START_REF] Milman | Isoperimetric and concentration inequalities: equivalence under curvature lower bound[END_REF]). Let µ(dx) = e -V(x) dx be an absolutely continuous probability measure on a smooth complete separable Riemannian manifold M equipped with its geodesic distance d. Suppose that V :

M → R is a function of class C 2 such that Ric + Hess V ≥ 0,
and that µ satisfies the following concentration of measure inequality

µ(A r ) ≥ 1 -α(r), ∀r ≥ 0, with α : [0, ∞) → [0, 1/2] such that α(r o ) < 1/2, for some r o > 0. Then µ satisfies the following Cheeger's inequality µ + (A) ≥ D min(µ(A); 1 -µ(A)), ∀A ⊂ M, with D = sup Ψ(α(r)) r ; r > 0 s.t α(r) < 1/2 ,
where Ψ : [0, 1/2) is some universal function.

We recall that Cheeger's inequality with the constant D implies the Poincaré inequality (1.2) with the constant λ = D 2 /4 [START_REF] Cheeger | A lower bound for the smallest eigenvalue of the Laplacian. Problems in analysis[END_REF][START_REF] Maz | ja Sobolev spaces[END_REF]. In our result the non-negative curvature assumption of Milman's result is replaced by the assumption that the concentration is dimension free.

Remark 2.2. Notice that, if M has non-negative Ricci curvature and µ(dx) = 1

|K| 1 K (x) dx is the normalized restriction of the Riemmanian volume to a geodesically convex set K, then E. Milman also obtains [START_REF] Milman | Isoperimetric bounds on convex manifolds[END_REF] that

D = sup 1 -2α(r) r ; r > 0 .
This bound is optimal (see [START_REF] Milman | Isoperimetric bounds on convex manifolds[END_REF]).

2.2.

A remark on the KLS conjecture. In this section, X = R k is always equipped with its standard Euclidean norm | • |.

Let us recall the celebrated conjecture by Kannan, Lovász and Simonovits [START_REF] Kannan | Isoperimetric problems for convex bodies and a localization lemma[END_REF]. Recall first that a probability measure µ on R k is isotropic if x µ(dx) = 0 and x i x j µ(dx) = δ i j for all 1 ≤ i, j ≤ n. It is log-concave if it has a density of the form e -V , where V : R k → R ∪ {+∞} is a convex function.

Conjecture 2.3 (Kannan-Lovász-Simonovits [25]

). There is a universal constant D > 0 such that for all k ∈ N * , any log-concave and isotropic probability measure µ on R k satisfies the following Cheeger inequality

µ + (A) ≥ D min(µ(A); 1 -µ(A)), ∀A ⊂ R k .
Equivalently, there is a universal constant λ > 0 such that for all k ∈ N * , any log-concave and isotropic probability measure µ on R k satisfies the following Poincaré inequality

λVar µ ( f ) ≤ |∇ f | 2 dµ, for all f : R k → R Lipschitz.
According to E. Milman's Theorem 2.1, the above conjecture can be reduced to a statement about universal concentration inequalities for log-concave isotropic probabilities.

Corollary 2.4. The KLS conjecture is equivalent to the following statement. There exists r o > 0, a o ∈ [0, 1/2) such that for any m ∈ N * , any log-concave and isotropic probability ν on R m satisfies

(2.5) ν(A + r o B 2 ) ≥ 1 -a o , ∀A ⊂ R m s.t. ν(A) ≥ 1/2, where B 2 is the Euclidean unit ball of R m .
This corollary follows immediately from Theorem 2.1. Below, we propose an alternative proof based on our main result (Theorem 1.6).

Proof of Corollary 2.4. According to Theorem 1.7, it is clear that the KLS conjecture implies uniform exponential concentration estimates for isotropic log-concave probability measures.

Conversely, let µ be isotropic and log-concave on R k . For all n ∈ N * , the probability µ n is still isotropic and log-concave on R k n . So applying (2.5) to ν = µ n on R k n , for all n ∈ N * , we conclude that µ satisfies CI ∞ 2 (β a o ,r o ), where the concentration profile β a o ,r o is defined by (1.9). According to Theorem 1.6, we conclude that µ satisfies Poincaré inequality with the constant

λ = Φ -1 (a o )/r o 2
. Since this holds for any isotropic log-concave probability measure in any dimension, this ends the proof. 2.3. Euclidean v.s Talagrand type enlargements. Theorem 1.6 improves a preceding result by the first author [START_REF] Gozlan | A characterization of dimension free concentration in terms of transport inequalities[END_REF] where a stronger form of exponential dimension free concentration, introduced by Talagrand [START_REF] Talagrand | A new isoperimetric inequality and the concentration of measure phenomenon[END_REF][START_REF] Talagrand | Concentration of measure and isoperimetric inequalities in product spaces[END_REF], was shown to be equivalent to a transport-entropy inequality which was known to be also equivalent to the Poincaré inequality. These equivalences, together with our main result, will allow us to prove that the two notions of exponential dimension free concentration properties are actually equivalent (see Theorem 2.11 below).

In order to present these equivalences, we need some notation and definition.

Given n ∈ N * and A ⊂ X n , consider the following family of enlargements of A:

A a,r =        x ∈ X n ; ∃y ∈ A s.t n i=1 θ(ad(x i , y i )) ≤ r        , a > 0, r ≥ 0 where θ(t) = t 2 , if t ∈ [0, 1] and θ(t) = 2t -1, if t ≥ 1.
In the next definition, we recall the dimension free concentration property introduced by Talagrand.

Definition 2.6. A probability measure µ on X is said to satisfy the Talagrand exponential type dimension free concentration inequality with constants a, b ≥ 0 if for all n ∈ N * , for all A ⊂ X n with µ n (A) ≥ 1/2, it holds

(2.7) µ n ( A a,r ) ≥ 1 -be -r , ∀r ≥ 0.
Remark 2.8. Using elementary algebra, one can compare the Talagrand concentration inequality (2.7) with the dimension free concentration inequality (1.1) under investigation in this paper. More precisely we may prove that the former is stronger than the latter. Indeed, since t → θ( √ t) is concave and vanishes at 0, it is thus sub-additive. In turn, the following inequality holds

n i=1 θ(ad(x i , y i )) ≥ θ          n i=1 a 2 d 2 (x i , y i )          = θ(ad 2 (x, y)), ∀x, y ∈ X n .
Therefore, A a,θ(ar) ⊂ A r,2 , and so, if µ satisfies the Talagrand concentration inequality (2.7), then it obviously verifies the dimension free concentration inequality with the profile α(u) = be -θ(au) ≤ ebe -2au , u ≥ 0.

The following theorem summarizes the known links between Talagrand exponential type dimension free concentration and the Poincaré inequality. Theorem 2.9. Let µ be a probability measure on X. The following statements are equivalent [START_REF] Aida | Moment estimates derived from Poincaré and logarithmic Sobolev inequalities[END_REF] µ satisfies the Poincaré inequality (1.2) with a constant λ > 0.

(2) µ satisfies the Talagrand exponential type dimension free concentration inequality (2.7)

with constants a, b > 0. (3) µ satisfies the following transport-entropy inequality inf (X,Y)∈Π(µ,ν) E (θ(Cd(X, Y))) ≤ H(ν|µ), ∀ν ∈ P(X),
for some constant C > 0, (recall that Π(µ, ν) and the relative entropy H(ν|µ) are defined before Theorem 1.11). Moreover the constants above are related as follows :

(1) ⇒ (2) with a = κ √ λ and b = 1, for some universal constant κ.

(2) ⇒ (3) with C = a. (3) ⇒ (1) with λ = 2C 2 .
Let us make some bibliographical comments about the different implications in Theorem 2.9. The implication (1) ⇒ (2) is due to Bobkov and Ledoux [START_REF] Bobkov | Poincaré's inequalities and Talagrand's concentration phenomenon for the exponential distribution[END_REF], the implication (2) ⇒ (3) is due to the first author [17, Theorem 5.1], and the implication (3) ⇒ (1) is due to Maurey [START_REF] Maurey | Some deviation inequalities[END_REF] or Otto-Villani [START_REF] Otto | Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality[END_REF]. The equivalence between (1) and ( 3) was first proved by Bobkov, Gentil and Ledoux in [START_REF] Bobkov | Hypercontractivity of Hamilton-Jacobi equations[END_REF].

Remark 2.10. It is worth noting that the implication (2) ⇒ (3) follows from Theorem 1.11 for p = 2 by a change of metric argument. Namely, suppose that µ satisfies the concentration property (2) of Theorem 2.9, for some a > 0, and define d(x, y) = θ(ad(x, y)) for all x, y ∈ X. It is not difficult to check that the function θ 1/2 is subadditive, and therefore d defines a new distance on X. The ℓ 2 extension of d to the product X n is [START_REF] Ambrosio | Calculus and heat flow in metric measure spaces and applications to spaces with Ricci bounds from below[END_REF] can be restated by saying that µ satisfies CI ∞ 2 (α) (with respect to the distance d) with the Gaussian concentration profile α(r) = be -r 2 . Applying Theorem 1.11, we conclude that µ satisfies the 2-Talagrand transport entropy inequality with the constant 1 with respect to the distance d, which is exactly [START_REF] Ané | Sur les inégalités de Sobolev logarithmiques, volume 10 of Panoramas et Synthèses [Panoramas and Syntheses[END_REF] with C = a.

d2 (x, y) =        n i=1 θ(ad(x i , y i ))        1/2 , x, y ∈ X n , and it holds A a,r = {x ∈ X n ; d2 (x, A) ≤ √ r}, ∀A ⊂ X n . Therefore, statement
An immediate consequence of Theorem 1.6 and of Bobkov-Ledoux Theorem (1) ⇒ (2) above is the following result showing the equivalence between the two forms of dimension free exponential concentration.

Theorem 2.11. Let µ be a probability measure on X. The following are equivalent.

(1) The probability measure µ satisfies the Talagrand exponential type dimension free concentration inequality (2.7) with constants a and b. [START_REF] Ambrosio | Calculus and heat flow in metric measure spaces and applications to spaces with Ricci bounds from below[END_REF] The probability measure µ satisfies CI ∞ 2 (α) with a profile α(u) = b ′ e -a ′ u , u ≥ 0. Moreover, the constants are related as follows: (1) ⇒ (2) with a ′ = 2a and b ′ = eb, and (2) ⇒ (1) with a = κa ′ / log(2b ′ ) (for some universal constant κ) and b = 1.

We do not know if there exists a direct proof of the implication (2) ⇒ (1).

Proof. We have already proved that (1) implies (2) (see Remark 2.8). Let us prove the converse. According to Theorem 1.6 we conclude from (2) that µ satisfies the Poincaré inequality with a

constant λ ≥ Φ -1 (α(u)) u 2
, for all u such that α(u) < 1/2. A classical inequality gives Φ(t) ≤ 1 2 e -t 2 /2 , t ≥ 0. Therefore, Φ -1 (t) ≥ 2log(2t), for all t ∈ (0, 1/2). Hence, taking u = 2 log(2b ′ )/a ′ (which guarantees that α(u) = 1/(4b ′ )) yields to λ ≥ a ′2 log(2b ′ ) . According to the implication (1) ⇒ (2) in Theorem 2.9 we conclude that µ satisfies Talagrand concentration inequality (2.7) with a = κa ′ / log(2b ′ ).

Some properties of the inf-convolution operators

In this short (technical) section, we recall some properties of the inf-convolution operators related to Hamilton-Jacobi equations and to the concentration of measure, in the setting of metric spaces (recall that (X, d) is a complete separable metric space).

3.1. Inf-convolution operators and Hamilton-Jacobi equations. In this paragraph, we shall only consider the case p = 2. We do this restriction for simplicity and also since only that particular case will be used in the proof of Theorem 1.6 (in the next section). However we mention that most of the results of this section can be extended to any p > 1.

The following proposition collects two basic observations about the operators Q t , t > 0.

Proposition 3.1. Let h : X → R be a Lipschitz function. Then (i) for all x ∈ X, Q t h(x) → h(x), when t → 0 + ; (ii) for all ν ∈ P(X),

(3.2) lim sup t→0 + 1 t h(x) -Q t h(x) ν(dx) ≤ 1 4 |∇ -h(x)| 2 ν(dx).
Before giving the proof of Proposition 3.1, let us complete the picture by recalling the following theorem of [START_REF] Ambrosio | Calculus and heat flow in metric measure spaces and applications to spaces with Ricci bounds from below[END_REF] and [START_REF] Gozlan | Hamilton-Jacobi equations on metric spaces and transport-entropy inequalities[END_REF] (improving preceding results of [START_REF] Lott | Hamilton-Jacobi semigroup on length spaces and applications[END_REF] and [START_REF] Balogh | Functional inequalities and Hamilton-Jacobi equations in geodesic spaces[END_REF]). This result will not be used in the sequel. Theorem 3.3. Let h be a bounded function on a polish metric space X. Then (t, x) → Q t h(x) satisfies the following Hamilton-Jacobi (in)equation

(3.4) d dt + Q t h(x) ≤ - 1 4 |∇Q t h| 2 (x), ∀t > 0, ∀x ∈ X
where d/dt + stands for the right derivative, and

|∇h|(x) = lim sup y→x |h(y)-h(x)| d(y,x)
. Moreover, if the space X is geodesic (i.e. for all x, y ∈ X there exists at least one curve (z t ) t∈[0,1] such that z 0 = x, z 1 = y and d(z s , z t ) = |t -s|d(x, y)) then (3.4) holds with equality.

Observe that, strangely, the two inequalities (3.2) and (3.4) goes in the opposite direction. This suggests that, at t = 0, there should be equality.

Proof of Proposition 3.1. Let L > 0 be a Lipschitz constant of h; since Q t h ≤ h one has Q t h(x) = inf y∈B(x,2Lt) h(y) + 1 t d 2 (x, y) . (Namely, if d(x, y) > 2Lt, it holds h(y) -h(x) + 1 t d 2 (x, y) ≥ -L + 1 t d(x, y) d(x, y) > 0.) Hence 0 ≤ h(x) -Q t h(x) t = sup y∈B(x,2Lt) h(x) -h(y) t - d 2 (x, y) t 2 ≤ sup y∈B(x,2Lt) [h(x) -h(y)] + d(x, y) d(x, y) t - d 2 (x, y) t 2 ≤ sup r∈R        sup y∈B(x,2Lt) [h(x) -h(y)] + d(x, y) r -r 2        = 1 4 sup y∈B(x,2Lt) [h(x) -h(y)] 2 + d 2 (x, y) .
We conclude from this that 0 ≤ (h -Q t h)/t ≤ L 2 /4. This implies in particular that Q t h → h when t → 0. Taking the lim sup when t → 0 + gives (3.5) lim sup

t→0 + h(x) -Q t h(x) t ≤ 1 4 |∇ -h(x)| 2 .
Inequality (3.2) follows from (3.5) using Fatou's Lemma in its lim sup version. The application of Fatou's Lemma is justified by the fact that the family of functions {(h -Q t h)/t} t>0 is uniformly bounded.

Remark 3.6. The proof of (3.5) can also be found in [START_REF] Villani | Optimal transport: Old and New, volume 338 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences[END_REF]Theorem 22.46] (see also [22, Proposition A.3], [START_REF] Lott | Hamilton-Jacobi semigroup on length spaces and applications[END_REF][START_REF] Balogh | Functional inequalities and Hamilton-Jacobi equations in geodesic spaces[END_REF][START_REF] Ambrosio | Calculus and heat flow in metric measure spaces and applications to spaces with Ricci bounds from below[END_REF]).

3.2.

Inf-convolution operators and concentration of measure. In this subsection we briefly recall the short proof of Proposition 1.16 for the sake of completeness (Proposition that relates the infimum convolution operator and the concentration property CI ∞ p (α)).

Proof. Let f : X n → R ∪ {+∞} be a function bounded from below with

µ n ( f = +∞) < 1/2. By definition of m( f ), it holds µ n ( f ≤ m( f )) ≥ 1/2. Define A = { f ≤ m( f )}. If µ satisfies the dimension free concentration property CI ∞ p (α)
, since by definition of m( f ), µ n (A) ≥ 1/2, one has µ n (X n \ A u,p ) ≤ α(u), for all u ≥ 0. Then, observe that

Q t f (x) ≤ m( f ) + 1 t p-1 d p p (x, A), ∀x ∈ X n .
Hence {Q t f > m( f ) + r} ⊂ {d p ( • , A) > r 1/p t 1-1/p } = X \ A r 1/p t 1-1/p ,p , which proves (1.17).

To prove the converse, take a Borel set A ⊂ X n such that µ n (A) ≥ 1/2 and consider the function i A equals to 0 on A and +∞ on A c . For this function, Q t i A = d p p (x, A)/t p-1 and one can choose m(i A ) = 0. Applying (1.17) gives the concentration property CI ∞ p (α).

Poincaré inequality and concentration of measure

This section is dedicated to the proof of our main result Theorem 1.6, and to Corollary 1.14. Moreover, we shall explain how Theorem 1.6 can be used to improve any non-trivial dimension concentration property to an exponential one.

4.1.

From dimension free concentration to the Poincaré inequality: proof of Theorem 1.6.

Proof of Theorem 1.6. Let h : X → R be a bounded Lipschitz function such that h dµ = 0. For all n ∈ N * , define f n :

X n → R + by f n (x) = h(x 1 ) + • • • + h(x n ), ∀x = (x 1 , . . . , x n ) ∈ X n .
Our aim is to apply the Central Limit Theorem. Applying (1.17) to f n with t = 1/ √ n and r = √ nu, for some u > 0, we easily arrive at

(4.1) µ n        1 √ nσ n n i=1 Q 1/ √ n h(x i ) -µ(Q 1/ √ n h) > 1 σ n √ n m( f n ) + √ n σ n µ h -Q 1/ √ n h + u σ n        ≤ α( √ u),
where

σ 2 n = Var µ (Q 1/ √ n h) and m( f n ) is a median of f n under µ n , that is to say any number m ∈ R such that µ n ( f ≥ m) ≥ 1/2 and µ n ( f n ≤ m) ≥ 1/2.
We deal with each term of (4.1) separately. According to Point (i) of Proposition 3.1, we observe that σ n → σ = Var µ (h), when n goes to ∞ and according to Point (ii) of Proposition 3.1, that lim sup

n→+∞ √ nµ h -Q 1/ √ n h ≤ 1 4 |∇ -h| 2 dµ.
On the other hand, let m n = m( f n )/( √ nσ). According to the Central Limit Theorem (Theorem 1.18) the law of the random variables T n = f n /( √ nσ) under µ n converges weakly to the standard Gaussian. Since weak convergence implies the convergence of quantiles as soon as the limit distribution has a continuous repartition function (see for instance [42, Lemma 21.2]), we have in particular, m n → 0 as n → ∞. Now, fix ε > 0. According to the above observations, (4.1) yields, for any u > 0 and any n sufficiently large,

µ n        1 √ nσ n n i=1 Q 1/ √ n h(x i ) -µ(Q 1/ √ n h) > 1 + ε σ ε + 1 4 |∇ -h| 2 dµ + u        ≤ α( √ u). (4.2)
In order to apply (again) the Central Limit Theorem (Theorem 1.18), introduce the following random variables

T n (x) = n i=1 1 √ nσ n Q 1/ √ n h(x i ) -µ(Q 1/ √ n h) under µ n . Since h is bounded Q 1/
√ n h is uniformly bounded in n, and by Lebesgue theorem, as n goes to ∞, we see that the Lindeberg condition (1.19) is verified:

1 σ 2 n (Q 1/ √ n h -µ(Q 1/ √ n h)) 2 1 |Q 1/ √ n h-µ(Q 1/ √ n h)|>t √ nσ n dµ → 0 as n → +∞.
Therefore, letting n go to +∞, and ε to 0, by continuity of Φ, the inequality (4.2) provides

Φ        |∇ -h| 2 dµ 4σ + u σ        ≤ α( √ u), ∀u ≥ 0. Let u ≥ 0 be such that α( √ u) < 1/2 and k(u) := Φ -1 (α( √ u)) > 0.
We easily get from the latter inequality that

k(u) Var µ (h) ≤ u + 1 4 |∇ -h| 2 dµ.
Replacing h by sh, s > 0, and taking the infimum, we arrive at

k(u) Var µ (h) ≤ inf s>0 u s + s 4 |∇ -h| 2 dµ = u |∇ -h| 2 dµ.
Optimizing over u, one concludes that Poincaré inequality (1.2) is satisfied with the constant λ announced in Theorem 1.6. Now let h : X → R be an unbounded Lipschitz function. Consider the sequence of functions h n = (h ∨ -n) ∧ n, n ∈ N * converging pointwise to h. For all n ∈ N * , h n is bounded and Lipschitz, and it is not difficult to check that

(4.3) |∇ -h n |(x) = 0 if x ∈ {h ≤ -n} ∪ {h > n} and |∇ -h n |(x) = |∇ -h n |(x) if x ∈ {-n < h ≤ n}.
In particular, the sequence |∇ -h n | converges monotonically to |∇ -h|. Applying Fatou's lemma and the monotone convergence theorem, we obtain

λ (h(x) -h(y)) 2 µ(dx)µ(dy) ≤ λ lim inf n→∞ Var µ (h n ) ≤ lim inf n→∞ |∇ -h n | 2 dµ = |∇ -h| 2 dµ,
which completes the proof of Theorem 1.6.

4.2.

Poincaré inequality and boundedness of observable diameters of product probability spaces. In this section we prove Corollary 1.14.

Proof of Corollary 1.14. Assume first that µ satisfies the Poincaré inequality (1.2) with the optimal constant λ. Then according to Theorem 1.7, µ satisfies CI ∞ 2 (α) with the concentration profile α(r) = be - √ λr , where a, b are universal constants (b ≥ 1/2). According to the first part of Lemma 1.13 (applied to the metric probability space (X n , d 2 , µ n )), it follows that for all n ∈ N * , Obs Diam(

X n , d 2 , µ n , t) ≤ 2 log(4b/t) a √ λ
, for all t ≤ 1 and thus

r ∞ (t) √ λ ≤ a ′ log(b ′ /t), ∀t ≤ 1 for some universal constants a ′ , b ′ . Conversely, assume that 0 < r ∞ (t o ) < ∞ for some t o ∈ (0, 1/2). According to the second part of Lemma 1.13, µ satisfies CI ∞ 2 (β t o ,r ∞ (t o ) )
, where the minimal profiles β are defined in (1.9). According to Theorem 1.6, it follows that µ satisfies the Poincaré inequality with an optimal constant λ > 0 such that

√ λr ∞ (t o ) ≥ Φ -1 (t o ).
According to the first step, we conclude that r ∞ (t) < ∞ for all t ≤ 1, and so the inequality above is true for all t ∈ (0, 1/2). 2 with an exponential concentration. More explicitly, it satisfies the dimension free concentration property with the profile α(r) = be -a √ λr , where a, b are universal constants and

√ λ = sup        Φ -1 (α(r)) r ; r > 0 s.t α(r) < 1/2        .
This result is an immediate corollary of Theorem 1.6 and Theorem 1.7.

In [START_REF] Talagrand | A new isoperimetric inequality and the concentration of measure phenomenon[END_REF] this result was stated and proved only for probability measures on R. We thank E. Milman for mentioning to us that the argument was in fact more general. For the sake of completeness, we extend below Talagrand's argument in a very general abstract framework. For a future use, we only assume that the dimension free concentration property holds on a good subclass of sets. We refer to the proof of Proposition 6.8 where this refinement will be used (the subclass of sets being the class of convex sets). Proposition 4.5. Let (X, d) be a complete separable metric space, p ≥ 1 and for all n ∈ N * let A n be a class of Borel sets in X n satisfying the following conditions:

(i) For all n ∈ N * and r ≥ 0

, if A ∈ A n then A r,p ∈ A n . (ii) If A ∈ A m , then A n ∈ A nm .
Suppose that a Borel probability measure µ on X satisfies the following dimension free concentration property: there exists r o > 0, a o ∈ [0, 1/2) such that for all n ∈ N * ,

µ n (A r o ,p ) ≥ 1 -a o , ∀A ∈ A n s.t. µ n (A) ≥ 1/2.
Then, for any γ ∈ (-log(1a o )/ log(2), 1), there exists c ∈ [1/2, 1) depending only on γ and a o such that for all n ∈ N * ,

µ n (A r,p ) ≥ 1 - 1 -c γ γ r/r o , ∀r ≥ 0, ∀A ∈ A n s.t. µ n (A) ≥ c.
Note in particular that in the case p = 2 (and A n the class of all Borel sets), we recover the conclusion of Corollary 4.4 with slightly less accurate constants.

Proof. Given

A ∈ A 1 , it holds (A n ) r o ,p ⊂ A r o
n and, according to (i) and (ii), both sets belong to

A n . Therefore, if µ(A) ≥ (1/2) 1/n , it holds µ(A r o ) ≥ (1 -a o ) 1/n . Now, let A ∈ A 1 be such that µ(A) ≥ 1/2 and let n A be the greatest integer n ∈ N * such that µ(A) ≥ (1/2) 1/n . By definition of n A , log(2) log(1/µ(A)) -1 < n A ≤ log(2) log(1/µ(A))
.

According to what precedes, 2) ∈ (0, 1), when µ(A) → 1. Therefore, if γ is any number in the interval (-log(1-a o ) log( 2) , 1), there exists c > 1/2 (depending only on γ) such that for all

µ(A c r o ) ≤ 1 -(1 -a o ) 1/n A ≤ 1 -exp log(1 -a o ) log(1/µ(A)) log(2) -log(1/µ(A)) . The function ϕ(u) = exp log(1-a o ) log(1/u) log(2)-log(1/u) satisfies ϕ(u) = 1 - log(1 -a o ) log(2) (u -1) + o(u -1), when u → 1. So 1-ϕ(µ(A)) 1-µ(A) → -log(1-a o ) log(
A ∈ A 1 with µ(A) ≥ c it holds µ(A c r o ) ≤ γµ(A c ).
Iterating (which is possible thanks to (i) and the easy to check property A r 1 ,p r 2 ,p ⊂ A r 1 +r 2 ,p ) yields

µ(A c kr o ) ≤ γ k µ(A c ), ∀k ∈ N * .
It follows easily that for all u ≥ 0,

µ(A c u ) ≤ ((1 -c)/γ)γ u/r o .
Applying the argument above to the product measure µ p , p ∈ N * , gives the conclusion.

5. From Poincaré inequality to exponential concentration: proof of Theorem 1.7

In this section, we give a proof of Theorem 1.7. Its conclusion is very classical in, say, a Euclidean setting. But to deal with the general metric space framework requires some additional technical ingredients that we present now. 5.1. Technical preparation. In order to regularize Lipschitz functions, we shall introduce an approximate sup-convolution operator. More precisely, for all ε > 0, and for all function f : X n → R ∪ {-∞}, we define the (approximate) sup-convolution operator by

(5.1) R ε f (x) := sup y∈X n f (y) -ε + d 2 2 (x, y) , x ∈ X n .
The next lemma collects some useful properties about R ε .

Lemma 5.2. Let f : X n → R ∪ {-∞} be a function taking at least one finite value and ε > 0. Then

(i) If R ε f (x o ) < ∞ for some x o ∈ X n , then R ε f is finite everywhere and is 1-Lipschitz with respect to d 2 . Moreover, it holds n i=1 |∇ - i R ε f (x)| 2 ≤ 1, ∀x ∈ X n . (ii) If f is 1-Lipschitz, then for all x ∈ X n , f (x) - √ ε ≤ R ε f (x) ≤ f (x).
(iii) If (X, d) is a Banach space and f is convex, then R ε f is also convex.

Proof. We fix ε > 0. Point (iii) follows easily from the fact that R ε f is a supremum of convex functions, since by a simple change of variable

R ε f (x) = sup z∈X n f (x -z) -ε + z 2 2 , x ∈ X n .
Point (ii) is also easy. Indeed, the first inequality follows by choosing y = x. For the second inequality, observe that, since f is 1-Lipschitz,

R ε f (x) -f (x) = sup y∈X n f (y) -f (x) -ε + d 2 2 (x, y) ≤ sup r≥0 r -ε + r 2 = 0.

Now we turn to the proof of Point (i).

The first part of the statement follows from the fact that R ε f is a supremum of 1-Lipschitz functions. To prove the other part, we need to fix some notation. For x = (x 1 , . . . , x n ), z = (z 1 , . . . , z n ) ∈ X n and i ∈ {1, 2, . . . , n}, we set

xi z = (x 1 , . . . , x i-1 , z i , x i+1 , . . . , x n ). Also, we set θ(u) := √ ε + u, u ∈ R, so that R ε f (x) = sup y { f (y) -θ(d 2 2 (x, y))} (observe that θ is concave). Fix x = (x 1 , . . . , x n ) ∈ X n
and a parameter η ∈ (0, 1) that will be chosen later on and consider z = (z 1 , . . . , z n ) ∈ X n such that z i

x i for all i ∈ {1, . . . , n}. We assume that R ε f is everywhere finite. Hence, since η min 1≤i≤n d(x i , z i ) > 0, there exists ŷ = ŷ(x, z, η) such that

R ε f (x) ≤ f (ŷ) -ε + d 2 2 (x, ŷ) + η min 1≤i≤n d(x i , z i ).
As a consequence, using that θ is concave, for all 1 ≤ i ≤ n, we have

[R ε f ( xi z i ) -R ε f (x)] -= [R ε f (x) -R ε f ( xi z i )] + ≤ θ(d 2 2 (x i z i , ŷ)) -θ(d 2 2 (x, ŷ)) + + η min 1≤i≤n d(x i , z i ) ≤ d 2 2 (x i z i , ŷ) -d 2 2 (x, ŷ) + θ ′ (d 2 2 (x, ŷ)) + η min 1≤i≤n d(x i , z i ) = d(ŷ i , z i ) -d(ŷ i , x i ) + (d(ŷ i , z i ) + d(ŷ i , x i )) θ ′ (d 2 2 (x, ŷ)) + η min 1≤i≤n d(x i , z i ) ≤ 2d(z i , x i )d(ŷ i , z i )θ ′ (d 2 2 (x, ŷ)) + η min 1≤i≤n d(x i , z i )
where, in the last line we used that the positive part

d(ŷ i , z i ) -d(ŷ i , x i ) + guarantees that d(ŷ i , x i ) ≤ d(ŷ i , z i
) and the triangular inequality.

Using the Cauchy-Schwarz inequality, it follows for any δ > 0 that

[R ε f ( xi z i ) -R ε f (x)] 2 - d 2 (x i , z i ) ≤ 2d(ŷ i , z i )θ ′ (d 2 2 (x, ŷ)) + η 2 ≤ (1 + δ)4d 2 (ŷ i , z i )θ ′ (d 2 2 (x, ŷ)) 2 + 1 + 1 δ η 2 .
Therefore, using the triangular and the Cauchy-Schwarz inequalities, we get for any δ > 0,

n i=1 [R ε f ( xi z i ) -R ε f (x)] 2 - d 2 (x i , z i ) ≤ (1 + δ)4d 2 2 (ŷ, z)θ ′ (d 2 2 (x, ŷ)) 2 + n 1 + 1 δ η 2 ≤ (1 + δ)4(d 2 (ŷ, x) + d 2 (x, z)) 2 θ ′ (d 2 2 (x, ŷ)) 2 + n 1 + 1 δ η 2 ≤ (1 + δ) 2 4d 2 2 (ŷ, x)θ ′ (d 2 2 (x, ŷ)) 2 + (1 + δ) 1 + 1 δ 4d 2 2 (x, z) 2 θ ′ (d 2 2 (x, ŷ)) 2 + n 1 + 1 δ η 2 ≤ (1 + δ) 2 + (1 + δ) 1 + 1 δ d 2 2 (x, z) 2 ε + n 1 + 1 δ η 2 ,
using that 4u 2 θ ′ (u 2 ) 2 ≤ 1 and θ ′ (u 2 ) 2 ≤ 1/(4ε). The expected result follows at once taking the limits z i → x i , and then η → 0 and δ → 0. This ends the proof of the lemma.

The next ingredient in the proof of Theorem 1.7 is the so-called Herbst argument that we explain now. We recall the following notation: for any f :

X n → R, set m( f ) = inf m ∈ R; µ n ( f ≤ m) ≥ 1/2 .
Proposition 5.3. Assume that µ satisfies the Poincaré inequality (1.2) with a constant λ > 0. Then, there exist universal constants a, b > 0 such that then for all n ∈ N * , it holds

µ n        f > m ( f ) + 2 λ + r        ≤ b exp -a √ λr , ∀r ≥ 0 for all function f : X n → R such that (5.4) n i=1 |∇ - i f | 2 (x) ≤ 1, ∀x ∈ X n .
The same conclusion holds if the function f satisfies

(5.5) n i=1 |∇ + i f | 2 (x) ≤ 1, ∀x ∈ X n .
Proof. It is well known that the Poincaré inequality tensorizes properly (see e.g. [26, proposition 5.6]). Indeed, recall that for all n ∈ N * and for all product probability measure µ n

λVar µ n (g) ≤ n i=1
Var µ (g i ) µ n (dx), where g i (x i ) := g(x 1 , . . . , x i-1 , x i , x i+1 , . . . , x n ), with x 1 , . . . , x i-1 , x i+1 , . . . , x n fixed. Therefore, if µ satisfies (1.2), then the product probability measure µ n satisfies (5.6)

λVar µ n (g) ≤ n i=1 |∇ - i g| 2 (x) µ n (dx),
for all function g : X n → R that is Lipschitz in each coordinate. Let f : X n → R be bounded and such that (5.4) holds, and define Z(s) = log e s f dµ n , for all s ≥ 0. Applying (5.6) to g = e s f (which is still bounded and Lipschitz) and using (5.4) yields easily to

λ        e 2s f dµ n - e s f dµ n 2        ≤ s 2 e 2s f dµ n . Thus log(1 -s 2 /λ) + Z(2s) ≤ 2Z(s), ∀0 ≤ s ≤ √ λ.
According to Hölder's inequality, the function Z is convex. Therefore,

Z(2s) ≥ Z(s) + Z ′ (s)s. As a result, log(1 -s 2 /λ) + Z ′ (s)s ≤ Z(s), ∀0 ≤ s ≤ √ λ, and so d ds Z(s) s ≤ - log(1 -s 2 /λ) s 2 , ∀0 < s ≤ √ λ.
Since Z(s)/s → f dµ n when s → 0, we conclude that

e s( f -f dµ n ) dµ n ≤ exp        s √ λ s/ √ λ 0 -log(1 -v 2 ) v 2 dv        , ∀s ≤ √ λ.
Taking s = √ λ/2, we easily get, by the (exponential) Chebychev Inequality,

µ n f - f dµ n > r ≤ be - √ λ 2 r , ∀r ≥ 0, (5.7) with b = exp 1 2 1/2 0 -log(1-v 2 ) v 2
dv . Now, since the probability measure µ n satisfies the Poincaré inequality with constant λ > 0, (5.4) implies that λVar µ n ( f ) ≤ 1. Therefore, by Markov's inequality, it holds, for all ε > 0

µ n        f ≤ f dµ n - 2 + ε λ        ≤ λ 2 + ε Var µ n ( f ) < 1 2 .
Hence, according to this definition of m( f ), it follows easily that

m ( f ) ≥ f dµ n - 2 λ .
This inequality together with (5.7) provides the expected deviation inequality (5.8)

µ n        f > m ( f ) + 2 λ + r        ≤ be - √ λ Now suppose that f : X n → R is Lipschitz but not bounded. Consider the function f n = ( f ∨ -n) ∧ n, n ∈ N * . Applying (4.3) componentwise, we see that |∇ - i f n | ≤ |∇ - i f
| for all i ∈ {1, 2, . . . , n}. Therefore, f n satisfies (5.4). Applying (5.8) to f n , and letting n go to ∞, one sees easily that (5.8) still holds for the unbounded Lipschitz function f .

Exactly the same proof works under the condition (5.5) (using the equivalent inequality (1.4))

5.2. Proof of Theorem 1.7. Thanks to the previous section (Section 5.1), we are now in position to prove Theorem 1.7.

Proof of Theorem 1.7. Let A be a measurable subset of X n of measure µ n (A) ≥ 1/2 and define for all ε > 0, f A,ε (x) := ε + d 2 2 (x, A), x ∈ X n . By definition of R ε given in (5.1), it holds f A,ε = -R ε i A , where i A : X n → {-∞; 0} is the function defined by i A (x) = 0, if x ∈ A and i A (x) = -∞ otherwise. According to Point (ii) of Lemma 5.2, we see that f A,ε satisfies Condition (5.5) of Proposition 5.3. Hence, observing that m( f A,ε ) = √ ε, it follows from Proposition 5.3 that

µ n        ε + d 2 2 (x, A) > √ ε + 2 λ + r        ≤ b exp -a √ λr , ∀r ≥ 0.
Letting ε go to 0 yields (after a change of variable) to,

1 -µ n (A r,2 ) ≤ b ′ exp(-a √ λr), ∀r ≥ 0, with b ′ = max(b, 1/2)e √ 2a
. The proof of Theorem 1.7 is complete.

6. Poincaré inequality for convex functions and dimension free convex concentration property.

In this final section, we investigate the links between the dimension free concentration property CI ∞ 2 (α) restricted to convex sets, and the Poincaré inequality restricted to the class of convex functions (see below for a precise definition) 6.1. Convexity and convex concentration on geodesic spaces. To deal with convexity properties, we shall assume throughout the section that the metric space (X, d) is geodesic. This means that any two points x and y of X can be connected by at least one constant-speed continuous curve in X: i.e. for all x, y ∈ X, there exists (x t ) t∈[0,1] in X satisfying x 0 = x, x 1 = y, and for all s, t ∈ [0, 1], d(x s , x t ) = |t -s|d(x 0 , x 1 ). Such a curve is called a (constant-speed) geodesic joining x to y. Definition 6.1. Let (X, d) be a geodesic space.

(i) A set A ⊂ X is said to be convex if for all x 0 , x 1 ∈ A and all geodesics

(x t ) t∈[0,1] joining x 0 to x 1 , it holds x t ∈ A, ∀t ∈ [0, 1]. (ii) A function f : X → R ∪ {+∞} is said to be convex if for all geodesics (x t ) t∈[0,1] in X, f (x t ) ≤ (1 -t) f (x 0 ) + t f (x 1 ).
Accordingly, one will say that µ ∈ P(X) satisfies the dimension free convex concentration property with the concentration profile α and with respect to the ℓ 2 product structure (in short CCI ∞ 2 (α)), if for all convex subset A ⊂ X n , with µ n (A) ≥ 1/2, (6.2)

µ n (A r,2 ) ≥ 1 -α(r), ∀r ≥ 0.
As for CI ∞ 2 (α) in Proposition 1.16, the convex concentration property can be characterized using the inf-convolution operator Q t . Proposition 6.3. Let µ ∈ P(X); µ satisfies CCI ∞ 2 (α) if and only if for all n ∈ N * and for all convex function f : X n → R ∪ {+∞} bounded from below and such that µ n ( f = +∞) < 1/2, it holds

(6.4) µ n (Q t f > m( f ) + r) ≤ α( √ tr), ∀r, t > 0,
where m( f

) = inf{m ∈ R; µ n ( f ≤ m( f )) ≥ 1/2}.
Proof. By the following two observations the proof of the above proposition (that we omit) becomes essentially identical to the one of Proposition 1.16 in section 3.2: (a) By definition, if f : X → R ∪ {+∞} is convex then any level set { f ≤ r}, r ∈ R, is convex; (b) for any convex set A, the function i A , that equals 0 on A and +∞ on X \ A, is convex.

For technical reasons, we will have to distinguish between the following two versions of the Poincaré inequality in restriction to convex functions (in short convex Poincaré): The argument used in Point (3) of Remark 1.3 to prove the equivalence between (1.2) and (1.4) in the usual setting does not work anymore since if f is convex,f is no more convex. However, if (X, d) is finite dimensional Banach space or a smooth Riemannian manifold and if one assumes that µ is absolutely continuous with respect to the Lebesgue (or the volume) measure, by Rademacher's theorem, both gradients in the definition of (6.5) and (6.6) are equal, except on a set of µ-measure 0, which, in turn, guarantees that (6.5) and (6.6) are equivalent. 6.2. Dimension free convex concentration implies the convex Poincaré inequality 6.5. Starting from the functional characterization of CCI ∞ 2 (α) stated in Proposition 6.3 and following the lines of the proof of Theorem 1.6, we shall obtain the first main theorem of this section (a counterpart of Theorem 1.6 in the convex situation). Theorem 6.7. If µ satisfies the dimension free convex concentration property CCI ∞ 2 (α), then µ satisfies the convex Poincaré inequality

(6.5) λVar µ ( f ) ≤ |∇ -f | 2 dµ, ∀ f
λVar µ ( f ) ≤ |∇ -f | 2 dµ,
for all locally Lipschitz 1 and convex function with finite variance with the constant λ defined by

√ λ = sup        Φ -1 (α(r)) r ; r > 0 s.t α(r) ≤ 1/2        .
If moreover ∞ 0 rα(r) dr < ∞ then the variance of all convex and Lipschitz functions is finite and thus µ verifies (6.5).

Proof. The proof is very similar to the proof of Theorem 1.6, but one needs to take care of the technical difficulties coming from the restriction to convex sets/functions. We give here only the main lines and omit most of the details. Also, we may use the notation of the proof of Theorem 1.6.

Let h : X → R be a locally Lipschitz convex function such that h dµ = 0 and h 2 dµ < +∞. For all n ∈ N * , define f n :

X n → R + by f n (x) = h(x 1 ) + • • • + h(x n ), ∀x = (x 1 , . . . , x n ) ∈ X n .
We first observe that f n is convex. Indeed, this point is an easy consequence of the fact that (x t ) t∈[0,1] is a geodesic in (X n , d 2 ) if and only if for all i ∈ {1 . . . , n}, (x i,t ) t∈[0,1] are geodesics in (X, d) (where x t = (x 1,t , . . . , x n,t )). Therefore we may apply Proposition 6.3 to the function f n .

For the next step of the proof, we need some analogue of Proposition 3.1 for convex locally Lipschitz functions h : X → R (not necessarily globally Lipschitz). From the definition of the convexity property of h, one may easily check that for all x, y ∈ X h(x)h(y) ≤ d(x, y)|∇ -h(x)|. 1 By locally Lipschitz, we mean Lipschitz on every ball of finite radius.

It follows that for all

t > 0, 0 ≤ h(x) -Q t h(x) t = sup y∈X h(x) -h(y) t - d 2 (x, y) t 2 ≤ sup y∈X |∇ -h(x)| d(x, y) t - d 2 (x, y) t 2 = sup r∈R |∇ -h(x)|r -r 2 ≤ 1 4 |∇ -h(x)| 2 < ∞.
This implies in particular that Q t h(x) → h(x) for all x ∈ X. Moreover, it holds

√ nµ h -Q 1/ √ n h ≤ 1 4 |∇ -h| 2 dµ, ∀n ∈ N * .
Let us first assume that h is bounded from below. Then it holds,

|Q 1/ √ n h| ≤ |h| + | inf h| for all n ∈ N * . Since h 2 dµ < ∞, applying the dominated convergence theorem yields to lim n→+∞ σ 2 n = lim n→+∞ Var µ (Q 1/ √ n h) = Var µ (h) = σ 2 .
Since h 2 dµ < +∞, we may show that any median of m n of f n /( √ nσ) tends to 0 as n goes to +∞. As a consequence, (4.2) holds for n sufficiently large. The rest of the proof is identical to the one of Theorem 1.6: we apply the Central Limit Theorem (Theorem 1.18), observing that the Lindeberg condition holds since |Q 1/ √ n h| ≤ | inf h| + |h| for all n ∈ N * , and h 2 dµ < ∞. This proves the claim in the case where h is assumed bounded from below. To show that the Poincaré inequality still holds if h is not bounded from below, one considers the approximation sequence h n = h ∨ -n, n ∈ N * (note that h n is convex) and one follows the same line of reasoning as in the end of the proof of Theorem 1.6.

Finally, to complete the proof, observe that if f : X → R is convex and 1-Lipschitz, then

A = { f ≤ m( f )} is a convex set with µ(A) ≥ 1/2, and since A r,2 ⊂ { f ≤ m + r}, we conclude from CCI 2 (α) that µ( f > m( f ) + r) ≤ α(r), ∀r ≥ 0.
Since ∞ 0 rα(r) dr < ∞, an integration by part shows that [ fm( f )] 2 + dµ < ∞. Therefore, if f is convex, 1-Lipschitz and bounded from below, then f has a finite variance and so applying the first part of the proof, we conclude that Var µ ( f ) ≤ 1/λ. Using the same truncation as above, we see that this inequality extends to all convex and 1-Lipschitz functions. This complete the proof.

Convex Poincaré inequality implies exponential dimension free convex concentration.

To get the converse, namely to get a counterpart of Gromov-Milman Theorem for convex sets (that the convex Poincaré inequalities (6.5) or (6.6) imply the dimension free concentration property CCI ∞ 2 (α)) with an exponential profile, we need to add the structural assumption that the underlying metric space is of Busemann type.

Recall that (X, d) is said to be a Busemann's space if the distance d : X 2 → R + is a convex function (of both variables). Banach spaces are obvious examples of such spaces. Another important class of Busemann's spaces are complete connected Riemannian manifolds with non positive sectional curvature. We refer to [START_REF] Burago | A course in metric geometry[END_REF], [START_REF] Bridson | Metric spaces of non-positive curvature[END_REF], [START_REF] Papadopoulos | Metric spaces, convexity and nonpositive curvature[END_REF] for more informations on the topic and a proof of this statement.

Let us mention some elementary properties of Busemann's spaces: (B1) if X is a Busemann's space, any two points of X are joined by a unique constant speed geodesic; (B2) for any convex subset A ⊂ X, the function X ∋ x → d(x, A) is convex; (B3) if (X, d) is a Busemann's space, then (X n , d 2 ) is a Busemann's space. We are now in position to state our second main theorem (a counterpart of Gromov-Milman's Theorem 1.7). Theorem 6.8. Let (X, d) be a geodesic space and µ be a probability measure. Assume one of the following hypothesis: either (a) X is a Busemann's space and µ satisfies the convex Poincaré inequality (6.6) with a constant λ > 0. or (b) (X, • ) is a Banach space (with xy = d(x, y), x, y ∈ X) and µ satisfies the convex Poincaré inequality (6.5) with a constant λ > 0; Then µ satisfies the dimension free convex concentration property CCI ∞ 2 (α) with the profile α(r) = b exp(-a √ λr), r ≥ 0, where a, b are universal constants.

As a direct corollary of Theorem 6.8 and Theorem 6.7, when X is a Banach space, we conclude that, similarly to the general case, the set of probability measures µ satisfying the dimension free convex concentration property CCI ∞ 2 (α) with exponential profile coincides with the set of probability measures verifying the convex Poincaré inequality (6.5).

The remaining of the section is dedicated to the proof of Theorem 6.8. There is a technical obstacle for applying Herbst argument as in Proposition 5.3. Namely, since the class of convex functions is not stable under truncation from above (if f is convex and a ∈ R, min( f ; a) is in general not convex) it is delicate to deal safely with e s f dµ, s ≥ 0. Although a method based on p-th moments could perhaps be considered in replacement, we use instead an argument based on Corollary 4.5: we first show that under (6.5) and (6.6), µ verifies the dimension free convex concentration property CCI ∞ 2 (α) with some polynomial concentration profile and then we upgrade it into an exponential one using Corollary 4.5.

Proof of Theorem 6.8. We start as in the proof of Proposition 1.7 by noticing that the convex Poincaré inequalities (6.5) and ( 6 Thus, it follows immediately from Markov's inequality that (6.9)

µ n ( f > m( f ) + r) ≤ 1 √ λr , ∀r > 0.
Let us first assume that Assumption (a) holds. Observe that the function X n → R : x → f A (x) := d 2 (x, A) is convex and 1-Lipschitz when A ⊂ X n is a convex set (this follows from properties (B 2 ) and (B 3 ) above). Moreover, using Point (i) of Lemma 5.2 and arguing as in the proof of Theorem 1.7, we see that f A,ε := ε + f 2 A satisfies the condition n i=1 |∇ + i f A | 2 ≤ 1. Since the function u → √ ε + u 2 is convex and increasing, the function f A,ε is itself convex. Applying (6.9) to f A,ε and letting ε → 0, we get (6.10)

µ n (A r,2 ) ≥ 1 - 1 √ λr ,
for all convex set A.

In particular, taking r o = 4/ √ λ we are in the framework of Corollary 4.5, with a o = 1/4 and A n being the class of convex sets of X n . (Note that Assumptions (i) and (ii) are well verified by A n : a product of convex sets is always convex and properties (B 2 ) and (B 3 ) above show that the enlargement of a convex set remains convex). We thus conclude that there are universal constants 0 < γ < 1 and 1/2 ≤ c < 1 such that, for all n ∈ N * , for all convex set A such that µ n (A) ≥ c µ n (A r,2 ) ≥ 1be -a √ λr , ∀r ≥ 0, with b = (1c)/γ and a =log(γ)/4. Now, if µ n (A) ≥ 1/2, then applying (6.10) we see that µ n (A r 1 ,2 ) ≥ c for r 1 =

1 √ λ(1-c)
. We easily conclude from this that µ verifies CCI ∞ 2 (α) with α(r) = b ′ e -a √ λr , for some other universal constant b ′ . Assume now that Assumption (b) holds. Let A ⊂ X n be a convex subset. The function f A defined above is 1-Lipschitz and convex. Therefore, according to Point (i) and (iii) Lemma 5.2, the function R ε f A , where R ε is the operator defined in (5.1), is 1 Lipschitz, convex and satisfies

n i=1 |∇ - i R ε f A | 2 ≤ 1.
Applying (6.9), we conclude that

µ n (R ε f A > m(R ε f A ) + r) ≤ 1 √ λr , ∀r > 0.
Moreover, according to Point (ii) of Lemma 5.2, it holds

f A - √ ε ≤ R ε f A ≤ f A .
Inserting this into the deviation inequality above and letting ε → 0 yields to the conclusion that (6.10) holds for all convex A. The rest of the proof is identical.

  the dual norm of the differential D f (x) ∈ B * of f at x. So (1.2) gives back the usual definitions in a smooth context. (3) To a Lipschitz function f on X, one can also associate |∇ + f | and |∇ f |, which are defined by replacing [ • ] -by [ • ] + or by | • | respectively. Since |∇ + f | = |∇ -(f )|, replacing f by f , we observe that the Poincaré inequality can be equivalently restated as (1.4) λVar µ ( f ) ≤ |∇ + f | 2 dµ, for all Lipschitz function f : X → R. Moreover, since |∇ f | = max(|∇ -f |; |∇ + f |), we see that (1.

2 =

 2 .6) tensorize properly. Therefore, if µ verifies one of the convex Poincaré inequalities, then for all n ∈ N * ,λVar µ n ( f ) ≤ n i=1 |∇ +/- i f | 2 dµ n ,for all Lipschitz and convex function f : X n → R. In particular, if f is 1-Lipschitz and such thatn i=1 |∇ +/- i f | 2 ≤ 1, then Var µ n ( f ) ≤ 1/λ. Applying Jensen's inequality, we see that 1/λ ≥ Var µ n ( f ) = inf a∈R ( fa) 2 dµ n ≥ inf a∈R | f -a| dµ n | fm( f )| dµ n 2

  4.3. Self improvement of dimension free concentration inequalities. The next result shows that a non-trivial dimension free concentration inequality can always be upgraded into an inequality with an exponential decay. This observation goes back to Talagrand[39, Proposition 5.1]. Corollary 4.4. If µ satisfies CI ∞ 2 (α) with a profile α such that α(r o ) < 1/2 for some r o , then it satisfies CI ∞

r , ∀r ≥ 0.

The authors were partially supported by the "Agence Nationale de la Recherche" through the grants ANR 2011 BS01 007 01 and ANR 10 LABX-58.