Do the elementary properties of mixed volume characterize it uniquely? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T04:23:03Z http://mathoverflow.net/feeds/question/71952 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/71952/do-the-elementary-properties-of-mixed-volume-characterize-it-uniquely Do the elementary properties of mixed volume characterize it uniquely? Tom Leinster 2011-08-03T01:58:03Z 2013-02-09T11:09:36Z <p><strong>Background</strong></p> <p>Take 2 convex sets in $\mathbb{R}^2$, or 3 convex sets in $\mathbb{R}^3$, or generally, $n$ convex sets in $\mathbb{R}^n$. "Mixed volume" assigns to such a family <code>$A_1, \ldots, A_n$</code> a real number <code>$V(A_1, \ldots, A_n)$</code>, measured in $\mathrm{metres}^n$. </p> <p>As I understand it, mixed volume is a kind of cousin of the determinant. I'll give the definition in a moment, but first here are some examples. </p> <ol> <li><p>$V(A, \ldots, A) = \mathrm{Vol}(A)$, for any convex set $A$.</p></li> <li><p>More generally, suppose that <code>$A_1, \ldots, A_n$</code> are all scalings of a single convex set (so that $A = r_i B$ for some convex $B$ and $r_i \geq 0$). Then <code>$V(A_1, \ldots, A_n)$</code> is the geometric mean of <code>$\mathrm{Vol}(A_1), \ldots, \mathrm{Vol}(A_n)$</code>.</p></li> <li><p>The previous examples don't show how mixed volume typically depends on the interplay between the sets. So, taking $n = 2$, let $A_1$ be an $a \times b$ rectangle and $A_2$ a $c \times d$ rectangle in $\mathbb{R}^2$, with their edges parallel to the coordinate axes. Then <code>$$V(A_1, A_2) = \frac{1}{2}(ad + bc).$$</code> (Compare and contrast the determinant formula $ad - bc$.)</p></li> <li><p>More generally, take axis-parallel parallelepipeds <code>$A_1, \ldots, A_n$</code> in $\mathbb{R}^n$. Write <code>$m_{i1}, \ldots, m_{in}$</code> for the edge-lengths of $A_i$. Then <code>$$V(A_1, \ldots, A_n) = \frac{1}{n!} \sum_{\sigma \in S_n} m_{1, \sigma(1)} \cdots m_{n, \sigma(n)}.$$</code> (Again, compare and contrast the determinant formula.)</p></li> </ol> <p>The definition of mixed volume depends on a theorem of Minkowski: for any compact convex sets <code>$A_1, \ldots, A_m$</code> in $\mathbb{R}^n$, the function <code>$$(\lambda_1, \ldots, \lambda_m) \mapsto \mathrm{Vol}(\lambda_1 A_1 + \cdots + \lambda_m A_m)$$</code> (where $\lambda_i \geq 0$ and $+$ means Minkowski sum) is a polynomial, homogeneous of degree $n$. For $m = n$, the mixed volume <code>$V(A_1, \ldots, A_n)$</code> is defined as the coefficient of <code>$\lambda_1 \lambda_2 \cdots \lambda_n$</code> in this polynomial, divided by $n!$.</p> <p>Why pick out this particular coefficient? Because it turns out to tell you everything, in the following sense: for any convex sets <code>$A_1, \ldots, A_m$</code> in $\mathbb{R}^n$, <code>$$\mathrm{Vol}(\lambda_1 A_1 + \cdots + \lambda_m A_m) = \sum_{i_1, \ldots, i_n = 1}^m V(A_{i_1}, \ldots, A_{i_n}) \lambda_{i_1} \cdots \lambda_{i_n}.$$</code></p> <p><strong>Properties of mixed volume</strong></p> <p>Formally, let $\mathscr{K}_n$ be the set of nonempty compact convex subsets of $\mathbb{R}^n$. Then mixed volume is a function $$V: (\mathscr{K}_n)^n \to [0, \infty),$$ and has the following properties:</p> <ol> <li><p><em>Volume:</em> $V(A, \ldots, A) = \mathrm{Vol}(A)$. (Here and below, the letters $A$, $A_i$ etc. will be understood to range over $\mathscr{K}_n$, and $\lambda$, $\lambda_i$ etc. will be nonnegative reals.)</p></li> <li><p><em>Symmetry:</em> $V$ is symmetric in its arguments.</p></li> <li><p><em>Multilinearity:</em> <code>$$V(\lambda A_1 + \lambda' A'_1, A_2, \ldots, A_n) = \lambda V(A_1, A_2, \ldots, A_n) + \lambda' V(A'_1, A_2, \ldots, A_n).$$</code> (These first three properties closely resemble a standard characterization of determinants.) </p></li> <li><p><em>Continuity:</em> $V$ is continuous with respect to the Hausdorff metric on $\mathscr{K}_n$.</p></li> <li><p><em>Invariance:</em> <code>$V(gA_1, \ldots, gA_n) = V(A_1, \ldots, A_n)$</code> for any isometry $g$ of Euclidean space $\mathbb{R}^n$ onto itself.</p></li> <li><p><em>Multivaluation:</em> <code>$$V(A_1 \cup A'_1, A_2, \ldots, A_n) = V(A_1, A_2, \ldots) + V(A'_1, A_2, \ldots) - V(A_1 \cap A'_1, A_2, \ldots)$$</code> whenever <code>$A_1, A'_1, A_1 \cup A'_1 \in \mathscr{K}_n$</code>.</p></li> <li><p><em>Monotonicity:</em> <code>$V(A_1, A_2, \ldots, A_n) \leq V(A'_1, A_2, \ldots, A_n)$</code> whenever <code>$A_1 \subseteq A'_1$</code>.</p></li> </ol> <p>There are other basic properties, but I'll stop there.</p> <p><strong>Questions</strong></p> <p>Is $V$ the unique function $(\mathscr{K}_n)^n \to [0, \infty)$ satisfying properties 1--7?</p> <p>If so, does some subset of these properties suffice? In particular, do properties 1--3 suffice? </p> <p>If not, is there a similar characterization involving different properties?</p> <p>(Partway through writing this question, I found a recent paper of Vitali Milman and Rolf Schneider: <a href="http://home.mathematik.uni-freiburg.de/rschnei/CharMixVol.rev.pdf" rel="nofollow">Characterizing the mixed volume</a>. I don't think it answers my question, though it does give me the impression that the answer might be unknown.)</p> http://mathoverflow.net/questions/71952/do-the-elementary-properties-of-mixed-volume-characterize-it-uniquely/71967#71967 Answer by auniket for Do the elementary properties of mixed volume characterize it uniquely? auniket 2011-08-03T05:39:20Z 2011-08-03T05:39:20Z <p>I think the first three properties do indeed characterize mixed volume. For example, in two dimensions they imply that</p> <p>$V(A_1, A_2) = \frac{1}{2}(V(A_1 + A_2, A_1 + A_2) - V(A_1, A_1) - V(A_2,A_2))$ <br> $= \frac{1}{2}(Vol(A_1 + A_2) - Vol(A_1) - Vol(A_2)),$</p> <p>which gives the formula of mixed volume in terms of volume. You can perform the same trick to get in 3 dimensions:</p> <p>$V(A_1,A_2, A_3) = \frac{1}{6}(Vol(A_1+A_2+A_3) - Vol(A_1+A_2) - Vol(A_2+A_3)$ <br> $- Vol(A_3+A_1) + Vol(A_1) + Vol(A_2) + Vol(A_3))$</p> <p>In general I believe you get something like:</p> <p>$V(A_1, \ldots,A_n) = \frac{1}{n!}(Vol(A_1 + \cdots + A_n) - \sum_{i=1}^n Vol(A_1 + \cdots \hat A_i + \cdots + A_n)$ <br> $+ \cdots +(-1)^{n-1}\sum_{i=1}^n Vol(A_i))$</p> <p>I learned of this from Bernstein's paper that contains his famous result that the number of solutions in $(\mathbb{C}^*)^n$ of $n$ generic Laurent polynomials is precisely the mixed volume of their Newton polytopes.</p> http://mathoverflow.net/questions/71952/do-the-elementary-properties-of-mixed-volume-characterize-it-uniquely/71980#71980 Answer by Tom Leinster for Do the elementary properties of mixed volume characterize it uniquely? Tom Leinster 2011-08-03T09:11:43Z 2011-08-03T14:55:08Z <p>Sorry to answer my own question, but asking this in public seems to have spurred me into thought.</p> <p>As auniket suspected, the answer is "yes" in the strongest sense I'd hoped: properties 1-3 do characterize mixed volume. In fact, something slightly stronger is true: $V$ is the unique function $(\mathscr{K}_n)^n \to \mathbb{R}$ satisfying</p> <ol> <li><p>$V(A, \ldots, A) = Vol(A)$</p></li> <li><p>$V$ is symmetric</p></li> <li><p><code>$V(A_1 + A'_1, A_2, \ldots, A_n) = V(A_1, A_2, \ldots, A_n) + V(A'_1, A_2, \ldots, A_n)$</code>.</p></li> </ol> <p>In other words, we don't need multilinearity, just multiadditivity. </p> <p>The proof is along the lines suggested by auniket. </p> <p>Fix $n$ and <code>$A_1, \ldots, A_n \in \mathscr{K}_n$</code>. Write <code>$\mathbf{n} = \{1, \ldots, n\}$</code>, and for sets $R$ and $S$, write $\mathrm{Surj}(R, S)$ for the set of surjections $R \to S$.</p> <p>I claim that for all subsets $S$ of $\mathbf{n}$, <code>$$\sum_{f \in \mathrm{Surj}(\mathbf{n}, S)} V(A_{f(1)}, \ldots, A_{f(n)})$$</code> is uniquely determined by the properties above. The proof will be by induction on the cardinality of $S$. When $S = \mathbf{n}$, this sum is <code>$$n! V(A_1, \ldots, A_n),$$</code> so this claim will imply the characterization theorem.</p> <p>To prove the claim, take $S \subseteq \mathbf{n}$. Then <code>$$Vol(\sum_{i \in S} A_i) = \sum_{f: \mathbf{n} \to S} V(A_{f(1)}, \ldots, A_{f(n)})$$</code> by the three properties. This in turn is equal to <code>$$\sum_{R \subseteq S} \sum_{f \in \mathrm{Surj}(\mathbf{n}, R)} V(A_{f(1)}, \ldots, A_{f(n)}).$$</code> By the inductive assumption, all but one of the summands in the first summation - namely, $R = S$ - is uniquely determined. Hence the $S$-summand is uniquely determined too. This completes the induction, and so completes the proof.</p> <p>The proof makes it clear that <code>$V(A_1, \ldots, A_n)$</code> is some rational linear combination of ordinary volumes of Minkowski sums of some of the $A_i$s. It must be possible to unwind this proof and get an explicit expression; and that expression must be the one auniket gave (which also appears in Lemma 5.1.3 of Schneider's book <em>Convex Bodies: The Brunn-Minkowski Theory</em>). </p> <p>This all seems rather easy, and must be well-known, though I'm a bit surprised that this characterization isn't mentioned in some of the things I've read. Incidentally, I now understand why it doesn't appear in the paper of Milman and Schneider mentioned in my question: they explicitly state that they want to avoid assuming property 1. </p>