Simone Di

Jean Louet
email: louet@ceremade.dauphine.fr

THE ENTROPIC REGULARIZATION OF THE MONGE PROBLEM ON THE REAL LINE

We study the entropic regularization of the optimal transport problem in dimension 1 when the cost function is the distance c(x, y) = |y -x|. The selected plan at the limit is, among those which are optimal for the nonpenalized problem, the most "diffuse" one on the zones where it may have a density.

Introduction

In this paper, we are concerned with the following approximation of the optimal transportation problem: given two probability measures µ, ν on R d and ε > 0, find the minimizer of [START_REF] Ambrosio | Lecture notes on optimal transport problems[END_REF] J ε : γ → ¨|y -x| dγ(x, y) + ε ¨log dγ d(µ ⊗ ν) dγ among all the measures γ on R d × R d which have a density with respect to µ ⊗ ν and whose first and second marginals are equal to µ and ν, respectively. At the limit ε → 0, we expect the minimizer γ ε to converge to an optimal measure for the energy ´|y -x| dγ with prescribed marginals, and our goal is to understand which one is selected.

The corresponding problem with ε = 0 is the "distance cost" version of the classical optimal transport problem, whose original formulation, due to Monge in the 18th century [START_REF] Monge | Mémoire sur la théorie des déblais et des remblais[END_REF], consists in looking for the map T : R d → R d which minimizes ˆRd c(x, T (x)) dµ(x), where c is a given positive function and T must satisfy the constraint [START_REF] Ambrosio | Functions of Bounded Variation and Free Discontinuity Problems[END_REF] for any Borel set B ⊂ R d , µ(T -1 (B)) = ν(B).

Due to the difficulty of this image-measure constraint, this problem remained quite difficult to solve for many years. A suitable relaxation, which corresponds to our problem [START_REF] Ambrosio | Lecture notes on optimal transport problems[END_REF] with no penalization, was introduced by Kantorovich in the 1940s [START_REF] Kantorovich | On the translocation of masses[END_REF][START_REF] Kantorovich | On a problem of Monge[END_REF], namely, the minimization problem:

(3) inf ¨Rd ×R d c(x, y) dγ(x, y) : γ ∈ Π(µ, ν) ,

where Π(µ, ν) is the set of probability measures γ on R d × R d having µ and ν as marginals, that is, [START_REF] Angenent | Minimizing flows for the Monge-Kantorovich problem[END_REF] for any Borel set

B ⊂ R d , γ(B × R d ) = µ(B) and γ(R d × B) = ν(B).
The problem (3) is a generalization of the Monge's problem as, from any map T satisfying the above measure constraint, it is easy to build a measure γ ∈ Π(µ, ν) which is concentrated on the graph of T and has same total energy; moreover, due to the compactness properties of Π(µ, ν) for the weak topology of measures, proving the existence of solutions of (3) is easy by the direct methods of the calculus of variations. Thanks to a suitable convex duality argument,

1
it is possible to prove [START_REF] Brenier | Décomposition polaire et réarrangement monotone de champs de vecteurs[END_REF][START_REF] Brenier | Polar factorization and monotone rearrangement of vector-valued functions[END_REF][START_REF] Gangbo | The geometry of optimal transportation[END_REF], under suitable assumptions on the data and the cost function c (which include the case c = |y -x| p for 1 < p < +∞), that the problem (3) admits a unique solution which is induced by a map T , yielding optimality of this map for the original Monge problem. In the case c = |y -x|, the existence results are more recent and the uniqueness is not guaranteed anymore; cf. [START_REF] Ambrosio | Lecture notes on optimal transport problems[END_REF]. We refer to the monographs [START_REF] Ambrosio | Gradient Flows in Metric Spaces and in the Space of Probability Measures[END_REF][START_REF] Villani | Topics in Optimal Transportation[END_REF][START_REF] Villani | Optimal Transport: Old and New[END_REF][START_REF] Santambrogio | Optimal Transport for Applied Mathematicians[END_REF] for a complete overview of the optimal transportation theory.

Although it was already present in much earlier works, the penalization (1) has been recently reintroduced for numerical reasons. Indeed, computing numerically the optimal transport map T remained for a long time a very challenging problem; a first major achievement appeared in the beginning of the 2000s, when Benamou and Brenier [START_REF] Benamou | A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem[END_REF] introduced the so-called "dynamical formulation" (based on the minimization of the kinetic energy among the curves of measures and velocity fields satisfying a mass conservation equation), which can be solved by an augmented Lagragian method after a convex change of variables. Let us also mention the algorithms due to Angenent, Hacker, and Tannenbaum [START_REF] Angenent | Minimizing flows for the Monge-Kantorovich problem[END_REF], which also rely on fluid-mechanics formulations, and more recently the approaches by discretization of the Monge-Ampère equation [START_REF] Benamou | Discretization of functionals involving the Monge-Ampère operator[END_REF][START_REF] Benamou | Monotone and consistent discretization of the Monge-Ampère operator[END_REF] or via semidiscrete optimal transport [START_REF] Mérigot | A multiscale approach to optimal transport[END_REF][START_REF] Lévy | A numerical algorithm for L2 semi-discrete optimal transport in 3D[END_REF].

The numerical interest of the approaches similar to [START_REF] Ambrosio | Lecture notes on optimal transport problems[END_REF] has been shown in the last few years. The general idea consists in perturbing the Kantorovich problem by the so-called "entropy functional" defined as

Ent(γ|ρ) =    ˆlog dγ dρ dγ if γ ρ, +∞ otherwise.
and in focusing, given a suitable small parameter ε > 0, on the problem [START_REF] Benamou | A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem[END_REF] inf ¨c(x, y) dγ(x, y) + ε Ent(γ|µ ⊗ ν) : γ ∈ Π(µ, ν) .

Among other properties, the function Ent(•|µ ⊗ ν) enforces γ to be an absolutely continuous measure with respect to the tensor product µ ⊗ ν and favors such transport plans which are as diffuse as possible (on the set Π(µ, ν), its unique minimizer is µ ⊗ ν). The idea of the entropic penalization actually goes back to Schrödinger's works [START_REF] Schrödinger | Über die Umkehrung der Naturgesetze[END_REF]; moreover, the algebraic properties of the entropy functional and of the dual problem of (5) make the numerical computation of its solution much easier, thanks to the so-called Sinkhorn's algorithm involving alternated projections. We refer to the papers [START_REF] Cuturi | Sinkhorn distances: Lightspeed computation of optimal transport[END_REF][START_REF] Benamou | Iterative Bregman projections for regularized transport problems[END_REF] and the Ph.D. thesis [START_REF] Nenna | Numerical Methods for Multi-Marginal Optimal Transportation[END_REF] for more details on the theoretical and numerical properties of this class of algorithms.

From a theoretical point of view, the convergence of the solution of (5) as ε → 0 has been recently proven in [START_REF] Carlier | Convergence of entropic schemes for optimal transport and gradient flows[END_REF] (we also mention [START_REF] Léonard | From the Schrödinger problem to the Monge-Kantorovich problem[END_REF][START_REF] Léonard | A survey of the Schrödinger problem and some of its connections with optimal transport[END_REF], in which similar problems are studied in a much more abstract framework): therein, the authors showed that the family of functionals [START_REF] Benamou | Iterative Bregman projections for regularized transport problems[END_REF] γ ∈ Π(µ, ν) → ˆc dγ + ε Ent(γ|µ ⊗ ν)

is Γ-converging, as ε → 0, to the transport energy γ → ´c dγ. Therefore, when c is one of the costs for which there exists a unique optimal plan γ for the Kantorovich problem (3), the family (γ ε ) ε of minimizers of (6) converges to γ.

In this paper, we are interested in the following theoretical question: What's happening if there are several minimal plans γ for the cost function c? As usual in minimization problems of penalized functionals, it is natural to guess that, when the set O c of optimal plans for cost function c has at least two elements, the family (γ ε ) ε of minimizers of J ε will converge to the "most diffuse" element of O c , namely, the one which minimizes the entropy functional E(•|µ ⊗ ν).

However, the existence of a plan belonging to O C and having finite entropy is far from clear, and is generally false depending on the cost function c and the data.

We here focus on the case where c(x, y) = |y -x|, which was the original cost function proposed by Monge. This cost function is certainly the most studied one for which it is known that the uniqueness of optimal plan and optimal map fails, and selecting a particular optimal plan by adding a "regularizing" term to the energy is quite common: this is classically done through strictly convex costs which brings to the monotone transport; see, for instance, [START_REF] Caffarelli | Constructing optimal maps for Monge's transport problem as a limit of strictly convex costs[END_REF][START_REF] Feldman | Uniqueness and transport density in Monge's mass transportation problem[END_REF][START_REF] Trudinger | On the Monge mass transfer problem[END_REF] for existence of optimal maps and [START_REF] Li | Regularity in Monge's mass transfer problem[END_REF] for very partial regularity results (we also mention the quite different approximation proposed in [START_REF] De Pascale | The Monge problem with vanishing gradient penalization: Vortices and asymptotic profile[END_REF], where the "regularizing" term enforces the transport plan to be induced by a regular map). In the present paper, we concentrate on the entropic regularization of this problem where the measures are supported on the real line. In higher dimension, let us just notice that the structure of optimal Monge's plans is much more complicated, involving the geometric notion of transport rays (see, for instance, [START_REF] Ambrosio | Lecture notes on optimal transport problems[END_REF] or [START_REF] Santambrogio | Optimal Transport for Applied Mathematicians[END_REF]Chapter 3]), and although one may guess that the "most diffuse transport plans on each ray" will be selected, attacking this regularization problem on the Euclidean space would probably require very different techniques from ours.

In the one-dimensional case, the contributions and results of this paper are the following:

• First of all, we need a complete description of the set of one-dimensional optimal transport plans for the distance cost c(x, y) = |y -x|; although this result is natural and its proof is not complicated, it was not present in the literature at that time to the best of our knowledge. The structure of optimal plans is described in Proposition 3.1 and can be summarized as follows: denoting by T the monotone rearrangement (that is, the unique non-decreasing transport map) between µ to ν, the optimal plans γ are those such that if (x, y) is in the support of γ, then if T (x) = x, then y must be exactly equal to x; if x belongs to some interval where T -id > 0, then y must belong to the same interval and be larger than x; the analogous constraint holds where T -id < 0. In particular, any optimal transport plan can be decomposed into a "bad plan" which is concentrated on the graph on the identity map (and therefore is singular with respect to the Lebesgue measure) and a "possibly good plan" which must only respect the sign of T -id and is allowed to have a density.

• Once this structural result is stated, our main result studies the Γ-convergence of the penalized functional. Actually, we need to consider the "rescaled functional"

F ε : γ → 1 ε ˆ|y -x| dγ -W 1 (µ, ν) + Ent(γ|µ ⊗ ν) -µ(A)| log(2ε)|,
where A is the set {x ∈ R : T (x) = x} and W 1 (µ, ν) the minimal transport energy for the distance cost. For fixed ε, the functional F ε admits exactly the same minimizers as J ε .

In Theorem 4.1 we prove, under technical assumptions on the data, that its Γ-limit is +∞ outside of the set of optimal plans, and that, in this set, it is equal to

F : γ → Ent(γ (R \ A) 2 |µ ⊗ ν) + C,
where the constant C only depends on the data. In particular, the unique minimizer of F is the plan which is optimal for distance cost and whose "good part" is "as diffuse as possible", as we could naturally expect. Moreover, this result implies the asymptotic expansion

min J ε = W 1 (µ, ν) + µ(A)ε| log(2ε)| + ε min F + o(ε);
notice that the excess of order ε| log ε| is a common phenomenon with the penalization of the Monge problem proposed in [START_REF] De Pascale | The Monge problem with vanishing gradient penalization: Vortices and asymptotic profile[END_REF]. • Finally, Section 5 studies the explicit form of the optimal plan which is selected at the limit, i.e., the minimizer of F ; the precise result is stated in Theorem 5.1, which also gives a necessary and sufficient condition for F to be not identically +∞. This section relies on entropy-minimization problems of the "good part of optimal plans", which can be rewritten

min Ent γ | (µ(x) ⊗ ν(y)) (I × I) • 1 y≥x
on maximal positivity intervals I of T -id (and as analogous minimization problems on their negative counterparts). Similar problems were already deeply analyzed in [START_REF] Borwein | Decomposition of multivariate functions[END_REF][START_REF] Borwein | Entropy minimization, DAD problems, and doubly stochastic kernels[END_REF], and we here provide new self-contained proofs more suitable for our needs.

Notation and preliminary results

In this section, we collect the notation and well-known facts on measure theory and optimal transportation which will be used throughout the paper.

Let X and Y be two Polish spaces (in this paper, we will only focus on the case X = Y = R), and let µ, ν be two positive measures on X, Y whose total masses are finite and equal. We denote by Π(µ, ν) the set of transport plans from µ to ν, that is, the set of positive measures on X × Y satisfying (4); recall that this constraint can be reformulated as follows: for any

(ϕ, ψ) ∈ C b (X) × C b (Y ),
¨ϕ(x) dγ(x, y) = ˆϕ dµ and ¨ψ(y) dγ(x, y) = ˆψ dν.

When T : X → Y is a map, we call it a transport map from µ to ν if it satisfies (2). This is equivalent to saying that the measure γ T defined as

for any f ∈ C b (X × Y ), ¨f dγ T = ˆf (x, T (x)) dµ(x)
belongs to Π(µ, ν). Equivalently, this means that the equality ´ϕ • T dµ = ´ϕ dν holds for any ϕ ∈ C b (X). A useful property of Π(µ, ν) is the following.

Proposition 2.1. Let X, Y be Polish spaces, and let µ, ν be positive measures on X, Y with finite mass. Then the set Π(µ, ν) is compact with respect to the narrow topology of measures.

We now introduce the definition of relative entropy. In this paper, we are interested in the optimal transport problem when c is given by the distance c(x, y) = |y -x|. In that case, the so-called "duality formula of the optimal transport problem" takes the following form.

Theorem 2.1. Given µ, ν ∈ P(R d ), we have the equality [START_REF] Benamou | Discretization of functionals involving the Monge-Ampère operator[END_REF] inf ˆ|y -x| dγ(x, y) :

γ ∈ Π(µ, ν) = sup ˆu dν -ˆu dµ : u ∈ Lip 1 (R d ) ,
where Lip 1 (R d ) stands for the set of Lipschitz functions on R d having Lipschitz constant at most 1. The common optimal value will be denoted by W 1 (µ, ν) and the set of optimal transport plans by O 1 (µ, ν); a maximizer of the dual problem will be called a Kantorovich potential.

As a consequence of (7), given a function u ∈ Lip 1 (R d ) and a transport plan γ ∈ Π(µ, ν), the following properties are equivalent:

(i) u is a Kantorovich potential and γ ∈ O 1 (µ, ν);

(ii) for γ-a.e. (x, y), |y -x| = u(y) -u(x).

The last theoretical notion we will need in this paper is the one of Γ-convergence.

Definition 2.2. Let X be a complete metric space and (F n ) n , F be functionals X → R ∪ {+∞}.

We say that (F n ) n Γ-converges to F if, for any x ∈ X, the two following inequalities are satisfied:

• for any sequence (x n ) n of X converging to x, lim inf n F n (x n ) ≥ F (x) (Γ-liminf inequality);
• there exists a sequence (x n ) n of X converging to x such that lim sup

n F n (x n ) ≤ F (x) (Γ-limsup inequality).
The main interests of this notion are its implications in terms of convergence of minima and minimizers.

Theorem 2.2. Let (F n ) n be a sequence of functions X → R ∪ {±∞} and assume that F n Γ -→ n F . Assume moreover that there exists a compact and nonempty subset K of X such that ∀n ∈ N, inf

X F n = inf K F n
(we say that (F n ) n is equi-mildly coercive on X). Then F admits a minimum on X and the sequence (inf X F n ) n converges to min F . Moreover, if (x n ) n is a sequence of X such that

lim n F n (x n ) = lim n (inf X F n )
and if (x ϕ(n) ) n is a subsequence of (x n ) n having a limit x, then F (x) = inf X F .

In our settings, all the functionals that we consider will be defined on the space Π(µ, ν). Thanks to its compactness property, the equi-coercivity assumption of Theorem 2.2 will always be satisfied in this paper: therefore, in order to conclude that the minimal values and the minimizers of a given family of functionals are converging to those of a given "target" functional, checking the upper and lower limit conditions of Definition 2.2 will be enough.

We recall now the already known Γ-convergence results in entropic regularization (see [START_REF] Carlier | Convergence of entropic schemes for optimal transport and gradient flows[END_REF]Theorem 2.7] where the proof is given for c(x, y) = |y -x| 2 but can easily be adapted for a much larger class of cost functions).

Theorem 2.3 (zeroth-order Γ-convergence). Let c : R d → R be continuous and µ, ν be two probability measures on R d having compact support and being absolutely continuous with respect to the Lebesgue measure. Assume that ˆlog dµ dL d dµ, ˆlog dν dL d dν < +∞. Then the family of functionals

J ε : γ ∈ Π(µ, ν) → ˆc dγ + ε Ent(γ|µ ⊗ ν) is Γ-converging, as ε → 0, to γ → ˆc dγ.
We end this section by the "first-order Γ-convergence" result, which completes the previous one.

Proposition 2.3 (first-order Γ-convergence). Under the same assumptions as Theorem 2.3, denoting by W c (µ, ν) the minimal transport energy for cost c and by O c (µ, ν) the set of corresponding optimal plans, the family of functionals

H ε : γ ∈ Π(µ, ν) → 1 ε ˆc dγ -W c (µ, ν) + Ent(γ|µ ⊗ ν) is Γ-converging to H : γ ∈ Π(µ, ν) → Ent(γ|µ ⊗ ν) if γ ∈ O c (µ, ν), +∞ otherwise.
Proof. The Γ-limsup inequality is trivial since, given γ ∈ Π(µ, ν),

• if H(γ) = +∞, there is nothing to prove;

• if H(γ) < +∞, this means that E(γ|µ ⊗ ν) is finite and ´c dγ = W c (µ, ν). Taking for (γ ε ) ε the constant family equal to γ, we have immediately H ε (γ ε ) = H(γ) for any ε, such that the upper limit condition is satisfied.

As for the Γ-liminf, given γ ε → γ in Π(µ, ν), then,

• if γ / ∈ O c (µ, ν)
, since the entropy is positive on Π(µ, ν), and ´c dγ ε → ´c dγ, we have that for ε small enough

H ε (γ ε ) ≥ 1 ε ˆc dγ ε -W c (µ, ν) ≥ 1 2ε ˆc dγ -W c (µ, ν) → +∞;
• otherwise, it is enough to observe, for any ε > 0, the inequality

H ε (γ ε ) ≥ Ent(γ ε |µ ⊗ ν)
and to conclude by semicontinuity of the entropy.

The consequences of Theorem 2.3 and Proposition 2.3 are the following.

• The minimal value and the minimizers of J ε are converging (up to subsequences) to the minimal transport energy and to an optimal transport plan for cost c, respectively. In particular, if there is only one optimal transport plan, then this plan is selected at the limit by the entropic regularization. • If the set O c (µ, ν) contains at least one plan with finite entropy (which is equivalent to saying that H is not identically +∞), then the plan which is selected at the limit is the one having minimal entropy in the set O c (µ, ν), and we have the asymptotic expansion

min J ε = W c (µ, ν) + ε min H + o(ε) as ε → 0.
• In the converse case, and if there is no uniqueness of the optimal plan for cost c, then the plan which is selected at the limit is unknown, and the only information on the behavior of the minimal value is (inf

J ε -W c (µ, ν))/ε → +∞.
As we will see later on in the paper, this last case may occur when c(x, y) = |y -x|, depending on the data µ and ν; precisely, the next section gives a general description of the optimal plans for distance cost in dimension one.

3. Structure of one-dimensional optimal plans 3.1. Additional notation and the monotone transport map. First of all, let us recall the precise definition of the monotone transport map that we will use, which is essentially taken from [START_REF] Santambrogio | Optimal Transport for Applied Mathematicians[END_REF]Chapter 2]. Let µ, ν be two probability measures on R compactly supported and with no atom, and let us denote by F µ , F ν the cumulative distribution functions of µ, ν, respectively; we notice that since neither µ or ν has any atom, both F µ and F ν are continuous on R. We define

T (x) := inf y ∈ R : F ν (y) ≥ F µ (x) .
We can then prove the following properties, thanks to the boundedness of the supports of µ, ν and to the continuity of F µ , F ν :

• the map T is finitely valued on (inf(supp µ), +∞);

• for any x with inf(supp µ) < x, the infimum in the definition of T (x) is attained; therefore,

F ν (T (x)) = F µ (x) (8)
and, for any y < T (x), F ν (y) < F µ (x).

The following theorem then holds; see [28, Theorems 2.5 and 2.9].

Theorem 3.1. The map T is nondecreasing and satisfies T # µ = ν. Moreover, any other such map coincides with T except on a µ-negligible set. Finally, for any cost function c having form c(x, y) = h(y -x) with h convex, the map T is optimal for the transport problem with cost c.

The following lemma is useful in order to make precise the links between F µ , F ν and the sign of T -id. Lemma 3.1. For µ-a.e. every point of R, the following equivalences are true:

(a) T (x) = x if and only if F µ (x) = F ν (x); (b) T (x) < x if and only if F µ (x) < F ν (x); (c) T (x) > x if and only if F µ (x) > F ν (x).
Proof. Let us start by the equivalence (b). First of all, let x be a point of the support of µ, different of its bounds, and such that T (x) < x; in particular, the monotonicity of F ν implies that F ν (T (x)) ≤ F ν (x). Assume moreover that F µ (x) ≥ F ν (x): keeping in mind that F ν • T and F µ coincide, this enforces F ν (x) = F ν (T (x)). We deduce that the interval (T (x), x) does not meet the support of ν: therefore, T (x), which belongs to supp ν, is actually a boundary point of one of the connected components of R \ supp ν. These boundary points being countably many, they form a ν-negligible set, and the preimage of this set by T is therefore µ-negligible, proving that the direct implication in (b) is true for µ-a.e. x.

Conversely, let x be such that F µ (x) < F ν (x) and assume that T (x) ≥ x: therefore, since F ν is nondecreasing,

F ν (T (x)) ≥ F ν (x) > F µ (x), which is impossible since F ν (T (x)) = F µ (x).
The equivalence (c) can be proved by pretty similar arguments, and (a) is an obvious consequence of (b) and (c).

In what follows in the paper, we will often use the following sets:

A := x ∈ R : F µ (x) = F ν (x) and A + := x ∈ R : F µ (x) > F ν (x) , A -:= x ∈ R : F µ (x) < F ν (x) .
We notice that A + and A -are both open and that A, which is the complementary set of their union, is closed. Moreover, thanks to the Lemma 3.1, these three sets coincide, up to µ-negligible sets, with the sets where T -id is respectively zero, positive and negative. The following remark, though obvious, will also sometimes be useful.

Lemma 3.2. Let I be a maximal interval fully included in A -or in A + . Then µ(I) = ν(I).

Proof. Such an I is necessarily an open and bounded interval of R; calling it (a, b) and using its maximality and the continuity of F µ , F ν , we can easily see that F µ (a) = F ν (a) and F µ (b) = F ν (b), so that µ(I) = ν(I).

We can now state the precise result on the structure of one-dimensional optimal plans. Proposition 3.1. Let µ, ν ∈ P(R) be atomless and compactly supported. Then the optimal plans for the Monge problem are exactly the transport plans from µ to ν such that, for γ-a.e.

(x, y) ∈ R 2 , (a) if x ∈ A, then y = x; (b) if x ∈ A + , then y ≥
x, and y belongs to the same connected component of A + as x;

(c) similarly, if x ∈ A -, then y ≤ x, and y belongs to the same connected component of A - as x.

The key point of the proof of Proposition 3.1 consists in building a suitable Kantorovich potential, which is the topic of the next subsection.

Construction of a

Kantorovich potential. Lemma 3.3. For x ∈ R, define u(x) = ˆx 0 1 A + -1 A -(t) dt.
Then u is a Kantorovich potential from µ to ν, that is, a maximizer of the problem [START_REF] Benamou | Discretization of functionals involving the Monge-Ampère operator[END_REF].

Proof of Lemma 3.3. The fact that u is 1-Lipschitz being obvious, the only non-trivial point of the proof is checking that (9) u(T (x)) -u(x) = |T (x) -x| for µ-a.e. x , which will ensure that u is optimal for the dual problem. Let then x be a point of the support of µ such that T (x) = x (otherwise the equality ( 9) is obviously satisfied); assume without loss of generality that T (x) > x. By contradiction, suppose that u(T (x)) -u(x) < |T (x) -x| (the converse inequality cannot hold since u is a 1-Lipschitz function): from the definition of u, this implies that L([x, T (x)] \ A + ) = 0 and in particular there exists a point y such that x < y < T (x) and y / ∈ A + , that is, F µ (y) ≤ F ν (y). By the property (8), we deduce y ≥ T (y): summarizing,

x < y; T (x) > y ≥ T (y).
Since T is a nondecreasing function, this is impossible. The arguments are identical in the case T (x) < x.

The two following paragraphs are then devoted to the rigorous proof of Proposition 3.1.

3.3.

Necessary condition to be optimal. In this paragraph, we prove that all the optimal plans for the Monge problem satisfy properties (a)-(c) of Proposition 3.1. We then fix γ ∈ O 1 (µ, ν).

Step I: for any x ∈ A, we have γ((-

∞, x] × [x, +∞)) = γ([x, +∞) × (-∞, x]) = 0. Let x ∈ A,
and assume by contradiction that [START_REF] Borwein | Entropy minimization, DAD problems, and doubly stochastic kernels[END_REF] γ((-∞, x] × [x, +∞)) > 0.

Notice that [START_REF] Borwein | Entropy minimization, DAD problems, and doubly stochastic kernels[END_REF]

implies that 0 < F µ (x) = F ν (x) < 1. We first show that (11) γ([x, +∞) × (-∞, x]) > 0.
Indeed, if [START_REF] Brenier | Décomposition polaire et réarrangement monotone de champs de vecteurs[END_REF] was false, then we would have

ν([x, +∞)) = µ([x, +∞)) = γ([x, +∞) × R) = γ([x, +∞) 2 )
and consequently

γ((-∞, x] × [x, +∞)) = ν([x, +∞)) -γ([x, +∞) × [x, +∞)) = 0,
which contradicts ( 10) From ( 10) and ( 11), we deduce that there exists (x 1 , y 1 ) and (x 2 , y 2 ) in the support of γ with

x 1 < x < y 1 and y 2 < x < x 2 .
Theorem 2.1 and the continuity of u imply that u(y 1 ) -u(x 1 ) = y 1 -x 1 and u(y 2 ) -u(x 2 ) = -(y 2 -x 2 ): since u is 1-Lipschitz, this enforces u to be an affine function with slope 1 and -1 on the whole intervals [x 1 , y 1 ] and [y 2 , x 2 ], respectively. But these intervals have nontrivial intersection, which leads to a contradiction.

Step II: γ satisfies property (a) of Proposition 3.1. Let x ∈ A, let y such that (x, y) belongs to the support of γ, and assume by contradiction that y > x. Without loss of generality, we may assume

(x, y) ∩ A = ∅.
Indeed, if this was not the case, x would be a boundary point of one of the connected components of R \ A: since this set is open, such points are countably many, forming then a µ-negligible set. Let then x ∈ A such that x < x < y. From the result of Step I, it holds that [START_REF] Brenier | Polar factorization and monotone rearrangement of vector-valued functions[END_REF] γ((-∞, x ] × [x , +∞)) = 0.

In particular, selecting a positive ε < min(x -x, y -x ), we deduce from (12) that γ([x ± ε] × [y ± ε]) = 0 so that (x, y) does not belong to the support of γ, a contradiction. Analogously, we prove that the inequality y < x cannot hold except for at most countably points x.

Step III: γ satisfies the properties (b) and (c) of Proposition 3.1. Let x ∈ A + and y ∈ R be such that (x, y) belongs to the support of γ and u(y) -u(x) = |y -x|. First, assume that y < x, which implies

- ˆx y (1 A + -1 A -) = x -y;
in particular, since A + is an open set and does not meet A -, we must have A + ∩ (y, x) = ∅, but since x belongs to A + which is open, this is impossible.

We then have y ≥ x; let us now prove that y belongs to the same connected component of A + as x. Since A + is an open set it suffices to prove that (x, y) ⊂ A + . As above, we deduce from the equality u(y) -u(x) = |y -x| that A -∩ (x, y) = ∅; therefore it suffices to prove that (x, y) does not meet A. Assume then that there exists z ∈ A with x < z < y; the result of Step I gives then

γ((-∞, z] × [z, +∞)) = 0.
By selecting a positive ε < min(z -x, y -z) we obtain again γ([x -ε, x + ε] × [y -ε, y + ε]) = 0, a contradiction since (x, y) belongs to the support of γ. As before, the arguments in the case x ∈ A -are identical.

3.4. Sufficient condition to be optimal. We now focus on the converse implication of Proposition 3.1 and denote by (I - j ) j , (I + k ) k the connected components of A -, A + , respectively (which are at most countably many). We also set for each j, k,

µ - j = µ I - j , µ + k = µ I + k , and
ν - j = ν I - j , ν + k = ν I + k . Lemma 3.2 implies that µ - j , ν - j (respectively, µ + k , ν + k )
have the same mass. Moreover, thanks to the previous subsection, the points (a)-(c) of Proposition 3.1 apply for the plan which is induced by the map T , which enforces, for any j, k,

ν - j = T # µ - j and ν + k = T # µ + k .
Using also Lemma 3.1, we deduce From the property (a), we immediately deduce that the first integral in the sum above is zero, and from (b) and (c), we infer that, for any j, k, ˆI-

W 1 (µ, ν) = ˆ|T (x) -x| dµ(x) = j ˆI- j (T (x) -x) dµ(x) + k ˆI+ k (x -T (x)) dµ(x) = j ˆy dν - j (y) -ˆx dµ - j (x) + k ˆx dµ + k (x) -ˆy dν + k (y) . (13
j ×R |y -x| dγ(x, y) = ˆI- j ×I - j (x -y) dγ(x, y) = ˆx dµ - j -ˆy dν - j and ˆI+ k ×R |y -x| dγ(x, y) = ˆI+ k ×I + k (y -x) dγ(x, y) = ˆy dν + k -ˆx dµ + k .
Adding on all the indexes j, k and using (13) leads to ´|y -x| dγ(x, y) = W 1 (µ, ν), so that γ is optimal, as required. where the intervals (a i , b i ) are pairwise disjoint and satisfy

(14) - i ˆbi ai log min{x -a i , b i -x} dµ(x) < +∞.
This assumption is in particular satisfied in the two following cases: (H1a) µ has bounded density on A and

i |a i -b i | log |a i -b i | < +∞, or (H1b) we have i |a i -b i | 1-δ < +∞ for some δ > 0.
(H2) There exists an optimal plan γ for the Monge problem such that γ (R \ A) 2 has finite entropy with respect to µ ⊗ ν.

Then the family (F ε ) ε of functionals defined on the set Π(µ, ν) by

F ε (γ) = 1 ε ˆ|y -x| dγ -W 1 (µ, ν) + Ent(γ|µ ⊗ ν) -| log(2ε)|µ(A)
is Γ-converging, as ε → 0, to the functional F which is finite only on the set O 1 (µ, ν) of optimal plans for the Monge problem, and is then equal to

F (γ) = Ent(γ (R \ A) 2 |µ ⊗ ν) -ˆA log dµ dL 1 dµ.
The main qualitative consequence of this result is that the minimizer which is selected by the entropic regularization is exactly the most diffuse one on the zone where an optimal transport plan may have a density, if such a plan having also finite entropy exists (which is the sense of the assumption (H2)). Indeed, Proposition 3.1 implies that if the set A has positive mass for µ, all the elements of O 1 (µ, ν) have infinite entropy, since their restriction to A × A is concentrated on the graph on the one-dimensional function T . On the contrary, it is natural to guess that there should exist two-dimensional densities on the squares (I - j ) 2 , (I + k ) 2 which respect the sign of T -id: selecting the most diffuse such density (that is, the one which minimizes the entropy with respect to µ ⊗ µ on these squares, provided that such a density exists), we obtain exactly the minimizer of the target functionals F . Since, for fixed ε > 0, the functional F ε is only a rescaling version of the original functional J ε , it admits exactly the same minimizers, which are therefore converging to the (only) minimizer of F .

As we said in the introduction, we may also notice that Theorem 4.1 allows us to know precisely the asymptotic behavior of the minimal value of the penalized problem: precisely, as ε → 0,

min J ε = W 1 (µ, ν) + ε| log(2ε)|µ(A) + ε min F + o(ε).
The excess of order | log ε| is a common phenomenon with another type of approximation of the Monge problem where the regularization impacts the transport map itself; see [START_REF] De Pascale | The Monge problem with vanishing gradient penalization: Vortices and asymptotic profile[END_REF]. Moreover, this was also the order of convergence of the construction proposed by Carlier et al. in [START_REF] Carlier | Convergence of entropic schemes for optimal transport and gradient flows[END_REF] ("block approximation") to prove the density, in the set of transport plans, of transport plans having finite entropy (see Proposition 2.14 therein).

We postpone to the last section an explicit representation formula for the minimizer of the entropy restricted to the squares (I - j ) 2 , (I + k ) 2 and in particular a necessary and sufficient condition for the assumption (H2). Concerning the assumption (H1), it is essentially needed for technical reasons; we do not claim it to be necessary for the Γ-convergence result, but unfortunately we were not able to conclude the lower limit estimate without it (see below the proof in subsection 4.3).

Γ-limsup inequality.

In this section, we prove the Γ-limsup inequality of Theorem 4.1, that is, for any fixed γ ∈ Π(µ, ν), building a family (γ ε ) ε in Π(µ, ν) having γ as limit and such that lim sup

ε→0 F ε (γ ε ) ≤ F (γ).
We then select γ ∈ Π(µ, ν) such that F (γ) < +∞; otherwise there is nothing to prove. therefore, γ satisfies the conditions (a)-(c) and the assumption (H2) of Proposition 3.1. Let ε > 0 be fixed. We will define separately two densities whose sum will be our approximating transport plan.

Our first transport plan is simply

γ 1 ε := γ (R \ A) 2 .
Thanks to the result of Proposition 3.1, it is exactly the part of γ where there is some displacement, so that its Monge cost has value W 1 (µ, ν).

In order to get a transport plan γ ε from µ to ν, we have to build a "complementary transport plan" γ 2 ε ∈ Π(µ A, µ A) and to set

γ ε = γ 1 ε + γ 2 ε .
Let us now see what the requirements are so that the family (γ ε ) ε that we will obtain satisfies the Γ-limsup condition. Assume then that γ 2 ε ∈ Π(µ A, µ A) is given: then, γ ε connects µ to ν and we have on one hand

(15) ˆ|y -x| dγ ε (x, y) = ˆ|y -x| dγ 2 ε (x, y) + W 1 (µ, ν)
and on the other, since γ 1 ε and γ 2 ε have disjoint supports, ( 16)

Ent(γ ε |µ ⊗ ν) = Ent(γ 2 ε |µ ⊗ ν) + Ent(γ 1 ε |µ ⊗ ν).
Plugging back the equalities ( 15) and ( 16) into the expression of F ε , we can see that the measure γ 2 ε that we want to build must be a transport plan from µ A to itself which satisfies ( 17)

1 ε ˆ|y -x| dγ 2 ε (x, y) + Ent(γ 2 ε |µ ⊗ ν) ≤ µ(A)| log(2ε)| -ˆA log dµ dL 1 dµ + o (1)
.

From now on, we will denote by µ A the density of the measure µ A; with a slight abuse of notation, we will also use, when required, the same symbols for positive measure on R 2 which are absolutely continuous with respect to the Lebesgue measure and, in that case, their densities (notice that by "density" we mean "density with respect to L 2 " and not to µ ⊗ ν).

Step I: the definition of γ 2 ε . The strategy would be easy if we knew exactly the expression of the transport plan which minimizes, for fixed ε > 0, the energy ´|y -x| dγ + ε Ent(γ|µ ⊗ ν) on the set Π(µ A , µ A ). From the dual formulation of this last problem, it is not hard to see that this plan must have form a ε (x)a ε (y)e -|y-x|/ε for some positive function a ε ; unfortunately, the function a ε seems difficult to compute explicitly. Instead, our strategy will be to define directly a first density γ ε which looks like a ε (x)a ε (y)e -|y-x|/ε , and whose marginals are almost µ A and are dominated by µ A; then, we will build another "complement" γ ε between the remaining part of the marginals.

Precisely, the first density that we define is given by

γ ε (x, y) := min(µ A (x), µ A (y)) e -|y-x|/ε 2ε .
We notice that, for µ-a.e. x ∈ A, we have

(18) ˆR γ ε (x, y) dy ≤ µ A (x) ˆR e -|y-x|/ε 2ε dy = µ A (x).
Let us denote by µ ε the first marginal of γ ε , which coincides with the second one, and let us set µ ε := µ A -µ ε : therefore, (18) implies that µ ε is a positive measure on R. It then remains to build a complementary transport plan γ ε belonging to Π( µ ε , µ ε ); then, setting γ 2 ε := γ ε + γ ε will be enough to get a transport plan from µ A to itself.

Our construction of γ ε is inspired by the "block approximation" in [14, Definition 2.9] and consists in building a density which is piecewise equal, on small squares, to the multiplication of µ ε ⊗ µ ε by appropriate constants, keeping in mind that γ ε must satisfy a marginal condition. Precisely, we select a family (Q i ) i of segments recovering the support of µ A (and so of µ ε ) and having all length at most ε; notice that thanks to the boundedness of A, the number N ε of such segments which are needed is bounded by C/ε for a universal constant C. Now we set, for any Borel set

B ⊂ R 2 , γ ε (B) = i µ ε ⊗ µ ε (B ∩ (Q i × Q i )) µ ε (Q i ) .
It is then easy to check that γ ε is, as required, a transport plan from µ ε to itself. In the next steps, we prove that γ ε + γ ε satisfies [START_REF] Feldman | Uniqueness and transport density in Monge's mass transportation problem[END_REF].

Step II: the total mass of µ ε vanishes as ε → 0. The result of this step will be proved by a dominated convergence argument: we thus begin by showing that for µ A -a.e. x, µ ε (x) → 0 as ε → 0.

From the definition of µ ε and µ ε , it is clear that, for µ A -a.e. x,

0 ≤ µ ε (x) ≤ ˆy∈R |µ A (y) -µ A (x)| e -|y-x|/ε 2ε dy.
Denoting by α ε (r) := re -r/ε ε 2 , it follows that

ˆy∈R |µ A (y) -µ A (x)| e -|y-x|/ε 2ε dy = ˆy∈R ˆ+∞ r=|y-x| α ε (r) 2r dr |µ A (y) -µ A (x)| dy = ˆ+∞ r=0 1 2r ˆx+r x-r |µ A (y) -µ A (x)| dy α ε (r) dr
by the Fubini theorem. Now we notice that, as a measure, α ε weakly converges to the Dirac mass δ 0 ; on the other hand, we have

lim r→0 1 2r ˆx+r x-r |µ A (y) -µ A (x)| dy = 0
as soon as x is a Lebesgue point of µ A . This proves that, for µ A -a.e. x ∈ R, the pointwise convergence of densities µ ε (x) → 0. The domination assumption can then easily be checked, concluding the proof of this step.

Before passing to the next steps, let us decompose the energy we are interested in in several terms, namely,

1 ε ˆ|y -x| dγ 2 ε (x, y) + Ent(γ 2 ε |µ ⊗ ν) = -2 ˆµA log µ A dx + 1 ε ˆ|y -x| dγ ε (x, y) + ˆlog(γ ε ) dγ ε (I) + 1 ε ˆ|y -x| d γ ε (x, y) (II) + ˆlog 1 + γ ε γ ε dγ ε (III) + ˆlog( γ ε + γ ε ) d γ ε (IV).
We will estimate successively the terms (I), (II), (III) and (IV).

Step III: estimates on the terms (I), (II), and (III). Starting from the definition of γ ε (x, y), we have for any

(x, y) ∈ R 2 log γ ε (x, y) = log min(µ A (x), µ A (y)) -log(2ε) - 1 ε |y -x|.
Integrating with respect to γ ε and coming back on the expression of (I) leads to This can be proved exactly in the same way as the result of Step II; more precisely, we notice that we have |f A (x, y) -g(x)| ≤ |g(y) -g(x)|, since f A (x, y) is either g(x) or g(y). In particular we have

(19) (I) = -log(2ε)γ ε (R 2 ) + ˆlog min(µ A (x), µ A (y)) min(µ A (x), µ A (y)) e -|y-x|/ε 2ε dx dy.
ˆy∈R |f A (x, y) -g(x)| e -|y-x|/ε 2ε dy ≤ ˆr>0 1 2r ˆx+r x-r |g(y) -g(x)| dy α ε (r) dr
with the same kernel α ε as above. It can be checked that the mean value in r goes to zero for a.e. x thanks to the fact that g ∈ L 1 , and since (α ε ) ε has δ 0 as limit in the weak sense of measures, this proves [START_REF] Kantorovich | On a problem of Monge[END_REF]. By combining [START_REF] Kantorovich | On the translocation of masses[END_REF] and ( 20), we conclude

(21) (I) = γ ε (R 2 ) • | log(2ε)| + ˆlog µ A dµ A + o(1)
.

We now pass to the terms (II) and (III), which are the two easiest terms. First, since γ ε is supported in the union of the squares Q i ×Q i which have length at most ε, we have |y -x| ≤ √ 2ε for γ ε -a.e. (x, y), so that

0 ≤ (II) ≤ 1 ε • γ ε (R 2 ) • √ 2ε = √ 2 µ ε (R) → 0
since, thanks to the result of Step II, we have µ ε (R) → 0 as ε → 0.

On the other hand, it also holds by the concavity of the logarithm

0 ≤ (III) = ˆlog 1 + γ ε γ ε dγ ε ≤ ˆ γ ε γ ε dγ ε = γ ε (R 2 ),
which is again equal to µ ε (R) and therefore vanishes as ε → 0. The two terms (II) and (III) have therefore zero as limit as ε → 0.

Step IV: estimate on the term (IV). This one is the most difficult. Recall that, from the definition of γ ε and γ ε , we have for any

(x, y) ∈ R 2 γ ε (x, y) = µ ε (x) µ ε (y) µ ε (Q i ) ≤ µ A (x)µ A (y) µ ε (Q i ) and γ ε (x, y) = min(µ A (x), µ A (y)) e -|y-x|/ε 2ε ≤ µ A (x) 2ε .
It immediately follows that

(IV) ≤ i ˆQ2 i log µ A (x)µ A (y) µ ε (Q i ) + µ A (x) 2ε d γ ε (x, y).
We separate this sum into two terms, depending if µ ε (Q i ) is larger or smaller than 2ε; therefore, we denote by I small the set of indexes i such that µ ε (Q i ) ≤ 2ε, by I large its complementary set, and also set

A small := i∈I small Q i and A large := i∈I large Q i .
Denoting by (IV.a) the part of the sum above whose indexes belong to I small , we have therefore

(IV.a) ≤ i∈I small ˆQ2 i log µ A (x)µ A (y) µ ε (Q i ) + µ A (x) µ ε (Q i ) d γ ε (x, y) ≤ i∈I small ˆQ2 i log(µ A (x)) + log(µ A (y) + 1) d γ ε -µ ε (Q i ) log ( µ ε (Q i )) ≤ 2 ˆAsmall log(µ A (x) + 1) d µ ε - i∈I small µ ε (Q i ) log ( µ ε (Q i )) .
Consequently, since log(µ A (x) + 1) is µ A integrable and µ A ≥ µ ε → 0 thanks to the results of

Step I, by dominated convergence we get

(22) (IV.a) ≤ o(1) - i∈I small µ ε (Q i ) log µ ε (Q i ).
For the second term, denoting by N ε the number of indexes in I small , the convexity of t → t log t gives

- 1 N ε i∈I small µ ε (Q i ) log µ ε (Q i ) ≤ - 1 N ε i∈I small µ ε (Q i ) log 1 N ε i∈I small µ ε (Q i ) ≤ 1 N ε µ ε (A small ) (log N ε -log µ ε (A small )) .
Plugging this inequality into [START_REF] Léonard | A survey of the Schrödinger problem and some of its connections with optimal transport[END_REF] provides

(IV.a) ≤ µ ε (A small ) log N ε + o(1)
as, at ε goes to 0, the term µ ε (A small ) log( µ ε (A small )) vanishes (thus giving a negligible term once we multiply it by ε). Keeping in mind that N ε ≤ C/ε for a constant C which does not depend on ε and using again the convergence µ ε (A small ) → 0, we infer

(23) (IV.a) ≤ | log ε| µ ε (A small ) + o(ε).
On the other hand, recall that we have (IV) ≤ (IV.a) + (IV.b) with

(IV.b) := i∈I large ˆQi log µ A (x)µ A (y) 2ε + µ A (x) 2ε d γ ε (x, y) ≤ i∈I large ˆQ2 i log(µ A (x)) + log(µ A (y) + 1) d γ ε -µ ε (Q i ) log (2ε) ≤ ˆAlarge log(µ A (x) + 1) d µ ε + | log 2ε| µ ε (A large ) = | log 2ε| µ ε (A large ) + o(1)
using again that the µ A ≥ µ ε → 0 and dominated convergence. Putting together this last estimate with [START_REF] Lévy | A numerical algorithm for L2 semi-discrete optimal transport in 3D[END_REF], we get (IV) ≤ | log(2ε)| µ ε (R) + o(1). Finally, by adding this last estimate to [START_REF] Léonard | From the Schrödinger problem to the Monge-Kantorovich problem[END_REF] and using that both (II) and (III) have zero limit as ε → 0, we get

1 ε ˆ|y -x| dγ 2 ε (x, y) + Ent(γ 2 ε |µ ⊗ ν) ≤ (µ ε (R) + µ ε (R))| log(2ε)| -ˆlog µ A dµ A + o(1) ≤ µ(A)| log(2ε)| -ˆµA log µ A dx + o(1)
so that ( 17) is proven.

4.3. Γ-liminf inequality. Let (γ ε ) ε be a family of transport plans having a limit γ as ε → 0 for the weak convergence of measures. First of all, we start by eliminating the case where γ is not an optimal transport plan for the Monge problem by noticing that, in that case,

F ε (γ ε ) ≥ M ε -µ(A)| log(2ε)|
for some positive constant M ; thus the Γ-liminf inequality is obviously satisfied. We now assume that γ ∈ O 1 (µ, ν), so that it verifies the statement of Proposition 3.1; we moreover may assume without loss of generality that all the γ ε , for ε > 0 small enough, have finite energy F ε and consequently that all of them have a density with respect to the two-dimensional Lebesgue measure. Again we will use generally the same notation for the measures γ ε and their twodimensional densities with respect to the Lebesgue measure (and not to µ ⊗ ν).

Let u be the Kantorovich potential given by Lemma 3.3. Using the 1-Lipschitz property of u, we may write

1 ε ˆ|y -x| dγ ε (x, y) -W 1 (µ, ν) = 1 ε ˆ |y -x| -(u(y) -u(x)) dγ ε (x, y) ≥ 1 ε ˆA×R |y -x| -(u(y) -u(x)) dγ ε (x, y).

Let us denote by γ

A ε = γ ε A × R and γε = γ ε -γ A ε .
Notice that the first marginal of γ A ε is precisely µ A , while the second marginal may be different and we call it ν ε ; notice that ν ε ν A = µ A but, thanks to the fact that ´ν log ν < ∞, we still have ´νε log ν → ´A µ A log µ A . Since γε and γ A ε are concentrated on disjoint sets and have γ ε as sum, we have

Ent(γ ε |µ ⊗ ν) = Ent(γ ε |µ ⊗ ν) + Ent(γ A ε |µ ⊗ ν)
. Moreover, it is clear that γε weakly converges, as ε → 0, to γ (R\A) 2 ; by the lower-semicontinuity property of the entropy functional, it follows that

lim inf ε→0 Ent(γ ε |µ ⊗ ν) ≥ Ent(γ (R \ A) 2 |µ ⊗ ν).
Putting together the above estimates, and using the lower semicontinuity of the entropy, it is clear that the Γ-liminf inequality we look for reduces to

¨ |y -x| -(u(y) -u(x)) dγ A ε (x, y) + ε Ent(γ A ε |µ ⊗ ν) ≥ ε µ(A)| log(2ε)| -ˆA log dµ dL 1 dµ + o(ε), which, by noticing that Ent(γ A ε |µ ⊗ ν) = ˜γA ε log γ A ε -2 ´A µ A log µ A + o(1), is equivalent to (24) ¨A×R |y -x| -(u(y) -u(x)) dγ A ε (x, y) + ε ¨A×R γ A ε log γ A ε ≥ ε µ(A)| log(2ε)| + ˆA µ log µ + o(ε).
In order to prove (24), we will make use of the following lemma.

Lemma 4.1. Let f, c be measurable positive functions such that cf ∈ L 1 (R) and f ∈ L log L(R).

Let ε > 0. Then the following inequality holds:

ˆ c(x)f (x) + εf (x) log(f (x)) dx ≥ ε ˆf log ˆf - ˆf log ˆe-c/ε .
Proof of Lemma 4.1. We write the left-hand side as

ε × ˆe-c/ε × 1 ´e-c/ε ˆf (x)
e -c(x)/ε log f (x) e -c(x)/ε e -c(x)/ε dx and the claimed inequality is then a direct consequence of the Jensen inequality, applied to the convex function t → t log t and the probability measure e -c(x)/ε dx ´e-c/ε .

Let ε > 0 and x ∈ A be fixed, and let [a, b] be a bounded interval containing the supports of µ and ν. We apply Lemma 4.1 to the function f x : y → γ A ε (x, y) and the function c defined as

c x (y) = (|y -x| -(u(y) -u(x))) 1 a≤y≤b .
We then obtain

ˆb a |y -x| -(u(y) -u(x)) γ ε (x, y) dy + ε ˆb a log γ ε (x, y)γ ε (x, y) dy ≥ ε ˆb a γ ε (x, •) log ˆb a γ ε (x, •) -ε ˆb a γ ε (x, •) dy log ˆb a e -cx(y)/ε dy ≥ εµ A (x) log µ A (x) -εµ(x) log
ˆb a e -cx(y)/ε dy .

After integrating with respect to x, it remains to prove the following lower estimate:

-ˆA log ˆb a e -cx(y)/ε dy dµ(x) ≥ µ(A)| log(2ε)| + o(1).
We notice that, from the definition of the Kantorovich potential u, it holds that

|y -x| -(u(y) -u(x)) ≤ L 1 (A ∩ [x, y])
for any x, y ∈ R (and where the notation [x, y] is used alternatively for [x, y] and [y, x], depending if x ≤ y or y ≤ x). Consequently, it is enough to prove the following:

-ˆA log ˆb a e -L 1 ([x,y]∩A)/ε dy dµ(x) ≥ µ(A)| log(2ε)| + o(1),
which can be written, after changing of variable y = x + εt, as

ε→0 ˆA -log 1 2 ˆIε(x) exp -|t| • L 1 ([x, x + εt] ∩ A) ε|t| dt dµ(x) ≥ 0 , (25) lim inf
where we denote by

I ε (x) the interval [-(x -a)/ε, (b -x)/ε].
We prove (25) by a dominated convergence argument. Denote by

I ε (x) := 1 2 ˆIε(x) exp -|t| • L 1 ([x, x + εt] ∩ A) ε|t| dt.
Let x be a fixed Lebesgue point of A for µ and let α > 0 be arbitrary small. Let η > 0 be fixed such that

1 -α ≤ L 1 ([x, y] ∩ A) |y -x| ≤ 1 + α
for any y ∈ [x -η, x + η]. Setting y = x + εt, we obtain after multiplying by t, composing with the function exp(-•) and integrating ( 26)

1 1 + α 1 -exp -(1 + α) η ε ≤ 1 2 ˆη/ε -η/ε exp -|t| • L 1 ([x, x + εt] ∩ A) ε|t| dt ≤ 1 1 -α 1 -exp -(1 -α) η ε .
The other part of I ε (x) can be estimated simply by noticing that, for any t such that |t| ≥ η/ε, it holds that L 1 ([x, x + εt] ∩ A) ≥ L 1 ([x, x + η] ∩ A) > 0, the last inequality coming from the fact that x is a Lebesgue point of A. Therefore,

(27) 1 2 ˆIε(x)\[-η/ε,η/ε] e -L 1 ([x,x+εt]∩A) dt ≤ b -a 2ε exp - L 1 ([x, x + η] ∩ A) ε .
Using [START_REF] Monge | Mémoire sur la théorie des déblais et des remblais[END_REF] and [START_REF] Nenna | Numerical Methods for Multi-Marginal Optimal Transportation[END_REF] and sending ε to 0, we obtain

1 1 + α ≤ lim inf ε→0 I ε (x) ≤ lim sup ε→0 I ε (x) ≤ 1 1 -α
and since α > 0 is arbitrary, we conclude that -log I ε (x) → 0 for µ-a.e. x ∈ A.

To conclude the proof, we have to control -log I ε (x) by an µ-integrable function which does not depend on ε; here our assumption (H1) on the structure of the set A comes into play. Denote by

l(x) = min (x -a i ), (x -b i ) for x ∈ int(A ∩ supp µ), a i < x < b i .
Since A has negligible boundary, the function l is well-defined µ-a.e. on A. Let now x be a point of the interior of A and i such that a i < x < b i . We claim that Inequality (28) directly implies

I ε (x) ≤ 1 2 ˆIε(x) exp -|t| l(x) b -a dt ≤ b -a l(x)
and we also notice, by simply using the inequality L 1 ([x, x + εt] ∩ A) ≤ εt for any x, that I ε (x) is also always at least equal to 1, for any x. Therefore,

0 ≤ log I ε (x) ≤ log b -a l(x) .
The domination assumption is therefore satisfied as soon as ´A | log l(x)| dµ(x) < +∞, as it was stated in (H1). It remains to prove that (H1) holds as soon as (H1a) or (H1b) does. Let us write, for each i,

[a i , b i ] = [a i , α i ] + [α i , β i ] + [β i , b i ],
where

α i = min a i + 1, a i + b i 2 and β i = max b i -1, a i + b i 2 .
We then obtain, by controlling l(x) with b -a on each [α , β i ],

ˆA | log l(x)| dµ(x) = i ˆbi ai | log l(x)| dµ(x) ≤ i - ˆαi ai log(x -a i ) dµ(x) - ˆbi βi log(b i -x) dµ(x) + i | log(b -a)|µ([a i , b i ]).
The last term in ( 29) is exactly µ(A)| log(b -a)|, so it remains to control the two first terms. In case assumption (H1a) is true, we simply notice

0 ≤ - ˆαi ai log(x -a i ) dµ(x) ≤ -µ ∞(α i -a i ) log(α i -a i ) -1 ≤ µ ∞ b i -a i 2 1 + log b i -a i 2
and the same bound holds for the term ´bi βi | log(b i -x)| dµ(x) by exactly the same computation, leading to

ˆA | log l(x)| dµ(x) ≤ µ ∞L 1 (A ∩ supp µ) + | log(b -a)|µ(A) + i (b i -a i )| log(b i -a i )|,
which is finite by assumption (H1a). Assume now instead that (H1b) holds. We then use the inequality δtu ≤ u log u + e δt-1 and get

δ ˆαi ai | log(x -a i )|µ(x) dx ≤ ˆαi ai e -δ log(x-ai) dx + ˆαi ai log(µ(x))µ(x) dx = ˆαi ai 1 (x -a i ) δ dx + ˆαi ai log(µ(x))µ(x) dx = (α i -a i ) 1-δ 1 -δ + ˆαi ai log(µ(x))µ(x) dx.
Using a similar argument for the intervals β i , b i and then summing up we get

δ ˆA | log l(x)| dµ(x) ≤ 2 ˆA log(µ)µ dx + | log(b -a)|µ(A) + 2 1 -δ i (b i -a i ) 1-δ ,
concluding the proof.

An explicit form of the minimizer

In this section we will try to compute explicitly what plan we are selecting via the limit procedure, that is, the minimizer of F . Given the expression of F and the result of Proposition 3.1 on the structure of O 1 (µ, ν), it is enough to know, on each maximal interval I where F µ -F ν has constant sign, the minimizer of the entropy among all the plans γ such that y -x has good sign for γ-a.e. pairs (x, y).

In particular, for each j (and using the notation of subsection 3.4), this plan will be the minimizer, on the set Π(µ I, ν I), of the entropy with respect to the measure k = µ - j ⊗ ν - j •

1 y>x . This problem is well known in the literature (see, for example, [START_REF] Borwein | Entropy minimization, DAD problems, and doubly stochastic kernels[END_REF]), and the shape of the minimizer is known to be of the form a(x) ⊗ b(y) • k. The proof of [START_REF] Borwein | Entropy minimization, DAD problems, and doubly stochastic kernels[END_REF] relies on an abstract and general result of [START_REF] Borwein | Decomposition of multivariate functions[END_REF]: to be more precise the usual proof relies on the existence of maximizers in the dual problem if the entropy minimization has a finite value; then, using the duality relation, we can get that the minimizer has the special shape a(x) ⊗ b(y) • k.

We will provide a self-contained proof of this result, in a more suitable context for our needs: precisely, we prove the existence of a plan with this special shape, independently of the finiteness of the entropy (see Proposition 5.1 below), which we think is an interesting result itself. It would anyway be interesting to know when there exists a plan of the form a(x) ⊗ b(y) • k still when the entropy minimization problem is not finite, besides our case.

In Proposition 5.2 we then prove that the construction in Proposition 5.1 gives in fact the unique minimizer in the optimization problem, whenever its value is finite; here we in fact pass to the dual problem and we use the dual functions given by the particular shape found in Proposition 5.1.

Then, thanks to the explicit construction given in Proposition 5.1 we can state in Theorem 5.1 a necessary and sufficient condition in order to satisfy assumption (H2).

G • ρ 1 = µ F • ρ 2 = ν on I.
Moreover G and F are continuous and positive on (a, b), and the positive measure

γ 0 (x, y) := ρ 1 (x) ⊗ ρ 2 (y) • 1 y>x
is a transport plan between µ I and ν I.

Similarly, if I is a maximal negativity interval of F, there exist two positive measures ρ 1 , ρ 2 with densities such that

G • ρ 1 = µ, F • ρ 2 = ν,
where

F (y) = ρ 1 ([y, b]), G(x) = ρ 2 ([a, x]),
the functions G and F being continuous and positive on (a, b), and γ 0 (x, y) := ρ 1 (x) ⊗ ρ 2 (y) • 1 y<x belongs to Π(µ I, ν I).

Proof. We treat only the case where I is a maximal positivity interval of F and claim that the proof is similar for their negative counterpart. Denote by

G µ : x → µ([a, x]) = F µ (x) -F µ (a)
and define the function G ν in the same way; in particular, the assumption on F, a, b implies that

G µ > G ν on I and G µ (a) = G ν (a) = 0, G µ (b) = G ν (b) = µ(I).
On the other hand, the function F is continuous and strictly positive on the whole I; we can thus define an integral of µ/F on I and call it T . We then observe that µ/F ≥ µ/G µ so that we have, for any x 0 , x ∈ I and using that

D log G µ = µ/G µ , T (x 0 ) -T (x) = ˆx0 x 1 F dµ ≥ ˆx0 x 1 G µ dµ = log G µ (x 0 ) -log G µ (x).
In particular, since G µ (a) = 0 we have T (a) = -∞. Let us define x) and G : y ∈ I → F(y) F (y) .

F : x ∈ I → e T (
The observations above imply F (a) = 0. Similarly, G(b) = 0 and log(G) is a primitive of -ν/F. Finally, we define ρ 1 = DF and ρ 2 = -DG as derivative of BV loc functions (since they are increasing and locally bounded); notice by construction F and G are continuous, so ρ 1 and ρ 2 will have no atoms. Since T and F are BV loc without jump part, the chain rule holds:

ρ 1 = DF = De T = e T • DT = F • µ F = µ G .
In other words, we have G • ρ 1 = µ and we can prove the equality F • ρ 2 = ν in the same way. By construction F and G are continuous and nonnegative; moreover, F • G = F > 0 on I, so that neither F nor G may vanish on I. Define now γ 0 as in the statement of Proposition 5.1: it is then clear that, for any ϕ

∈ C b (R), ˆI×I ϕ(x) dγ 0 (x, y) = ˆI ϕ(x)G(x) dρ 1 (x) = ˆI ϕ(x) dµ(x)
and that, similarly, the second marginal of γ 0 is ν.

The next result proves that the transport plan γ 0 defined in Proposition 5.1 is actually the minimizer of the entropy among the transport plans on I 2 satisfying the corresponding sign constraint.

Proposition 5.2. Let µ, ν, ρ 1 , ρ 2 , I and γ 0 as in Proposition 5.1. Let Γ 0 be the set of optimal plans from µ I to ν I (that is, the set of γ ∈ Π(µ I, ν I) such that y -x > 0 for γa.e. (x, y)). Then we have

(29) min γ∈Γ0 Ent(γ|µ ⊗ ν) = Ent(γ 0 |µ ⊗ ν),
this equality also being true if both sides are +∞. Moreover, whenever Ent(γ 0 |µ ⊗ ν) < ∞, the only minimizer in (29) is γ 0 .

In the proof of Proposition 5.2 we will make use of the following lemma.

n (a) = ϕ n (k -b) ≤ ϕ n (k) + ϕ n (-b) = ϕ n (k) -ϕ n (b) ≤ k -ϕ n (b)
, where we used that ϕ n is odd and it is subadditive on the positive numbers. In order to conclude the proof of (30) we need to show that ϕ n (a) + ϕ n (b) ≤ 0 whenever a + b ≤ 0, but this is obvious from the fact that ϕ n is increasing and odd and in particular if a + b ≤ 0 we have a ≤ -b and so

ϕ n (a) + ϕ n (b) ≤ ϕ n (-b) + ϕ n (b) = 0.
In particular, using [START_REF] Trudinger | On the Monge mass transfer problem[END_REF] we immediately get Now we use that t log(t) -ct ≥ -e c-1 for any real numbers c, t; applying this with c = A(x) + B(y) + 1 and t = γ(x, y), we deduce [START_REF] Villani | Topics in Optimal Transportation[END_REF] Ent(γ|µ ⊗ ν) ≥ -ˆΩ e A(x)+B(y) dµ dν + ˆΩ(A(x) + B(y) + 1) dγ 0 (x, y).

Let now ϕ n be defined as in Lemma 5.1 and define

A n (x) := ϕ n (-log(G(y))) and B n (y) = ϕ n (-log(F (y))).

Equation ( 31) holds in particular with A n and B n instead of A and B, and we will estimate the two terms of the right-hand side from below by Ent(γ 0 |µ⊗ν) as n → +∞. By Lemma 5.1 we know that (A n (x) + B n (y)) + ≤ (-log G(x) -log F (y)) + and so e An(x)+Bn(y) ≤ max{1/G(x)F (y), 1}. Thus, by dominated convergence, we get ˆΩ e An+Bn dµ dν → ˆΩ 1 GF dµ dν = ˆΩ dγ 0 .

As for the second term of [START_REF] Villani | Topics in Optimal Transportation[END_REF], it is clear that (-log G(x) -log(F (y)) -∈ L 1 (γ 0 ) since ˆΩ(log(G) -log(F )) -dγ 0 = ˆΩ log 1 GF - 1 GF dµ ⊗ ν ≤ ˆΩ e -1 dµ ⊗ ν < ∞.

In particular using again Lemma 5.1 we get ˆΩ(A n (x) + B n (y) + 1) dγ 0 → ˆΩ log 1 F (y)G(x) + 1 dγ 0 .

So, putting all the estimates together and using dγ 0 d(µ ⊗ ν) = 1 G(x)F (y)

, we obtain Ent(γ (I × I)|µ ⊗ ν) ≥ -ˆΩ e An(x)+Bn(y) dx dy + ˆ(A n (x) + B n (y) + 1) dγ 0 (x, y)

→ -ˆΩ dγ 0 + ˆΩ log dγ 0 dµ ⊗ ν + 1 dγ 0 = Ent(γ 0 |µ ⊗ ν),
proving that γ 0 minimizes Ent(•|µ ⊗ ν) on Γ 0 . As for the uniqueness it is sufficient to observe that Γ 0 is a linear space and Ent(•|µ ⊗ ν) is strictly convex.

We can now prove the following result, which expresses exactly when the above assumption (H2) holds depending on the cumulative distribution functions F µ , F ν . Theorem 5.1. Let µ, ν be two probability measures on R, compactly supported and absolutely continuous with respect to the Lebesgue measure. Let F = F µ -F ν , where F µ , F ν are the cumulative distribution functions of µ, ν, and A + , A -as in Section 3. Then a necessary and sufficient condition for assumption (H2) is

- ˆA+ ∪A - log |F(x)| dµ(x) < +∞
and in that case, the minimal entropy among the elements of O 1 (µ, ν) is reached by the plan γ which coincides with the identity map on A × A and, on each square I 2 where I is a maximal positivity (resp., negativity) interval of F, is equal to the γ 0 defined by Proposition 5.2. Moreover, for any such interval I, we have Proof. Let I be a maximal positivity interval of F (the set where F is negative being treated in a similar way). We first notice that, thanks to Proposition 3.1(b) we have that γ I 2 = γ I×R = γ R×I and so it is an (optimal) plan between µ I and ν I . Then we can deduce from Proposition 5.2 that the minimal entropy of γ I 2 among the elements of O 1 (µ, ν) is reached by γ 0 , even if it is +∞; so it is sufficient to prove that equality [START_REF] Villani | Optimal Transport: Old and New[END_REF] holds, even when one of the two sides is not finite. Let us assume, for simplicity, that I = (0, 1). Then by definition Ent(γ 0 |µ ⊗ ν) = -ˆ1 0 ˆ1 x log(G(x)F (y)) dρ 2 (y) dρ 1 (x).

We can split the logarithm in the inner integral since G(x) is constant and use the definition of F, G and the results from where we used F (x) • G(x) = F(x) and in the last passage G • ρ 1 = µ, proving the desired equality [START_REF] Villani | Optimal Transport: Old and New[END_REF].

)

  Let now γ be a transport plan from µ to ν satisfying conditions (a)-(c) of Proposition 3.1. Then we have ˆ|y -x| dγ(x, y) = ˆA×R |y -x| dγ(x, y) x| dγ(x, y) + k ˆI+ k ×R |y -x| dγ(x, y).

4. Γ-convergence result 4 . 1 .Theorem 4 . 1 .

 4141 Statement of the main theorem. Having at hand the notation of the previous section and of Proposition 3.1, we can now state the main result of this paper. Let µ, ν ∈ P(R) be two probability measures with bounded support such that Ent(µ|L 1 ), Ent(ν|L 1 ) < ∞; in particular they are absolutely continuous with respect to the Lebesgue measure. Assume that the following assumptions are true.(H1) The set A ∩ supp µ has a Lebesgue-negligible boundary, and its interior has the formint(A ∩ supp µ) = i (a i , b i )

  Denoting by f A (x, y) := min{µ A (x), µ A (y)} log(min{µ A (x), µ A (y)}) and g(x) = µ A (x) log(µ A (x)), we claim that (20) ¨fA (x, y) e -|y-x|/ε 2ε dx dy ---→ ε→0 ˆR g(x) dx.

( 28 )

 28 for any y ∈ I, L 1 ([x, y] ∩ A) ≥ |y -x| (b -a) l(x). Indeed, this inequality is clearly true if y ∈ (a i , b i ), since this implies L 1 ([x, y] ∩ A) = |y -x| and since l(x) < b -a; on the other hand, if y > b i for instance, then L 1 ([x, y] ∩ A) ≥ (b i -x) ≥ l(x), and since y and x both belong to [a, b], yielding |y -x|/(b -a) ≥ 1.

Proposition 5 . 1 .

 51 Let µ, ν be two probability measures on R, compactly supported and with no atom, and denote by F = F µ -F ν (where F µ , F ν are the cumulative distribution functions of µ, ν, respectively). Let I = (a, b) be a maximal positivity interval for F, that is, F(a) = F(b) = 0 and F > 0 on I. Then there exist two nonnegative measures ρ 1 , ρ 2 on I such that, definingG(x) := ρ 2 ([x, b]) and F (y) := ρ 1 ([a, y])for any x, y ∈ I, we have

Lemma 5 . 1 .

 51 Let a, b two Borel functions defined on an open set Ω and let us consider a finite measure µ on Ω. Then, we have that ˆΩ(ϕ n (a) + ϕ n (b)) + dµ → ˆΩ(a + b) + dµ, ˆΩ(ϕ n (a) + ϕ n (b)) -dµ → ˆΩ(a + b) -dµ, where ϕ n (t) = max{-n, min{t, n}}. In particular, if either (a + b) -or (a + b) + is in L 1 (µ), we have also ˆΩ(ϕ n (a) + ϕ n (b)) dµ → ˆΩ(a + b) dµ. Proof. First we claim that (30) (ϕ n (a) + ϕ n (b)) + ≤ (a + b) + (and similarly (ϕ n (a) + ϕ n (b)) -≤ (a + b) -). If a, b > 0 this is obvious, so let us suppose a > 0 and b < 0, with a + b = k > 0 then a = k -b and so ϕ

  n (a) + ϕ n (b)) + dµ ≤ ˆΩ(a + b) + dµ, while, since lim n→∞ (ϕ n (a) + ϕ n (b)) + = (a + b) + , by Fatou's lemma we have lim inf n→∞ ˆΩ(ϕ n (a) + ϕ n (b)) + dµ ≥ ˆΩ(a + b) + dµ, thus giving us that ´(ϕ n (a) + ϕ n (b)) + → ´(a + b) + . We deal with the negative part in the same way. Proof or Proposition 5.2. Again we only will deal with an interval I where F is positive. Assume that Ent(•|µ ⊗ ν) is not identically +∞ on Γ 0 and let γ ∈ Γ 0 having finite entropy; with a slight abuse of notation, we will also denote by γ(x, y) the density of the plan γ with respect to µ ⊗ ν. Let us denote Ω = I × I ∩ {y > x}; we know that for every bounded measurable couple of functions A, B : I → R, we have Ent(γ|µ ⊗ ν) = ˆΩ γ log(γ) -(A(x) + B(y))γ -γ dµ(x) dν(y) + ˆΩ(A + B + 1) dγ 0 .

( 32 )

 32 Ent(γ 0 I 2 |µ ⊗ ν) = -ˆI log |F(x)| dµ(x) -µ(I).

1 F

 1 Proposition 5.1 to get Ent(γ 0 |µ ⊗ ν) = ˆ1 0 -log(G(x))G(x) + ˆ1 x log(F (y)) dρ 2 (y) dρ 1 (x).Since -ρ 2 = DG we can use integration by parts in order to get ˆ1 x log(F (y)) dDG(y) dy= G(y) log(F (y) dDF = -G(x) log F (x) -ˆ1 x dµ(y) F (y) ,where we used that G(y) log F (y) → 0 for y → 1. This is true since for y sufficiently close to 1 we have F(y) < 1 and so in particular F (1/2) ≤ F (y) = F(y)/G(y) ≤ 1/G(y). In particular, using G(y) → 0 as y → 1 we get0 = lim y→1 G(y) log(F (1/2)) ≤ lim y→1 G(y) log(F (y)) ≤ lim y→1 -G(y) log(G(y)) = 0.Now for any nonnegative measure η in (0, 1) we have that ´1 0 f (x) ´1 x dη(y) F (y) dx = η(0, 1): it is true by integration by parts for any measure compactly supported in (0, 1), and then we reach every measure by an approximation argument. We use this to get Ent(γ 0 |µ ⊗ ν) = ˆ1 0 -log(G(x))G(x) -log(F (x))G(x) -ˆ1 x dµ -µ(I),

  Let ρ be a fixed positive measure on R d , d ≥ 1. Then the functional Ent(•|ρ) is strictly convex, and it is lower semicontinuous with respect to the narrow convergence of measures.

	Definition 2.1. Let ρ be a fixed positive measure on R d , d ≥ 1. For any positive measure γ on
	R d , we set	Ent(γ|ρ) :=	 	ˆlog	dγ dρ	dγ if γ	ρ,
				+∞		otherwise,
	and the functional Ent(•|ρ) is called relative entropy with respect to ρ.
	The following properties of the functional Ent are classical (see, for instance, [2, Theo-
	rem 2.34]).
	Proposition 2.2.

Acknowledgements. This work has been mostly developed while the first author was visiting INRIA-Paris, supported by the FSMP Distinguished Professor Program. Both authors wish to thank the anonymous referees for helpful suggestions which allowed to substantially improve several proofs, and in particular for pointing out the references [9,10] and the links with our work.