11institutetext: Information Sciences Institute, University of Southern
California 11email<EMAIL_ADDRESS>22institutetext: Dept. of
Informatics, Pontificia Universidade Católica Rio de Janeiro
22email<EMAIL_ADDRESS>
# Commonsense Knowledge in Wikidata

Filip Ilievski 11 Pedro Szekely 11 Daniel Schwabe 22

###### Abstract

Wikidata and Wikipedia have been proven useful for reasoning in natural
language applications, like question answering or entity linking. Yet, no
existing work has studied the potential of Wikidata for commonsense reasoning.
This paper investigates whether Wikidata contains commonsense knowledge which
is complementary to existing commonsense sources. Starting from a definition
of common sense, we devise three guiding principles, and apply them to
generate a commonsense subgraph of Wikidata (_Wikidata-CS_). Within our
approach, we map the relations of Wikidata to ConceptNet, which we also
leverage to integrate Wikidata-CS into an existing consolidated commonsense
graph. Our experiments reveal that: 1) albeit Wikidata-CS represents a small
portion of Wikidata, it is an indicator that Wikidata contains relevant
commonsense knowledge, which can be mapped to 15 ConceptNet relations; 2) the
overlap between Wikidata-CS and other commonsense sources is low, motivating
the value of knowledge integration; 3) Wikidata-CS has been evolving over time
at a slightly slower rate compared to the overall Wikidata, indicating a
possible lack of focus on commonsense knowledge. Based on these findings, we
propose three recommended actions to improve the coverage and quality of
Wikidata-CS further.

###### Keywords:

Commonsense Knowledge Wikidata Knowledge Graphs

##  1 Introduction

Common sense is “the basic ability to perceive, understand, and judge things
that are shared by nearly all people and can be reasonably expected of nearly
all people without need for debate” [10]. For instance, humans typically know
that the political opposition is an opposite of the government, that hunger
causes one to eat, and that if one walks in the rain one gets wet. Possessing
such commonsense knowledge is important for both humans and machines in order
to fill gaps in communication, and fulfill tasks such as entity recognition
and linking from text, question answering, and planning. Yet, understanding
common sense is difficult for machines. Even with the recent progress of
language models such as BERT [6] and GPT-2 [22], which have been able to
perform very well on a number of tasks with enough training,111For example:
https://leaderboard.allenai.org/socialiqa/submissions/public the correct
answer is often given for wrong reasons [8]. The utterances produced are
syntactically sound, but may lack plausibility. For instance, GPT-2
complements the following prompt ‘if you break a bottle that contains liquids,
some of the liquid will (other things being equal) probably…’ with ‘…wind up
300 meters away’ [18].

Commonsense graphs like ConceptNet [25] and ATOMIC [24] provide relevant
knowledge that can be used to enhance the ability of language models to reason
on downstream tasks. Unfortunately, these are largely incomplete, e.g., while
ConceptNet contains information that a barbecue can be located in a garage, it
is unable to infer that they are also common in other outdoor places, like
parks, nor it has information on the expectations from such an event.

According to [27], common knowledge graphs (KGs) derived from Wikipedia, such
as Wikidata [31] or YAGO4 [30], provide knowledge which is ‘often required to
achieve a deep understanding of both the low- and high-level concepts found in
language’. In addition, Wikipedia has been used by a large number of systems
for downstream reasoning tasks [11]. As the largest and highest-quality
structured counterpart of Wikipedia [9], Wikidata holds the promise of
containing useful commonsense knowledge. Yet, to our knowledge, no existing
work has studied the commonsense coverage of Wikidata.

In this paper, we investigate whether Wikidata contains commonsense knowledge
and whether that is complementary to existing commonsense knowledge graphs.
The contributions of the paper as as follows:  1. we formulate three key
principles for distinguishing commonsense knowledge from the remaining one in
Wikidata, starting from three key properties of commonsense knowledge and from
a survey of existing commonsense knowledge graphs (Section 3.1). These
principles dictate that commonsense knowledge concerns well-known concepts and
general-domain relations.  2. Based on these principles, we design and
implement computational steps to extract a commonsense subgraph from Wikidata
which we refer to as Wikidata-CS in the remainder of this paper (Section 3.2).
During these steps, we also map relations in Wikidata to relations in
ConceptNet.  3. We leverage this mapping to integrate Wikidata-CS into the
Commonsense Knowledge Graph (CSKG) [13], which already contains well-known
commonsense sources, such as ATOMIC and ConceptNet (Section 3.3).  4. We
perform quantitative and qualitative analysis of the resulting subgraph
(Section 4.1). In addition, we compute overlaps between Wikidata-CS and other
resources included in CSKG, including ConceptNet and WordNet (Section 4.2).
5. We perform the same experiments with three different versions of Wikidata
from 2017, 2018, and 2020, and compare the results (Section 4.3). This allows
us to quantify the evolution of commonsense knowledge in Wikidata over time.
6. In Section 5, we reflect on the findings from our experiments and propose
recommended actions for further inclusion of commonsense knowledge in
Wikidata.

##  2 Related Work

We review:  1. well-known commonsense KGs  2. prior works on reasoning with
Wikidata or Wikipedia over text  3. studies of completeness of Wikidata  .

Commonsense KGs such as ConceptNet and ATOMIC are popular and have been
utilized by downstream reasoners [17]. Lexical resources, like WordNet [19]
and FrameNet [1], capture commonsense knowledge about concepts and frames,
respectively. Moreover, sources like Visual Genome [15] which have been
originally proposed for a different purpose (image captioning and visual
recognition), have recently been recognized as sources of commonsense
knowledge. Commonsense knowledge can also be extracted from documents [29,
20], query logs [23], or quantities [7]. A recent resource, called the
Commonsense Knowledge Graph [13], consolidates many of these resources into a
single KG. The complementarity of these sources motivates their integration,
but also reveals that they are still largely incomplete. Wikidata, as one of
the richest public KGs, holds a promise to enrich the set of recorded
commonsense facts even further.

A recent idea is to use language models, like BERT [6] and GPT-2 [22], as
knowledge bases, due to their inherent ability to produce a fact for any input
prompt. Still, they often exhibit shallow understanding of the world [8].
Integration with KGs like Wikidata or ConceptNet may increase their robustness
[17].

Reasoning with Wikipedia and Wikidata Wikipedia and Wikidata serve as sources
of background knowledge in natural language processing tasks [11], e.g., as a
repository of entities to link to, or as a source of contextual information to
help linking entities in text [21, 3, 5]. The work by Suh et al. [28] attempts
to extract commonsense knowledge from Wikipedia. As far as we are aware, there
is no comprehensive proposal to extract commonsense knowledge from Wikipedia
or Wikidata, or to study their strengths and weaknesses for this purpose.

Studies of completeness of Wikidata Several papers study the completeness of
Wikidata [4, 2, 16]. Luggen et al. [16] provide an approach to estimate class
completeness in knowledge graphs, and use Wikidata as a use case. They note
that some classes in Wikidata, like Painting, are more complete than others,
such as Mountain. In addition, they also quantify the evolution of Wikidata
over time. Similarly, we also study the completeness of Wikidata and its
richness over time, albeit focusing on its coverage of commonsense knowledge.

##  3 Extraction of Commonsense Knowledge from Wikidata

###  3.1 Principles of commonsense knowledge

Common sense is “the basic ability to perceive, understand, and judge things
that are shared by nearly all people and can be reasonably expected of nearly
all people without need for debate” [10]. From this definition, we can infer
that commonsense knowledge: 1) concerns conceptual rather than instance-based
information; 2) is primarily about commonly known observations; 3) targets
general-domain information. We expand these three aspects into three guiding
principles for our approach, which would allow us to define a commonsense
subset of the knowledge in a general KG such as Wikidata.

  1. P1

Concepts, not entities The primary principle of commonsense knowledge draws on
the distinction between concept- and named-entity-level (instance) knowledge.
Generally speaking, most concept-level knowledge is common sense, whereas most
named-entity-level knowledge is not. The fact that _houses_ have _rooms_ is
commonsense knowledge, as it common and widely applicable; the fact that the
_Versailles Palace_ has _700 rooms_ is not, as it concerns a particular
instance and cannot be expected by most people. Thus, principle P1 is that
commonsense knowledge has to be about concepts.

  2. P2

Commonness The second principle (P2) of commonsense knowledge is its
‘commonness’: it is knowledge about well-known concepts that is shared among
most human beings. The fact that a _container_ (Q987767) is used for _storage_
(Q9158768) is a common fact, whereas the fact that _noma_ (Q994794) is a
subclass of _aphthous stomatitis_ (Q189956) is fairly unknown.

  3. P3

General-domain knowledge The third principle is that commonsense knowledge is
about general-domain information rather than expert knowledge about a specific
domain like chemistry or biology. Notably, even within a knowledge type, some
relations describe general information, whereas others require expert
knowledge. For instance, considering meronymy relations, we observe that _part
of_ describes well-known facts (e.g., wheel is part of a car), whereas _cell
component_ focuses on biological knowledge (e.g., _cholesterol_ has component
_cell membrane_). As a third principle (P3), we aim to distinguish between
domain-specific and general-domain knowledge.

###  3.2 Approach

Next, we apply P1-P3 to select commonsense knowledge from Wikidata.

1\. Excluding named entities (P1) In practice, Wikidata does not make a clear
distinction between concepts and named instances through its structured
knowledge. The relation instance of (P31) would intuitively be useful for
this; yet, it often expresses an is-a relation between concepts, similar to
subclass of (P279). For instance, Wikidata states that surgeon is an instance
of medical profession, and a subclass of medical specialist. Leveraging the
rdf:type relation from another public ontology, such as DBpedia, is a possible
direction, yet this strategy would be limited to the set of nodes that are
mapped between Wikidata and DBpedia. Hence, we follow a different route. The
convention of Wikidata stipulates that the labels of named entities should be
capitalized, whereas the ones for concepts should
not.222https://www.wikidata.org/wiki/Help:Label Following this rule, we employ
a simple heuristic of selecting edges where both nodes have alphanumeric
labels starting with a lowercase letter. We expand this rule and filter out
labels that contain any capital letter, to remove entities with labels like
“graf Nikolai Aleksyeevich Sheremetev”. This procedure implicitly excludes
nodes without English labels.

Table 1: Number of edges and representative examples for the top 20 relations. Relation | #edges | Examples
---|---|---
subclass of (P279) | 172,535 | saxophone - woodwind instrument
instance of (P31) | 141,499 | happiness - positive emotion
part of (P361) | 9,118 | shower - bathroom
different from (P1889) | 7,767 | vein - artery
has part (P527) | 6,252 | senses - touch
cell component (P681) | 5,607 | cholesterol - cell membrane
property constraint (P2302) | 5,180 | votes received - integer constraint
facet of (P1269) | 4,792 | wind - weather
strand orientation (P2548) | 4,345 | sac-1 - forward strand
use (P366) | 3,045 | crystal ball - psychic reading
opposite of (P461) | 3,028 | political opposition - government
properties for this type (P1963) | 2,382 | human - date of birth
molecular function (P680) | 2,369 | protein kinase - kinase activity
see also (P1659) | 2,344 | position held - member of
sport (P641) | 2,338 | head stand - gymnastics
followed by (P156) | 2,244 | middle school - secondary school
follows (P155) | 2,234 | queen - jack
material used (P186) | 2,047 | ice cream cone - wafer
is a list of (P360) | 1,914 | list of major opera composers - human
Wikidata property (P1687) | 1,746 | president - head of government

2\. Characterizing commonness (P2) We argued that commonsense facts concern
common concepts. Wikidata-based metrics of frequency or popularity, such as
PageRank, cannot be used to estimate commonness, as they inherit the bias
towards topics that are heavily represented in Wikidata (e.g., entertainment
or science). Instead, we approximate commonness by frequencies of word and
phrase usage that have been pre-computed over an independent corpus
[26].333https://pypi.org/project/wordfreq/ Here, we assume that frequently
occurring words and phrases refer to well-known concepts. According to this
tool, the frequency of a common word, like _storage_ , is much higher than
that of a relatively unknown word, such as _noma_ (3.39e-05 compared to
3.24e-07). We select edges where both the subject and the object labels have
usage frequency above an empirically determined threshold of $1e-06$.

Figure 1: Frequency distribution of the 50 most frequent remaining relations. For readability, we exclude P31 and P279, as these are much more populated than the rest. Table 2: Mapping of relations between Wikidata and ConceptNet. The Wikidata relations prefixed with ‘*’ are inverse to the relation in ConceptNet. Category | ConceptNet | Wikidata
---|---|---
distinctness | /r/DistinctFrom | different from (P1889)
antonymy | /r/Antonym | opposite of (P461)
synonymy | /r/Synonym | said to be the same as (P460)
similarity | /r/SimilarTo | partially coincident with (P1382)
derivation | /r/DerivedFrom | named after (P138), fictional analog of (P1074)
inheritance | /r/IsA | instance of (P31), subclass of (P279), subproperty of
|  | (P1647)
meronymy | /r/PartOf | part of (P361), *has part (P527), *has parts of the
|  | class (P2670)
material | /r/MadeOf | material used (P186), is a list of (P360), *has list
|  | (P2354)
attribution | /r/CreatedBy | *product or material produced (P1056)
utility | /r/UsedFor | use (P366), *uses (P2283), used by (P1535)
properties | /r/HasProperty | color (P462), has quality (P1552), properties of this
|  | type (P1963), Wikidata property (P1687), sex or
|  | gender (P21)
causation | /r/Causes | *has cause (P828), has effect (P1542), symptoms
|  | (P780)
ordering | /r/HasPrerequisite | *followed by (P156), follows (P155)
context | /r/HasContext | facet of (P1269), field of this occupation (P425),
|  | health specialty (P1995), main subject (P921),
|  | competition class (P2094), genre (P136), studied
|  | by (P2579), field of work (P101), afflicts (P689),
|  | *practiced by (P3095), depicts (P180), sport (P641)
other | /r/RelatedTo | see also (P1659), subject item of this property
|  | (P1629)

3\. Excluding domain knowledge (P3) The initial two steps yield 420,822 edges,
involving 414 edge types and describing 194,595 nodes. Table 1 presents the
number of occurrences for the 20 most frequent edge types, together with a
representative example edge for each type. By analyzing the frequency
distribution of the remaining relations, we observe that the frequency quickly
decays. The 50th most common relation describes less than 500 edges, and their
frequency plot becomes relatively flat (Figure 1). Hence, we focus on the 50
most frequent relations and distinguish the remaining knowledge by manually
mapping them to relations in ConceptNet
v5.7.444https://github.com/commonsense/conceptnet5/wiki/Downloads These
account for 409,775 edges, which is 97.4% of the total set of edges available
at this point.555In the future, we intend to consolidate the remaining
statements of Wikidata by mapping them to ConceptNet relations as well.

The main guideline for this mapping was to exclude properties which are meant
to describe domain-specific information, such as strand orientation (P2548).
The mapping was performed independently by two authors of this paper. In all
cases, the annotators agreed on whether the relation describes general-domain
knowledge. In 9 cases, the annotators disagreed on which ConceptNet relation
is the most appropriate to map to. Typically, this meant that ConceptNet lacks
a relation with the same specificity, forcing the annotators to opt for a more
generic relation, such as /r/HasContext. The disagreements were resolved
through a joint discussion and examination of exemplar edges in Wikidata.

The resulting mappings are shown in Table 2. 44 out of the top 50 relations
were mapped to existing relations in ConceptNet, yielding 388,250 edges. The
remaining six relations are either biology domain-specific: cell component
(P681), strand orientation (P2548), molecular function (P680), biological
process (P682); physical domain-specific: decays to (P816); or ontological:
property constraint (P2302). The mapping shows that some ConceptNet properties
(e.g., /r/Antonym) have a single counterpart in Wikidata (opposite of), while
others (e.g., /r/HasContext) map to several properties, often with more
specific meanings (e.g., genre, sport). This might reveal an opportunity to
enrich the specificity of relations in ConceptNet with more detailed ones as
in Wikidata.666For some ConceptNet relations, like /r/PartOf and
/r/HasProperty, a similar proposal to add detail comes from WebChild [29].
Some relations in ConceptNet (e.g., /r/MotivatedByGoal) may have no
counterpart in Wikidata, and others map to a relation which is very sparse for
common concepts. For instance, /r/AtLocation maps to location, which is well-
populated for named entities in Wikidata, but only ranks 72nd with 159
occurrences in our commonsense subset. These observations reveal a knowledge
gap in Wikidata. In several cases, the relation in Wikidata is inverse to that
in ConceptNet, e.g., has part to /r/PartOf and has cause to /r/Causes. We
analyze the overlap between ConceptNet and Wikidata further in Section 4.2.

Finally, assuming that domain-specific relations involve domain-specific
nodes, we construct a set of ‘blacklist’ nodes found in these relations. We
ensure that the remaining edges do not contain these domain-specific nodes.
This allows us to filter out nodes like protein (Q8054), which has over 172
thousand incoming edges, typically from child proteins.

###  3.3 Integration in the Commonsense Knowledge Graph

The Commonsense Knowledge Graph (CSKG) [13] is an existing resource that
consolidates information from seven commonsense sources, including ConceptNet,
Roget [14], Visual Genome [15], WordNet [19], and Wikidata. It is represented
using the KGTK [12] format with 10 columns, including the core elements of an
edge (id, node1, relation, and node2), their labels (e.g., node1;label, and
provenance information about an edge (source and sentence). Regarding
Wikidata, CSKG includes all the edges involving the inheritance (P279)
relation.

We integrate the commonsense subset of Wikidata presented in this paper into
CSKG. For this purpose, we adapt its columns to match those specified by CSKG.
The columns for which we lack information, such as sentence, are left empty.
We map the 50 most frequent relations to ConceptNet relations following Table
2, and discard the small number of remaining statements.

###  3.4 Implementation

We implement the proposed selection of commonsense knowledge from Wikidata by
using the Knowledge Graph ToolKit (KGTK) [12]. KGTK allows us to carry out the
proposed approach in a direct and simple way, despite the challenging size and
complexity of Wikidata. The full experiment reported in this paper is coded as
three Jupyter Notebooks which run on a laptop in under an
hour.777https://github.com/usc-isi-i2/cskg/tree/master/wikidata The starting
point is the entire Wikidata split into three Wikidata files in KGTK tabular
format (an edge file, a node file, and a qualifiers file), as pre-computed
with the _import-wikidata_ command.

The concrete steps are as follows. We use a customized Python function to
create a subset of the node file that contains only concept nodes, by removing
nodes whose labels are either empty or contain a capital letter. We use the
_ifexists_ join operator to filter out edges that do not connect two concepts
from the edge file.The command _remove-columns_ trims all columns which are
not necessary for the experiment. After this, we run _compact_ to remove
duplicate edges. At this point, we have a subset of edges that are about
concepts (P1). To prepare for the usage filtering and help human readability,
we expand the set of columns with the _lift_ command to include the labels of
the subject, the object, and the relation. We use the aforementioned
threshold-based filter to select edges for which both the subject and the
object are common concepts. Next, we inspect the remaining edges in terms of
their relations. We apply the manual mapping of the top 50 relations (Section
3.2) to consolidate the remaining Wikidata graph and make its edge types
compatible with the format of CSKG.

These steps produce the subset of Wikidata (Wikidata-CS), which satisfies our
principles (P1-P3), in the CSKG format. Finally, we use _graph-statistics_ to
compute metrics over this subset. Wikidata-CS is available for
download.888https://doi.org/10.5281/zenodo.3983029

##  4 Analysis

###  4.1 General Statistics

Wikidata-CS consists of 71,243 nodes and 106,103 edges. It uses 44 edge types
to describe these edges. The mean node degree is 2.98, which is higher than in
the subclass of subset of Wikidata (2.45) [13]. The nodes with the highest
PageRank in the resulting graph are: _artificial entity_ (Q16686448),
_kinship_ (Q171318), and _class_ (Q16889133), which are more customary
compared to the top nodes in the unfiltered subclass-of data, all of which
describe biochemical concepts [13].

Table 3: Comparison of the size of Wikidata-CS to commonsense sources in CSKG. | ATOMIC | Concept | Frame | Roget | Visual | Word | Wikidata-CS
---|---|---|---|---|---|---|---
|  | Net | Net |  | Genome | Net | (this paper)
# nodes | 304,909 | 1,787,373 | 36,582 | 71,804 | 10,830 | 91,294 | 71,243
# edges | 732,723 | 3,423,004 | 79,060 | 1,403,461 | 2,218,868 | 111,276 | 106,103

The five most frequent relations in Wikidata-CS are: subclass of (P279),
instance of (P31), different from (P1889), part of (P361), and has part
(P527). The first two account for 68.8% of all edges, indicating the the
commonsense knowledge in Wikidata mostly concerns taxonomic information. After
mapping the relations to ConceptNet, all commonsense knowledge corresponds to
15 edge types. We perform de-duplication to consolidate edges that were
expressed with relations of the same group (e.g., subclass of and instance
of), or in two directions with inverse properties (e.g., has cause and has
effect). The distribution of knowledge across these types is shown in Table 4
(last column). The final set has 101,771 edges, which is below 0.01% of the
full Wikidata. Next, we compare the content and size of Wikidata-CS to those
of other commonsense KGs.

###  4.2 Comparison to other graphs in CSKG

The integration of Wikidata-CS into CSKG allows one to easily compare its
content to other sources, such as ConceptNet. How does the size of the
commonsense subset in Wikidata compare to that of the other sources? How much
of the commonsense knowledge in Wikidata is already present in these other
sources? How much is missing? Conversely: how many edges are defined in
ConceptNet or WordNet, but are lacking in Wikidata? We provide insight into
these questions.

Table 4: Temporal evolution of the Wikidata commonsense knowledge. | 2017-12-27 | 2018-12-10 | 2020-05-04
---|---|---|---
/r/IsA | 31,668 | 45,606 (144%) | 72,707 (230%)
/r/PartOf | 3,390 | 4,416 (130%) | 7,938 (234%)
/r/HasContext | 1,968 | 3,189 (162%) | 6,152 (313%)
/r/DistinctFrom | 782 | 2,011 (257%) | 4,934 (631%)
/r/HasPrerequisite | 413 | 1,965 (476%) | 4,131 (1,000%)
/r/UsedFor | 735 | 1,215 (165%) | 2,469 (336%)
/r/Antonym | 1,109 | 1,530 (138%) | 2,184 (197%)
/r/MadeOf | 415 | 834 (201%) | 1,426 (344%)
/r/Synonym | 478 | 655 (137%) | 1,070 (224%)
/r/HasProperty | 339 | 650 (192%) | 1,049 (309%)
/r/Causes | 150 | 238 (159%) | 651 (434%)
/r/DerivedFrom | 190 | 293 (154%) | 540 (284%)
/r/SimilarTo | 28 | 77 (275%) | 345 (1,232%)
/r/CreatedBy | 51 | 68 (133%) | 187 (367%)
/r/RelatedTo | 33 | 40 (121%) | 42 (127%)
edges (Wikidata-CS) | 41,769 | 62,787 (150%) | 101,771 (244%)
edges (Wikidata) | 405,081,219 | 696,605,955 (172%) | 1,105,944,515 (273%)
nodes (Wikidata-CS) | 32,620 | 47,056 | 71,243
nodes (Wikidata) | 42,187,222 | 53,004,762 | 84,601,621
Table 5: Overlap between Wikidata and other commonsense knowledge sources. Other source | Both | Wikidata-CS only | Other source only
---|---|---|---
ConceptNet | 2,386 | 97,473 (97.6%) | 3,320,935 (99.9%)
Roget | 299 | 99,560 (99.7%) | 1,403,162 (99.9%)
WordNet | 1,613 | 98,246 (98.4%) | 419,103 (99.6%)

Table 3 compares the size of Wikidata-CS with the other subgraphs within CSKG.
Despite the fact that Wikidata is by far the largest graph, its commonsense
subset ranks 6th in terms of edges and 5rd in terms of nodes, being only
larger than FrameNet and over 30 times smaller than ConceptNet.999To be fair,
the edge count of the other graphs may include edges with named entities
(e.g., through the /r/IsA relation), which were excluded in Wikidata-CS.  We
also inspect the overlap between the knowledge in Wikidata-CS and in other
CSKG sources that share the same relations. Since only the relations are
mapped between these sources, whereas the nodes are not, we assume equivalence
of two edges with identical subject labels, object labels, and edge types. The
results are given in Table 5. We observe that Wikidata-CS shares 2,386 edges
with ConceptNet, 1,613 with WordNet, and only 299 with Roget. Above all, this
investigation shows extremely little overlap between Wikidata-CS and the other
three graphs. The observation that commonsense knowledge in Wikidata is almost
entirely missing in the other KGs, and vice versa, validates the main pursuit
of this paper, and motivates the consolidation of these sources into a single
graph.

We note that, with this lexical overlap approach, an edge might be counted
multiple times if its nodes have multiple labels. This is why WordNet has over
500k edges in total in Table 5, while having little over 100k in the original
data. Future work should investigate more semantic overlap estimation methods.

###  4.3 Evolution of the Wikidata commonsense knowledge over time

The size of Wikidata has been growing at a tremendous rate. In only 30 months,
its number of edges nearly tripled and the number of nodes doubled (Table 4).
A natural question arises: has the size of its commonsense subset been growing
at a similar rate? To investigate this question, we consider three versions of
Wikidata, with dates: 2017-12-27, 2018-12-10, and 2020-05-04. For fair
comparison, we apply our approach (Section 3.2) on the three Wikidata dumps.

For each of the Wikidata dumps, we present the number of edges per relation in
Table 4. Firstly, while the number of edges in Wikidata-CS has multiplied for
nearly all relations (except RelatedTo), its growth is slightly slower than
the full Wikidata - 244% vs 273% between December 2017 and May 2020. A similar
trend holds for the December 2018 version. Hence, despite the apparent
interest in enriching the commonsense knowledge subset of Wikidata, this has
not been a priority so far. Secondly, we see larger growth of the relations
SimilarTo, HasPrerequisite, and DistinctFrom relative to the others. This
shows that certain commonsense aspects (like differentiating potentially
confusing concepts) may be more relevant to the Wikidata community and its
applications than others.

##  5 Discussion

The commonsense knowledge in Wikidata could benefit applications like question
answering or entity linking. For instance, let’s consider the following
true/false question from the CycIC
dataset:101010https://leaderboard.allenai.org/cycic/submissions/get-started
Suppose something is under the table. It is either a toaster or a correction
tape dispenser. You can tell that it isn’t a kitchen tool. True or False: The
thing under the table is a correction tape dispenser. The key implicit
knowledge in this example is the fact that the toaster is often found in the
kitchen, while the dispenser is not. Luckily, over 100k such commonsense facts
are part of our Wikidata-CS collection, and could help a downstream system to
reason over such questions.

Still, we noted that only a neglegible portion of Wikidata directly describes
commonsense knowledge today. Given the considerable community involved in
Wikidata and Wikipedia, and the commonsense relations identified in this
paper, we propose for the commonsense knowledge in Wikidata to be
substantially enriched in the near future. We discuss three actions towards
this goal:

1\. Integration of ready commonsense sources into Wikidata A number of
commonsense sources, like ConceptNet and ATOMIC, contain much complementary
knowledge that could be included into Wikidata (cf. Table 3). Our prior work
on consolidating their formats and modeling principles into CSKG enables their
seamless integration into Wikidata, when so desired. At present, CSKG contains
5.89 million edges, expressed through 58 relations. The mappings in Table 2
could be used as a starting point, whereas missing relations might need to be
added to Wikidata. Data licensing may be a a roadblock here.

2\. Generalizing over instance-level knowledge Much of the commonsense
knowledge in Wikidata is indirectly expressed through its instance-level
knowledge. While Barack Obama being born in Hawaii is not a commonsense fact,
the fact that humans have a birthplace is. Furthermore, all humans have a
single birthplace, i.e., it is a functional property. One could think of other
generalizations as well, e.g., if many locations belong to countries, it is
common sense thinking that any location would belong to a country. Such
commonsense information is not directly represented in Wikidata, yet it could
be inferred by statistical generalization over instance-level knowledge.

3\. Missing knowledge types The Wikidata model defines the notion of
qualifiers, which would be ideal to represent much commonsense knowledge.
However, in many cases, Wikidata does not only lack a commonsense fact, but
also the relation or the qualifier that would express it. For instance, while
many qualifiers (e.g., minimum and maximum value) express quantities, no
qualifier describes typical/expected
quantity.111111https://www.wikidata.org/wiki/Wikidata:List_of_properties/Wikidata_qualifier
This could express that spiders typically have eight legs, while chairs have
four. Qualifiers for expressing a purpose or a goal (e.g., one participates in
a competition in order to win) are also missing. Besides qualifiers, it might
be of use to include relations that are currently missing, like typical
properties of concepts (e.g., elephants are heavy), or their symbolism (e.g.,
red is a symbol of danger). The actual information could be extracted from
unstructured sources, like Wikipedia, or reused from previous extractions [7].

##  6 Conclusion

Wikidata has been growing tremendously in terms of both size and popularity.
Consequently, it has been attracting interest from applications that require
background knowledge in order to fill in gaps, such as question answering and
entity linking. In this paper, we studied the commonsense knowledge coverage
of Wikidata and its complementarity to existing commonsense graphs. Starting
from three key principles of commonsense, we devised a three-step filtering
approach that distinguishes concepts from named entities, favors common
concepts, and general-domain knowledge types. Here, we also created mappings
between the relations in the commonsense subset of Wikidata (Wikidata-CS) and
those in ConceptNet, which allowed us to integrate Wikidata-CS into CSKG, an
existing consolidated graph of commonsense knowledge. We analyzed the content
of Wikidata-CS and compared it to other existing sources, like ConceptNet and
WordNet, noting that while Wikidata contains useful and novel commonsense
knowledge that complements other sources, its coverage of commonsense
knowledge is currently largely incomplete. We propose three directions to
improve this in the future: by inclusion of the knowledge from the Commonsense
Knowledge Graph, by generalizing over existing instance-level knowledge in
Wikidata, and by inclusion of missing knowledge types that are relevant for
representing commonsense knowledge. In addition, subsequent research should
evaluate the quality of Wikidata-CS and its relevance for commonsense
reasoning, based on user studies and downstream tasks.

## Acknowledgements

We would like to thank _Daniel Garijo_ for the very helpful comments and
suggestions on drafts of this paper. We would also like to thank _Craig Milo
Rogers_ for his help with KGTK. We are grateful for the reviewer comments.
This material is based upon work sponsored by the DARPA MCS program under
Contract No. N660011924033 with the United States Office Of Naval Research and
by Air Force Research Laboratory under agreement number FA8750-20-2-10002.

## References

  * [1] Baker, C.F., Fillmore, C.J., Lowe, J.B.: The berkeley framenet project. In: 36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics, Volume 1. pp. 86–90 (1998)
  * [2] Balaraman, V., Razniewski, S., Nutt, W.: Recoin: relative completeness in wikidata. In: Companion Proceedings of the The Web Conference 2018. pp. 1787–1792 (2018)
  * [3] Cetoli, A., Bragaglia, S., O’Harney, A.D., Sloan, M., Akbari, M.: A neural approach to entity linking on wikidata. In: European Conference on Information Retrieval. pp. 78–86. Springer (2019)
  * [4] Darari, F., Prasojo, E., Razniewski, S., Nutt, W.: Cool-wd: A completeness tool for wikidata. CEUR-WS. org (2017)
  * [5] Delpeuch, A.: Opentapioca: Lightweight entity linking for wikidata. arXiv preprint arXiv:1904.09131 (2019)
  * [6] Devlin, J., Chang, M.W., Lee, K., Toutanova, K.: Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805 (2018)
  * [7] Elazar, Y., Mahabal, A., Ramachandran, D., Bedrax-Weiss, T., Roth, D.: How large are lions? inducing distributions over quantitative attributes. arXiv preprint arXiv:1906.01327 (2019)
  * [8] Ettinger, A.: What bert is not: Lessons from a new suite of psycholinguistic diagnostics for language models. Transactions of the Association for Computational Linguistics 8, 34–48 (2020)
  * [9] Färber, M., Ell, B., Menne, C., Rettinger, A.: A comparative survey of dbpedia, freebase, opencyc, wikidata, and yago. Semantic Web Journal 1(1), 1–5 (2015)
  * [10] Gunning, D.: Machine common sense concept paper. arXiv preprint arXiv:1810.07528 (2018)
  * [11] Hovy, E., Navigli, R., Ponzetto, S.P.: Collaboratively built semi-structured content and artificial intelligence: The story so far. Artificial Intelligence 194, 2–27 (2013)
  * [12] Ilievski, F., Garijo, D., Chalupsky, H., Divvala, N.T., Yao, Y., Rogers, C., Li, R., Liu, J., Singh, A., Schwabe, D., et al.: Kgtk: A toolkit for large knowledge graph manipulation and analysis. arXiv preprint arXiv:2006.00088 (2020)
  * [13] Ilievski, F., Szekely, P., Cheng, J., Zhang, F., Qasemi, E.: Consolidating commonsense knowledge. arXiv preprint arXiv:2006.06114 (2020)
  * [14] Kipfer, B.: Roget’s 21st century thesaurus in dictionary form (éd. 3). new york: The philip lief group (2005)
  * [15] Krishna, R., Zhu, Y., Groth, O., Johnson, J., Hata, K., Kravitz, J., Chen, S., Kalantidis, Y., Li, L.J., Shamma, D.A., et al.: Visual genome: Connecting language and vision using crowdsourced dense image annotations. International Journal of Computer Vision 123(1), 32–73 (2017)
  * [16] Luggen, M., Difallah, D., Sarasua, C., Demartini, G., Cudré-Mauroux, P.: Non-parametric class completeness estimators for collaborative knowledge graphs—the case of wikidata. In: International Semantic Web Conference. pp. 453–469. Springer (2019)
  * [17] Ma, K., Francis, J., Lu, Q., Nyberg, E., Oltramari, A.: Towards generalizable neuro-symbolic systems for commonsense question answering. arXiv preprint arXiv:1910.14087 (2019)
  * [18] Marcus, G.: The next decade in ai: four steps towards robust artificial intelligence. arXiv preprint arXiv:2002.06177 (2020)
  * [19] Miller, G.A.: Wordnet: a lexical database for english. Communications of the ACM 38(11), 39–41 (1995)
  * [20] Mishra, B.D., Tandon, N., Clark, P.: Domain-targeted, high precision knowledge extraction. Transactions of the Association for Computational Linguistics 5, 233–246 (2017)
  * [21] Mulang, I.O., Singh, K., Vyas, A., Shekarpour, S., Sakor, A., Vidal, M.E., Auer, S., Lehmann, J.: Context-aware entity linking with attentive neural networks on wikidata knowledge graph. arXiv preprint arXiv:1912.06214 (2019)
  * [22] Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., Sutskever, I.: Language models are unsupervised multitask learners. OpenAI Blog 1(8), 9 (2019)
  * [23] Romero, J., Razniewski, S., Pal, K., Z. Pan, J., Sakhadeo, A., Weikum, G.: Commonsense properties from query logs and question answering forums. In: Proceedings of the 28th ACM International Conference on Information and Knowledge Management. pp. 1411–1420 (2019)
  * [24] Sap, M., Le Bras, R., Allaway, E., Bhagavatula, C., Lourie, N., Rashkin, H., Roof, B., Smith, N.A., Choi, Y.: Atomic: An atlas of machine commonsense for if-then reasoning. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 33, pp. 3027–3035 (2019)
  * [25] Speer, R., Chin, J., Havasi, C.: Conceptnet 5.5: An open multilingual graph of general knowledge. In: Thirty-First AAAI Conference on Artificial Intelligence (2017)
  * [26] Speer, R., Chin, J., Lin, A., Jewett, S., Nathan, L.: Luminosoinsight/wordfreq: v2.2 (Oct 2018). https://doi.org/10.5281/zenodo.1443582, https://doi.org/10.5281/zenodo.1443582
  * [27] Storks, S., Gao, Q., Chai, J.Y.: Commonsense reasoning for natural language understanding: A survey of benchmarks, resources, and approaches. arXiv preprint arXiv:1904.01172 pp. 1–60 (2019)
  * [28] Suh, S., Halpin, H., Klein, E.: Extracting common sense knowledge from wikipedia. In: Proceedings of the Workshop on Web Content Mining with Human Language Technologies at ISWC. vol. 6 (2006)
  * [29] Tandon, N., De Melo, G., Weikum, G.: Webchild 2.0: Fine-grained commonsense knowledge distillation. In: Proceedings of ACL 2017, System Demonstrations. pp. 115–120 (2017)
  * [30] Tanon, T.P., Weikum, G., Suchanek, F.: Yago 4: A reason-able knowledge base. In: European Semantic Web Conference. pp. 583–596. Springer (2020)
  * [31] Vrandečić, D., Krötzsch, M.: Wikidata: a free collaborative knowledgebase. Communications of the ACM 57(10), 78–85 (2014)


# Marginals with finite repulsive cost

U. Bindini

###### Abstract

We consider a multimarginal transport problem with repulsive cost, where the
marginals are all equal to a fixed probability
$\rho\in\mathcal{P}(\mathbb{R}^{d})$. We prove that, if the concentration of
$\rho$ is less than $1/N$, then the problem has a solution of finite cost. The
result is sharp, in the sense that there exists $\rho$ with concentration
$1/N$ for which the cost is infinite.

_2010 Mathematics Subject Classification:_ 49J10, 49K10.

##  1 Introduction

Consider a system of $N$ unitary-charged particles of negligible mass under
the effect of the Coulomb force. We may describe the stationary states using a
wave-function $\psi(x_{1},\dotsc,x_{N})$, where $x_{j}\in\mathbb{R}^{3}$; via
the Born interpretation, $\left|\psi(x_{1},\dotsc,x_{N})\right|^{2}$ may be
viewed as the density of the probability that the particles occupy the
positions $x_{1},\dotsc,x_{N}$, and it is symmetric, since the particles are
indistinguishable.

When the semi-classical limit is considered, as already proved in [2, 7, 8,
16], the stationary states reach the minimum of potential energy, _i.e._ ,

$V_{0}=\min_{\psi}V(\psi)=\min\int_{\mathbb{R}^{3N}}c(x_{1},\dotsc,x_{N})\left|\psi(x_{1},\dotsc,x_{N})\right|^{2}\mathop{}\\!\mathrm{d}x_{1}\dotsm\mathop{}\\!\mathrm{d}x_{N},$
(1)

where $c$ is the Coulomb (potential) cost function
$c\colon(\mathbb{R}^{3})^{N}\to\mathbb{R}$ defined as

$c(x_{1},\dotsc,x_{N})=\sum_{1\leq i<j\leq
N}\frac{1}{\left|x_{i}-x_{j}\right|}.$

This can also be viewed as the exchange correlation functional linking the
Kohn-Sham to the Hohenberg-Kohn approach, see for instance [13].

Given any wave-function $\psi$, define its single-particle density as

$\rho^{\psi}(x)=\int_{\mathbb{R}^{3(N-1)}}\left|\psi(x,x_{2},\dotsc,x_{N})\right|^{2}\mathop{}\\!\mathrm{d}x_{2}\dotsm\mathop{}\\!\mathrm{d}x_{N},$

which is quite natural from the physical point of view, since the charge
density is a fundamental quantum-mechanical observable.

It is a well-known result by Lieb [17] (see also Levy [15]) that the set of
all possible marginal densities is

$\mathcal{R}=\left\\{\rho\in L^{1}(\mathbb{R}^{d})\left|\right.\rho\geq
0,\sqrt{\rho}\in
H^{1}(\mathbb{R}^{d}),\int_{\mathbb{R}^{d}}\rho(x)dx=1\right\\}.$

One may thus consider

$C(\rho)=\min\left\\{\int_{\mathbb{R}^{3N}}c(x_{1},\dotsc,x_{N})\left|\psi(x_{1},\dotsc,x_{N})\right|^{2}\mathop{}\\!\mathrm{d}x_{1}\dotsm\mathop{}\\!\mathrm{d}x_{N}\left|\right.\rho^{\psi}=\rho\right\\},$

and factorize the original minimum problem (1) as

$V_{0}=\min_{\rho\in\mathcal{R}}\min_{\rho^{\psi}=\rho}V(\psi)=\min_{\rho}C(\rho).$

This is a well known approach, which dates back to Thomas and Fermi, and was
later revised by Hohenberg and Kohn [14], Levy [15] and Lieb [17], whose
questions are still sources of ideas for this field.

In this paper, firstly we generalize the physical dimension $d=3$ to any
$d\geq 1$. Moreover, we adopt a measure-theoretic approach: instead of
considering wave-functions, we set the problem for every probability over
$(\mathbb{R}^{d})^{N}$ and formulate the corresponding relaxed minimum problem

$\mathcal{C}(P)=\min\int_{(\mathbb{R}^{d})^{N}}c(x_{1},\dotsc,x_{N})\mathop{}\\!\mathrm{d}P(x_{1},\dotsc,x_{N}),$

where $P\in\mathcal{P}((\mathbb{R}^{d})^{N})$ is a probability measure. In
this fashion, the single-particle density constraint gives rise to a multi-
marginal optimal transport problem of the form

$\displaystyle\begin{split}C(\rho)=\inf\bigg{\\{}&\int_{(\mathbb{R}^{d})^{N}}c(x_{1},\dotsc,x_{N})\mathop{}\\!\mathrm{d}P(x_{1},\dotsc,x_{N})\colon\\\
&P\in\mathcal{P}((\mathbb{R}^{d})^{N}),\
\pi_{\\#}^{i}P=\rho,i=1,\dotsc,N\bigg{\\}},\end{split}$ (2)

where $\rho$ is a fixed probability measure over $\mathbb{R}^{d}$, and
$\pi^{i}$ is the projection over the $i$-th factor of $(\mathbb{R}^{d})^{N}$.
It is a simple and well known observation that the infimum (2) is equal to

$\displaystyle\begin{split}C(\rho)=\inf\bigg{\\{}&\int_{(\mathbb{R}^{d})^{N}}c(x_{1},\dotsc,x_{N})\mathop{}\\!\mathrm{d}P(x_{1},\dotsc,x_{N})\colon\\\
&P\in\mathcal{P}((\mathbb{R}^{d})^{N}),P\text{ symmetric
},\pi_{\\#}^{i}P=\rho,i=1,\dotsc,N\bigg{\\}}.\end{split}$ (3)

In order to give even a stronger result, we take as a cost function a general
repulsive potential, as in the following

######  Definition 1.

A function $c\colon(\mathbb{R}^{d})^{N}\to\mathbb{R}$ is a _repulsive cost
function_ if it is of the form

$c(x_{1},\dotsc,x_{N})=\sum_{1\leq i<j\leq
N}\frac{1}{\omega(\left|x_{i}-x_{j}\right|)}$

where $\omega\colon\mathbb{R}^{+}\to\mathbb{R}^{+}$ is continuous, strictly
increasing, differentiable on $(0,+\infty)$, with $\omega(0)=0$.

Although there are many works about this formulation, and the multi-marginal
transport problem in general (see for instance [3, 5, 6, 9, 10]), none of them
gives a condition on $\rho$ which assures that the infimum in (3) is finite.
We found that the correct quantity to consider is the one given by the
following

######  Definition 2.

If $\rho\in\mathcal{P}(\mathbb{R}^{d})$, the _concentration_ of $\rho$ is

$\mu(\rho)=\sup_{x\in\mathbb{R}^{d}}\rho(\left\\{x\right\\}).$

This allows us to state the main result:

######  Theorem 1.1.

Let $c$ be a repulsive cost function, and $\rho\in\mathcal{P}(\mathbb{R}^{d})$
with

$\mu(\rho)<\frac{1}{N}.$ (4)

Then the infimum in (3) is finite.

After this paper was already submitted, the author became aware of an
independent work in preparation by F. Stra, S. Di Marino and M. Colombo about
the same problem. The techniques are different and the second result, although
not yet available in preprint form, seems to be closer in the approach to some
arguments in [3].

#### Structure of the paper

In Section 2 we give some notation, and regroup some definitions,
constructions and results to be used later. In particular, we state and prove
a simple but useful result about partitioning $\mathbb{R}^{d}$ into measurable
sets with prescribed mass.

We then show in Section 3 that the condition (4) is sharp, _i.e._ , given any
repulsive cost function, there exists $\rho\in\mathcal{P}(\mathbb{R}^{d})$
with $\mu(\rho)=1/N$, and $C(\rho)=\infty$. The construction of this
counterexample is explicit, but it is important to note that the marginal
$\rho$ depends on the given cost function.

Finally we devote Sections 4 to 6 to the proof of Theorem 1.1. The
construction is universal, in the following sense: given
$\rho\in\mathcal{P}(\mathbb{R}^{d})$ such that (4) holds, we exhibit a
symmetric transport plan $P$ which has support outside the region

$D_{\alpha}=\left\\{(x_{1},\dotsc,x_{N})\in(\mathbb{R}^{d})^{N}\left|\right.\exists
i\neq j\text{ with }\left|x_{i}-x_{j}\right|<\alpha\right\\}$

for some $\alpha>0$. This implies that $C(P)$ is finite for any repulsive cost
function.

#### Aknowledgements

The author is grateful to prof. Luigi Ambrosio and prof. Luigi De Pascale for
all their useful remarks, and wish to thank prof. Emmanuel Trélat for his
suggestions.

##  2 Notation and preliminary results

In the following, $x,x_{j}$ denote elements of $\mathbb{R}^{d}$, and
$X=(x_{1},\dotsc,x_{N})$ is an element of
$(\mathbb{R}^{d})^{N}=\mathbb{R}^{Nd}$. We also indicate with $B(x_{j},r)$ a
ball with center $x_{j}\in\mathbb{R}^{d}$ and radius $r>0$. Where it is not
specified, the integrals are extended to all the space; if $\tau$ is a measure
over $\mathbb{R}^{d}$, we denote by $\left|\tau\right|$ its total mass, _i.e._
,

$\left|\tau\right|=\int_{\mathbb{R}^{d}}\mathop{}\\!\mathrm{d}\tau.$

We use the expression _$N$ -transport plan for the marginal $\rho$_ to denote
a probability measure $P\in\mathcal{P}(\mathbb{R}^{Nd})$ with all the
marginals equal to $\rho\in\mathcal{P}(\mathbb{R}^{d})$.

If $P\in\mathcal{M}(\mathbb{R}^{Nd})$ is any measure, we define

$P_{sym}=\frac{1}{N!}\sum_{s\in S_{N}}\phi^{s}_{\\#}P,$

where $S_{N}$ is the premutation group over the elements
$\left\\{1,\dotsc,N\right\\}$, and
$\phi^{s}\colon\mathbb{R}^{Nd}\to\mathbb{R}^{Nd}$ is the function
$\phi^{s}(x_{1},\dotsc,x_{N})=(x_{s(1)},\dotsc,x_{s(N)})$. Note that $P_{sym}$
is a symmetric measure; moreover, if $P$ is a probability measure, then also
$P_{sym}$ is a probability measure.

######  Lemma 2.1.

Let $P\in\mathcal{M}(\mathbb{R}^{Nd})$. Then $P_{sym}$ has marginals equal to

$\frac{1}{N}\sum_{j=1}^{N}\pi^{j}_{\\#}P$

###### Proof.

Since $P_{sym}$ is symmetric, me may calculate its first marginal:

$\displaystyle\pi^{1}_{\\#}P_{sym}$
$\displaystyle=\pi^{1}_{\\#}\left(\frac{1}{N!}\sum_{s\in
S_{N}}\phi^{s}_{\\#}P\right)=\frac{1}{N!}\sum_{s\in
S_{N}}\pi^{1}_{\\#}(\phi^{s}_{\\#}P)$ $\displaystyle=\frac{1}{N!}\sum_{s\in
S_{N}}\pi^{s(1)}_{\\#}P=\frac{1}{N}\sum_{j=1}^{N}\pi^{j}_{\\#}P,$

where the last equality is due to the fact that for every $j=1,\dotsc,N$ there
are exactly $(N-1)!$ permutations $s\in S_{N}$ such that $s(1)=j$. ∎

For a symmetric probability $P\in\mathcal{P}(\mathbb{R}^{Nd})$ we will use the
shortened notation $\pi(P)$ to denote its marginals $\pi^{j}_{\\#}P$, which
are all equal.

If $\sigma_{1},\dotsc,\sigma_{N}\in\mathcal{M}(\mathbb{R}^{d})$, we define
$\sigma_{1}\otimes\dotsb\otimes\sigma_{N}\in\mathcal{M}(\mathbb{R}^{Nd})$ as
the usual product measure. In similar fashion, if
$Q\in\mathcal{M}(\mathbb{R}^{(N-1)d})$, $\sigma\in\mathcal{M}(\mathbb{R}^{d})$
and $1\leq j\leq N$, we define the measure
$Q\otimes_{j}\sigma\in\mathcal{M}(\mathbb{R}^{Nd})$ as

$\int_{\mathbb{R}^{Nd}}f\mathop{}\\!\mathrm{d}(Q\otimes_{j}\sigma)=\int_{\mathbb{R}^{Nd}}f(x_{1},\dotsc,x_{N})\mathop{}\\!\mathrm{d}\sigma(x_{j})\mathop{}\\!\mathrm{d}Q(x_{1},\dotsc,\hat{x}_{j},\dotsc,x_{N})$
(5)

for every $f\in C_{b}(\mathbb{R}^{Nd})$.

###  2.1 Partitions of non-atomic measures

Let $\sigma\in\mathcal{M}(\mathbb{R}^{d})$ be a finite non-atomic measure, and
$b_{1},\dotsc,b_{k}$ real positive numbers such that
$b_{1}+\dotsb+b_{k}=\left|\sigma\right|$. We may want to write

$\mathbb{R}^{d}=\bigcup_{j=1}^{k}E_{j},$

where the $E_{j}$’s are disjoint measurable sets with $\sigma(E_{j})=b_{j}$.
This is trivial if $d=1$, since the cumulative distribution function
$\phi_{\sigma}(t)=\sigma((-\infty,t))$ is continuous, and one may find the
$E_{j}$’s as intervals. However, in higher dimension, the measure $\sigma$
might concentrate over $(d-1)$-dimensional surfaces, which makes the problem
slightly more difficult. Therefore we present the following

######  Proposition 2.2.

Let $\sigma\in\mathcal{M}(\mathbb{R}^{d})$ be a finite non-atomic measure.
Then there exists a direction $y\in\mathbb{R}^{d}\setminus\left\\{0\right\\}$
such that $\sigma(H)=0$ for all the affine hyperplanes $H$ such that $H\perp
y$.

In order to prove Proposition 2.2, it is useful to present the following

######  Lemma 2.3.

Let $(X,\mu)$ be a measure space, with $\mu(X)<\infty$, and $\\{E_{i}\\}_{i\in
I}$ a collection of measurable sets such that

  1. 1.

$\mu(E_{i})>0$ for every $i\in I$;

  2. 2.

$\mu(E_{i}\cap E_{j})=0$ for every $i\neq j$.

Then $I$ is countable.

###### Proof.

Let $i_{1},\dotsc,i_{n}$ be a finite set of indices. Then using the
monotonicity of $\mu$ and the fact that $\mu(E_{i}\cap E_{j})=0$ if $i\neq j$,

$\mu(X)\geq\mu\left(\bigcup_{k=1}^{n}E_{i_{k}}\right)=\sum_{k=1}^{n}\mu(E_{i_{k}}).$

Hence we have that

$\sup\left\\{\sum_{j\in J}\mu(E_{j})\left|\right.J\subset I,J\text{
finite}\right\\}\leq\mu(X)<\infty.$

Since all the $\mu(E_{i})$ are strictly positive numbers, this is possible
only if $I$ is countable. ∎

Now we present the proof of Proposition 2.2.

###### Proof.

For $k=0,1,\dotsc,d-1$ we recall the definitions of the Grassmannian

$\mathrm{Gr}(k,\mathbb{R}^{d})=\left\\{v\text{ linear subspace of
}\mathbb{R}^{d}\left|\right.\dim v=k\right\\}$

and the affine Grassmannian

$\mathrm{Graff}(k,\mathbb{R}^{d})=\left\\{w\text{ affine subspace of
}\mathbb{R}^{d}\left|\right.\dim w=k\right\\}.$

Given $w\in\mathrm{Graff}(k,\mathbb{R}^{d})$, we denote by $[w]$ the unique
element of $\mathrm{Gr}(k,\mathbb{R}^{d})$ parallel to $w$. If
$S\subseteq\mathrm{Graff}(k,\mathbb{R}^{d})$, we say that $S$ is _full_ if for
every $v\in\mathrm{Gr}(k,\mathbb{R}^{d})$ there exists $w\in S$ such that
$[w]=v$. For every $k=1,2,\dotsc,d-1$ let
$S^{k}\subseteq\mathrm{Graff}(k,\mathbb{R}^{d})$ be the set

$S^{k}=\left\\{w\in\mathrm{Graff}(k,\mathbb{R}^{d})\left|\right.\sigma(w)>0\right\\}.$

The goal is to prove that $S^{d-1}$ is _not_ full, while by hypothesis we know
that $S^{0}=\emptyset$, since $\sigma$ is non-atomic.

The following key Lemma leads to the proof in a finite number of steps:

######  Lemma 2.4.

Let $1\leq k\leq d-1$. If $S^{k-1}$ is not full, then $S^{k}$ is not full.

###### Proof.

Let $v\in\mathrm{Gr}(k-1,\mathbb{R}^{d})$, such that for every
$v^{\prime}\in\mathrm{Graff}(k-1,\mathbb{R}^{d})$ with $[v^{\prime}]=v$ it
holds $\sigma(v^{\prime})=0$. Consider the collection
$W_{v}=\left\\{w\in\mathrm{Graff}(k,\mathbb{R}^{d})\left|\right.v\subseteq[w]\right\\}$.
If $w,w^{\prime}\in W_{v}$ are distinct, then $w\cap w^{\prime}\subseteq
v^{\prime}$ for some $v^{\prime}\in\mathrm{Graff}(k-1,\mathbb{R}^{d})$ with
$[v^{\prime}]=v$, thus $\sigma(w\cap w^{\prime})=0$. Since the measure
$\sigma$ is finite, because of Lemma 2.3 at most countably many elements $w\in
W_{v}$ may have positive measure, which implies that $S^{k}$ is not full. ∎

∎

######  Corollary 2.5.

Given $b_{1},\dotsc,b_{k}$ real positive numbers with
$b_{1}+\dotsb+b_{k}=\left|\sigma\right|$, there exist measurable sets
$E_{1},\dotsc,E_{k}\subseteq\mathbb{R}^{d}$ such that

  1. (i)

The $E_{j}$’s form a partition of $\mathbb{R}^{d}$, _i.e._ ,

$\mathbb{R}^{d}=\bigcup_{j=1}^{k}E_{j},\hskip 14.22636ptE_{i}\cap
E_{j}=\emptyset\text{ if $i\neq j$;}$

  2. (ii)

$\sigma(E_{j})=b_{j}$ for every $j=1,\dotsc,k$.

###### Proof.

Let $y\in\mathbb{R}^{d}\setminus\left\\{0\right\\}$ given by Proposition 2.2,
and observe that the cumulative distribution function

$F(t)=\sigma\left(\left\\{x\in\mathbb{R}^{d}\left|\right.x\cdot
y<t\right\\}\right)$

is continuous. Hence we may find $E_{1},\dotsc,E_{k}$ each of the form

$E_{j}=\left\\{x\in\mathbb{R}^{d}\left|\right.t_{j}<x\cdot y\leq
t_{j+1}\right\\}$

for suitable $-\infty=t_{1}<t_{2}<\dotsb<t_{k}<t_{k+1}=+\infty$, such that
$\sigma(E_{j})=b_{j}$. ∎

######  Corollary 2.6.

Given $b_{1},\dotsc,b_{k}$ non-negative numbers with
$b_{1}+\dotsb+b_{k}<\left|\sigma\right|$, there exists measurable sets
$E_{0},E_{1},\dotsc,E_{k}\subseteq\mathbb{R}^{d}$ such that

  1. (i)

The $E_{j}$’s form a partition of $\mathbb{R}^{d}$, _i.e._ ,

$\mathbb{R}^{d}=\bigcup_{j=0}^{k}E_{j},\hskip 14.22636ptE_{i}\cap
E_{j}=\emptyset\text{ if $i\neq j$;}$

  2. (ii)

$\sigma(E_{j})=b_{j}$ for every $j=1,\dotsc,k$;

  3. (iii)

the distance between $E_{i}$ and $E_{j}$ is strictly positive if $i,j\geq 1$,
$i\neq j$.

###### Proof.

If $k=1$ the results follows trivially by Corollary 2.5 applied to
$b_{1},\left|\sigma\right|-b_{1}$. If $k\geq 2$, define

$\epsilon=\frac{\left|\sigma\right|-b_{1}-\dotsb-b_{k}}{k-1}>0.$

As before, letting $y\in\mathbb{R}^{d}\setminus\left\\{0\right\\}$ given by
Proposition 2.2 and considering the corresponding cumulative distribution
function, we may find $F_{1},\dotsc,F_{2k-1}$ each of the form

$F_{j}=\left\\{x\in\mathbb{R}^{d}\left|\right.t_{j}<x\cdot y\leq
t_{j+1}\right\\}$

for suitable $-\infty=t_{1}<t_{2}<\dotsb<t_{2k-1}<t_{2k}=+\infty$, such that

$\displaystyle\sigma(F_{2j-1})$ $\displaystyle=b_{j}\hskip 14.22636pt\forall
j=1,\dotsc,k$ $\displaystyle\sigma(F_{2j})$ $\displaystyle=\epsilon\hskip
14.22636pt\forall j=1,\dotsc,k-1$

Finally we define

$\displaystyle E_{j}$ $\displaystyle=F_{2j-1}\hskip 14.22636pt\forall
j=1,\dotsc,k$ $\displaystyle E_{0}$ $\displaystyle=\bigcup_{j=1}^{k-1}F_{2j}.$

The properties (i), (ii) are immediate to check, while the distance between
$E_{i}$ and $E_{j}$, for $i,j\geq 1$, $i\neq j$, is uniformly bounded from
below by

$\min\left\\{t_{2j+1}-t_{2j}\left|\right.1\leq j\leq k-1\right\\}>0.$

∎

##  3 The condition (4) is sharp

In this section we prove that the condition (4) is the best possible, _i.e._ ,
given any repulsive cost function there exists
$\rho\in\mathcal{P}(\mathbb{R}^{d})$ with $\mu(\rho)=1/N$ such that
$C(\rho)=\infty$.

Fix $\omega$ as in Definition 1, and set

$k=\int_{B(0,1)}\frac{\omega^{\prime}(\left|y\right|)}{\left|y\right|^{d-1}}\mathop{}\\!\mathrm{d}y.$

Note that $k$ is a positive finite constant, depending only on $\omega$ and
the dimension $d$. In fact, integrating in spherical coordinates,

$k=\int_{0}^{1}\frac{\omega^{\prime}(r)}{r^{d-1}}\alpha_{d}r^{d-1}\mathop{}\\!\mathrm{d}r=\alpha_{d}\omega(1),$

where $\alpha_{d}$ is the $d$-dimensional volume of the unit ball
$B(0,1)\subseteq\mathbb{R}^{d}$.

Now define a probability measure $\rho\in\mathcal{P}(\mathbb{R}^{d})$ as

$\int_{\mathbb{R}^{d}}f\mathop{}\\!\mathrm{d}\rho:=\frac{1}{N}f(0)+\frac{N-1}{N}\int_{B(0,1)}f(x)\frac{\omega^{\prime}(\left|x\right|)}{k\left|x\right|^{d-1}}\mathop{}\\!\mathrm{d}x\hskip
14.22636pt\forall f\in C_{b}(\mathbb{R}^{d}).$ (6)

This measure has an atom of mass $1/N$ in the origin, and is absolutely
continuous on $\mathbb{R}^{d}\setminus\left\\{0\right\\}$. Hence the
concentration of $\rho$ is equal to $1/N$, even if for every ball $B$ around
the origin one has $\rho(B)>1/N$.

We want to prove that any symmetric transport plan with marginals $\rho$ has
infinite cost. Let us consider, by contradiction, a symmetric plan $P$, with
$\pi(P)=\rho$, such that

$\int\sum_{1\leq i<j\leq
N}\frac{1}{\omega(\left|x_{i}-x_{j}\right|)}\mathop{}\\!\mathrm{d}P(X)<\infty$

Then one would have the following geometric properties.

######  Lemma 3.1.

  1. (i)

$P(\left\\{(x_{1},\dotsc,x_{N}):\exists i\neq j,x_{i}=x_{j}\right\\})=0;$

  2. (ii)

$P$ is concentrated over the $N$ coordinate hyperplanes
$\left\\{x_{j}=0\right\\}$, $j=1,\dotsc,N$, _i.e._ ,

$\operatorname{supp}(P)\subseteq
E:=\bigcup_{j=1}^{N}\left\\{x_{j}=0\right\\}.$

###### Proof.

(i) Since $\omega(0)=0$, recalling Definition 1, the cost function is
identically equal to $+\infty$ in the region
$\left\\{(x_{1},\dotsc,x_{N}):\exists i\neq j,x_{i}=x_{j}\right\\}$.
Therefore, since by assumption the cost of $P$ is finite, it must be

$P(\left\\{(x_{1},\dotsc,x_{N}):\exists i\neq j,x_{i}=x_{j}\right\\})=0.$

(ii) Define

$\displaystyle p_{1}$ $\displaystyle=P(\left\\{x_{1}=0\right\\})$
$\displaystyle p_{2}$
$\displaystyle=P(\left\\{x_{1}=0\right\\}\cap\left\\{x_{2}=0\right\\})$
$\displaystyle\vdots$ $\displaystyle p_{N}$ $\displaystyle=P((0,\dotsc,0)).$

Note that
$p_{1}=P(\left\\{x_{1}=0\right\\})=\pi(P)(\left\\{0\right\\})=\rho(\left\\{0\right\\})=1/N$.
We claim that $p_{2}=\dotsb=p_{N}=0$. It suffices to prove that $p_{2}=0$,
since by monotonicity of the measure $P$ we have $p_{j}\geq p_{j+1}$. Since
$P$ has finite cost,

$\int_{\mathbb{R}^{Nd}}\frac{\mathop{}\\!\mathrm{d}P}{\omega(\left|x_{1}-x_{2}\right|)}$

must be finite. However,

$\int_{\mathbb{R}^{Nd}}\frac{\mathop{}\\!\mathrm{d}P}{\omega(\left|x_{1}-x_{2}\right|)}\geq\int_{\left\\{x_{1}=0\right\\}\cap\left\\{x_{2}=0\right\\}}\frac{\mathop{}\\!\mathrm{d}P}{\omega(\left|x_{1}-x_{2}\right|)}=p_{2}\int_{\mathbb{R}^{2d}}\frac{\delta_{0}(x_{1})\delta_{0}(x_{2})}{\omega(\left|x_{1}-x_{2}\right|)}\mathop{}\\!\mathrm{d}x_{1}\mathop{}\\!\mathrm{d}x_{2},$

and hence $p_{2}$ must be zero.

By inclusion-exclusion we have

$P(E)=\sum_{j=1}^{N}(-1)^{j+1}\binom{N}{j}p_{j}=Np_{1}=1,$

and hence $P$ is concentrated over $E$. ∎

In view of Lemma 3.1, letting $H_{j}=\\{x_{j}=0\\}$ for $j=1,\dotsc,N$,

$P=\sum_{j=1}^{N}P|_{H_{j}}.$

For every $j=1,\dotsc,N$ there exists a unique measure $Q_{j}$ over
$\mathbb{R}^{(N-1)d}$ such that, recalling equation (5),
$P|_{H_{j}}=Q_{j}\otimes_{j}\delta_{0}$, with
$Q_{j}(\mathbb{R}^{(N-1)d})=\frac{1}{N}$. Since $P$ is symmetric, considering
a permutation $s\in S_{N}$ with $s(j)=j$, it follows that $Q_{j}$ is
symmetric; then, considering any permutation in $S_{N}$ we see that there
exists a symmetric probability $Q$ over $\mathbb{R}^{(N-1)d}$ such that
$Q_{j}=\frac{1}{N}Q$ for every $j=1,\dotsc,N$, _i.e._ ,

$P=\frac{1}{N}\sum_{j=1}^{N}Q\otimes_{j}\delta_{0}.$

Projecting $P$ to its one-particle marginal and using the definition of $\rho$
in (6), we get that $\pi(Q)$ is absolutely continuous w.r.t. the Lebesgue
measure, with

$\frac{\mathop{}\\!\mathrm{d}\pi(Q)}{\mathop{}\\!\mathrm{d}\mathcal{L}^{d}}=\frac{\chi_{B(0,1)}(x)\omega^{\prime}(x)}{k\left|x\right|^{d-1}}.$

Here we get the contradiction, because

$\displaystyle\int c(X)dP(X)$
$\displaystyle\geq\frac{1}{N}\int\frac{1}{\omega(\left|x_{1}-x_{2}\right|)}\delta_{0}(x_{1})\mathop{}\\!\mathrm{d}x_{1}\mathop{}\\!\mathrm{d}Q(x_{2},\dotsc,x_{N})$
$\displaystyle=\frac{1}{N}\int\frac{1}{\omega(\left|x_{2}\right|)}\mathop{}\\!\mathrm{d}Q(x_{2},\dotsc,x_{N})=\frac{1}{N}\int_{\mathbb{R}^{d}}\frac{1}{\omega(\left|x\right|)}\mathop{}\\!\mathrm{d}\pi(Q)(x)$
$\displaystyle=\frac{1}{N}\int_{B(0,1)}\frac{\omega^{\prime}(\left|x\right|)}{\omega(\left|x\right|)}\frac{1}{k\left|x\right|^{d-1}}\mathop{}\\!\mathrm{d}x=\frac{1}{N}\frac{\alpha_{d}}{k}\int_{0}^{1}\frac{\omega^{\prime}(r)}{\omega(r)}\mathop{}\\!\mathrm{d}r=+\infty.$

##  4 Non-atomic marginals

This short section deals with the case where $\rho$ is non atomic, _i.e._ ,
$\mu(\rho)=0$. In this case the transport plan is given by an optimal
transport map in Monge’s fashion, which we proceed to construct.

Using Corollary 2.5, let $E_{1},\dotsc,E_{2N}$ be a partition of
$\mathbb{R}^{d}$ such that

$\rho(E_{j})=\frac{1}{2N}\hskip 14.22636pt\forall j=1,\dotsc,2N.$

Next we take a measurable function
$\phi\colon\mathbb{R}^{d}\to\mathbb{R}^{d}$, preserving the measure $\rho$ and
defined locally such that

$\displaystyle\phi(E_{j})$ $\displaystyle=E_{j+2}\hskip 14.22636pt\forall
j=1,\dotsc,N-2$ $\displaystyle\phi(E_{2N-1})$ $\displaystyle=E_{1}$
$\displaystyle\phi(E_{2N})$ $\displaystyle=E_{2}.$

The behaviour of $\phi$ on the hyperplanes which separate the $E_{j}$’s is
arbitrary, since they form a $\rho$-null set. Note that
$\left|x-\phi(x)\right|$ is uniformy bounded from below by some constant
$\gamma>0$, as is clear by the construction of the $E_{j}$’s (see the proof of
Corollary 2.5). A transport plan $P$ of finite cost is now defined for every
$f\in C_{b}(\mathbb{R}^{Nd})$ by

$\int_{\mathbb{R}^{Nd}}f\mathop{}\\!\mathrm{d}P=\int_{\mathbb{R}^{Nd}}f(x,\phi(x),\dotsc,\phi^{N-1}(x))\mathop{}\\!\mathrm{d}\rho(x),$

since

$\int_{\mathbb{R}^{Nd}}c\mathop{}\\!\mathrm{d}P=\binom{N}{2}\int_{\mathbb{R}^{d}}\frac{1}{\omega(\left|x-\phi(x)\right|)}\mathop{}\\!\mathrm{d}\rho(x)\leq\binom{N}{2}\frac{1}{\omega(\gamma)}.$

##  5 Marginals with a finite number of atoms

This section constitutes the core of the proof, as we deal with measures of
general form with an arbitrary (but finite) number of atoms. Throughout this
and the next Section we assume that the marginal $\rho$ fulfills the condition
(4).

###  5.1 The number of atoms is less than or equal to $N$

Note that, if the number of atoms is at most $N$, then $\rho$ must have a non-
atomic part $\sigma$, due to the condition (4). From here on we consider

$\rho=\sigma+\sum_{i=1}^{k}b_{i}\delta_{x_{i}},$

where $b_{1}\geq b_{2}\geq\dotsb\geq b_{k}>0$.

We begin with the following

######  Definition 3.

A _partition_ of $\sigma$ of level $k\leq N$ subordinate to
$(x_{1},\dotsc,x_{k};$ $b_{1},\dotsc,b_{k})$ is

$\sigma=\tau+\sum_{i=1}^{k}\sum_{h=i+1}^{N}\sigma^{i}_{h},$

where:

  1. (i)

$\tau,\sigma^{i}_{h}$ are non-atomic measures;

  2. (ii)

for every $i$ and every $h\neq k$, the distance between
$\operatorname{supp}\sigma^{i}_{h}$ and $\operatorname{supp}\sigma^{i}_{k}$ is
strictly positive;

  3. (iii)

for every $i,h$, if $j\leq i$ then $x_{j}$ has a strictly positive distance
from $\operatorname{supp}{\sigma^{i}_{h}}$;

  4. (iv)

for every $i,h$, $\left|\sigma^{i}_{h}\right|=b_{i}$, and
$\left|\tau\right|>0$.

Note that such a partition may only exists if

$\left|\sigma\right|>\sum_{i=1}^{k}(N-i)b_{i}.$ (7)

On the other hand, the following Lemma proves that the condition (7) is also
sufficient to get a partition of $\sigma$.

######  Lemma 5.1.

Let $(b_{1},\dotsc,b_{k})$ with $k\leq N$, and

$\left|\sigma\right|>\sum_{i=1}^{k}(N-i)b_{i}.$

Then there exists a partition of $\sigma$ subordinate to
$(x_{1},\dotsc,x_{k};b_{1},\dotsc,b_{k})$.

###### Proof.

Fix $(x_{1},\dotsc,x_{k})$ and for every $\varepsilon>0$ define

$A_{\varepsilon}=\bigcup_{j=1}^{k}B(x_{j},\varepsilon).$

and $\sigma_{\varepsilon}=\sigma\chi_{A_{\varepsilon}}$. Then take
$\varepsilon$ small enough such that

$\left|\sigma-\sigma_{\varepsilon}\right|>\sum_{i=1}^{k}(N-i)b_{i},$ (8)

which is possibile because $\mu(\sigma)=0$ ($\sigma$ has concentration zero),
and hence $\left|\sigma_{\varepsilon}\right|\to 0$ as $\varepsilon\to 0$. Due
to Corollary 2.6, the set $\mathbb{R}^{d}\setminus A_{\varepsilon}$ may be
partitioned as

$\mathbb{R}^{d}\setminus
A_{\varepsilon}=\left(\bigcup_{i=1}^{k}\bigcup_{h=i+1}^{N}E^{i}_{h}\right)\cup
E,$

with $\sigma(E^{i}_{h})=b_{i}$, and $\mathrm{dist}(E^{i}_{h},E^{i}_{k})$ is
uniformly bounded from below.

Finally define $\sigma^{i}_{h}=\sigma\chi_{E^{i}_{h}}$,
$\tau=\sigma_{\varepsilon}+\sigma\chi_{E}$.

∎

######  Proposition 5.2.

Suppose that $k\leq N$ and $(b_{1},\dotsc,b_{k})$ are such that

$\left|\sigma\right|>Nb_{1}-\sum_{j=1}^{k}b_{j}.$ (9)

Then there exists a transport plan of finite cost with marginals

$\sigma+\sum_{j=1}^{k}b_{j}\delta_{x_{j}}.$

###### Proof.

In order to simplify the notation, set $b_{k+1}=0$. First of all we shall fix
a partition of $\sigma$ subordinate to
$(x_{1},\dotsc,x_{k};b_{1}-b_{2},\dotsc,b_{k-1}-b_{k},b_{k})$. To do this we
apply Lemma 7, since

$\displaystyle\sum_{i=1}^{k-1}(N-i)(b_{i}-b_{i+1})+(N-k)b_{k}$
$\displaystyle=(N-1)b_{1}-\sum_{i=2}^{k}b_{i}<\left|\sigma\right|.$

Next we define the measures
$\lambda_{i}=\delta_{x_{1}}\otimes\dotsb\otimes\delta_{x_{i}}\otimes\sigma^{i}_{i+1}\otimes\dotsb\otimes\sigma^{i}_{N}\in\mathcal{M}(\mathbb{R}^{Nd})$.
Let us calculate the marginals of $\lambda_{i}$: since
$\left|\sigma^{i}_{h}\right|=b_{i}-b_{i+1}$ for all $h=i+1,\dotsc,N$, we get

$\pi^{j}_{\\#}\lambda_{i}=\begin{cases}(b_{i}-b_{i+1})^{N-i}\delta_{x_{j}}&\text{if
$0\leq j\leq i$}\\\ (b_{i}-b_{i+1})^{N-i-1}\sigma^{i}_{j}&\text{if $i+1\leq
j\leq N$.}\end{cases}$

Let us define, for $i=1,\dotsc,k$, the measure

$P_{i}=\frac{N}{(b_{i}-b_{i+1})^{N-i-1}}(\lambda_{i})_{sym},$

where $P_{i}=0$ if $b_{i}=b_{i+1}$. By Lemma 2.1, the marginals of $P_{i}$ are
equal to

$\pi(P_{i})=\frac{1}{(b_{i}-b_{i+1})^{N-i-1}}\sum_{j=0}^{N}\pi^{j}_{\\#}\lambda_{i}=\sum_{j=1}^{i}(b_{i}-b_{i+1})\delta_{x_{j}}+\sum_{h=i+1}^{N}\sigma^{i}_{h},$

so that

$\sum_{i=1}^{k}\pi(P_{i})=\sum_{j=1}^{k}b_{j}\delta_{x_{j}}+\sum_{i=1}^{k}\sum_{h=i+1}^{N}\sigma^{i}_{h}$

It suffices now to take any symmetric transport plan $P_{\tau}$ of finite cost
with marginals $\tau$, given by the result of Section 4, and finally set

$P=P_{\tau}+\sum_{i=1}^{k}P_{i}.$

∎

As a corollary we obtain

######  Theorem 5.3.

If $\rho$ has $k\leq N$ atoms, then there exists a transport plan of finite
cost.

###### Proof.

Let

$\rho=\sigma+\sum_{j=1}^{k}b_{j}\delta_{x_{j}}.$

Note that, since $b_{1}<1/N$,

$\left|\sigma\right|=1-\sum_{j=1}^{k}b_{j}>Nb_{1}-\sum_{j=1}^{k}b_{j},$

hence we may apply Proposition 5.2 to conclude.

∎

###  5.2 The number of atoms is greater than $N$

Here we deal with the much more difficult situation in which $\rho$ has $N+1$
or more atoms, _i.e._ ,

$\rho=\sigma+\sum_{j=1}^{k}b_{j}\delta_{x_{j}}$

with $k\geq N+1$ and as before $b_{1}\geq b_{2}\geq\dotsb\geq b_{k}>0$. Note
that in this case it might happen that $\sigma=0$.

The main point is to use a double induction on the dimension $N$ and the
number of atoms $k$, as will be clear in Proposition 5.5. The following lemma
is a simple numerical trick needed for the inductive step in Proposition 5.5.

######  Lemma 5.4.

Let $(b_{1},\dotsc,b_{k})$ with $k\geq N+2$ and

$(N-1)b_{1}\leq\sum_{j=2}^{k}b_{j}.$ (10)

Then there exist $t_{2},\dotsc,t_{k}$ such that

  1. (i)

$t_{2}+\dotsb+t_{k}=(N-1)b_{1}$;

  2. (ii)

for every $j=2,\dotsc,k$, $0\leq t_{j}\leq b_{j}$, and moreover

$t_{2}\geq\dotsb\geq t_{k}.$ $b_{2}-t_{2}\geq b_{3}-t_{3}\geq\dotsb\geq
b_{k}-t_{k},$

  3. (iii)

$(N-2)t_{2}\leq\sum_{j=3}^{k}t_{j};$

  4. (iv)

$(N-1)(b_{2}-t_{2})\leq\sum_{j=3}^{k}(b_{j}-t_{j}).$

###### Proof.

For $j=2,\dotsc,k$ define

$p_{j}=\sum_{h=j}^{k}b_{j},$

and let $\bar{\jmath}$ be the least $j\geq 2$ such that $(N-j+2)b_{j}\leq
p_{j}$; note that $j=N+2$ works — hence $\bar{\jmath}\leq N+2$. Define

$\displaystyle t_{j}$ $\displaystyle=b_{j}-\frac{p_{2}-(N-1)b_{1}}{N}$ for
$j=2,\dotsc,\bar{\jmath}-1$, $\displaystyle t_{j}$
$\displaystyle=b_{j}-\frac{b_{j}}{p_{\bar{\jmath}}}\frac{p_{2}-(N-1)b_{1}}{N}(N-\bar{\jmath}+2)$
for $j=\bar{\jmath},\dotsc,k$.

Next we prove that this choice fulfills the conditions (i)-(iv).

#### Proof of (i)

$\displaystyle\sum_{j=2}^{k}t_{j}$
$\displaystyle=p_{2}-\frac{p_{2}-(N-1)b_{1}}{N}(\bar{\jmath}-2)-\frac{p_{2}-(N-1)b_{1}}{N}(N-\bar{\jmath}+2)$
$\displaystyle=p_{2}\left(1-\frac{\bar{\jmath}-2}{N}-\frac{N-\bar{\jmath}+2}{N}\right)+(N-1)b_{1}\left(\frac{\bar{\jmath}-2}{N}+\frac{N-\bar{\jmath}+2}{N}\right)$
$\displaystyle=(N-1)b_{1}.$

#### Proof of (ii)

In view of the fact that $(N-1)b_{1}\leq p_{2}$ and $\bar{\jmath}\leq N+2$, it
is clear that $t_{j}\leq b_{j}$. If $j<\bar{\jmath}$ we have
$(N-j+2)b_{j}>p_{j}$, and hence

$p_{2}=b_{2}+\dotsb+b_{j-1}+p_{j}<(j-2)b_{1}+(N-j+2)b_{j}.$

Thus, since $2\leq j\leq N+1$,

$\displaystyle t_{j}$
$\displaystyle=\frac{Nb_{j}-p_{2}+(N-1)b_{1}}{N}>\frac{Nb_{j}-(N-j+2)b_{j}-(j-2)b_{1}+(N-1)b_{1}}{N}$
$\displaystyle=\frac{(j-2)b_{j}+(N-j+1)b_{1}}{N}\geq 0.$

To show that $t_{j}\geq 0$ for $j\geq\bar{\jmath}$, we must prove
$[p_{2}-(N-1)b_{1}](N-\bar{\jmath}+2)\leq Np_{\bar{\jmath}}$, which is trivial
if $\bar{\jmath}=N-2$. Otherwise, it is equivalent to

$-(\bar{\jmath}-2)[p_{2}-(N-1)b_{1}]+N[b_{2}+\dotsb+b_{\bar{\jmath}-1}-(N-1)b_{1}]\leq
0.$

Since $2\leq\bar{\jmath}\leq N+1$, the first term is negative and
$b_{2}+\dotsb+b_{\bar{\jmath}-1}-(N-1)b_{1}\leq-(N-\bar{\jmath}+1)b_{1}\leq
0$.

Using the fact that $b_{2}\geq\dotsb\geq b_{k}$, it is easy to see that
$t_{2}\geq\dotsb\geq\dotsb t_{\bar{\jmath}-1}$ and
$t_{\bar{\jmath}}\geq\dotsb\geq t_{k}$ — note that for $j\geq\bar{\jmath}$ we
have $t_{j}=\alpha b_{j}$, for some $0\leq\alpha\leq 1$. As for the remaining
inequality,

$t_{\bar{\jmath}-1}\geq t_{\bar{\jmath}}\iff
b_{\bar{\jmath}-1}-b_{\bar{\jmath}}\geq\frac{p_{2}-(N-1)b_{1}}{Np_{\bar{\jmath}}}[p_{\bar{\jmath}}-(N-\bar{\jmath}+2)b_{\bar{\jmath}}],$

we already proved

$\frac{p_{2}-(N-1)b_{1}}{Np_{\bar{\jmath}}}\leq\frac{1}{N-\bar{\jmath}+2};$

moreover, by definition of $\bar{\jmath}$, we have
$(N-\bar{\jmath}+3)b_{\bar{\jmath}-1}>p_{\bar{\jmath}-1}$, or equivalently
$(N-\bar{\jmath}+2)b_{\bar{\jmath}-1}>p_{\bar{\jmath}}$. Thus

$\frac{p_{2}-(N-1)b_{1}}{Np_{\bar{\jmath}}}[p_{\bar{\jmath}}-(N-\bar{\jmath}+2)b_{\bar{\jmath}}]\leq\frac{p_{\bar{\jmath}}}{N-\bar{\jmath}+2}-b_{\bar{\jmath}}<b_{\bar{\jmath}-1}-b_{\bar{\jmath}},$

as wanted.

It is left to show that $b_{2}-t_{2}\geq\dotsb\geq b_{k}-t_{k}$. It is trivial
to check that $b_{2}-t_{2}=\dotsb=b_{\bar{\jmath}-1}-t_{\bar{\jmath}-1}$, and
$b_{\bar{\jmath}}-t_{\bar{\jmath}}\geq\dotsb\geq b_{k}-t_{k}$ using
$b_{\bar{\jmath}}\geq\dotsb\geq b_{k}$ as before. Finally,

$b_{\bar{\jmath}-1}-t_{\bar{\jmath}-1}\geq
b_{\bar{\jmath}}-t_{\bar{\jmath}}\iff\frac{p_{2}-(N-1)b_{1}}{N}\geq\frac{b_{\bar{\jmath}}}{p_{\bar{\jmath}}}\frac{p_{2}-(N-1)b_{1}}{N}(N-\bar{\jmath}+2),$

which is true since $(N-\bar{\jmath}+2)b_{\bar{\jmath}}\leq p_{\bar{\jmath}}$
and $p_{2}-(N-1)b_{1}\geq 0$.

#### Proof of (iii)

The thesis is equivalent to

$(N-1)t_{2}\leq\sum_{j=2}^{k}t_{j}\iff(N-1)t_{2}\leq(N-1)b_{1},$

and this is implied by $t_{2}\leq b_{2}\leq b_{1}$.

#### Proof of (iv)

The thesis is equivalent to

$N(b_{2}-t_{2})\leq p_{2}-(N-1)b_{1},$

which is in fact an equality (see the definition of $t_{2}$).

∎

We are ready to present the main result of this Section, which provides a
transport plan of finite cost under an additional hypothesis on the tuple
$(b_{1},\dotsc,b_{k})$. The result is peculiar for the fact that it does not
involve the non-atomic part of the measure – it is in fact a general discrete
construction to get a purely atomic symmetric measure having fixed purely
atomic marginals.

######  Proposition 5.5.

Let $k>N$ and $(b_{1},\dotsc,b_{k})$ with

$(N-1)b_{1}\leq b_{2}+\dotsb+b_{k}.$ (11)

Then for every $x_{1},\dotsc,x_{k}\in\mathbb{R}^{d}$ distinct, there exists a
symmetric transport plan of finite cost with marginals
$\rho=b_{1}\delta_{x_{1}}+\dotsb+b_{k}\delta_{x_{k}}$.

###### Proof.

For every pair of positive integers $(N,k)$, with $k>N$, let
$\mathfrak{P}(N,k)$ be the following proposition:

Let $(x_{1},\dotsc,x_{k};b_{1},\dotsc,b_{k})$ with $(N-1)b_{1}\leq
b_{2}+\dotsb+b_{k}$. Then for every $(x_{1},\dotsc,x_{k})$ there exists a
symmetric $N$-transport plan of finite cost with marginals
$b_{1}\delta_{x_{1}}+\dotsb+b_{k}\delta_{x_{k}}$.

We will prove $\mathfrak{P}(N,k)$ by double induction, in the following way:
first we prove $\mathfrak{P}(1,k)$ for every $k$ and $\mathfrak{P}(N,N+1)$ for
every $N$. Then we prove

$\mathfrak{P}(N-1,k)\wedge\mathfrak{P}(N,k-1)\implies\mathfrak{P}(N,k).$

#### Proof of $\mathfrak{P}(1,k)$

This is trivial: simply take $b_{1}\delta_{x_{1}}+\dotsb+b_{k}\delta_{x_{k}}$
as a “transport plan”.

#### Proof of $\mathfrak{P}(N,N+1)$

Let us denote by $A_{N}$ the $(N+1)\times(N+1)$ matrix

$A_{N}=\begin{pmatrix}0&1&\cdots&1\\\ 1&0&\cdots&1\\\ \vdots&&\ddots&\\\
1&\cdots&1&0\end{pmatrix},$

whose inverse is

$A_{N}^{-1}=\frac{1}{N}\begin{pmatrix}-(N-1)&1&\cdots&1\\\
1&-(N-1)&\cdots&1\\\ \vdots&&\ddots&\\\ 1&\cdots&1&-(N-1)\end{pmatrix}$

Define also the following $(N+1)\times N$ matrix, with elements in
$\mathbb{R}^{d}$:

$(x_{ij})=\begin{pmatrix}x_{2}&x_{3}&\cdots&x_{N+1}\\\
x_{1}&x_{3}&\cdots&x_{N+1}\\\ \vdots&\vdots&\ddots&\vdots\\\
x_{1}&x_{2}&\cdots&x_{N}\end{pmatrix},$

where the $i$-th row is $(x_{1},\dotsc,x_{i-1},x_{i+1},\dotsc,x_{N+1})$. We
want to construct a transport plan of the form

$P=N\sum_{i=1}^{N+1}a_{i}(\delta_{x_{i1}}\otimes\dotsb\otimes\delta_{x_{iN}})_{sym},$

where $a_{i}\geq 0$. Note that, by Lemma 2.1, the marginals of $P$ are equal
to

$\pi(P)=\sum_{j=1}^{N+1}\left(\sum_{\begin{subarray}{c}i=1\\\ i\neq
j\end{subarray}}^{N+1}a_{i}\right)\delta_{x_{j}}.$

Thus, the condition on the $a_{i}$’s to have $\pi(P)=\rho$ is

$A_{N}\begin{pmatrix}a_{1}\\\ \vdots\\\
a_{N+1}\end{pmatrix}=\begin{pmatrix}b_{1}\\\ \vdots\\\ b_{N+1}\end{pmatrix},$

_i.e._ ,

$\begin{pmatrix}a_{1}\\\ \vdots\\\
a_{N+1}\end{pmatrix}=A_{N}^{-1}\begin{pmatrix}b_{1}\\\ \vdots\\\
b_{N+1}\end{pmatrix}.$

Finally, observe that the condition (10) implies that $a_{1}\geq 0$, while the
fact that $b_{1}\geq b_{2}\geq\dotsb\geq b_{N+1}$ leads to $a_{1}\leq
a_{2}\leq\dotsb\leq a_{N+1}$, and hence $a_{i}\geq 0$ for every $i$ and we are
done.

#### Inductive step

Let $(b_{1},\dotsc,b_{k})$ satisfying (10), with $k\geq N+2$ (otherwise we are
in the case $\mathfrak{P}(N,N+1)$, already proved). Take $t_{2},\dotsc,t_{k}$
given by Lemma 5.4, and apply the inductive hypotheses to find

  * •

a symmetric transport plan $Q_{1}$ of finite cost in $(N-1)$ variables, with
marginals

$\pi(Q_{1})=\sum_{j=2}^{k}t_{j}\delta_{x_{j}};$

  * •

a symmetric transport plan $R$ of finite cost in $N$ variables, with marginals

$\pi(R)=\sum_{j=2}^{k}(b_{j}-t_{j})\delta_{x_{j}}.$

Define

$Q=\frac{1}{N-1}\sum_{j=1}^{N}(Q_{1}\otimes_{j}\delta_{x_{1}}).$

Since $Q_{1}$ is symmetric, $Q$ is symmetric. Moreover, using Lemma 5.4 (i),

$\pi(Q)=\frac{1}{N-1}\delta_{x_{1}}\sum_{j=2}^{k}t_{j}+\sum_{j=2}^{k}t_{j}\delta_{x_{j}}=b_{1}\delta_{x_{1}}+\sum_{j=2}^{k}t_{j}\delta_{x_{j}}.$

The transport plan $P=Q+R$ is symmetric, with marginals
$\pi(P)=b_{1}\delta_{x_{1}}+\dotsb+b_{k}\delta_{x_{k}}$.

∎

In order to conclude the proof of this Section, we must now deal not only with
the non-atomic part of $\rho$, but also with the additional hypothesis of
Proposition 5.5. Indeed, the presence of a non-atomic part will fix the atomic
mass exceeding the inequality (11), as will be seen soon.

######  Definition 4.

Given $N$, we say that the tuple $(b_{1},\dotsc,b_{\ell})$ is _fast
decreasing_ if

$(N-j)b_{j}>\sum_{i>j}b_{i}\hskip 14.22636pt\forall j=1,\dotsc,\ell-1.$

######  Remark 1.

Note that if $(b_{1},\dotsc,b_{\ell})$ is fast decreasing, then necessarily
$\ell<N$. As a consequence, given any sequence $(b_{1},b_{2},\dotsc)$, even
infinite, we may select its maximal fast decreasing initial tuple
$(b_{1},\dotsc,b_{\ell})$ (which might be empty, _i.e._ , $\ell=0$).

######  Theorem 5.6.

If $\rho$ is such that

$\rho=\sigma+\sum_{j=1}^{k}b_{j}\delta_{x_{j}}$

with $k>N$ atoms, then there exists a transport plan of finite cost.

###### Proof.

Consider $(b_{1},\dotsc,b_{k})$ and use the Remark 1 to select its maximal
fast decreasing initial tuple $(b_{1},\dotsc,b_{\ell})$, $\ell<N$. Thanks to
Proposition 5.5, we may construct a transport plan $P_{\ell+1}$ over
$\mathbb{R}^{(N-\ell)d}$ with marginals
$b_{\ell+1}\delta_{x_{\ell+1}}+\dotsb+b_{k}\delta_{x_{k}}$, since

$(N-\ell-1)b_{\ell+1}\leq\sum_{j=\ell+2}^{k}b_{j}$

by maximality of $(b_{1},\dotsc,b_{\ell})$ — and this is condition (10) in
this case. We extend step by step $P_{\ell+1}$ to an $N$-transport plan,
letting

$P_{j}=\frac{1}{N-j}\sum_{i=j}^{N}(P_{j+1}\otimes_{i}\delta_{x_{j}}),$

for $j=\ell,\ell-1,\dotsc,1$.

Let $p_{\ell}=b_{\ell+1}+\dotsb+b_{k}$, and
$q_{\ell}=\tfrac{p_{\ell}}{N-\ell}$. We claim that
$\left|P_{j}\right|=(N-j+1)q_{\ell}$. In fact, by construction
$\left|P_{\ell+1}\right|=p_{\ell}$, and inductively

$\left|P_{j}\right|=\frac{1}{N-j}\sum_{i=j-1}^{N}\left|P_{j+1}\right|=\frac{N-j+1}{N-j}(N-j)q_{\ell}=(N-j+1)q_{\ell}.$

Moreover,

$\pi(P_{j})=\sum_{i=j}^{k}q_{\ell}\delta_{x_{i}}+\sum_{i=\ell+1}^{k}b_{i}\delta_{x_{i}}.$

This is true by construction in the case $j=\ell+1$, and inductively

$\pi(P_{j})=\frac{1}{N-j}\delta_{x_{j}}\left|P_{j+1}\right|+\frac{N-j}{N-j}\pi(P_{j+1})=\sum_{i=j}^{\ell}q_{\ell}\delta_{x_{i}}+\sum_{i=\ell+1}^{k}b_{i}\delta_{x_{i}}.$

Note that, for every $i=1,\dotsc,\ell$, $b_{i}\geq b_{\ell}>q_{\ell}$. We
shall find, using Proposition 5.2, a transport plan of finite cost with
marginals

$\sigma+\sum_{i=1}^{\ell}(b_{i}-q_{\ell})\delta_{x_{i}},$

since the condition (9) reads

$N(b_{1}-q_{\ell})-\sum_{i=1}^{\ell}(b_{i}-q_{\ell})=Nb_{1}-\sum_{i=1}^{\ell}b_{i}-(N-\ell)q_{\ell}<1-\sum_{i=1}^{k}b_{i}=\left|\sigma\right|.$

∎

##  6 Marginals with countably many atoms

In this Section we finally deal with the case of an infinite number of atoms,
_i.e._ ,

$\rho=\sigma+\sum_{j=1}^{\infty}b_{j}\delta_{x_{j}}$

with $b_{j}>0$, $b_{j+1}\leq b_{j}$ for every $j\geq 1$.

The main issue is of topological nature: if the atoms $x_{j}$ are too close
each other (for example, if they form a dense subset of $\mathbb{R}^{d}$) and
the growth of $b_{j}$ for $j\to\infty$ is too slow, the cost might diverge.
With this in mind, we begin with an elementary topological result, in order to
separate the atoms in $N$ groups, with controlled minimal distance from each
other.

######  Lemma 6.1.

There exists a partition $\mathbb{R}^{d}=E_{2}\sqcup\dotsb\sqcup E_{N+1}$ such
that:

  1. (i)

for every $j=2,\dotsc,N+1$, $x_{j}\in\mathring{E}_{j}$;

  2. (ii)

for every $j=2,\dotsc,N+1$, $\partial E_{j}$ does not contain any $x_{i}$.

###### Proof.

For $j=3,\dotsc,N+1$ let $r_{j}>0$ small enough such that

$x_{i}\notin B(x_{j},r_{j})\hskip 14.22636pt\text{for every $i=1,\dotsc,N$,
$i\neq j$.}$

Fixed any $j=3,\dotsc,N+1$, by a cardinality argument there must be a positive
real $t_{j}$ with $0<t_{j}<r_{j}$ and $\partial B(x_{j},t_{j})$ not containing
any $x_{i}$, $i\geq 1$. We take $E_{j}=B(x_{j},t_{j})$ for $j=3,\dotsc,N+1$.
Note that this choice fullfills the conditions (i), (ii) for $j=3,\dotsc,N+1$.
Finally, we take

$E_{2}=\mathbb{R}^{d}\setminus\left(\bigcup_{j=3}^{N+1}E_{j}\right)$

Clearly $x_{2}\in\mathring{E_{2}}$, and moreover the condition (ii) is
satisfied, since

$\partial E_{2}=\bigcup_{j=3}^{N+1}\partial E_{j}.$

∎

Consider the partition given by Lemma 6.1, and define the corresponding
partition of $\mathbb{N}$ given by $\mathbb{N}=A_{2}\cup\dotsb\cup A_{N+1}$,
where

$A_{j}=\left\\{i\in\mathbb{N}\left|\right.x_{i}\in E_{j}\right\\}.$

Next we consider, for every $j=2,\dotsc,{N+1}$ a threshold $n_{j}\geq 2$ large
enough such that, defining

$\epsilon_{j}=\sum_{\begin{subarray}{c}i\geq n_{j}\\\ i\in
A_{j}\end{subarray}}b_{i},$

then

$\epsilon_{2}+\dotsb+\epsilon_{N+1}<\min\left\\{b_{N+1},\frac{1}{N}-b_{1}\right\\}.$
(12)

This may be done since the series $\sum b_{i}$ converges, and hence for every
$j=2,\dotsc,{N+1}$ the series

$\sum_{i\in A_{j}}b_{i}$

is convergent.

For every $j=2,\dotsc,N+1$ define the following transport plan:

$P_{j}=N\left[\left(\sum_{i\in A_{j},i\geq
n_{j}}b_{i}\delta_{x_{i}}\right)\otimes\delta_{x_{2}}\otimes\dotsb\otimes\hat{\delta}_{x_{j}}\otimes\dotsb\otimes\delta_{x_{N+1}}\right]_{sym},$

and note that, by Lemma 2.1,

$\pi(P_{j})=\epsilon_{j}\sum_{\begin{subarray}{c}h=2\\\ h\neq
j\end{subarray}}^{N+1}\delta_{x_{h}}+\sum_{\begin{subarray}{c}i\geq n_{j}\\\
i\in A_{j}\end{subarray}}b_{i}\delta_{x_{i}}.$

Then let

$P_{\infty}=\sum_{j=2}^{N+1}P_{j},$

and observe that

$\pi(P_{\infty})=\sum_{j=2}^{N+1}\left(\sum_{\begin{subarray}{c}i=2\\\ i\neq
j\end{subarray}}^{N+1}\epsilon_{i}\right)\delta_{x_{j}}+\sum_{j=2}^{N+1}\sum_{\begin{subarray}{c}i\geq
n_{j}\\\ i\in A_{j}\end{subarray}}b_{i}\delta_{x_{i}}.$

Let now

$\tilde{b}_{i}=\left\\{\begin{array}[]{ll}\displaystyle
b_{i}-\sum_{\begin{subarray}{c}h=2\\\ h\neq
i\end{subarray}}^{N+1}\epsilon_{h}&\text{if $2\leq i\leq N+1$}\\\ 0&\text{if
$i\geq n_{j}$ and $i\in A_{j}$ for some $j=2,\dotsc,N+1$}\\\
b_{i}&\text{otherwise}.\end{array}\right.$

We are left to find a transport plan of finite cost with marginals

$\sigma+\sum_{i=1}^{\infty}\tilde{b}_{i}\delta_{x_{i}},$

which has indeed a finite number of atoms. Note that $\tilde{b}_{i}\geq 0$ for
every $i$, thanks to condition (12). Moreover, since $\tilde{b}_{1}=b_{1}$ and
$\tilde{b}_{j}\leq b_{j}$, then $\tilde{b}_{1}\geq\tilde{b}_{j}$ for every
$j\in\mathbb{N}$, as is used in what follows. If

$(N-1)\tilde{b}_{1}\leq\sum_{i=2}^{\infty}\tilde{b}_{i}$

we may conclude using Proposition 5.5. Otherwise, we proceed like in the proof
of Theorem 5.6, with $\\{\tilde{b}_{j}\\}$ replacing $\left\\{b_{j}\right\\}$.
At the final stage, it is left to check that

$N(\tilde{b}_{1}-\tilde{q}_{k+1})-\sum_{i=1}^{k}(\tilde{b}_{i}-\tilde{q}_{k+1})<1-\sum_{i=1}^{\infty}b_{i}=\left|\sigma\right|.$

Indeed this is true, since using the condition (12) one gets

$N(\tilde{b}_{1}-\tilde{q}_{k+1})-\sum_{i=1}^{k}(\tilde{b}_{i}-\tilde{q}_{k+1})=Nb_{1}-\sum_{i=1}^{\infty}b_{i}+N(\epsilon_{2}+\dotsc+\epsilon_{N+1})<1-\sum_{i=1}^{\infty}b_{i}.$

## References

  * [1] L. Ambrosio, N. Gigli and G. Savaré, “Gradient Flows in Metric Spaces and in the Space of Probability Measures”, Birkhäuser Verlag, Basel – Boston – Berlin (2005)
  * [2] U. Bindini, L. De Pascale, _Optimal transport with Coulomb cost and the semiclassical limit of Density Functional Theory_ , J. Éc. polytech. Math. 4 (2017), 909-934
  * [3] G. Buttazzo, T. Champion and L. De Pascale, _Continuity and estimates for multimarginal optimal transportation problems with singular costs_ , Appl. Math. Optim. (2017), 1-16
  * [4] G. Buttazzo, L. De Pascale and P. Gori-Giorgi, _Optimal-transport formulation of electronic density-functional theory_ , Phys. Rev. A (2012)
  * [5] M. Colombo, L. De Pascale and S. Di Marino, _Multimarginal optimal transport maps for 1-dimensional repulsive costs_ , Canad. J. Math. (2013), 350-368
  * [6] M. Colombo and S. Di Marino, _Equality between Monge and Kantorovich multimarginal problems with Coulomb cost_ , Ann. Mat. Pura Appl. (2013), 1-14
  * [7] C. Cotar, G. Friesecke and C. Klüppelberg, _Density functional theory and optimal transportation with Coulomb cost_ , Comm. Pure Appl. Math. 66 (2013), 548–599
  * [8] C. Cotar, G. Friesecke and C. Klüppelberg, _Smoothing of transport plans with fixed marginals and rigorous semiclassical limit of the Hohenberg-Kohn functional_ , arXiv:1706.05676 (2017)
  * [9] L. De Pascale, _Optimal transport with Coulomb cost. Approximation and duality_ , ESAIM Math. Model. Numer. Anal. 49 (2015), 1643-1657
  * [10] S. Di Marino, A. Gerolin and L. Nenna, _Optimal transportation theory for repulsive costs_ , Topoligal Optimization and Optimal Transport in the Applied Sciences (2017)
  * [11] W. Gangbo, A. Swiech, _Optimal maps for the multidimensional Monge-Kantorovich problem_ , Comm. Pure Appl. Math. 51 (1998), 23-45
  * [12] P. Gori-Giorgi, M. Seidl, _Density functional theory for strongly-interacting electrons: perspectives for physics and chemistry_ , Phys. Chem. Chem. Phys. 12 (2010), 14405-14419
  * [13] P. Gori-Giorgi, M. Seidl, G. Vignale, _Density-functional theory for strongly interacting electrons_ , Phys. Rev. Lett. 103 (2009), 166402-166405
  * [14] P. Hohenberg, W. Kohn, _Inhomogeneous electron gas_ , Phys. Rev. 136 (1964)
  * [15] M. Levy, _Universal variational functionals of electron densities, first-order density matrices, and natural spin-orbitals and solution of the v-representability problem_ , Proc. Nat. Acad. Sci. USA 76 (1979)
  * [16] M. Lewin, _Semi-classical limit of the Levy-Lieb functional in Density Functional Theory_ , arXiv:1706.02199 (2017)
  * [17] E. H. Lieb, _Density functionals for Coulomb systems_ , International Journal of Quantum Chemistry 24 (1983), 243-277
  * [18] B. Pass, _On the local structure of optimal measures in the multi-marginal optimal transportation problem_ , Calc. Var. Partial Differential Equations 43 (2012), 529-536

Ugo Bindini
Scuola Normale Superiore,
Piazza dei Cavalieri, 7
56127 Pisa - ITALY
<EMAIL_ADDRESS>