{'fraction_non_alphanumeric': 0.05499840306611306, 'fraction_numerical': 0.01775790482274034, 'mean_word_length': 3.5583054301936237, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 16, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the local structure of optimal measures in the multi-marginal optimal transportation problem

We consider an optimal transportation problem with more than two marginals. We use a family of semi-Riemannian metrics derived from the mixed, second order partial derivatives of the cost function to provide upper bounds for the dimension of the support of the solution.


Introduction
The optimal transportation problem (with two marginals) asks what is the most efficient way to transform one distribution of mass to another relative to a given cost function. The problem was originally posed by Monge in 1781 [19]. In 1942, Kantorovich proposed a relaxed version of the problem [11]; roughly speaking, he allowed a piece of mass to be split between two or more target points. Since then, these problems have been studied extensively by many authors and have found applications in such diverse fields as geometry, fluid mechanics, statistics, economics, shape recognition, inequalities, meteorology, etc. [12]. Although this theorem holds for general cost functions, it alone says little about the structure of the optimal measure; the proofs of each of the aforementioned results rely heavily on the special forms of the cost.
The support of γ, which we will denote by spt(γ), is defined as the smallest closed subset of M 1 × M 2 × ... × M m of full mass. It is natural to ask what this set looks like. When m = 2 and the cost function satisfies a twist condition, the solution γ is unique and is contained in the graph of a function from M 1 to M 2 , provided the first marginal is suitably regular; this function then solves the original problem posed by Monge [15] [7][1] [8] [2]. Assuming M 1 and M 2 are both C 2 smooth manifolds of common dimension n, the present author, together with McCann and Warren, has shown that under a related non-degeneracy condition on c, spt(γ) must be contained in an n-dimensional Lipschitz submanifold of M 1 × M 2 [17]. For a general m, there is an immediate lower bound on the Hausdorff dimension of spt(γ); as spt(γ) projects to spt(µ i ) for all i, dim(spt(γ)) ≥ max i (dim(spt(µ i ))). In the present manuscript, we establish an upper bound on dim(spt(γ)). This bound depends on the cost function; however, it will always be greater than the largest of the n i 's. In the case when the n i 's are equal to some common value n, we identify conditions on c that ensure our bound will be n and we show by example that when these conditions are violated, the solution may be supported on a higher dimensional submanifold and may not be unique. In fact, the costs in these examples satisfy naive multimarginal extensions of both the twist and non-degeneracy conditions; given the aforementioned results in the two marginal case, we found it surprising that higher dimensional solutions can exist for twisted, non-degenerate costs. On the other hand, if the support of at least one of the measures µ i has Hausdorff dimension n, the remarks above imply that spt(γ) must be at least n dimensional; therefore, in cases where our upper bound is n, the support is exactly n-dimensional, in which case we show it is actually n-rectifiable.
A striking development in the theory of optimal transportation over the last 15 years has been its interplay with geometry. Recently, the insight that intrinsic properties of the solution γ, such as the regularity of Monge solutions, should not depend on the coordinates used to represent the spaces has been very fruitful. The natural conclusion is that understanding these properties is related to tensors, or coordinate independent quantities. The relevant tensors encode information about the way that the cost function and the manifolds interact. For example, Kim and McCann [13] introduced a pseudo-Riemannian form on the product space, derived from the mixed sec-ond order partial derivatives of the cost, whose sectional curvature is related to the regularity of Monge solutions; they also noted that smooth solutions must be timelike for this form.
Unlike the results of Gangbo andŚwiȩch, Heinich and Carlier, our contribution does not rely on a dual formulation of the Kantorovich problem; instead, our method uses an intuitive c-monotonicity condition to establish a geometrical framework for the problem. The question about the dimension of spt(γ) should certainly have a coordinate independent answer. Indeed, inspired partially by Kim and McCann, our condition is related to a family of semi-Riemannian metrics 1 ; heuristically, spt(γ) must be timelike for these metrics and so their signatures control its dimension. From this perspective, the major difference from the m = 2 case is that with two marginals, the metric of Kim and McCann always has signature (n, n). In the multimarginal case, there is an entire convex family of relevant metrics, generated by 2 m−1 − 1 extreme points, and their signatures may vary depending on the cost.
Like our work in [17] and in contrast to the results of Gangbo andŚwiȩch [9], Heinich [10], and Carlier [3], our results here only concern the local structure of the optimizer γ and cannot be easily used to assert uniqueness of γ or the existence of a solution to an appropriate Monge type problem. On the other hand, we do explicitly exhibit fairly innocuous looking cost functions which have high dimensional and non-unique solutions and so it is apparent that these questions cannot be resolved in the affirmative without imposing stronger conditions on c. We address these problems in a separate paper [21].
The manuscript is organized as follows: in Section 2, we prove our main result. In Section 3 we apply this result to several example cost functions; many of these are the costs studied by the authors mentioned above and we discuss how they fit into our framework. In Section 4, we discuss conditions that ensure the relevant metrics have only n timelike directions, which will ensure spt(γ) is at most n-dimensional. In Section 5, we discuss some applications of our main result to the two marginal problem and in the final section we take a closer look at the case when the marginals all have one dimensional support.
Acknowledgments: The author is indebted to his advisor Robert Mc-Cann, for originally suggesting this problem to him, for many fruitful discussions and for his continuous support. He would also like to thank the members of his PhD supervisory committee, Jim Colliander and Bob Jerrard, for providing constructive feedback, and Man-Duen Choi and Chandler Davis for useful discussions concerning the signatures of symmetric matrices.
2 Dimension of the support Before stating our main result, we must introduce some notation. Suppose that c ∈ C 2 (M 1 × M 2 × ... × M m ). Consider the set P of all partitions of the set {1, 2, 3, ..., m} into 2 disjoint, nonempty subsets; note that P has 2 m−1 −1 elements. For any partition p ∈ P , label the corresponding subsets p + and p − ; thus, p + ∪p − = {1, 2, 3, ..., m} and p + ∩p − is empty. For each p ∈ P , define the symmetric bi-linear form where, in accordance with the Einstein summation convention, summation on the α k and α j is implicit.
Definition 2.1. We will say that a subset S of M 1 × M 2 × ... × M m is c-monotone with respect to a partition p if for all y = (y 1 , y 2 , ..., y m ) and y = (ỹ 1 ,ỹ 2 , ...,ỹ m ) in S we have The following lemma, which is well known when m = 2, provides the link between c-monotonicity and optimal transportation. Lemma 2.2. Suppose γ is an optimizer and C(γ) < ∞. Then the support of γ is c-monotone with respect to every partition p ∈ P .
Proof. Define M p + = ⊗ i∈p + M i and M p − = ⊗ i∈p − M i . Note that we can identify M 1 × M 2 × ... × M m with M p + × M p − and let γ p + and γ p − be the projections of γ onto M p + and M p − respectively. Consider the two marginal problem where the infinum is taken over all measures λ whose projections onto M p + and M p − are γ p + and γ p − , respectively. Then γ is optimal for this problem and, as c is continuous, the result follows from c-monotonicity for two marginal problems; see for example [24].
We are now ready to state our main result: Theorem 2.3. Let g be a convex combination of the g p 's; that is g = p∈P t p g p where 0 ≤ t p ≤ 1 for all p ∈ P and p∈P t p = 1. Suppose γ is an optimizer and C(γ) < ∞; choose a point (x 1 , x 2 , ..., x m ) ∈ M 1 ×M 2 ×...×M m . Let N = m i=1 n i . Suppose the (+, −, 0) signature of g at (x 1 , x 2 , ..., x m ) is (q + , q − , N −q + −q − ) (ie, the corresponding matrix has q + positive eigenvalues, q − negative eigenvalues and a zero eigenvalue with multiplicity N − q + − q − ). Then there is a neighbourhood O of (x 1 , x 2 , ..., x m ) such that the intersection of the support of γ with O is contained in a Lipschitz submanifold of dimension N − q − . Wherever the support is smooth, it is non-spacelike for g.
Before we prove Theorem 2.3, a few remarks are in order. The roughly says that the dimension of spt(γ) is controlled by the signature of any convex combinations of the g p 's; as these metrics may have very different signatures, we are free to pick the one with the fewest timelike directions to give us the best upper bound on the dimension of spt(γ) for a particular cost. When m = 2, there is only one partition in P and consequently there is only one relevant metric, The matrix corresponding to this metric is the block matrix studied by Kim and McCann: Here D 2 x j x k c is the n j by n k matrix whose (α j , α k )th entry is For m > 2, in the remainder of this paper we will focus primarily on the special case when t p = 1 2 m−1 −1 for all p ∈ P . To distinguish it from the metrics obtained by other convex combinations of the g p 's, we will denote the corresponding metric by g. Note that the matrix of g in local coordinates is the block matrix given by Let us note, however, that other choices of the t p 's can give new and useful information. For example, suppose we take t p to be 1 for a particular p and 0 for all others. As in the proof of Lemma 2.2, we can identify In this case, G will take the form: The signature of this g is (r, r, N − 2r) where r is the rank of the matrix Letting n p ± = j∈p ± n j be the dimension of M p ± , we will have r ≤ min(n p + , n p − ). If it is possible to choose a partition so that n p + = n p − = N 2 and D 2 xp + xp − c has full rank, we can conclude that spt(γ) is at most N 2 dimensional. As we will see later, the number of timelike directions for g may be very large and so this bound may in fact be better. Our proof is an adaptation of our argument with McCann and Warren in [17]. When m = 2, after choosing appropriate coordinates, we rotated the coordinate system and showed that c-monotonicity implied that the solution was concentrated on a Lipschitz graph over the diagonal, a trick dating back to Minty [18]. When passing to the multi-marginal setting, however, it is not immediately clear how to choose coordinates that make an analogous rotation possible; unlike in the two marginal case, it is not possible in general to choose coordinates around a point ( The key to resolving this difficulty is the observation that Minty's trick amounts to diagonalizing the pseudometric of Kim and McCann and that this approach generalizes to m ≥ 3.
Let G be the matrix of g at x in our chosen coordinates. There exists some invertible N by N matrix U such that where the diagonal I, −I and 0 blocks have sizes determined by the signature of g.
Define new coordinates in O by u := Uy, where y = (y 1 , y 2 , ..., y m ) and let u = (u 1 , u 2 , u 3 ) be the obvious decomposition. We will show that the optimizer is locally contained in a Lipschitz graph in these coordinates.

Lemma 2.2 then implies
This implies that Hence, But this means With ∆u = U∆y and ∆u = (∆u 1 , ∆u 2 , ∆u 3 ) being the obvious decomposition, this becomes: where the last line follows because for each i and j we have Choosing ǫ sufficiently small, we have Rearranging yields Together with Kirzbraun's theorem, the above inequality implies that the support of γ is locally contained in a Lipschitz graph of u 1 over u 2 and u 3 .
If spt(γ) is differentiable at x, the non-spacelike implication follows from taking y = x in (1), then noting that we can take ǫ → 0 asỹ → x.

Examples
In this section we apply Theorem 2.3 to several cost functions. Throughout this section, the dimensions of the M i are all equal to some common n and we will restrict our attention to the special semi-Riemannian metric g defined in the last section.
this is the form of the cost function studied by Gangbo and Swiȩch [9] and Heinich [10] (actually Heinich made the slightly weaker assumption that h is strictly concave). Then, up to a positive, multiplicative constant, we have If v is an eigenvector of D 2 h with eigenvalue λ, then are linearly independent eigenvectors with eigenvalue −λ. It follows that the signature of g is ((m − 1)n, n, 0) and the solution is contained in an n dimensional submanifold; this is consistent with the results of Gangbo and Swiȩch and Heinich, who show that if the first marginal assigns measure zero to every set of Hausdorff dimension n − 1, then spt(γ) is contained in the graph of a function over x 1 .
Then the signature of g is (n, n(m − 1), 0). Furthermore, we can show that any measure supported on the n(m − 1) dimensional surface where y ∈ R n is any constant, is optimal for its marginals. Indeed, adding a function of the form m i=1 u i (x i ) to the cost c shifts the functional C(γ) by an amount m i=1 M i u i (x i )dµ i for each γ but does not change its minimizers. In particular, minimizing the cost c is equivalent to minimizing where f (z) := h(z) − z · Dh(y). Then f is a strictly convex function whose gradient vanishes at z = y; it follows that y is the unique minimum of f . Hence, c ′ (x 1 , x 2 , ..., x m ) ≤ f (y) with equality only when m i=1 x i = y. It follows that any measure supported on S is optimal for its marginals.
, but now suppose the signature of D 2 h is (q, n − q, 0). Then the signature of g is (q + (m − 1)(n − q), n − q + q(m − 1), 0), and in fact we will find an optimal measures whose support has dimension (n − q + q(m − 1)).
At a fixed point p, we can add an affine function of (x 1 + x 2 + ... + x m ) so that Dh(p) = 0 and choose variables so that where the top left hand corner block is q by q and the bottom left hand corner block is n − q by n − q. Then define the q-dimensional variables y i = ( . Now, near p, the implicit function theorem implies that for fixed z i , i = 1, 2, ..., m there is a unique If we consider an optimal transportation problem for the z i with cost f , the solution must be concentrated on a Lipschitz n − k dimensional submanifold. Choose an n − q dimensional set S which supports an optimizer for this problem; by considering a dual problem as in Gangbo and Swiȩch [9], we can find functions and we have equality only when (z 1 , z 2 , ...z m ) ∈ S and m i=1 y i = K( m i=1 z i ), which is a n − q + (m − 1)q dimensional set. It follows that this set is the support of an optimizer for appropriate marginals. 2. For all i, f i is C 2 and the matrix D 2 x i y f i of mixed, second order partials derivatives is everwhere non-singular 3. For each (x 1 , x 2 , ..., x m ) the infinum is attained by a unique y(x 1 , x 2 Fixing (x 1 , x 2 , ..., x m ), we can choose coordinates so that D 2 .., x m )) and note that as M is non-singular by assumption we must have M > 0.. The implicit function theorem now implies that y is differentiable with respect to each x j and: y)) with equality when y = y(x 1 , x 2 , ..., x m ) we have Differentiating with respect to x j yields D 2 x i x j c(x 1 , x 2 , ..., x m ) = D x i y f (x i , y(x 1 , x 2 , ..., x m ))D x j y(x 1 , x 2 , ..., x m ) = −M −1 for all i = j. Hence, the signature of g is ((m − 1)n, n, 0), by the same argument as in Example 1.
Example 3.5. The problem studied by Carlier and Nazaret in [5] is equivalent to the case where m = n and the cost function is the −1 times the determinant; ie, for x 1 , x 2 , , ..., x n ∈ R n , c(x 1 , x 2 , ..., x n ) is −1 times the determinant of the n by n matrix whose ith column is the vector x i . When n = 3, they exhibit a specific example where the solution has 4 dimensional support; specifically, it's support is the set We show that g has signature (5, 4, 0) on S. Choose (x 1 , x 2 , x 3 ) in the support; after applying a rotation we may assume x 1 = (|x 1 |, 0, 0), x 2 = (0, |x 1 |, 0) and x 3 = (0, 0, |x 1 |). A straightforward calculation then yields: There are 5 eigenvectors with eigenvalue 1: [010100000] T Finally, there is a single eigenvalue with eignenvector -2: [100010001] T Example 3.6. (Non-uniqueness) Our final example demonstrates that when the dimension of spt(γ) is larger than n, the solution may not be unique. Set m = 4 and c(x, y, z, w) = h(x + y + z + w) for h strictly convex. Suppose all four marginals µ i are Lebesgue measure on the unit cube I n in R n . Let S 1 be the surface y = −w + (1, 1, 1, ..., 1), z = −x + (1, 1, 1, ..., 1) and take γ 1 be uniform measure on the intersection of S 1 with I n × I n × I n × I n . This projects to µ i for i = 1, 2, 3 and 4 and by the argument in Example 2, it must be optimal. Now, if we take S 2 to be the surface y = −x + (1, 1, 1, ..., 1), z = −w + (1, 1, 1, ..., 1) and γ 2 be uniform measure on the intersection of S 2 with I n × I n × I n × I n , we obtain a second optimal measure.
It is worth noting that this cost is twisted: the maps x i → D x j c(x 1 , x 2 , ..x m ) are injective for all i = j where x k is held fixed for all k = i. In the two marginal case, the twist condition and mild regularity on the µ 1 suffices to imply the uniqueness of the solution γ [15]; this example demonstrates that this is no longer true for m ≥ 3.

The Signature of g
This section is devoted to developing some results about the signature of the semi-metric g = p∈P t p g p at some point x = (x 1 , x 2 , ..., x m ). Studying the signature at a point reduces to understanding the matrix Here, for i = j, G ij = a ij D 2 x i x j c where a ij = t p and the sum is over all partitions p ∈ P that separate i and j; that is, i ∈ p + and j ∈ p − or i ∈ p − and j ∈ p + . One observation about the signature of the matrix G is immediate; as G has zero blocks on the diagonal, it is possible to construct a lightlike subspace of dimension n max = max i {n i }. This in turn implies that the number of spacelike directions can be no greater than N − n max ; otherwise, it would be possible to construct a spacelike subspace of dimension N − n max + 1, which would have to intersect non trivially with the null subspace. Therefore, the best possible bound on the dimension of spt(γ) that Theorem 2.3 can provide is n max . This result is not too surprising. We have already noted that for suitable marginals, the Hausdorff dimension of spt(γ) must be at least n max ; the discussion above verifies that this is consistent with Theorem 2.3.
Throughout the remainder of this section we will assume the dimensions n i of the manifolds M i are all equal to some common n. Then G is an nm by nm matrix; however, we show here that because of its special form, its signature can be computed from lower dimensional data. For example, when m = 2 the signature will always be (n, n) and, as we will see, when m = 3 it is enough to calculate the signature of an appropriate n by n matrix. We will refer to the signature of g as (q + , q − , nm − q + − q − ) The first proposition gives an upper and lower bound for the number of timelike directions.
Proposition 4.1. Suppose rank(G ij ) = r for some i = j. Then q + , q − ≥ r. In particular, if G ij is invertible for some i = j, the support of γ is at most Note that (v, u) is a null vector if and only if u is in the null space of G ij and v is in the nullspace of G ji . As both of these spaces are n − r dimensional, the nullspace of this matrix is 2(n − r) dimensional. As has been noted by Kim and McCann [13], the nonzero eigenvalues of this matrix come in pairs of the form λ, −λ, with corresponding eigenvectors (v, u) and (v, −u), respectively, where we take λ ≥ 0 [13]. Therefore, there are 1 2 (2n − 2(n − r)) = r positive eigenvalues and as many negative ones. We can now construct a r dimensional timelike subspace for g. If q + < r, then we could construct a non-timelike subspace of dimension mn − q + > nm − r (for example, take the space spanned by all negative and null eigenvalues of G). These two spaces would have to intersect non trivially as their dimensions add to more than nm, which is a contradiction. An analagous argument applies to q − . Next, we describe the signature in the m = 3 case: Lemma 4.2. Suppose m = 3 and that the mixed second order partials are all G 12 , G 13 , and G 23 non-singular. Set A = G 12 (G 32 ) −1 G 31 ; suppose A+A T has signature (r + , r − , n − r + − r − ). Then g has signature (q + , q − , 3n − q + − q − ) = (n + r − , n + r + , n − r + − r − ).
Proof. By changing variables in x 2 and x 3 , we may assume G 12 = G 13 = I. In these coordinates, G 32 = A −1 . Consider the subspace By Proposition 4.1 we can find an orthonormal basis for this subspace consisting of n spacelike and n timelike directions. To determine the signature of g then, it suffices to consider the restriction ofg to the orthogonal complement (relative to g) S ⊥ of S; any orthonormal basis of S ⊥ can be concatenated with a basis for S to form an orthonormal basis for A simple calculation yields that which yields the desired result.
In particular, if A is negative definite, g has signature (2n, n, 0) and the support of any minimizer has dimension at most n.
A brief remark about Lemma 4.2 is in order. We mentioned in section 2 that, while there is only one interesting pseudo metric when m = 2, there is an entire family of metrics in the m ≥ 3 setting which may give new information about the behaviour of spt(γ). However, when m = 3, D 2 x i x j c is non singular for all i = j, and the coefficients a ij are all non zero, the signature of g is determined entirely by A = G 12 (G 32 ) −1 G 31 = a 12 a 31 a 32 D 2 Choosing a different g simply changes the a ij 's, which does not effect the signature of A + A T . If one of the a ij 's is zero, it is easy to check that the signature of g must be (n, n, n); this yields a bound of 2n on the dimension of sptγ which is no better than the bound obtained when all the a ij 's are non-zero. Thus, when m = 3 the only information about the dimension of spt(γ) which can be provided by Theorem 2.3 is encoded in the bi-linear form When m > 3, Lemma 4.2 easily yields the following necessary condition for the signature of G to be ((m − 1)n, n, 0): Corollary 4.3. Suppose the signature of g is ((m − 1)n, n, 0). Then for all distinct i, j and k.
Proof. Note that the G ij 's must be invertible (and hence D 2 x i x j c must be invertible and a ij > 0) ; otherwise, the argument in Proposition 4.1 implies the existence of a non-spacelike subspace of T x i M i × T x j M j whose dimension is greater than n. The signature of G ensures the existence of a (m − 1)n dimensional spacelike subspace, however, and so these two spaces would have to intersect non-trivially, a contradiction.
Similarly, if D 2 x k x i c was not negative definite, we could use Lemma 4.2 to construct a non-timelike subspace of T x i M i ×T x j M j ×T x k M k of dimension greater that n; this, in turn, would have to intersect our (m−1)n dimensional timelike subspace, which is again a contradiction.
The method in the proof above can be extended to give us a method to explicitly calculate the signature of g for larger m when a certain set of matrices are invertible.
For l = 2, 3, ..., m, let G l be the lower right hand corner ln by ln block of G: Lemma 4.4. Suppose G l has signature (q, ln−q, 0) Let G l ij be the i, jth block of the inverse of G l . and consider the n by n matrix i G l ij D 2 j,l+1 c. Suppose this matrix has signature (r + , r − , n − r + − r − ). Then the signature of G l+1 is (q + r − , ln − q + r + , n − r + − r − ).
For an algorithm to calculate the signature in the general case, start with the lower right hand two by two block, which has signature (n, n, 0). Use Lemma 4.4, or equivalently Lemma 4.2 to find the signature of the lower right hand three by three block. Then use Lemma 4.4 again to determine the signature of the lower right hand four by four block and so on. After m − 1 applications of Lemma 4.4 we obtain the signature of g.

Applications to the two marginal problem
Together with McCann and Warren, we proved in [17] that any solution to the two marginal problem was supported on an n-dimensional Lipschitz submanifold, provided the marginals both live on smooth n-dimensional manifolds and the cost is non-degenerate; that is, D 2 x 1 x 2 c(x 1 , x 2 ) seen as a map from T x 1 M 1 to T * x 2 M 2 is injective. Kim and McCann noted that in this case, the signature of g is (n, n, 0) [13], so Theorem 2.3 immediately implies this result. In fact, our analysis here is applicable to a larger class of two marginal problems.
Unfortunately, the topology of many important manifolds prohibits the non-degeneracy condition from holding everywhere. Suppose, for example, that M 1 = M 2 = S 1 , the unit circle. Then periodicity in x 1 of ∂c It follows that for every x 2 there is at least one x 1 such that ∂ 2 c ∂x 1 ∂x 2 (x 1 , x 2 ) = 0. In [17], we noted that under certain conditions the set where non-degeneracy fails is at most 2n − 1 dimensional, which yields an immediate upper bound on the dimension of spt(γ). We now use Theorem 2.3 to derive a better bound. To this end, suppose that we have two n dimensional manifolds and the non-degeneracy condition fails at some point (x 1 , x 2 ). If r is the rank of the map D 2 x 1 x 2 c(x 1 , x 2 ), then the signature of g at (x 1 , x 2 ) is (r, r, 2n − 2r). We conclude that locally spt(γ) is at most 2n−r dimensional. A global lower bound on r immediately yields an upper bound for the dimension of spt(γ) Next we consider a two marginal problem where the dimensions of the spaces fail to coincide; suppose the two manifolds M 1 and M 2 have dimensions n 1 and n 2 respectively, where n 2 ≤ n 1 . Again, let r be the rank of D 2 x 1 x 2 c; then g has signature (r, r, n 1 + n 2 − 2r). If D 2 x 1 x 2 c has full rank, ie, if r = n 2 then this reduces to (n 2 , n 2 , n 1 − n 2 ) and the solution may have as many as n 1 dimensions (in fact, if the support of the first marginal has Hausdorff dimension n 1 , then the Hausdorff dimension of spt(γ) must be exactly n 1 ). This result has a nice heuristic explanation. To solve the problem, one would first solve its dual problem, yielding two potential functions u 1 (x 1 ) and u 2 (x 2 ), and the solutions lies in the set where the first order condition Du 2 (x 2 ) = D x 2 c(x 1 , x 2 ) is satisfied. For a fixed x 2 , this is a level set of the function x 1 → D x 2 c(x 1 , x 2 ), which is generically n 1 − n 2 dimensional. Fixing x 2 and moving along this level set corresponds exactly to moving along the null directions of g. On the other hand, as x 2 varies, x 1 must vary in such a way so that the resulting tangent vectors are timelike. Hence, the solution may contain all the lightlike directions of g, which correspond to fixing x 2 and varying x 1 , plus n 2 timelike directions, which correspond to varying x 2 and with it x 1 .
6 The 1-dimensional case: coordinate independence and a new proof of Carlier's result In [3], Carlier studied a multi-marginal problem where all the measures were supported on the real line and proved that under a 2-monotonicity condition on the cost, the solution must be one dimensional. To the best of our knowledge, this is the only result about the multi-marginal problem proved to date that deals with a general class of cost functions. The purpose of this section is to expose the relationship between 2-monotonicity and the geometric framework developed in this paper. We will find an invariant form of this condition and provide a new and simpler proof of Carlier's result. We begin with a definition: Definition 6.1. We say c : R m → R is i, j strictly 2-monotone with sign ±1 and write sgn(c) ij = ±1 if for all x = (x 1 , x 2 , ..., x m ) ∈ R m and s, t > 0 we have where (e 1 , e 2 , ...e m ) is the canonical basis for R m .
In this notation, Carlier's 2-monotonicity condition is that sgn(c) ij = −1 for all i = j. This is not invariant under smooth changes of coordinates, however; the change of coordinates x i → −x i takes a cost with sgn(c) ij = −1 and transforms it to one with sgn(c) ij = 1. However, it is easy to check that the following condition is coordinate independent. Definition 6.2. We say c is compatible if, for all distinct i, j, k we have It is also easy to check that c is compatible if and only if there exist smooth changes of coordinates x i → y i = f i (x i ) for i = 1, 2, ..., m which transform c to a 2-monotone cost. Combined with Carlier's result, this observation implies that compatibility is sufficient to ensure that the support of any optimizer is 1-dimensional.
If the cost is C 2 , the condition We can think of the condition on the threefold products D 2 x 1 x 2 c(D 2 x 3 x 2 c) −1 D 2 x 3 x 1 c in Lemma 4.2 as a multi-dimensional, coordinate independent version of Carlier's condition. Corollary 4.3 demonstrates that this condition is necessary for g to have signature ((m − 1)n, n, 0) and, when m = 3, Lemma 4.2 shows that it is also sufficient. For m > 3, however, it is not sufficient even in one dimension. As a counterexample, consider the cost function which has signature (2, 2, 0) Thus, Theorem 2.3 implies neither Carlier's result nor the generalization above , at least if we restrict our attention to the special metric g. Below, we reconcile this by providing a new proof of Carlier's result, with the slightly stronger assumption d 2 c dx i dx j < 0 in place of 2-monotonicity. The crux of Carlier's argument is the following result: Theorem 6.3. Suppose d 2 c dx i dx j < 0 for all i = j . Then the projections of the support of the optimizer onto the planes spanned by x 1 and x j are non-decreasing subsets.
In view of the preceding remarks, this implies that when the cost has negative threefold products d 2 c dx i dx j ( d 2 c dx k dx j ) −1 d 2 c dx i dx k , the support is 1-dimensional. Carlier's proof relies heavily on duality. He shows that he can reduce the problem to a series of two marginal problems with costs derived from the solution to the dual problem. He then shows that these cost inherit monotonicity from c and hence their solutions are concentrated on monotone sets. We provide a simple proof that uses only the c-monotonicity of the support. In addition, our proof does not require any compactness assumptions on the supports of the measures. However, after establishing this result, it is not hard to show that, if the first measure is nonatomic, the support is concentrated on the graph of a function over x 1 .
Morally, our proof applies the non-spacelike conclusion of Theorem 2.3 to a well chosen semi-metric; however, because we don't know a priori that the optimizer is smooth we will prove the theorem directly from c-monotonicity.