22
$\begingroup$

Background

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 $A_1, \ldots, A_n$ a real number $V(A_1, \ldots, A_n)$, measured in $\mathrm{metres}^n$.

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.

  1. $V(A, \ldots, A) = \mathrm{Vol}(A)$, for any convex set $A$.

  2. More generally, suppose that $A_1, \ldots, A_n$ are all scalings of a single convex set (so that $A = r_i B$ for some convex $B$ and $r_i \geq 0$). Then $V(A_1, \ldots, A_n)$ is the geometric mean of $\mathrm{Vol}(A_1), \ldots, \mathrm{Vol}(A_n)$.

  3. 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 $$ V(A_1, A_2) = \frac{1}{2}(ad + bc). $$ (Compare and contrast the determinant formula $ad - bc$.)

  4. More generally, take axis-parallel parallelepipeds $A_1, \ldots, A_n$ in $\mathbb{R}^n$. Write $m_{i1}, \ldots, m_{in}$ for the edge-lengths of $A_i$. Then $$ V(A_1, \ldots, A_n) = \frac{1}{n!} \sum_{\sigma \in S_n} m_{1, \sigma(1)} \cdots m_{n, \sigma(n)}. $$ (Again, compare and contrast the determinant formula.)

The definition of mixed volume depends on a theorem of Minkowski: for any compact convex sets $A_1, \ldots, A_m$ in $\mathbb{R}^n$, the function $$ (\lambda_1, \ldots, \lambda_m) \mapsto \mathrm{Vol}(\lambda_1 A_1 + \cdots + \lambda_m A_m) $$ (where $\lambda_i \geq 0$ and $+$ means Minkowski sum) is a polynomial, homogeneous of degree $n$. For $m = n$, the mixed volume $V(A_1, \ldots, A_n)$ is defined as the coefficient of $\lambda_1 \lambda_2 \cdots \lambda_n$ in this polynomial, divided by $n!$.

Why pick out this particular coefficient? Because it turns out to tell you everything, in the following sense: for any convex sets $A_1, \ldots, A_m$ in $\mathbb{R}^n$, $$ \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}. $$

Properties of mixed volume

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:

  1. Volume: $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.)

  2. Symmetry: $V$ is symmetric in its arguments.

  3. Multilinearity: $$ 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). $$ (These first three properties closely resemble a standard characterization of determinants.)

  4. Continuity: $V$ is continuous with respect to the Hausdorff metric on $\mathscr{K}_n$.

  5. Invariance: $V(gA_1, \ldots, gA_n) = V(A_1, \ldots, A_n)$ for any isometry $g$ of Euclidean space $\mathbb{R}^n$ onto itself.

  6. Multivaluation: $$ 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) $$ whenever $A_1, A'_1, A_1 \cup A'_1 \in \mathscr{K}_n$.

  7. Monotonicity: $V(A_1, A_2, \ldots, A_n) \leq V(A'_1, A_2, \ldots, A_n)$ whenever $A_1 \subseteq A'_1$.

There are other basic properties, but I'll stop there.

Questions

Is $V$ the unique function $(\mathscr{K}_n)^n \to [0, \infty)$ satisfying properties 1--7?

If so, does some subset of these properties suffice? In particular, do properties 1--3 suffice?

If not, is there a similar characterization involving different properties?

(Partway through writing this question, I found a recent paper of Vitali Milman and Rolf Schneider: Characterizing the mixed volume. I don't think it answers my question, though it does give me the impression that the answer might be unknown.)

$\endgroup$
4
  • $\begingroup$ Looking at your papers, it appears that you are in contact with some of the top experts in this area. The only other person I suggest asking is Monika Ludwig. If she and the other who you know already don't know the answer to this, I doubt anybody else does. But I do like the question. $\endgroup$
    – Deane Yang
    Aug 3, 2011 at 2:30
  • $\begingroup$ Thanks, Deane. It's a pleasant surprise to be told I'm so well-connected, as I'm genuinely a total amateur at this stuff. $\endgroup$ Aug 3, 2011 at 2:33
  • $\begingroup$ The other obvious person to ask is Dan Klain. $\endgroup$
    – Deane Yang
    Aug 3, 2011 at 3:42
  • 1
    $\begingroup$ Is it possible that your "cousin of the determinant" is just the permanent? $\endgroup$
    – Wolfgang
    Oct 14, 2018 at 20:24

2 Answers 2

15
$\begingroup$

Sorry to answer my own question, but asking this in public seems to have spurred me into thought.

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

  1. $V(A, \ldots, A) = Vol(A)$

  2. $V$ is symmetric

  3. $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)$.

In other words, we don't need multilinearity, just multiadditivity.

The proof is along the lines suggested by auniket.

Fix $n$ and $A_1, \ldots, A_n \in \mathscr{K}_n$. Write $\mathbf{n} = \{1, \ldots, n\}$, and for sets $R$ and $S$, write $\mathrm{Surj}(R, S)$ for the set of surjections $R \to S$.

I claim that for all subsets $S$ of $\mathbf{n}$, $$ \sum_{f \in \mathrm{Surj}(\mathbf{n}, S)} V(A_{f(1)}, \ldots, A_{f(n)}) $$ 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 $$ n! V(A_1, \ldots, A_n), $$ so this claim will imply the characterization theorem.

To prove the claim, take $S \subseteq \mathbf{n}$. Then $$ Vol(\sum_{i \in S} A_i) = \sum_{f: \mathbf{n} \to S} V(A_{f(1)}, \ldots, A_{f(n)}) $$ by the three properties. This in turn is equal to $$ \sum_{R \subseteq S} \sum_{f \in \mathrm{Surj}(\mathbf{n}, R)} V(A_{f(1)}, \ldots, A_{f(n)}). $$ 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.

The proof makes it clear that $V(A_1, \ldots, A_n)$ 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 Convex Bodies: The Brunn-Minkowski Theory).

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.

$\endgroup$
10
$\begingroup$

I think the first three properties do indeed characterize mixed volume. For example, in two dimensions they imply that

$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))$
$= \frac{1}{2}(Vol(A_1 + A_2) - Vol(A_1) - Vol(A_2)),$

which gives the formula of mixed volume in terms of volume. You can perform the same trick to get in 3 dimensions:

$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)$
$- Vol(A_3+A_1) + Vol(A_1) + Vol(A_2) + Vol(A_3))$

In general I believe you get something like:

$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)$
$ + \cdots +(-1)^{n-1}\sum_{i=1}^n Vol(A_i))$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Great! Thanks. I see that formula in Lemma 5.1.3 of Schneider's book Convex Bodies, but he doesn't say there that it holds for all convex bodies (just ones in a certain class), and he also doesn't say there that it follows from properties 1-3. $\endgroup$ Aug 3, 2011 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.