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. It is, in my opinion, 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). Once you have that, it is toute simple… A spectral trick of Ivan applies, and you get what you want. The main optimization lies in the object we contract to, that is where it gets a bit more technical (that and nonsimple polytopes).

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 INVINCIBLE. No, 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}.$

Homogeneity and translation invariance give two identities. Since $V(th)=t^nV(h)$ ,

$\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 this invariance gives

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

The remaining ingredient is

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

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

Here is a direct derivation. The Brunn–Minkowski inequality says

$\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 lemma

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.

Proof. First 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.$

By (9),

$\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 equality:

$\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, without assumptions on edges outside that face. For each vertex $v_i$ , choose a linear functional $\ell_i$ uniquely maximized at $v_i$ . Equations (7)–(8) imply

$\displaystyle \sum_{j\ne i}M_{ij}\bigl(\ell_i(v_i)-\ell_i(v_j)\bigr)=\alpha_i\bigl(\ell_i(v_i)-\ell_i(x)\bigr).\qquad\text{(13)}$

The differences on the left are strictly positive. It follows, uniformly for interior $x$ , that

$\displaystyle 0\le\sum_{j\ne i}M_{ij}\le C_i\alpha_i,\qquad|M_{ii}|\le(1+C_i)\alpha_i.$

Thus, as interior points approach a boundary point $x$ , the matrices have a convergent subsequence. By (5), every limiting row and column indexed outside the minimal face $F$ vanishes.

All identities and inequalities (7)–(12) persist in the limit. The limiting edge sum involves only edges of $F$ , so the same proof establishes (10) on $F$ . 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}$ .

Normalize

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.

A little technical stuff here

Take an admissible $\Phi$ of separation $D$ , and suppose, toward a contradiction, that

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

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

$\displaystyle Q=X^\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 $X$ , and its angular edge lengths are $\gamma_{ij}$ .

Each facet $F_i$ maps entirely into at least one cubical facet. Choose one such facet $C_{k,s}$ , and label $v_i$ by $\ell_i=s e_k$ . The labels on a proper face $G\subset Q$ contain no opposite pair: the corresponding facets $F_i$ of $X$ have a common point, whose image would otherwise have to lie in two opposite cubical facets.

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 need

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

Here is the topological identification explicitly. For a nonempty proper face $F\subset X$ , let

$\displaystyle C_F=\bigcap_{F_i\supseteq F}C_{\ell_i},$

where $C_{\ell_i}$ denotes the selected cubical facet. Then $\Phi(F)\subseteq C_F$ . Moreover, $F\subseteq F'$ implies $C_F\subseteq C_{F'}$ .

Recall that the barycentric subdivision of a polytope boundary has a vertex $\mathrm{bar}(F)$ for each nonempty proper face $F$ , and a simplex for each chain of such faces. Thus the assignment

$\displaystyle \mathrm{bar}(F)\longmapsto\mathrm{bar}(C_F)$

extends simplicially. It is homotopic to $\Phi|_{\partial X}$ : on every subdivision simplex, the straight homotopy stays inside the cube face associated with its largest face.

Polarity reverses face inclusion and therefore induces simplicial homeomorphisms between the barycentric subdivisions of $\partial X,\partial Q$ , and likewise of $\partial C,\partial C^\circ$ . After these identifications, the preceding map sends

$\displaystyle \mathrm{bar}(G)\longmapsto\mathrm{bar}\mathrm{conv}\{\ell_i:v_i\in G\}.$

This map and $\Lambda$ are homotopic within those same crosspolytope faces, using the face-support property (5). Their degrees consequently agree up to the signs of the two duality homeomorphisms. Since $\deg(\Phi|_{\partial X})\ne0$ , equation (18) follows.

Next construct slowly varying vectors $b_i\in[-1,1]^n$ . Set

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

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)}$

The contraction (finally)

Define

$\displaystyle w_i=r_iT_p(b_i).$

This is the useful polar rescaling: change directions while retaining the original radii $r_i$ .

For an edge $\{i,j\}$ , equations (15) and (20), together with $d_\angle(i,j)\le\gamma_{ij}$ , give

$\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\|.$

Indeed, for unit vectors $u,v$ ,

$\displaystyle \|r_i u-r_j v\|^2=(r_i-r_j)^2+2r_ir_j(1-\langle u,v\rangle).$

The comparison lemma therefore says that

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

never vanishes on $Q$ . Thus

$\displaystyle \deg\left(\frac{W}{\|W\|}\Big|_{\partial Q}\right)=0.\qquad\text{(23)}$

To contradict this, we must relate its boundary degree to (18). 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,

$\displaystyle {\|b_i+t\Lambda(x)\|_\infty\ge1\qquad(v_i\in G).}\qquad\text{(25)}$

For fixed $x,t$ , the translation $t\Lambda(x)$ is common to all the vectors. Hence

$\displaystyle \bigl(b_i+t\Lambda(x)\bigr)-\bigl(b_j+t\Lambda(x)\bigr)=b_i-b_j.$

Equations (20), (25), and the normalization estimate (15) therefore give exactly the same angular contraction as (22), on every edge of $G$ .

Apply the localized comparison lemma to

$\displaystyle z_i=r_iT_p\bigl(b_i+t\Lambda(x)\bigr),\qquad v_i\in G.$

It follows that

$\displaystyle {\|H_t(x)\|\ge\|x\|>0\qquad(x\in\partial Q,\ t\ge0).}\qquad\text{(26)}$

The homotopy is continuous. Active terms have nonzero arguments by (25). When a term becomes inactive, its norm is bounded by $\alpha_i(x)r_i$ , which tends to zero.

At $t=0$ , we have $H_0=W|_{\partial Q}$ . As $t\to\infty$ , positive homogeneity of $T_p$ gives

$\displaystyle H_t(x)\longrightarrow\left(\sum_i\alpha_i(x)r_i\right)T_p(\Lambda(x)).\qquad\text{(27)}$

The convergence is uniform: by (17),

$\displaystyle \|\Lambda(x)\|_\infty\ge1/n,$

so the arguments $\Lambda(x)+b_i/t$ remain uniformly away from zero for large $t$ .

Thus (24) extends to a nonvanishing homotopy with the endpoint in (27). Its scalar factor is positive, and

$\displaystyle T_p:\partial C^\circ\longrightarrow S^{n-1}$

is a homeomorphism: invert the coordinatewise power and then normalize in $\ell_1$ .

It follows from (18) that

$\displaystyle \deg\left(\frac W{\|W\|}\Big|_{\partial Q}\right)=\deg(T_p\circ\Lambda)\ne0,$

contradicting (23). Therefore $D>\pi+2K$ is impossible.

Optimize

We have proved, for every $p\ge1$ ,

$\displaystyle \square_\angle^{\,n}(X)\le\pi+2p\,n^{1/(2p)}.$

Since

$\displaystyle \frac{d}{dp}\log\bigl(p\,n^{1/(2p)}\bigr)=\frac1p-\frac{\log n}{2p^2},$

the minimizing exponent is

$\displaystyle p=\max\left\{1,\frac{\log n}{2}\right\}.$

For $n\ge8$ , this yields

$\displaystyle p\,n^{1/(2p)}=\frac e2\log n,$

and hence (2).

Finally, let $\gamma_{\min}$ be the minimum complementary dihedral angle, and let $d_{\mathrm{comb}}$ be the shortest-path metric on the same facet-adjacency graph with every edge assigned length one. Define $\square_{\mathrm{comb}}^{\,n}(X)$ using the same admissible maps, but measuring their separations with $d_{\mathrm{comb}}$ .