Gromov’s angular spread theorem

I recently reported about a polyhedral proof of Stoker’s theorem using a lemma of Martin Winter; this, in turn, uses technique by Izmestiev.

I wanted to take a brief moment to illustrate that technique; Gromov, a few years ago, published a marvelous little paper. He used differential geometry techniques to show that a polytope cannot be too long in every direction. Specifically: Consider P a d-dimensional polytope, and map it cellularly to a d-cube C. Pick two opposing facets $F_-$ , $F_+$ of that d-cube. Their preimages in P are d-1-disks.

Nice enough. Now, try to go from the preimage of $F_-$ to the preimage of $F_+$ . If you go from one facet to an adjacent one in $P$ , then you “pay” the angle between their normals. All together, the optimal way you can take gives a minimal angular distance between the preimage of $F_-$ to the preimage of $F_+$ in $P$ ; it describes how far the two preimages are apart.

Now, it would be nice, and perhaps point towards the polynomial Hirsch conjecture, if we could say something about this distance. But Gromov says: geometry naturally gives something different: If I minimize over ALL the opposing pairs of facets of $C$ , then I obtain $\square_{\rangle}^{\,n}(P)$ , the angular spread… it describes the question whether P is long in every direction. Gromov’s paper obtains a displayed $O(n^{3/2})$ bound by passing through smooth mean-curvature geometry [1]. He needs to smoothen the polytope first, and his argument for non-simple polytopes is a bit … fishy. In comes Izmestiev, and I want to illustrate his method here, and improve the bound using it.

The bound obtained here is, for any n-polytope P

$\displaystyle \square_{\rangle}^{\,n}(P)\le\pi+2\inf_{p\ge1}p\,n^{1/(2p)}.\qquad (1)$

In particular, for $n\ge8$ ,

$\displaystyle \square_{\rangle}^{\,n}(P)\le\pi+e\log n.\qquad (2)$

I should say: Gromov conjectured that one could show a constant bound of $\pi$ . Not sure that is true. But maybe someone can throw LLM on my post and improve the bound… or find a counterexample. That said, this method here is pretty optimized. It is, in my opinion, impressive that such a bound depends on the dimension only.

The trick, in two sentences: Use the cellular map to C to construct a contraction that, in a topological sense, is nicely behaved (it needs, under what is called a Wachspress map, contain the origin in the interior). The trick is to look at the polar, and reassign the vertices to new points

$\displaystyle b_{i,k}=-1+\frac2D\min\{D,d_\angle(i,A_{k,-})\}.$

Here D is the angular spread (assume it is HUGE) and $d_\angle(i,A_{k,-}$ measures the angular distance to facets of the cube… And if you think about it, this map can only contract angular distances. Now use the Izmestiev trick is to show that in a polytope, you cannot contract edges if the radial distance of the vertices is the same (or rather, you can, but you cannot envelope the origin: the map must be of degree zero.) Intuitively clear, but maybe nonobvious.

On the other hand, you can also show that this map cannot be of degree 0… because you can homotope it to basically a nice map to the crosspolytope. And voila, you have the contradiction.

Once you have that, it is toute simple… The main optimization lies in the object we contract to, that is where it gets a bit more technical.

(I also messed up the numbering, rearranged after the fact… wordpress doesn’t do it automatically. Apologies… the numbers of equations are not exactly consecutive integers.)

Wachspress coordinates

For the moment, let

$\displaystyle Q=\mathrm{conv}\{v_1,\ldots,v_m\}\subset\mathbb R^n$

be any full-dimensional polytope, and fix $x\in\mathrm{int}Q$ . For a convex body $K$ containing the origin in its interior, its polar is $K^\circ=\{y:\langle z,y\rangle\le1\text{ for every }z\in K\}$ . Take the polar of the translated polytope:

$\displaystyle R_x=(Q-x)^\circ=\{y\in\mathbb R^n:\langle v_i-x,y\rangle\le1\text{ for every }i\}.$

The vertex $v_i$ corresponds to the facet

$\displaystyle E_i(x)=\{y\in R_x:\langle v_i-x,y\rangle=1\}.$

Define

$\displaystyle {\begin{aligned} \alpha_i(x)&=\frac{\mathrm{vol}_n(\mathrm{conv}(\{0\}\cup E_i(x)))}{\mathrm{vol}_n(R_x)}\\ &=\frac{\mathrm{vol}_{n-1}(E_i(x))}{n\,\mathrm{vol}_n(R_x)\,\|v_i-x\|}. \end{aligned}}\qquad\text{(3)}$

These are the generalized Wachspress coordinates of $x$ with respect to the vertices of $Q$ ; see §3.3 in [2]. You think probably: barycentric coordinates? Yes. In a way.

Indeed, the pyramids with apex $0$ and bases $E_i(x)$ partition $R_x$ . Therefore

$\displaystyle \alpha_i(x)>0,\qquad\sum_i\alpha_i(x)=1.$

The outward unit normal of $E_i(x)$ is $(v_i-x)/\|v_i-x\|$ . Hence

$\displaystyle \sum_i\mathrm{vol}_{n-1}(E_i(x))\frac{v_i-x}{\|v_i-x\|}=0.$

Dividing by $n\mathrm{vol}_n(R_x)$ proves

$\displaystyle \boxed{\sum_i\alpha_i(x)v_i=x.}\qquad\text{(4)}$

Thus, on a simplex, these are necessarily the ordinary barycentric coordinates.

The functions $\alpha_i$ extend continuously to all of $Q$ , including for nonsimple polytopes; see Remark 3.7 [2].

Their face-support property then follows from (4): Suppose that $x$ lies in a face $F$ , exposed by

$\displaystyle \ell\le c\text{ on }Q,\qquad F=\{\ell=c\}\cap Q.$

Then

$\displaystyle 0=c-\ell(x)=\sum_i\alpha_i(x)\bigl(c-\ell(v_i)\bigr).$

Every summand is nonnegative, so

$\displaystyle v_i\notin F\quad\Longrightarrow\quad\alpha_i(x)=0.\qquad\text{(5)}$

Given vectors $z=(z_i)$ , their Wachspress interpolation is

$\displaystyle \mathcal W_z(x)=\sum_i\alpha_i(x)z_i.$

Note that on a face $F$ , the only nonzero coefficients correspond to vertices of $F$ . And that is the key: We can map the polytope to a new world entirely, the face structure is in a way respected… and we can compare the new and old geometry. For this, we need a

comparison inequality

Fix $x\in\mathrm{int}Q$ , and abbreviate $a_i=v_i-x$ . Vary the support parameters of $R_x$ :

$\displaystyle R_x(h)=\{y:\langle a_i,y\rangle\le h_i,\ i=1,\ldots,m\},\qquad V(h)=\mathrm{vol}_n(R_x(h)).$

All derivatives below are evaluated at $h=\mathbf1$ . Write

$\displaystyle V_0=V(\mathbf1),\qquad g=\nabla V(\mathbf1),\qquad B=\nabla^2V(\mathbf1).$

Moving the $i$ -th supporting hyperplane gives

$\displaystyle g_i=\frac{\mathrm{vol}_{n-1}(E_i(x))}{\|a_i\|}=nV_0\alpha_i.$

For $i\ne j$ , the second variation is

$\displaystyle B_{ij}=\begin{cases} \dfrac{\mathrm{vol}_{n-2}(E_i(x)\cap E_j(x))}{\|a_i\|\|a_j\|\sin\angle(a_i,a_j)},&\{i,j\}\in E(Q),\\[0.8em] 0,&\{i,j\}\notin E(Q). \end{cases}\qquad\text{(6)}$

Here $E(Q)$ denotes the edge set of $Q$ , and $\mathrm{vol}_0$ of a point is one. In particular, $B_{ij}>0$ on edges. Slightly nontrivial: these support-volume derivatives exist also at nonsimple polytopes; see §2.3 and Appendix A.3 in [3].

Normalize by

$\displaystyle M=M(x):=\frac{B}{n(n-1)V_0}.$

Because of homogeneity, we have

$\displaystyle B\mathbf1=(n-1)g,\qquad\text{hence}\qquad{M\mathbf1=\alpha.}\qquad\text{(7)}$

Translating $R_x(h)$ by $t\in\mathbb R^n$ replaces $h_i$ by $h_i+\langle a_i,t\rangle$ , without changing its volume. Differentiating gives

$\displaystyle {\sum_jM_{ij}(v_j-x)=0\quad\text{for every }i.}\qquad\text{(8)}$

The remaining ingredient we need is

$\displaystyle {M\preceq\alpha\alpha^{\mathsf T},}\qquad\text{(9)}$

where $\preceq$ denotes the ordering of symmetric matrices by positive semide finiteness.

It follows from Brunn–Minkowski: remember

$\displaystyle \mathrm{vol}_n((1-t)A+tB)^{1/n}\ge(1-t)\mathrm{vol}_n(A)^{1/n}+t\mathrm{vol}_n(B)^{1/n}$

for convex bodies $A,B$ and $0\le t\le1$ . Since

$\displaystyle (1-t)R_x(h)+tR_x(k)\subseteq R_x((1-t)h+tk),$

the function $V(h)^{1/n}$ is concave. Its Hessian at $\mathbf1$ is therefore nonpositive:

$\displaystyle B-\frac{n-1}{nV_0}gg^{\mathsf T}\preceq0.$

Substituting $g=nV_0\alpha$ and dividing by $n(n-1)V_0$ proves (9).

A “Izmestiev-Winter lemma” that does a lot

Assume now that $0\in\mathrm{int}Q$ .

Lemma. Let $x\in Q$ , and let $F$ be its minimal face, meaning the unique face whose relative interior contains $x$ . Suppose vectors $z_i$ , indexed by the vertices of $F$ , satisfy

$\displaystyle \|z_i\|=\|v_i\|,\qquad\|z_i-z_j\|\le\|v_i-v_j\|\quad\text{on every edge of }F.$

Then

$\displaystyle {\left\|\sum_i\alpha_i(x)z_i\right\|\ge\|x\|.}\qquad\text{(10)}$

For $x\in\mathrm{int}Q$ , the inequality is strict whenever at least one edge is strictly shortened. This lemma gives some intuition what a Wachspress map does, geometrically.

Proof. Consider interior $x$ . For any configuration $z$ , let

$\displaystyle \mathrm{Var}_\alpha(z)=\sum_i\alpha_i\|z_i\|^2-\left\|\sum_i\alpha_i z_i\right\|^2.$

Expanding squared edge lengths and using (7) gives

$\displaystyle \sum_{\{i,j\}\in E(Q)}M_{ij}\|z_i-z_j\|^2=\sum_i\alpha_i\|z_i\|^2-\sum_{i,j}M_{ij}\langle z_i,z_j\rangle.$

Hence,

$\displaystyle \mathrm{Var}_\alpha(z)\le\sum_{\{i,j\}\in E(Q)}M_{ij}\|z_i-z_j\|^2.\qquad\text{(11)}$

For the original configuration $v_i$ , equations (4) and (8) give:

$\displaystyle \sum_{\{i,j\}\in E(Q)}M_{ij}\|v_i-v_j\|^2=\sum_i\alpha_i\|v_i\|^2-\|x\|^2.\qquad\text{(12)}$

Consequently,

$\displaystyle \begin{aligned} \sum_i\alpha_i\|v_i\|^2-\left\|\sum_i\alpha_i z_i\right\|^2 &\le\sum_{\{i,j\}}M_{ij}\|z_i-z_j\|^2\\ &\le\sum_{\{i,j\}}M_{ij}\|v_i-v_j\|^2\\ &=\sum_i\alpha_i\|v_i\|^2-\|x\|^2. \end{aligned}$

This proves (10), including strictness because all edge weights $M_{ij}$ are positive.

We also need the assertion on a proper face, but this is immediate from limiting and the “face compatibility” observed above. This proves the lemma.

In particular, if a fixed configuration $z_i$ preserves all vertex radii, lengthens no edge, and strictly shortens at least one edge, then its Wachspress map never vanishes on $Q$ . On the interior the comparison is strict, while on the boundary $\|x\|>0$ . Its normalized boundary map consequently has degree zero: it extends over the ball $Q$ as a map to $S^{n-1}$ .

Take a step back. Have a coffee. Realize you just proved Stoker conjecture.

The rest of the proof a contraction whose boundary degree is nevertheless nonzero.

From the polar to the crosspolytope

Translate $P$ so that $0\in\mathrm{int}P$ , and put

$\displaystyle Q=P^\circ=\mathrm{conv}\{v_i\}.$

Write

$\displaystyle v_i=r_i\nu_i,\qquad r_i>0.$

The edge graph of $Q$ is the facet-adjacency graph of $P$ , and its angular edge lengths are $\gamma_{ij}$ .

For each facet $F_i$ , let $v_i$ be the corresponding vertex of $Q$ and $n_i$ the normal. The facet maps entirely into at least one cubical facet. Choose one such facet $C_{k,s}$ , k denoting direction, s the sign, and label $v_i$ by $\ell_i=s e_k$ ; in other words, from the map to the cube, we construct a map to the crosspolytope.

Therefore

$\displaystyle \Lambda(x)=\sum_i\alpha_i(x)\ell_i,\qquad x\in\partial Q,$

takes values in the boundary of the crosspolytope

$\displaystyle C^\circ=\{y:\|y\|_1\le1\},$

because there is no cancellation among opposite labels:

$\displaystyle {\|\Lambda(x)\|_1=1.}\qquad\text{(17)}$

We claim

$\displaystyle {\deg\Lambda\ne0.}\qquad\text{(18)}$

Think about it. It is obvious. But it is not yet the contraction. Still, we have one way to show zero degree, and one to show non-zero degree. We exploit this now.

Distortion

Let me set up a particular parameter family of distortions that we will use.

For $p\ge1$ , define

$\displaystyle B_p(u)_k=\mathrm{sgn}(u_k)|u_k|^p,\qquad T_p(u)=\frac{B_p(u)}{\|B_p(u)\|_2},\qquad u\ne0,$

and set

$\displaystyle K=p\,n^{1/(2p)}.$

Differentiating the normalization and applying Hölder gives

$\displaystyle \begin{aligned} \|DT_p(u)\|_{\ell_\infty\to\ell_2} &\le p\,\frac{\left(\sum_k|u_k|^{2p-2}\right)^{1/2}}{\left(\sum_k|u_k|^{2p}\right)^{1/2}}\\ &\le\frac{p\,n^{1/(2p)}}{\|u\|_{2p}}\le\frac K{\|u\|_\infty}. \end{aligned}\qquad\text{(14)}$

For $p=1$ , the same estimate follows directly from ordinary radial normalization.

Suppose

$\displaystyle \|u\|_\infty,\|v\|_\infty\ge1,\qquad\delta=\|u-v\|_\infty<2.$

Along their straight segment,

$\displaystyle \|(1-s)u+sv\|_\infty\ge1-\delta\min(s,1-s)\ge1-\delta/2.$

Integrating (14) along that segment bounds the spherical distance:

$\displaystyle {d_S(T_p(u),T_p(v))\le\frac{K\delta}{1-\delta/2}.}\qquad\text{(15)}$

Here $d_S$ is geodesic distance on the unit sphere.

Constructing the contra(di)ction

Take an map $\Phi:P\rightarrow C$ of angular separation $D$ , and suppose, toward a contradiction, that

$\displaystyle D>\pi+2K.\qquad\text{(16)}$

We now construct a Wachspress map that is simultaneously a contraction in the sense of the IW lemma, and hence of degree 0… but also homotopic to $\Lambda$ , and hence not of degree 0.

Let us denote the set of facets $F_i$ whose image lies in $C_{k,\pm}$ by $latex A_{k,\pm}.

Next construct the target for the Wachspress map (for this, we need the new vertices $z_i$ : We want to relocate the vertices of $Q$ to new points $b_i\in[-1,1]^n$ . Set

$\displaystyle b_{i,k}=-1+\frac2D\min\{D,d_\angle(i,A_{k,-})\}.\qquad\text{(19)}$

In other words, we measure the distance of a facet $F_i$ to the facets in the preimage of $C_{k,-}$ .

Distance to a set is 1-Lipschitz, so

$\displaystyle \|b_i-b_j\|_\infty\le\frac2D\,d_\angle(i,j).\qquad\text{(20)}$

The separation assumption also gives

$\displaystyle i\in A_{k,s}\quad\Longrightarrow\quad b_{i,k}=s.$

In particular,

$\displaystyle \|b_i\|_\infty=1,\qquad\ell_i=s e_k\quad\Longrightarrow\quad b_{i,k}=s.\qquad\text{(21)}$

Define

$\displaystyle w_i=r_iT_p(b_i),$

where $v_i=r_i n_i$ .

For an edge $\{i,j\}$ , equations (15) and (20), together with $d_\angle(i,j)\le\gamma_{ij}:=\mathrm{arccos}(n_i,n_j)$ ,

$\displaystyle \begin{aligned} d_S(T_p(b_i),T_p(b_j)) &\le\frac{2K\gamma_{ij}/D}{1-\gamma_{ij}/D}\\ &=\frac{2K}{D-\gamma_{ij}}\gamma_{ij}<\gamma_{ij}, \end{aligned}\qquad\text{(22)}$

since $\gamma_{ij}<\pi$ and $D>\pi+2K$ . Keeping the radii fixed turns strict angular contraction into strict Euclidean edge contraction:

$\displaystyle \|w_i-w_j\|<\|v_i-v_j\|.$

The comparison lemma therefore says that

$\displaystyle W(x)=\sum_i\alpha_i(x)w_i$

never vanishes on $Q$ . Hence, remember, the map has degree 0! But wait.

The contradiction

Let’s try to compare the map (as in, homotope) to $\Lambda$ . Consider

$\displaystyle H_t(x)=\sum_i\alpha_i(x)r_iT_p\bigl(b_i+t\Lambda(x)\bigr),\qquad x\in\partial Q,\quad t\ge0,\qquad\text{(24)}$

omitting terms with $\alpha_i(x)=0$ .

Fix $x$ , and let $G$ be its minimal face. For any vertex $v_i$ of $G$ , write $\ell_i=s e_k$ . By (21), $s b_{i,k}=1$ . Because the labels on $G$ contain no opposite pair, $s\Lambda_k(x)\ge0$ . Consequently,