What is the functional form of the projections of a subdimensional polytope?

Question

Let $\mathbf{S}$ be a $m\times n$ matrix, with $m < n$. We define a subdimensional polytope as the space of $n$-dimensional vectors $\mathbf{x}$ that satisfy the following equation:

$$\mathbf{S}\cdot\mathbf{x}=0$$

subject to the inequalities:

$$\mathbf{a}\le\mathbf{x}\le\mathbf{b}$$

where $\mathbf{a}$ and $\mathbf{b}$ are $n$-dimensional vectors.

Denote by $\Omega$ this space of solutions. The projection of $\Omega$ over the $i$'th coordinate ($0\le i\le n$) is the function:

$$f_{k}\left(x_{k}\right)=\int\delta\left(\mathbf{S}\cdot\mathbf{x}\right)\prod_{i\ne k}\mathrm{d}x_{i}$$

where the integral goes through all the values of $x_i$ for all $i\ne k, 1\le i \le n$, and $\delta(\mathbf{y})$ is the $m$-dimensional Dirac's delta function, given by:

$$\delta\left(\mathbf{y}\right)=\prod_{j}\delta\left(y_{j}\right)$$

where $\delta(y_j)$ are ordinary one-variable Dirac's delta functions.

I understand that the exact computation of $f_{k}\left(x_{k}\right)$ is NP-hard. But I was wondering if something can be said about its form. I have the intuition that $f_{k}\left(x_{k}\right)$ should be concave, or at least have zero or one maximum. Can you prove this? What other properties $f_{k}\left(x_{k}\right)$ satisfies in general?

Answer 1

Assuming that $S$ is full rank, let $u$ be some unit vector not orthogonal to the null space of $S$, and let $\Omega_t =\lbrace x-t u~:~x\in\Omega,~ (x-tu)\cdot u = 0\rbrace$. then you are interested in the $(n-m-1)$-dimensional volumes $f(t)=|\Omega_t|$. Note that convexity of $\Omega$ implies that for $0\le\lambda\le1$, and $t$, $t'$ such that $\Omega_t$, $\Omega_{t'}$ are non-empty, $\lambda\Omega_t+(1-\lambda)\Omega_{t'}\subseteq\Omega_{\lambda t+(1-\lambda) t'}$. By the Brunn-Minkowski theorem we then have $$f(\lambda t+(1-\lambda) t')^{1/(n-m-1)}\ge|\lambda\Omega_t+(1-\lambda)\Omega_{t'}|^{1/(n-m-1)}\ge \lambda f(t)^{1/(n-m-1)}+(1-\lambda)f(t')^{1/(n-m-1)}\text.$$

EDIT: strange to see you came to check the answer one year later, but to answer your further question: yes, $f(t)$ is piecewise polynomial of degree at most $n-m-1$. Between values of $t$ corresponding to vertices, say $t_0$ and $t_1$, the cross section takes the form $\Omega_t = \frac{t-t_0}{t_1-t_0} \Omega_{t_1} + \frac{t_1-t}{t_1-t_0} \Omega_{t_0}$. That the volume is a polynomial in $t$ follows from Steiner's formula (see https://en.wikipedia.org/wiki/Mixed_volume).