Franck Barthe
email: barthe@math.univ-toulouse.fr

Mokshay Madiman
email: madiman@udel.edu

Volumes of subset Minkowski sums and the Lyusternik region

Introduction

The Brunn-Minkowski-Lyusternik inequality is a cornerstone in a number of fields of mathematics-it appears in geometry as a route to the isoperimetric principle in Euclidean spaces, in algebraic geometry as a route to the Hodge inequality, in functional analysis as a tool in the asymptotic theory of Banach spaces due to the appearance of symmetric convex bodies as their unit balls, and in probability as the heart of the Prékopa-Leindler inequality that provides an efficient route to the concentration of measure phenomenon. It states that, for nonempty compact subsets A, B of R d ,

|A + B| 1 d ≥ |A| 1 d + |B| 1 d ,
where |A| denotes the volume (Lebesgue measure) of A. First developed for convex sets by Brunn and Minkowski, it was extended by Lyusternik [START_REF] Lusternik | Die Brunn-Minkowskische ungleichung fur beliebige messbare mengen[END_REF] to compact sets, and more generally to Borel sets. The survey [START_REF] Gardner | The Brunn-Minkowski inequality[END_REF] is an excellent introduction to the Brunn-Minkowski-Lyusternik inequality, its history, and its many ramifications and connections to other geometric and functional inequalities.

The fractional superadditivity property is defined in Section 2; it would have been a strict improvement of the inequality [START_REF] Artstein | Solution of Shannon's problem on the monotonicity of entropy[END_REF] for M sets when M > 2. It was observed in [START_REF] Bobkov | Fractional generalizations of Young and Brunn-Minkowski inequalities[END_REF] that Conjecture 1 holds for convex sets; thus the interest lay in extending this to general compact, and thence, Borel sets.

Conjecture 1 was motivated by analogies between the inequalities explored in this paper to Information Theory. The formal resemblance between inequalities in Information Theory and Convex Geometry was first noticed by Costa and Cover [START_REF] Costa | On the similarity of the entropy power inequality and the Brunn-Minkowski inequality[END_REF] but has since been extensively developed. For example, there now exist entropy analogues of the Blaschke-Santaló inequality [START_REF] Lutwak | Moment-entropy inequalities[END_REF], the reverse Brunn-Minkowski inequality [START_REF] Bobkov | Dimensional behaviour of entropy and information[END_REF][START_REF] Bobkov | Reverse Brunn-Minkowski and reverse entropy power inequalities for convex measures[END_REF], the Rogers-Shephard inequality [START_REF] Bobkov | On the problem of reversibility of the entropy power inequality[END_REF][START_REF] Madiman | Entropy bounds on abelian groups and the Ruzsa divergence[END_REF] and the Busemann inequality [START_REF] Ball | A reverse entropy power inequality for log-concave random vectors[END_REF]. Indeed, volume inequalities, entropy inequalities, and certain small ball inequalities can be unified using the framework of Rényi entropies [START_REF] Wang | Beyond the entropy power inequality, via rearrangements[END_REF][START_REF] Madiman | Rogozin's convolution inequality for locally compact groups[END_REF]; the surveys [START_REF] Dembo | Information-theoretic inequalities[END_REF][START_REF] Madiman | Forward and reverse entropy power inequalities in convex geometry[END_REF] may be consulted for much more in this vein. On the other hand, natural analogues in the Brunn-Minkowski theory of inequalities from Information Theory hold sometimes but not always [START_REF] Fradelizi | Some inequalities about mixed volumes[END_REF][START_REF] Artstein-Avidan | Remarks about mixed discriminants and volumes[END_REF][START_REF] Fradelizi | On the analogue of the concavity of entropy power in the Brunn-Minkowski theory[END_REF]. Another related set of results has to do with Schur-concavity of entropy or volume in various settings; see [START_REF] Madiman | Two remarks on generalized entropy power inequalities[END_REF] for details.

Define the entropy of a random vector X with density function f X (with respect to Lebesgue measure dx) as h(X) =f X (x) log f X (x)dx if the integral exists and -∞ otherwise (see, e.g., [START_REF] Cover | Elements of Information Theory[END_REF]). The entropy power of X is N (X) = exp{2h(X)/n}. The functional A → Vol n (A) 1/n in the geometry of compact subsets of R n , and the functional f X → N (X) in probability are analogues in the resemblance discussed above. The superadditivity property N (X+Y ) ≥ N (X)+N (Y ) for independent random vectors, which is called the Shannon-Stam entropy power inequality [START_REF] Shannon | A mathematical theory of communication[END_REF][START_REF] Stam | Some inequalities satisfied by the quantities of information of Fisher and Shannon[END_REF] is then the analogue of the Brunn-Minkowski-Lyusternik inequality. Fractional superadditivity of the entropy power was established in stages: by [START_REF] Artstein | Solution of Shannon's problem on the monotonicity of entropy[END_REF] for the leave-one-out case in a paper that was celebrated because it resolved a conjecture regarding the central limit theorem (simpler proofs were given by [START_REF] Madiman | The monotonicity of information in the central limit theorem and entropy power inequalities[END_REF][START_REF] Tulino | Monotonic decrease of the non-gaussianness of the sum of independent random variables: A simple proof[END_REF][START_REF] Shlyakhtenko | A free analogue of Shannon's problem on monotonicity of entropy[END_REF]), for a larger class of hypergraphs by [START_REF] Madiman | Generalized entropy power inequalities and monotonicity properties of information[END_REF], and finally in full by [START_REF] Madiman | Combinatorial entropy power inequalities: A preliminary study of the Stam region[END_REF], where the Stam region (which is like the Lyusternik region that we define and explore in this paper, but for entropy powers) was defined and explored. Conjecture 1 is the precise analogue in this dictionary of the fractional superadditivity of entropy power established by [START_REF] Madiman | Combinatorial entropy power inequalities: A preliminary study of the Stam region[END_REF].

Therefore, it was rather surprising when [START_REF] Fradelizi | Do Minkowski averages get progressively more convex?[END_REF] constructed a counterexample to establish that Conjecture 1 fails in dimension 12 and above. This provides another example where the analogy between Euclidean geometry and Information Theory breaks down. The goal of this note is to show that, in fact, the fractional superadditivity conjecture of [START_REF] Bobkov | Fractional generalizations of Young and Brunn-Minkowski inequalities[END_REF] does hold in dimension 1. Moreover, a variant of Conjecture 1 does hold in general dimension-namely, the volume functional itself (without an exponent) is fractionally superadditive with respect to Minkowski summation on the class of compact sets in R d . This note is organized as follows. In Section 2, we describe our main results carefully, giving all necessary definitions along the way. Section 3 is devoted to proving the theorems described in Section 2specifically, Sections 3.1 to 3.4 prove in stages the fractional superadditivity statement in Theorem 2, which is the technically most demanding part of this note, while Section 3.5 proves the key lemma underlying the proof of Theorem 3, and Section 3.6 proves Theorem 4. We supplement this main part of the paper with some discussion and open questions in Section 4, and with some reasons why we believe fractional superadditivity is an important structural property of set functions and therefore worthy of study in the Appendix (Section A).

Main Results

Let A 1 , A 2 , . . . , A M be compact sets in R d . We write [M ] for the index set {1, 2, . . . , M }, and ∅ for the empty set. For any nonempty S ⊂ [M ], define the Minkowski subset sum

A S = i∈S A i .
We are interested in the volumes of the subset sums A S (denoted |A S |), which leads naturally to the following objects of study.

Definition. Let K d,M be the collection of all M -tuples A = (A 1 , . . . , A M ) of nonempty compact subsets A i of R d . Define the set function ν A : 2 [M] → R + := [0, ∞) by ν A (∅) = 0 and ν A (S) = i∈S A i ( 2
)
for nonempty S ⊂ [M ]. The d-dimensional Lyusternik region is the subset of (R + ) 2 M given by Λ d (M ) = {ν A : A ∈ K d,M }.
We name these regions after L. A. Lyusternik in honor of his pioneering role [START_REF] Lusternik | Die Brunn-Minkowskische ungleichung fur beliebige messbare mengen[END_REF] in the study of volumes of Minkowski sums, especially when dealing with sets that are not necessarily convex. Clearly, any inequality that relates volumes of different subset sums gives a bound on the Lyusternik region. Conversely, knowing the Lyusternik region is equivalent, in principle, to knowing all volume inequalities that hold for Minkowski sums of general collections of compact sets, and all that do not.

Let (G, β) be a weighted hypergraph on a set T , i.e., a collection G of subsets of T (which we may think of as "hyperedges"), together with a weight function β : G → R + that assigns weight β S = β(S) to each set S in G. We say that (G, β) is a fractional partition of T if for each i ∈ T , we have S∈G: i∈S β S = 1. These conditions can be phrased as a single one, using the characteristic functions 1 S : T → {0, 1}, as

S∈G β S 1 S = 1 T = 1. We say that a set function v : 2 [M] → R + is fractionally superadditive if for every subset T ⊂ [M ] v(T ) ≥ S∈G β S v(S) (3)
holds for every fractional partition (G, β) of T . Write Γ F SA (M ) for the class of all fractionally superadditive set functions v with v(φ) = 0. The set function v : 2

[M] → R + is said to be supermodular if v(S ∪ T ) + v(S ∩ T ) ≥ v(S) + v(T )
for all sets S, T ⊂ [M ]. Write Γ SM (M ) for the class of all supermodular set functions v with v(φ) = 0. It is known [START_REF] Ollagnier | Filtre moyennant et valeurs moyennes des capacités invariantes[END_REF][START_REF] Madiman | Information inequalities for joint distributions, with interpretations and applications[END_REF] that for n ≥ 3, Γ SM (M ) Γ F SA (M ), i.e., every supermodular set function is fractionally superadditive but not vice versa. For n = 2, given the limited availability of subsets, it is easy to see that Γ SM (2) = Γ F SA [START_REF] Artstein-Avidan | Remarks about mixed discriminants and volumes[END_REF], and both are equal to the class of superadditive set functions.

We start with two straightforward observations that set the stage for further discussion. When d = 1, this can be rephrased as Λ 1 (2) = Γ SM (2) = Γ F SA [START_REF] Artstein-Avidan | Remarks about mixed discriminants and volumes[END_REF].

Proof. The Brunn-Minkowski inequality states that every nonempty compact subsets of

A 1 , A 2 of R d verify |A 1 + A 2 | 1 d ≥ |A 1 | 1 d + |A 2 | 1 d
; this proves the inclusion of Λ d (2) in the above set. To see the reverse inclusion, we need to show that for any triple (a, b, c) ∈ R 3 + with c

1 d ≥ a 1 d + b 1 d , there exists a pair of compact sets A 1 , A 2 in R with |A 1 | = a, |A 2 | = b and |A 1 + A 2 | = c.
We start with the case when a or b is strictly positive. Without loss of generality (thanks to the invariance property mentioned in Observation 1), we may assume a > 0, b ≥ 0 and c

1 d ≥ a 1 d + b 1 d . We may find q ∈ N and r ∈ [0, a 1 d ) such that c -a 1 d + b 1 d d a d-1 d = qa 1 d + r.
Let e 1 be the first vector in the canonical basis of

R d . Consider A 1 = [0, a 1 d ] d and A 2 = [-b 1 d , 0] d ∪ q i=1 ia 1 d e 1 ∪ qa 1 d + r e 1 ,
(we understand the union within parentheses to be empty when q = 0). Then

A 1 + A 2 = [-b 1 d , a 1 d ] d ∪ q i=1 [ia 1 d , (i + 1)a 1 d ]} ∪ [qa 1 d + r, (q + 1)a 1 d + r] × [0, a 1 d ] d-1 = [-b 1 d , a 1 d ] d ∪ [a 1 d , (q + 1)a 1 d + r] × [0, a 1 d ] d-1 . Consequently |A 1 | = a, |A 2 | = b and |A 1 + A 2 | = a 1 d + b 1 d d + (qa 1 d + r)a d-1 d
= c; thus we are done. It remains to deal with triples of the form (0, 0, c) with c ≥ 0. By the cone property of Observation 1 it is enough to deal with one c > 0. This is very easy in dimension d ≥ 2, by considering lower dimensional cubes A 1 = [0, 1] × {0} d-1 , A 1 = [0, 1] d-1 × {0}, which have measure 0 and sum up to the full cube [0, 1] d . In dimension 1, we can still use sets of lower dimensions: consider the Cantor ternary set C = ∩ n∈N E n , where E 0 = [0, 1] and for all n ≥ 0,

E n+1 = 1 3 E n ∪ 2 3 + 1 3 E n .
It is classical that this compact set has measure zero, and contains all numbers which can be expressed as k≥1 x k 3 -k for some sequence (x k ) taking values in {0, 2} (in other words, numbers in [0, 1] admitting an expansion in base 3 involving only digits 0 and 2). As a consequence, 1 2 C contains numbers in [0, 1] admitting an expansion in base 3 involving only digits 0 and 1, and it is clear that

[0, 1] ⊂ C + 1 2 C ⊂ 0, 3 2 .
We have put forward two sets of measure 0, with a sum of positive measure. This completes the proof of Observation 2.

Observation 2 gives a complete description of the Lyusternik region for the case where one has only two sets. This naturally gives rise to the question that is the main focus of this paper: what is the relationship between Λ d (M ) on the one hand, and Γ F SA (M ) or Γ SM (M ) on the other, when M ≥ 3?

The following statement sums up our contribution to this problem:

Theorem 1. For any d ∈ N * and M ≥ 3, • Λ d (M ) Γ F SA (M ),
• Λ d (M ) and Γ SM (M ) have nonempty intersection but neither is a subset of the other.

Proof. The inclusion Λ d (M ) ⊂ Γ F SA (M ) comes from the inequality in Theorem 2 below. The fact that the inequality is strict is a consequence of the second item, since Γ SM (M ) ⊂ Γ F SA (M ).

Next we turn to the proof of the second part of the theorem. The null sequence is obviously in Λ d (M ) ∩ Γ SM (M ). It was observed in [START_REF] Fradelizi | The convexification effect of Minkowski summation[END_REF] that the volume is not supermodular already in dimension 1. Indeed, they considered the sets A = {0, 1} and

B = C = [0, 1]. Then, |A + B + C| + |A| = 3 < 4 = |A + B| + |A + C|.
Consequently it is clear that for any M ≥ 3, Λ 1 (M ) Γ SM (M ). This example can be adapted to cover the case of dimensions d ≥ 2: let k ∈ N * , and consider

A = [k] d = {0, . . . , k} d , B = C = [0, 1] d . Plainly A + B = A + C = [0, k + 1] d and A + B + C = [0, k + 2] d and for k large enough |A + B + C| + |A| = (k + 2) d < 2(k + 1) d = |A + B| + |A + C|.
Eventually, we need to show that volumes of partial sums cannot reach all supermodular set functions. Consider the set function α : 2 [M] → R + defined by α(S) = Card(S), which is clearly supermodular. If α was in Λ d (M ), there would be compacts sets in R d with, in particular,

|A i | = Card({i}) = 1 and |A 1 + A 2 | = Card({1, 2}) = 2. In dimension d ≥ 2 this is impossible since the Brunn-Minkowski inequality ensures that |A 1 + A 2 | ≥ |A 1 | 1 d + |A 2 | 1 d d = 2 d > 2.
To deal with dimension d = 1, we consider the set function

β defined by β([M ]) = M +1 = α([M ])+1 and for S [M ], β(S) = Card(S) = α(S)
. It is still supermodular, since increasing the value of a supermodular function on the full set only improves the supermodularity property. If β was in Λ 1 (M ), we would have compact sets in R with |A i | = 1, |A i + A j | = 2 for i = j. Therefore A i , A j are an equality case of the one-dimensional Brunn-Minkowski inequality, which ensures that they are intervals (see, e.g., [START_REF] Schneider | Convex bodies: the Brunn-Minkowski theory[END_REF]Theorem 7

.1.1]), of length 1. This implies that |A 1 + • • •+ A M | = M < β(M ). Hence β ∈ Λ 1 (M ).
Our main result is the following fractional superadditivity property:

Theorem 2. For any fractional partition (G, β) of [M ], A 1 + • • • + A M ≥ S∈G β S i∈S A i (4)
holds for non-empty compact subsets A 1 , . . . , A M of R d . In dimension d = 1, the inequality is an equality when all sets S ⊂ [M ] with β S > 0 satisfy that i∈S A i is an interval.

We note that it is possible to have equality in (4) for non-convex sets-for example, one can consider 3 2 ], and the leave-one-out hypergraph (i.e., G = {{1, 2}, {2, 3}, {3, 1}} is all sets of cardinality 2, and each β S = 1

A 1 = A 2 = A 3 = [0, 1 2 ] ∪ [1,
2 ). Theorem 2 may be compared with the conjecture made by Bobkov et al. [START_REF] Bobkov | Fractional generalizations of Young and Brunn-Minkowski inequalities[END_REF]Conjecture 3.1], which proposed that

A 1 + • • • + A M 1 d ≥ S∈G β S i∈S A i 1 d , (5)
for all compact sets, and verified the same for convex sets. The motivation of [START_REF] Bobkov | Fractional generalizations of Young and Brunn-Minkowski inequalities[END_REF] came from the fact that the conjectured inequality would have provided a fundamental refinement of the Brunn-Minkowski inequality for 3 or more sets. It was proved in [START_REF] Fradelizi | Do Minkowski averages get progressively more convex?[END_REF] that even a very special case of the inequality (5) (involving a particular fractional partition and all sets A i being copies of the same compact set A) fails in dimension 12 and above; nonetheless, Theorem 2 shows in particular that the conjectured inequality ( 5) is true for all compact sets in dimension 1.

In fact, we also have a positive result in general dimension for a special class of sets.

Theorem 3. Let (G, β) be a fractional partition of [M ]. Fix k ≤ M . For each i ∈ [k], suppose C i,1 , . . . , C i,M are nonempty compact convex subsets of R di . For each k+1 ≤ i ≤ L, suppose C i,1 , . . . , C i,M are non-empty compact subsets of R. Let A j = C 1,j × . . . × C L,j , so that each A i is a compact subset of R d , with d = L -k + k i=1 d i . Then A 1 + • • • + A M 1 d ≥ S∈G β S i∈S A i 1 d .
Proof. Combining Lemma 3 (which we will prove in Section 3.5) with our main result (fractional superadditivity for d = 1) and the fractional Brunn-Minkowski inequality for convex bodies observed in [START_REF] Bobkov | Fractional generalizations of Young and Brunn-Minkowski inequalities[END_REF], we obtain Theorem 3.

It is natural to ask if the phenomena investigated thus far for Minkowski sums in finite-dimensional real vector spaces also have analogues in a discrete setting, i.e., for Minkowski sums of finite subsets of a discrete group, with volume replaced by cardinality. One would expect such discrete analogues to be relevant to the field of additive combinatorics, as they are related to the Cauchy-Davenport inequality. We observe that an analogue does hold in the group of integers, extending a result of Gyarmati, Matolcsi and Ruzsa [START_REF] Gyarmati | A superadditivity and submultiplicativity property for cardinalities of sumsets[END_REF].

Theorem 4. Let (G, β) be a fractional partition of [M ]. Let A 1 , . . . , A M be non-empty finite subsets of Z. Then A 1 + • • • + A M -1 ≥ S∈G β S i∈S A i -1 ,
where for S ⊂ Z, |S| denotes the cardinal of S. The inequality is an equality when there exists ρ ∈ N such that all S ⊂ [M ] with β S > 0 verify that i∈S A i is an arithmetic progression of increment ρ. This is proved in Section 3.6. Note that the leave-one-out case of Theorem 4 was proved by [START_REF] Gyarmati | A superadditivity and submultiplicativity property for cardinalities of sumsets[END_REF]. For other related inequalities, the reader may consult [START_REF] Madiman | Information-theoretic inequalities in additive combinatorics[END_REF][START_REF] Madiman | Entropy and set cardinality inequalities for partitiondetermined functions[END_REF][START_REF] Wang | A lower bound on the Rényi entropy of convolutions in the integers[END_REF][START_REF] Madiman | Rényi entropy inequalities for sums in prime cyclic groups[END_REF][START_REF] Madiman | Majorization and Rényi entropy inequalities via Sperner theory[END_REF].

Proofs 3.1 A reduction to regular fractional partitions

A first step in the proof is to reduce to regular fractional partitions. First note that fractional partitions can be viewed as maps defined on subsets of [M ], β : 2 [M] → [0, 1] where subsets with non-zero coefficients will give the collection G of subsets. The fractional partition condition becomes

S⊂[M] β S 1 S = 1.
Obviously the term corresponding to S = ∅ is superfluous, so that we may represent the set of possible fractional partitions of [M ] as follows:

F M =    (β S ) ∅⊂S⊂[M] ; ∀S, β S ≥ 0 and ∀i ∈ [M ], S; i∈S β S = 1    .
Note that the above conditions ensure that β S ≤ 1. This representation thus shows that F M is a compact polyhedral convex set. Any of its extreme points β is the unique point in F M satisfying β S = 0 for all S in a certain collection G ⊂ 2 [M] \ {∅}. This means that (β S ) S ∈G is the unique solution of a system of the form: for all i ∈ [M ], S ∈G; i∈S β S = 1. Hence this system is invertible and since it has rational coefficients, we get that the non-zero coefficients β S are rational. Hence, we have shown1 that extreme fractional partitions only involve rational coefficients β S .

In order to prove Inequality (4) for all fractional partitions (a convex condition on β), it is enough to prove it for the extreme points of the set of fractional partitions. In particular it is enough to deal with partitions with β S ∈ Q for all S. Writing these coefficients as fractions with the same denominator q and allowing to repeat sets (as many times as the numerator of their coefficient by β), we can reduce to the following simpler setting: S 1 , . . . , S s are subsets of [M ] and verify s j=1

1 Sj = q1, (6)
or equivalently, for each i ∈ [M ], there are exactly q indices j such that i ∈ S j . This means that [M ] is covered exactly q times by the sets (S j ) 1≤j≤s . Observe that because of repetitions, we use a finite sequence of sets, rather than a collection of sets. Under the above assumption (6), our task is to show that

q A 1 + • • • + A M ≥ s j=1 i∈Sj A i .

Starting with examples

Gyarmati, Matolcsi and Ruzsa [START_REF] Gyarmati | A superadditivity and submultiplicativity property for cardinalities of sumsets[END_REF] have dealt (for subsets of Z), with the "leave-one-out" case where the fractional partition is made of all the subsets of [M ] with cardinality M -1 and equal weights. Their argument is based on decompositions of the small sums-sets and a double counting argument. As noted in [START_REF] Fradelizi | Do Minkowski averages get progressively more convex?[END_REF] it also works for subsets of R. As a warm-up we present the simplest non-trivial case of M = 3, for subsets of R and the fractional partition

1 {1,2,3} = 1 2 1 {1,2} + 1 {2,3} + 1 {3,1} .
Let A 1 , A 2 , A 3 be three non-empty compact subsets of R. Assume that min(A i ) = 0 and denote a i := max(A i ). Since 0 belongs to all A i 's, the following inclusions hold:

(A 1 + A 2 ) ∪ a1+a2< (a 1 + A 2 + A 3 ) ⊂ A 1 + A 2 + A 3 (7) (A 2 + A 3 ) ≤a2 ∪ (A 1 + a 2 + A 3 ) ⊂ A 1 + A 2 + A 3 ,
where t< S := S ∩ (t, +∞) and S ≤t := S ∩ (-∞, t]. By construction the unions are essentially disjoint (sets intersect in at most one point), hence passing to lengths and summing up the corresponding two inequalities gives

2|A 1 + A 2 + A 3 | ≥ |A 1 + A 2 | + | a1+a2< (a 1 + A 2 + A 3 )| + |(A 2 + A 3 ) ≤a2 | + |A 1 + a 2 + A 3 | = |A 1 + A 2 | + | a2< (A 2 + A 3 )| + |(A 2 + A 3 ) ≤a2 | + |A 1 + A 3 | = |A 1 + A 2 | + |A 2 + A 3 | + |A 1 + A 3 |
One can cook up by hand such decompositions for slightly more complicated fractional partitions. In order to explain our strategy for general regular partitions, let us put forward some features of the above decomposition. Since this is only meant to explain where our forthcoming formal proof comes from, we do not try to give formal definitions.

We shall say that and element i ∈ [M ] is covered by a term in the above decompositions (i.e. a truncated sum-set), if this term contains a translate of A i (or rather of A i \ {0, a i } and this should be true regardless of the actual values of the sets. This is actually a property of the formula rather than of the sets).

For instance A 1 + A 2 covers 1 since A 1 ⊂ A 1 + A 2 (for all A i 's). It also covers 2, but not 3. The term a1+a2< (a 1 + A 2 + A 3 ) covers 3 since it contains a 1 + a 2 + A 3 (more precisely a 1 + a 2 + A 3 \ {0}). It does not cover 1, neither 2.

If we rewrite the decompositions [START_REF] Bobkov | On the problem of reversibility of the entropy power inequality[END_REF] and underline in each term the indices which it covers, we get:

(A 1 + A 2 ) ∪ a1+a2< (a 1 + A 2 + A 3 ) ⊂ A 1 + A 2 + A 3 (8) (A 2 + A 3 ) ≤a2 ∪ (A 1 + a 2 + A 3 ) ⊂ A 1 + A 2 + A 3 , (9)
we observe that each decomposition covers every index once. We can encode this on the incidence matrix of the regular partition (columns correspond to elements i ∈ [M ] and lines to the sets in the partition):

for each decomposition we connect the couples (i, S) where i is covered by a term involving a translation of k∈S A k . For the first line (8) we connect (1, {1, 2}) to (2, {1, 2}) and to (3, {2, 3}). As we observed that all indices are covered this line is a graph of a function on [M ] = {1, 2, 3}. For (9) we connect (1, {1, 3}) to (2, {, 2, 3}) and to (3, {1, 3}). We get Figure 1.

Reading this simple figure from bottom to top, one can recover the decompositions (7): the bottom graph (in blue) corresponds to (8); again we read by considering lines (corresponding to sets) from bottom up: we use A 1 + A 2 to cover 1 and 2, and then A 2 + A 3 to cover 3, but we truncate it from below at a 1 + a 2 (corresponding to 1 and 2 being already covered) for disjointness. Next we pass to the upper graph, and consider sets starting from below: the first relevant one is A 2 + A 3 which we use to cover 2 only, so we truncate it from above at a 2 . Next we use A 1 + A 3 , translated by a 2 (note that the translation corresponds to the previously covered index).

The main feature of the figure is that it contains the graphs of two functions on {1, 2, 3} which do not cross. Since the partition is regular, they are uniquely determined by this property.

Let us try this reverse engineering approach in a more intricate situation:

31 [5] = 1 {2,3} + 1 {1,2,4} + 1 {1,2,4,5} + 1 {1,3,5} + 1 {3,4,5} .
We start with plotting the incidence table of this fractional partition in Figure 2 and we draw the corresponding non-crossing graphs. Next we use them in order to build decompositions of sum-sets.

We start with the bottom graph over [START_REF] Bobkov | Reverse Brunn-Minkowski and reverse entropy power inequalities for convex measures[END_REF] (in blue). We consider the sets of the partition starting from the botton and at each step we want to cover exactly the indices 1 ≤ i ≤ 5 which are on the set and on the graph:

• The first set is {2, 3} it is entirely on the blue graph: we need to cover 2 and 3, so can simply take A 2 + A 3 . We could write (A 2 + A 3 ) ≤a2+a3 even if the truncation is useless here, in order to stress our goal: cover 2 and 3, but nothing more.

• We move up and consider the next set {1, 2, 4}. Our goal is to cover the indices 1 and 4 (which correspond to the dots on the graph at the height of {1, 2, 4}), using A 1 + A 2 + A 4 translated by as many a i as we can, for previously covered indices i. The truncation from below is imposed by the upper bound on the previous set, the one from above by the fact that we do not want to cover more indices than 1 and 4 (it is surperfluous in this case). The only choice is

a2+a3< (A 1 + A 2 + a 3 + A 4 ) ≤a1+a2+a3+a4 .
• The last dot on the blue graph in at the third line, so we have to use the set {1, 2, 4, 5} in order to cover the last uncovered index 5. By similar considerations we are led to choose:

a1+a2+a3+a4< (A 1 + A 2 + a 3 + A 4 + A 5 ).
Summing up, using the blue line, we have obtained the following disjoint union inside the full sum set:

(A 2 + A 3 ) a2+a3< (A 1 + A 2 + a 3 + A 4 ) a1+a2+a3+a4< (A 1 + A 2 + a 3 + A 4 + A 5 ) ⊂ 5 i=1 A i (10)
Next we deal with the second graph (in red).

• The first relevant set (starting from bottom) is {1, 2, 4} and only the point (2, {1, 2, 4}) is on the red graph. So we select (A 1 + A 2 + A 4 ) ≤a2

• Going up one set, the points (1, {1, 2, 4, 5}) and (4, {1, 2, 4, 5}) are on the red graph so we need to use {1, 2, 4, 5} to cover 1 and 4. This leads to

a2< (A 1 + A 2 + A 4 + A 5 ) ≤a1+a2+a4 .
• Eventually considering the set {1, 3, 5} which meets the red graph at 3 and 5 we choose

a1+a2+a4< (A 1 + a 2 + A 3 + a 4 + A 5 ).
Summing up, the red line leads to the inclusion

(A 1 +A 2 +A 4 ) ≤a2 a2< (A 1 +A 2 +A 4 +A 5 ) ≤a1+a2+a4 a1+a2+a4< (A 1 +a 2 +A 3 +a 4 +A 5 ) ⊂ 5 i=1 A i (11)
The same procedure for the upper graph (in black) gives

(A 1 + A 2 + A 4 + A 5 ) ≤a2 (A 1 + a 2 + A 3 + A 5 ) ≤a1+a2 (a 1 + a 2 + A 3 + A 4 + A 5 ) ⊂ 5 i=1 A i (12)
Eventually, passing to length of sets in the inclusions [START_REF] Cover | Elements of Information Theory[END_REF], [START_REF] Dembo | Information-theoretic inequalities[END_REF], [START_REF] Figalli | Quantitative stability for sumsets in R n[END_REF], adding everything up and collecting the pieces of the various sum-sets gives

3 5 i=1 A i ≥ |A 2 + A 3 | + |A 1 + A 2 + A 4 | + |A 1 + A 2 + A 4 + A 5 | + |A 1 + A 3 + A 5 | + |A 3 + A 4 + A 5 |.
After these examples, we are ready for the general case.

Proof for the real line

Let us proceed to some simplifications and introduce concise notation. First of all, by translation invariance of Lebesgue's measure, we can translate all the sets and assume that for all i ∈ [M ], min A i = 0. Then we denote a i := max A i . Viewing A as a function from [M ] to 2 R and a as a function from [M ] to R + , we write With this notation our goal is to show that

q [M] A ≥ s j=1 Sj A . ( 13
)
Our proof of this inequality will rely on the arbitrary choice of an order of the sets (which was already made in the notation (S j ) 1≤j≤s ).

By the q-covering hypothesis, each i ∈ [M ] belongs to exactly q of the sets (S j ) s j=1 . Hence there are indices

1 ≤ h 1 (i) < h 2 (i) < • • • < h q (i) ≤ s
such that i belongs to the sets having these indices, and to these sets only: i ∈ S h k (i) for all k with 1 ≤ k ≤ q. Hence, we have built q functions h 1 , . . . , h k from [M ] to [s]. They will play a central role in the argument. For each of these functions, we prove a lower bound on the length of the full sum [M] A:

Lemma 1. Let k ∈ [q]
be an integer between 1 and q. Then

s j=1     Sj A + h -1 k ([1,j-1])\Sj a   ∩   h -1 k ([1,j-1]) a ; h -1 k ([1,j]) a     ⊂ [M] A, ( 14
)
where the union is disjoint. Hence, passing to lengths of sets:

s j=1   Sj A + h -1 k ([1,j-1])\Sj a   ∩   h -1 k ([1,j-1]) a ; h -1 k ([1,j]) a   ≤ [M] A . ( 15
)
Observe that quite a few of the above sets can be empty. For instance when j = 1, [1, j -1] = ∅ and

h -1 k ([1,j-1]
) a = 0 as a sum on the empty set. More importantly, when j does not belong to the range of h k the interval

h -1 k ([1,j-1]) a ; h -1 k ([1,j]) a is also empty. Proof. Since for all i ∈ [M ], 0 ∈ A i and a i ∈ A i it is plain that Sj A + h -1 k ([1,j-1])\Sj a ⊂ [M]
A, hence the inclusion is proved. The fact that the union is disjoint comes from the disjointness of the intervals

  h -1 k ([1,j-1]) a ; h -1 k ([1,j]) a   .
Indeed, since a i ≥ 0,

j 1 ≤ j 2 implies that h -1 k ([1,j1]) a ≤ h -1 k ([1,j2]) a.
In order to prove the fractional inequality (13), we sum up the inequalities provided by the above lemma, for k ranging from 1 to q. Permuting sums, we obtain

q [M] A ≥ s j=1 q k=1   Sj A + h -1 k ([1,j-1])\Sj a   ∩   h -1 k ([1,j-1]) a ; h -1 k ([1,j]) a   = s j=1   q k=1 Sj A ∩   h -1 k ([1,j-1])∩Sj a ; h -1 k ([1,j])\(h -1 k ([1,j-1])\Sj ) a     Using in the first place that B \ (C \ D) = (B \ C) ∪ (B ∩ D)
, and then the inclusion h -1 k ({j}) ⊂ S j (which follows from the definitions), we get that

h -1 k ([1, j]) \ (h -1 k ([1, j -1]) \ S j ) = h -1 k ({j}) ∪ (h -1 k ([1, j]) ∩ S j ) = h -1 k ([1, j]) ∩ S j . Hence we have shown that q [M] A ≥ s j=1   q k=1 Sj A ∩   h -1 k ([1,j-1])∩Sj a ; h -1 k ([1,j])∩Sj a     (16)
In order to combine the terms in the inner sum, we need some observations on the end-points of the various intervals.

Lemma 2. Let 1 ≤ j ≤ s and 1 ≤ k ≤ q -1 be integers. Then

1. h -1 q [1, j -1] ∩ S j = ∅ 2. h -1 1 [1, j] ∩ S j = S j 3. h -1 k+1 [1, j] ∩ S j = h -1 k [1, j -1] ∩ S j
Proof. The first point is obvious when j

= 1 since [1, j -1] = ∅ in that case. If j ≥ 1, and if i ∈ h -1 q [1, j -1] ∩ S j then h q (i) ≤ j -1.
Therefore, by definition the q sets to which i belongs have indices h 1 (i) < • • • < h q (i) ≤ j -1. This contradicts the fact that i ∈ S j .

To prove the second point, it is enough to show that

S j ⊂ h -1 1 [1, j]
. This is also very simple: if i ∈ S j then by definition there exists 1 ≤ ℓ ≤ q such that j = h ℓ (i). Therefore 1

≤ h 1 (i) ≤ h ℓ (i) = j.
Let us address the third point, by establishing inclusions in both directions. First, assume that i ∈ S j and h k+1 (i) ≤ j. By definition h k (i) < h k+1 (i). Since these are integer numbers,

h k (i) ≤ h k+1 (i) -1 ≤ j -1. This proves that h -1 k+1 [1, j] ∩ S j ⊂ h -1 k [1, j -1] ∩ S j .
Conversely, assume that i ∈ S j and h k (i) ≤ j -1. Since i belongs to S j there exists ℓ such that

h ℓ (i) = j. It follows that h k (i) < h ℓ (i) = j. Since t → h t (i) is strictly increasing, we can deduce that k < ℓ, that is k+1 ≤ ℓ. Consequently h k+1 (i) ≤ h ℓ (i) = j. Thus we have shown that i ∈ h -1 k+1 [1, j] ∩S j .
The proof of the lemma is complete.

Let us explain how to conclude the proof, resuming at [START_REF] Fradelizi | The convexification effect of Minkowski summation[END_REF]. By the latter lemma,

  h -1 q ([1,j-1])∩Sj a ; h -1 q ([1,j])∩Sj a   =   ∅ a ; h -1 q ([1,j])∩Sj a   =   0 ; h -1 q ([1,j])∩Sj a   ,
and for all k such that 1

≤ k ≤ q -1   h -1 k ([1,j-1])∩Sj a ; h -1 k ([1,j])∩Sj a   =    h -1 k+1 ([1,j])∩Sj a ; h -1 k ([1,j])∩Sj a    .
Recalling h k < h k+1 , it is then clear that the above q intervals are disjoint, and that their union is

  0 ; h -1 1 ([1,j])∩Sj a   =   0 ; Sj a   ,
where we have used the second point of the lemma in the last step. Using this information, we may rewrite [START_REF] Fradelizi | The convexification effect of Minkowski summation[END_REF] as

q [M] A ≥ s j=1 Sj A ∩ 0 ; Sj a (17)
Recall that

A i ⊂ [min(A i ), max(A i )] = [0, a i ],
hence Sj A ⊂ 0 ; Sj a and actually it contains 0. A point being Lebesgue negligeable,

Sj A ∩ 0 ; Sj a = Sj A
and the fractional inequality is established.

Eventually we check the sufficient condition for equality claimed in Theorem 2. Without loss of generality we may assume that for all S, β S > 0 (otherwise we remove the sets from the fractional partition) and that min

(A i ) = 0, max(A i ) = a i . Summing up the inclusions {0, a i } ⊂ A i ⊂ [0, a i ] gives for all S ⊂ [M ], 0, S a ⊂ S A ⊂ 0, S a .
Since by hypothesis S A is an interval for S ∈ G, we get | S A| = i∈S a i . Hence, using the fractional partition,

S∈G β S S A = S∈G β S i∈S a i = M i=1 a i   S∈G;i∈S β S   = M i=1 a i .

Moreover the above inclusion implies that |

[M] A| ≤ M i=1 a i = S∈G β S S
A , which should be combined to the general inequality | [M] A| ≥ S∈G β S S A in order to get equality.

Extension to higher dimensions

A 1 + • • • + A M ≥ S∈G β S i∈S A i ,
where for |S| denotes the d-dimensional Lebesgue measure.

Proof. As before, it is enough to deal with the regular case. On each compact set A i the first coordinate function π (defined for x ∈ R d by π(x) = x 1 ) achieves its maximum at a point a i ∈ A i . Since our problem is invariant by translation, we may assume without loss of generality that the minimum of x → x 1 on A i is achieved at the origin. So {0, a i } ⊂ A i and

A i ⊂ {x ∈ R d ; x 1 ∈ [0, (a i ) 1 ]}
, where (a i ) 1 is the first coordinate of a i . In other words

A i ⊂ π -1 [0, π(a i )] ,
and their boundaries meet at least at 0 and a i . The statement of Lemma 1 should be modified by replacing the intervals

  h -1 k ([1,j-1]) a ; h -1 k ([1,j]) a   by the slabs π -1     h -1 k ([1,j-1]) π(a) ; h -1 k ([1,j]) π(a)     .
The rest of the proof is the same.

We remark that the idea here follows [START_REF] Fradelizi | The convexification effect of Minkowski summation[END_REF], where a similar approach is used for the leave-one-out case.

Cartesian products

The next simple lemma allows combining fractional superadditivity results for volumes:

Lemma 3. Let d 1 , d 2 be positive integers and p, q > 0 For i ∈ [M ], let A i ⊂ R d1 and B i ⊂ R d2 be non-empty compact sets. Let (β S ) S⊂[M] be non-negative numbers and assume that we have the following two volume inequalities:

i∈[M] A i 1 p d1 ≥ S β S i∈S A i 1 p d1 and i∈[M] B i 1 q d2 ≥ S β S i∈S B i 1 q d2
Then the cartesion product sets

A i × B i ∈ R d1+d2 satisfy i∈[M] (A i × B i ) 1 p+q d1+d2 ≥ S β S i∈S (A i × B i ) 1 p+q d1+d2 . Proof. Observe that i∈S (A i × B i ) = i∈S A i × i∈S B i .
Thus by Hölder's inequality

S β S i∈S (A i × B i ) 1 p+q = S β S i∈S A i 1 p+q i∈S B i 1 p+q ≤ S β S i∈S A i 1 p p p+q S β S i∈S B i 1 q q p+q ≤   i∈[M] A i 1 p   p p+q   i∈[M] B i 1 q   q p+q = i∈[M] (A i × B i ) 1 p+q

Proof for the integers

The argument is the same with minor changes. Again we translate the sets in order to have min A i = 0 and set a i := max A i ∈ Z. Then we observe that the set on the left-hand side of ( 14) is included in

  0 ; h -1 k ([1,s]) a   =   0 ; [M]
a   so it does not contain 0, the minimal element of [M] A. So we may improve on ( 14):

s j=1     Sj A + h -1 k ([1,j-1])\Sj a   ∩   h -1 k ([1,j-1]) a ; h -1 k ([1,j]) a     ⊂ [M] A \ {0}, (18)
Taking cardinals gives

s j=1   Sj A + h -1 k ([1,j-1])\Sj a   ∩   h -1 k ([1,j-1]) a ; h -1 k ([1,j]) a   ≤ [M] A -1. (19)
Then we follow the same line of reasoning and get instead of (17):

q   [M] A -1   ≥ s j=1 Sj A ∩ 0 ; Sj a = s j=1   Sj A -1   , (20)
since min Sj A = 0 and max Sj A = Sj a. This concludes the proof in the regular case. The general case follows.

Eventually we check the sufficient condition for equality. Without loss of generality, we assume that for all S, β S > 0 and that min(A i ) = 0, max(A i ) = a i . Summing up the inclusions {0,

a i } ⊂ A i ⊂ [0, a i ] gives for all S ⊂ [M ], 0, S a ⊂ S A ⊂ 0, S a . (21)
Since by hypothesis S A is an arithmetic progression of increment ρ, we get | S A| = 1 + 1 ρ i∈S a i . Hence, using the fractional partition,

S∈G β S S A -1 = S∈G β S 1 ρ i∈S a i = 1 ρ M i=1 a i   S∈G;i∈S β S   = 1 ρ M i=1 a i . Each i ∈ [M ] belongs to some S ∈ G, hence A i ⊂ S A ⊂ ρZ,
where we used that 0 ∈ ∩ j A j and that S A is an arithmetic progression of increment ρ. Hence [M] A ⊂ ρZ, which together with [START_REF] Gill | An algorithmic and a geometric characterization of coarsening at random[END_REF] implies that

| [M] A| -1 ≤ 1 ρ M i=1 a i = S∈G β S S A -1 .

Concluding remarks and open questions

We leave a number of interesting open questions for future work.

• The question of characterizing all equality cases for our main inequality (4) in dimension 1 is interesting, and seems doable but tedious.

• The central problem posed in this paper-that of a full characterization of the Lyusternik region for M > 2 -seems quite difficult in general. It should however be possible to improve on our (inclusion) bounds or to put forward qualitative properties of these sets. From the discussion of the counterexample showing that partial sums cannot reach all supermodular set functions, it is clear that characterizing the region would require at least to be able to say that if the two-by-two sums are not too big, then the sets are not far from convex and thus the three-by-three sum is not too big either. Such considerations lead towards refined stability results (see, e.g., [START_REF] Figalli | Quantitative stability for sumsets in R n[END_REF]) and additive combinatorics, and would be very interesting to pursue.

• It is natural to ask what the analogue of the Lyusternik region looks like when, instead of allowing all compact sets, one restricts to convex sets. In this case, the question becomes clearly related to mixed volumes and their properties-indeed, supermodularity properties of mixed volumes are discussed in [START_REF] Fradelizi | Sumset estimates in convex geometry[END_REF], some properties of the reverse kind (log-submodularity) that hold for special subclasses of convex sets are discussed in [START_REF] Fradelizi | Sumset estimates in convex geometry[END_REF][START_REF] Fradelizi | On the volume of zonoid sums[END_REF], and some extensions to measures beyond Lebesgue measure are discussed in [START_REF] Fradelizi | The Gaussian measure of Minkowski sums[END_REF]. We remark that studies of regions involving the set of possible mixed volumes of convex bodies have been undertaken in a series of works in convex geometry (see, e.g., [START_REF] Shephard | Inequalities between mixed volumes of convex sets[END_REF][START_REF] Henk | Steiner polynomials via ultra-logconcave sequences[END_REF]); however there does not appear to be a direct connection between our work and those results because our interest is focused on what can be said for general compact sets.

• It is shown in [START_REF] Fradelizi | The convexification effect of Minkowski summation[END_REF] that if A, B, C are compact subsets of R, then

|A + B + C| + |conv(A)| ≥ |A + B| + |A + C|.
In particular, a supermodularity-type inequality holds if the set A is convex (i.e., a closed interval). This may also be written as follows: if A is a compact convex set and B, C are arbitrary compact sets, and we define ∆

B (A) = |A + B| -|A|, then ∆ B+C (A) ≥ ∆ B (A) + ∆ C (A).
This inequality was recently verified in general dimension when B is a zonoid (and C is an arbitrary compact set) by [START_REF] Fradelizi | Sumset estimates in convex geometry[END_REF], but the question is open in general. It is also unknown if even in R, the superadditivity property of ∆ • (A) for a fixed convex body A under Minkowski summation can be refined to a fractional superadditivity statement.

A The relevance of fractional superadditivity

In this Appendix, we discuss some motivations for considering fractionally superadditivity a structural property of importance for set functions. Our first observation, which is elementary but seemingly new, is that fractional superadditivity is closely connected to the extendability of a set function to a function on the positive orthant with nice properties. As usual we identify the set of subsets of [M ] with {0, 1} M or with the set of application from [M ] to {0, 1}. In particular for S ⊂ [M ], the indicator function 1 S is viewed as a vector in {0, 1} M ⊂ R M . The following result may be compared with the Lovász extension theorem for submodular functions, see [START_REF] Lovász | Submodular functions and convexity[END_REF]. Observe that the superadditivity condition, when applied to empty sets gives that f (0) = f (1 ∅ ) = 0. So we can we can also restrict the summation to S = ∅ in the supremum without changing its value. Then F (0) = 0 (as only β ∅ may be non-zero and f (1 ∅ ) = 0). Let us consider x = 0 now. The above set is not empty as x = i∈[M] x i 1 {i} and the relationship x i = S; i∈S β S implies that for S = ∅, β S ∈ 0, x ∞ . So F (x) is a well defined non-negative real number. One readily checks that F is 1-homogeneous and concave. We have already seen that f (0) = F (0) = 0. By definition F (1 T ) ≥ f (1 T ) by choosing the trivial decomposition of 1 S as itself. But for general decompositions 1 T = S β S 1 S , fractional superadditivity gives that S β S f (1 S ) ≤ f (1 T ), so by taking supremum

F (1 T ) ≤ f (1 T ). Consequently F (1 T ) = f (1 T ) for every T ⊂ [M ].
It is tempting to try to find a simpler proof of Theorem 2 by constructing a 1-homogeneous concave function that extends the set function f (s) = | i∈s A i |. However, we have been unable to do this. We note that the obvious choice to consider is F (x) = | i∈[M] x i A i |, and moreover, the concavity of this function is easy to check when each A i is a convex set using the Brunn-Minkowski inequality and the "distributive" property (s + t)A = sA + tA (which holds for s, t > 0 if and only if A is convex). However, the same idea to prove concavity of F does not work for general compact sets because of the failure of the distributive property.

Our second observation, which is classical, is that fractional superadditivity (or "balancedness" as it is called in the economics literature) is equivalent to a certain "nonempty core" property of an optimization problem connected to the set function. This equivalence, proved by the duality theorem of linear programming, is the content of the Bondareva-Shapley theorem [START_REF] Bondareva | Some applications of the methods of linear programming to the theory of cooperative games (in Russian)[END_REF][START_REF] Shapley | On balanced sets and cores[END_REF] in the theory of cooperative games. We now state this theorem in our language and avoiding game-theoretic terminology.

Let f : {0, 1} M → R + with f (∅) = 0. Define the polyhedron

A(f ) = t ∈ R M + : i∈s t i ≥ f (s) for each s ⊂ [M ] .
The Bondareva-Shapley theorem states that f is fractionally superadditive if and only if there exists t ∈ A(f ) such that i∈[M] t i = f ([M ]). The reader may consult [START_REF] Madiman | Cores of cooperative games in information theory[END_REF] for a review of the cooperative game theory literature, including the Bondareva-Shapley theorem, from the viewpoint of information theory.

Observation 1 . 1 d A 1 , . . . , λ 1 d

 1111 For each d, M ∈ N * , Λ d (M ) is a cone, which is invariant under the natural action of the symmetric group on M elements. Proof. To prove the first part, suppose (α S : S ∈ [M ]) ∈ Λ d (M ). Then there exist compact sets A = (A 1 , . . . , A M ) in R d such that α S = |A S |. For any λ > 0, consider the compact sets A ′ = (λ A M ). Clearly ν A ′ = (λα S : S ∈ [M ]). This is also true for λ = 0, since 0 ∈ Λ d (M ) (it can be realized e.g. with singletons). Hence Λ d (M ) is a cone. Let us address the second part. If A = (A 1 , . . . , A M ) realizes (α S : S ∈ [M ]) ∈ Λ d (M ), then clearly π(A) := (A π(1) , . . . , A π(M) ) realizes the vector (α π(S) : S ∈ [M ]), where π(S) := {π(i) : i ∈ S}. Thus (α π(S) : S ∈ [M ]) ∈ Λ d (n).

Observation 2 .

 2 For all d ∈ N * , Λ d (2) = (0, a, b, c) ∈ R 4 + :

Figure 1 :Figure 2 :

 12 Figure 1: Leave-one-out partition on {1, 2, 3}

Theorem 5 .

 5 Let (G, β) be a fractional partition of [M ]. Let A 1 , . . . , A M be non-empty compact subsets of R d . Then

Proposition 1 .

 1 Let f : {0, 1} M → R + . Then the following assertions are equivalent:1. f is fractionally superadditive, meaning that if T ⊂ [M ] and non-negative numbers (β S ) S⊂[M] satisfy 1 T = S⊂[M] β S 1 S then f (1 T ) ≥ S β S f (1 S ).

2. f admits a 1 -

 1 homogeneous concave extension to R M + = [0, +∞) M . Proof. 2 =⇒ 1: Let F be such an extension then for β S ≥ 0, set β := S β S . Assume β > 0 (otherwise all β S = 0 and the conclusion will be trivial). Then by homogeneity and concavityF S β S 1 S = βF S β S β 1 S ≥ S β S F (1 S ) = S β S f (1 S ). So if 1 T = S β S 1 S , we obtain f (1 T ) = F (1 T ) ≥ S β S f (1 S ). 1 =⇒ 2: For x ∈ R n + we define F (x) := sup S⊂M β S f (1 S ) β S ≥ 0 s.t. x = S⊂M β S 1 S .

This is not claimed to be new; similar arguments and conclusions appear, e.g., in[43,

[START_REF] Gill | An algorithmic and a geometric characterization of coarsening at random[END_REF], which also contain additional information about extreme fractional partitions. For example,[START_REF] Gill | An algorithmic and a geometric characterization of coarsening at random[END_REF] show that one needs to allow denominators of the rational numbers that appear in extreme fractional partitions to grow at least exponentially in n.

Acknowledgments: M.M. was supported in part by the U.S. National Science Foundation (NSF) through grants DMS-1409504 and CCF-1346564. This research was begun during the stay of the authors at the Isaac Newton Institute for the Mathematical Sciences, Cambridge, UK during the "Discrete Analysis" program in 2011; we are grateful to Liyao Wang for some useful discussions at that time. Its completion was supported by the NSF under Grant No. 1440140, while the authors were in residence at the Mathematical Sciences Research Institute in Berkeley, California, for the "Geometric and Functional Analysis and Applications" program during the fall semester of 2017.